This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[CFG] Unswitching cleanup
- 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: Wed, 1 May 2002 14:20:42 +0200
- Subject: [CFG] Unswitching cleanup
Hello.
This patch cleans up the code concerning loop unswitching a lot, removing most
of the dark magic. It also allows us to really remove the loop when we peel it
completely (till now we were just leaving it in place, hoping that some
following optimization pass will get rid of it).
It also fixes some bugs in recent count_loop_iterations patch.
Bootstrapped on i686.
Zdenek Dvorak
Changelog:
* basic_block.h (cancel_loop, cancel_loop_tree): Declare.
(iterate_fix_dominators): Declaration changed.
* cfgloop.c (flow_loop_free): New static function.
(flow_loops_dump, flow_loops_free, verify_loop_structure): Modified
to be able to handle removed loops.
(flow_loop_tree_node_remove): Modified.
(cancel_loop, cancel_loop_tree): New functions.
* loop-new.c (iterate_fix_dominators): Fixed.
(remove_path): Removed.
(try_remove_path): Reworked and renamed to remove_path.
(find_branch, fix_loop_placement): Modified.
(fix_loop_placements): New.
(unswitch_loops): Handle possibility of removing loops.
(unswitch_single_loop): Use reworked remove_path.
(loopify, unswitch_loops): Reworked.
* loop.h (struct loop_desc): New fields out_edge and in_edge.
(remove_path): Declare.
* unroll-new.c (simple_condition_p): Fix.
(simple_loop_p): Fill in out_edge and in_edge fields.
(peel_loop_completely): Really remove the loop.
Index: basic-block.h
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.127.2.23
diff -c -3 -p -r1.127.2.23 basic-block.h
*** basic-block.h 19 Apr 2002 22:44:39 -0000 1.127.2.23
--- basic-block.h 1 May 2002 12:14:09 -0000
*************** extern edge loop_latch_edge PARAMS ((str
*** 703,715 ****
extern void add_bb_to_loop PARAMS ((basic_block, struct loop *));
extern void remove_bb_from_loops PARAMS ((basic_block));
! struct loop * find_common_loop PARAMS ((struct loop *, struct loop *));
! void verify_loop_structure PARAMS ((struct loops *, int));
#define VLS_EXPECT_PREHEADERS 1
#define VLS_EXPECT_SIMPLE_LATCHES 2
#define VLS_FOR_LOOP_NEW (VLS_EXPECT_PREHEADERS | VLS_EXPECT_SIMPLE_LATCHES)
! int expected_loop_iterations PARAMS ((const struct loop *));
typedef struct conflict_graph_def *conflict_graph;
--- 703,718 ----
extern void add_bb_to_loop PARAMS ((basic_block, struct loop *));
extern void remove_bb_from_loops PARAMS ((basic_block));
! extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *));
! extern void cancel_loop PARAMS ((struct loops *, struct loop *));
! extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *));
!
! extern void verify_loop_structure PARAMS ((struct loops *, int));
#define VLS_EXPECT_PREHEADERS 1
#define VLS_EXPECT_SIMPLE_LATCHES 2
#define VLS_FOR_LOOP_NEW (VLS_EXPECT_PREHEADERS | VLS_EXPECT_SIMPLE_LATCHES)
! extern int expected_loop_iterations PARAMS ((const struct loop *));
typedef struct conflict_graph_def *conflict_graph;
*************** extern int get_dominated_by PARAMS ((sbi
*** 766,772 ****
basic_block recount_dominator PARAMS ((sbitmap *, basic_block));
extern void redirect_immediate_dominators PARAMS ((sbitmap *, basic_block,
basic_block));
! void iterate_fix_dominators PARAMS ((sbitmap *, basic_block *, int, int));
extern void verify_dominators PARAMS ((void));
/* In cfgloopanal.c */
--- 769,775 ----
basic_block recount_dominator PARAMS ((sbitmap *, basic_block));
extern void redirect_immediate_dominators PARAMS ((sbitmap *, basic_block,
basic_block));
! void iterate_fix_dominators PARAMS ((sbitmap *, basic_block *, int));
extern void verify_dominators PARAMS ((void));
/* In cfgloopanal.c */
Index: cfgloop.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.2.2.15
diff -c -3 -p -r1.2.2.15 cfgloop.c
*** cfgloop.c 9 Apr 2002 10:28:59 -0000 1.2.2.15
--- cfgloop.c 1 May 2002 12:14:09 -0000
*************** static basic_block make_forwarder_block
*** 44,49 ****
--- 44,50 ----
static void canonicalize_loop_headers PARAMS ((void));
static bool glb_enum_p PARAMS ((basic_block, void *));
static void redirect_edge_with_latch_update PARAMS ((edge, basic_block));
+ static void flow_loop_free PARAMS ((struct loop *));
/* Dump loop related CFG information. */
*************** flow_loops_dump (loops, file, loop_dump_
*** 171,176 ****
--- 172,180 ----
{
struct loop *loop = loops->parray[i];
+ if (!loop)
+ continue;
+
flow_loop_dump (loop, file, loop_dump_aux, verbose);
}
*************** flow_loops_dump (loops, file, loop_dump_
*** 178,183 ****
--- 182,203 ----
flow_loops_cfg_dump (loops, file);
}
+ /* Free data allocated for LOOP. */
+ static void
+ flow_loop_free (loop)
+ struct loop *loop;
+ {
+ if (loop->pre_header_edges)
+ free (loop->pre_header_edges);
+ if (loop->entry_edges)
+ free (loop->entry_edges);
+ if (loop->exit_edges)
+ free (loop->exit_edges);
+ if (loop->pred)
+ free (loop->pred);
+ free (loop);
+ }
+
/* Free all the memory allocated for LOOPS. */
void
*************** flow_loops_free (loops)
*** 196,210 ****
{
struct loop *loop = loops->parray[i];
! if (loop->pre_header_edges)
! free (loop->pre_header_edges);
! if (loop->entry_edges)
! free (loop->entry_edges);
! if (loop->exit_edges)
! free (loop->exit_edges);
! if (loop->pred)
! free (loop->pred);
! free (loop);
}
free (loops->parray);
--- 216,225 ----
{
struct loop *loop = loops->parray[i];
! if (!loop)
! continue;
!
! flow_loop_free (loop);
}
free (loops->parray);
*************** flow_loop_tree_node_remove (loop)
*** 473,478 ****
--- 488,494 ----
loop->depth = -1;
free (loop->pred);
+ loop->pred = NULL;
}
/* Helper function to compute loop nesting depth and enclosed loop level
*************** remove_bb_from_loops (bb)
*** 1067,1072 ****
--- 1083,1126 ----
bb->loop_depth = 0;
}
+ /* Cancels the LOOP; it must be innermost one. */
+ void
+ cancel_loop (loops, loop)
+ struct loops *loops;
+ struct loop *loop;
+ {
+ basic_block *bbs;
+ int i;
+
+ if (loop->inner)
+ abort ();
+
+ /* Move blocks up one level (they should be removed as soon as possible). */
+ bbs = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
+ bbs[i]->loop_father = loop->outer;
+
+ /* Remove the loop from structure. */
+ flow_loop_tree_node_remove (loop);
+
+ /* Remove loop from loops array. */
+ loops->parray[loop->num] = NULL;
+
+ /* Free loop data. */
+ flow_loop_free (loop);
+ }
+
+ /* Cancels LOOP and all its subloops. */
+ void
+ cancel_loop_tree (loops, loop)
+ struct loops *loops;
+ struct loop *loop;
+ {
+ while (loop->inner)
+ cancel_loop_tree (loops, loop->inner);
+ cancel_loop (loops, loop);
+ }
+
/* Finds nearest common ancestor in loop tree for given loops. */
struct loop *
find_common_loop (loop_s, loop_d)
*************** void verify_loop_structure (loops, flags
*** 1111,1122 ****
sizes[loop->num]++;
for (i = 0; i < loops->num; i++)
! if (loops->parray[i]->num_nodes != sizes[i])
! {
! error ("Size of loop %d should be %d, not %d.",
! i, sizes[i], loops->parray[i]->num_nodes);
! err = 1;
! }
free (sizes);
--- 1165,1181 ----
sizes[loop->num]++;
for (i = 0; i < loops->num; i++)
! {
! if (!loops->parray[i])
! continue;
!
! if (loops->parray[i]->num_nodes != sizes[i])
! {
! error ("Size of loop %d should be %d, not %d.",
! i, sizes[i], loops->parray[i]->num_nodes);
! err = 1;
! }
! }
free (sizes);
*************** void verify_loop_structure (loops, flags
*** 1124,1129 ****
--- 1183,1190 ----
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
+ if (!loop)
+ continue;
bbs = get_loop_body (loop);
for (j = 0; j < loop->num_nodes; j++)
*************** void verify_loop_structure (loops, flags
*** 1140,1145 ****
--- 1201,1209 ----
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
+ if (!loop)
+ continue;
+
if ((flags & VLS_EXPECT_PREHEADERS)
&& (!loop->header->pred->pred_next
|| loop->header->pred->pred_next->pred_next))
Index: loop-new.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/Attic/loop-new.c,v
retrieving revision 1.1.2.16
diff -c -3 -p -r1.1.2.16 loop-new.c
*** loop-new.c 7 Apr 2002 15:58:04 -0000 1.1.2.16
--- loop-new.c 1 May 2002 12:14:09 -0000
*************** recount_dominator (dom, bb)
*** 183,210 ****
return dom_bb;
}
! /* Iteratively recount dominators of BBS. If LOCAL is set, the change is
! supposed to be local and not to grow further. Otherwise BBS is supposed
! to be able to hold all affected blocks (i.e. n_basic_blocks worst case). */
void
! iterate_fix_dominators (doms, bbs, n, local)
sbitmap *doms;
basic_block *bbs;
int n;
- int local;
{
- sbitmap affected;
int i, changed = 1;
basic_block old_dom, new_dom;
- edge e;
- if (!local)
- affected = sbitmap_alloc (n_basic_blocks);
while (changed)
{
changed = 0;
- if (!local)
- sbitmap_zero (affected);
for (i = 0; i < n; i++)
{
old_dom = get_immediate_dominator (doms, bbs[i]);
--- 183,202 ----
return dom_bb;
}
! /* Iteratively recount dominators of BBS. The change is supposed to be local
! and not to grow further. */
void
! iterate_fix_dominators (doms, bbs, n)
sbitmap *doms;
basic_block *bbs;
int n;
{
int i, changed = 1;
basic_block old_dom, new_dom;
while (changed)
{
changed = 0;
for (i = 0; i < n; i++)
{
old_dom = get_immediate_dominator (doms, bbs[i]);
*************** iterate_fix_dominators (doms, bbs, n, lo
*** 213,234 ****
{
changed = 1;
set_immediate_dominator (doms, bbs[i], new_dom);
- if (!local)
- for (e = bbs[i]->pred; e; e = e->pred_next)
- SET_BIT (affected, e->src->index);
}
}
- if (changed && !local)
- {
- n = 0;
- EXECUTE_IF_SET_IN_SBITMAP (affected, 0, i,
- {
- bbs[n++] = BASIC_BLOCK (i);
- });
- }
}
- if (!local)
- sbitmap_free (affected);
}
static struct loop * duplicate_loop PARAMS ((struct loops *, struct loop *, struct loop *));
--- 205,213 ----
*************** static void remove_exit_edges PARAMS ((b
*** 241,253 ****
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 *));
! static int find_branch PARAMS ((edge, sbitmap *, struct loop *, basic_block **));
! static void remove_path PARAMS ((edge, struct loop *, sbitmap *, int));
! static int try_remove_path PARAMS ((struct loops *, struct loop *, edge));
static struct loop *loopify PARAMS ((struct loops *, edge, edge, basic_block));
static bool alp_enum_p PARAMS ((basic_block, void *));
static void add_loop PARAMS ((struct loops *, struct loop *));
! static void fix_loop_placement PARAMS ((struct loop *));
static void place_new_loop PARAMS ((struct loops *, struct loop *));
static void unswitch_single_loop PARAMS ((struct loops *, struct loop *, rtx, int));
static bool may_unswitch_on_p PARAMS ((struct loops *, basic_block, struct loop *, basic_block *));
--- 220,231 ----
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 *));
! static int find_branch PARAMS ((edge, sbitmap *, basic_block **));
static struct loop *loopify PARAMS ((struct loops *, edge, edge, basic_block));
static bool alp_enum_p PARAMS ((basic_block, void *));
static void add_loop PARAMS ((struct loops *, struct loop *));
! static int fix_loop_placement PARAMS ((struct loop *));
! static void fix_loop_placements PARAMS ((struct loop *));
static void place_new_loop PARAMS ((struct loops *, struct loop *));
static void unswitch_single_loop PARAMS ((struct loops *, struct loop *, rtx, int));
static bool may_unswitch_on_p PARAMS ((struct loops *, basic_block, struct loop *, basic_block *));
*************** void
*** 336,347 ****
unswitch_loops (loops)
struct loops *loops;
{
! int i;
! /* Scan the loops, last ones first, since this means inner ones are done
! before outer ones. */
! for (i = loops->num - 1; i > 0; i--)
{
! struct loop *loop = loops->parray[i];
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
verify_dominators ();
--- 314,335 ----
unswitch_loops (loops)
struct loops *loops;
{
! int i, num;
! struct loop *loop;
!
! /* Go through inner loops (only original ones). */
! num = loops->num;
!
! for (i = 1; i < num; i++)
{
! /* Removed loop? */
! loop = loops->parray[i];
! if (!loop)
! continue;
! /* Not innermost? */
! if (loop->inner)
! continue;
!
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
verify_dominators ();
*************** unswitch_single_loop (loops, loop, cond_
*** 550,572 ****
abort ();
if (always_true)
{
! /* Attempt to remove false path if possible. */
for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
! if (try_remove_path (loops, loop, e))
! {
! free (bbs);
! repeat = 1;
! }
}
else if (always_false)
{
! /* Attempt to remove true path if possible. */
for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
! if (try_remove_path (loops, loop, e))
! {
! free (bbs);
! repeat = 1;
! }
}
} while (repeat);
--- 538,556 ----
abort ();
if (always_true)
{
! /* Remove false path. */
for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
! remove_path (loops, e);
! free (bbs);
! repeat = 1;
}
else if (always_false)
{
! /* Remove true path. */
for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
! remove_path (loops, e);
! free (bbs);
! repeat = 1;
}
} while (repeat);
*************** unswitch_single_loop (loops, loop, cond_
*** 600,606 ****
/* Checks whether BB is inside RPE_LOOP and is dominated by RPE_DOM. */
struct rpe_data
{
- struct loop *loop;
basic_block dom;
sbitmap *doms;
};
--- 584,589 ----
*************** rpe_enum_p (bb, data)
*** 611,618 ****
void *data;
{
struct rpe_data *rpe = data;
! return flow_bb_inside_loop_p (rpe->loop, bb)
! && dominated_by_p (rpe->doms, bb, rpe->dom);
}
/* Remove BBS. */
--- 594,600 ----
void *data;
{
struct rpe_data *rpe = data;
! return dominated_by_p (rpe->doms, bb, rpe->dom);
}
/* Remove BBS. */
*************** remove_bbs (bbs, nbbs)
*** 637,648 ****
}
}
! /* Find branch beginning at Edge inside LOOP and put it into BBS. */
static int
! find_branch (e, doms, loop, bbs)
edge e;
sbitmap *doms;
- struct loop *loop;
basic_block **bbs;
{
edge ae = NULL;
--- 619,629 ----
}
}
! /* Find branch beginning at Edge and put it into BBS. */
static int
! find_branch (e, doms, bbs)
edge e;
sbitmap *doms;
basic_block **bbs;
{
edge ae = NULL;
*************** find_branch (e, doms, loop, bbs)
*** 662,792 ****
}
/* Find bbs we are interested in. */
- rpe.loop = loop;
rpe.dom = e->dest;
rpe.doms = doms;
! *bbs = xcalloc (loop->num_nodes, sizeof (basic_block));
return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
! loop->num_nodes, &rpe);
}
! /* Remove given edge E and all bbs inside LOOP that are dominated by target
! of E. Fix dominators by redirecting to copy if FIX is set. */
! static void
! remove_path (e, loop, doms, fix)
edge e;
- struct loop *loop;
- sbitmap *doms;
- int fix;
{
! int nrem, i, j;
! basic_block *rem_bbs, bb, nbb, *dom_bbs, dom_bb, ndom;
! int n_dom_bbs;
!
! nrem = find_branch (e, doms, loop, &rem_bbs);
!
! if (fix)
{
- /* Fix dominators. */
- for (i = 0; i < nrem; i++)
- {
- bb = rem_bbs[i];
- ndom = RBI (bb)->copy;
- n_dom_bbs = get_dominated_by (doms, bb, &dom_bbs);
- for (j = 0; j < n_dom_bbs; j++)
- {
- /* This may also be bbs inside loop; but it does not matter,
- as they will be deleted anyway. */
- dom_bb = dom_bbs[j];
- set_immediate_dominator (doms, dom_bb, ndom);
- }
- free (dom_bbs);
- }
- /* Fix frequencies. */
for (i = 0; i < nrem; i++)
{
bb = rem_bbs[i];
! nbb = RBI (bb)->copy;
! nbb->frequency += bb->frequency;
! nbb->count += bb->count;
}
}
else
! {
! /* Fix frequencies. */
! for (i = 0; i < nrem; i++)
! {
! bb = rem_bbs[i];
! nbb = RBI (bb)->original;
! nbb->frequency += bb->frequency;
! nbb->count += bb->count;
! }
! }
! /* Remove the jump and edge. */
loop_delete_branch_edge (e);
-
- /* Remove the blocks. */
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
- }
! /* Attempts to remove path beginning at E from LOOP. Returns 1 if successful.
! */
! static int
! try_remove_path (loops, loop, e)
! struct loops *loops;
! struct loop *loop;
! edge e;
! {
! edge ae;
! basic_block *rem_bbs, *dom_bbs, from, *border_bbs;
! int i, j, nrem, n_dom_bbs, n_border_bbs;
! /* First identify the branch. */
! nrem = find_branch (e, loops->cfg.dom, loop, &rem_bbs);
! /* Check whether we would not create unreachable blocks. */
! for (i = 0; i < nrem; i++)
! {
! n_dom_bbs = get_dominated_by (loops->cfg.dom, rem_bbs[i], &dom_bbs);
! for (j = 0; j < n_dom_bbs; j++)
! if (!flow_bb_inside_loop_p (loop, dom_bbs[j]))
! {
! free (dom_bbs);
! free (rem_bbs);
! return 0;
! }
! free (dom_bbs);
}
! /* Remember border blocks. */
! border_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
! n_border_bbs = 0;
! for (i = 0; i < nrem; i++)
! for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next)
! if (!flow_bb_inside_loop_p (loop, ae->dest))
! border_bbs[n_border_bbs++] = ae->dest;
! /* OK. Remove the path. */
! from = e->src;
! loop_delete_branch_edge (e);
! remove_bbs (rem_bbs, nrem);
! free (rem_bbs);
!
! /* Recount dominators for from. */
! n_dom_bbs = get_dominated_by (loops->cfg.dom, from, &dom_bbs);
! iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs, 1);
free (dom_bbs);
! /* Recount dominators for border bbs. */
! iterate_fix_dominators (loops->cfg.dom, border_bbs, n_border_bbs, 0);
! free (border_bbs);
!
! /* Fix loop placement. */
! fix_loop_placement (loop);
!
! return 1;
}
/* Predicate for enumeration in add_loop. */
--- 643,735 ----
}
/* Find bbs we are interested in. */
rpe.dom = e->dest;
rpe.doms = doms;
! *bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
! n_basic_blocks, &rpe);
}
! /* Removes path beginning at E. */
! void
! remove_path (loops, e)
! struct loops *loops;
edge e;
{
! edge ae;
! basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
! int i, nrem, n_bord_bbs, n_dom_bbs;
! sbitmap seen;
!
! /* 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;
! dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
! bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
! seen = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (seen);
!
! /* Find border hexes. */
! for (i = 0; i < nrem; i++)
! SET_BIT (seen, rem_bbs[i]->index);
! if (nrem)
{
for (i = 0; i < nrem; i++)
{
bb = rem_bbs[i];
! for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next)
! if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
! {
! SET_BIT (seen, ae->dest->index);
! bord_bbs[n_bord_bbs++] = ae->dest;
! }
}
}
else
! bord_bbs[n_bord_bbs++] = e->dest;
! /* OK. Remove the path. */
! from = e->src;
loop_delete_branch_edge (e);
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
! /* Find blocks with affected dominators. */
! sbitmap_zero (seen);
! for (i = 0; i < n_bord_bbs; i++)
! {
! int j, nldom;
! basic_block *ldom;
! bb = get_immediate_dominator (loops->cfg.dom, bord_bbs[i]);
! if (TEST_BIT (seen, bb->index))
! continue;
! SET_BIT (seen, bb->index);
! nldom = get_dominated_by (loops->cfg.dom, bb, &ldom);
! for (j = 0; j < nldom; j++)
! if (!dominated_by_p (loops->cfg.dom, from, ldom[j]))
! dom_bbs[n_dom_bbs++] = ldom[j];
! free(ldom);
}
! free (bord_bbs);
! free (seen);
! /* Recount dominators. */
! iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
free (dom_bbs);
! /* Fix loop placements. */
! fix_loop_placements (from->loop_father);
}
/* Predicate for enumeration in add_loop. */
*************** scale_loop_frequencies (loop, num, den)
*** 859,868 ****
}
/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
! latch to header. Everything between them plus LATCH_EDGE destrination
! must be dominated by HEADER_EDGE destination. Add SWITCH_BB to original
! entry edge. Returns newly created loop. Dominators outside the area
! are intentionally left wrong. */
static struct loop *
loopify (loops, latch_edge, header_edge, switch_bb)
struct loops *loops;
--- 802,811 ----
}
/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
! latch to header. Everything between them plus LATCH_EDGE destination
! must be dominated by HEADER_EDGE destination, and backreachable from
! LATCH_EDGE source. Add SWITCH_BB to original entry edge. Returns newly
! created loop. */
static struct loop *
loopify (loops, latch_edge, header_edge, switch_bb)
struct loops *loops;
*************** loopify (loops, latch_edge, header_edge,
*** 872,877 ****
--- 815,823 ----
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
+ basic_block *dom_bbs, *body;
+ int n_dom_bbs, i, j;
+ sbitmap seen;
struct loop *loop = xcalloc (1, sizeof (struct loop));
struct loop *outer = succ_bb->loop_father->outer;
int freq, prob, tot_prob;
*************** loopify (loops, latch_edge, header_edge,
*** 915,926 ****
scale_loop_frequencies (loop, prob, tot_prob);
scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
return loop;
}
/* Move LOOP up the hierarchy while it is not backward reachable from the
latch of the outer loop. */
! static void
fix_loop_placement (loop)
struct loop *loop;
{
--- 861,903 ----
scale_loop_frequencies (loop, prob, tot_prob);
scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
+ /* Update dominators of outer blocks. */
+ dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+ n_dom_bbs = 0;
+ seen = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (seen);
+ body = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ SET_BIT (seen, body[i]->index);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ int nldom;
+ basic_block *ldom;
+
+ nldom = get_dominated_by (loops->cfg.dom, body[i], &ldom);
+ for (j = 0; j < nldom; j++)
+ if (!TEST_BIT (seen, ldom[j]->index))
+ {
+ SET_BIT (seen, ldom[j]->index);
+ dom_bbs[n_dom_bbs++] = ldom[j];
+ }
+ free (ldom);
+ }
+
+ iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
+
+ free (body);
+ free (seen);
+ free (dom_bbs);
+
return loop;
}
/* Move LOOP up the hierarchy while it is not backward reachable from the
latch of the outer loop. */
! static int
fix_loop_placement (loop)
struct loop *loop;
{
*************** fix_loop_placement (loop)
*** 946,951 ****
--- 923,946 ----
act->num_nodes -= loop->num_nodes;
flow_loop_tree_node_remove (loop);
flow_loop_tree_node_add (father, loop);
+ return 1;
+ }
+ return 0;
+ }
+
+ /* Fix placement of superloops of LOOP. */
+ static void
+ fix_loop_placements (loop)
+ struct loop *loop;
+ {
+ struct loop *outer;
+
+ while (loop->outer)
+ {
+ outer = loop->outer;
+ if (!fix_loop_placement (loop))
+ break;
+ loop = outer;
}
}
*************** unswitch_loop (loops, loop, unswitch_on)
*** 961,970 ****
basic_block unswitch_on;
{
edge entry, e, latch_edge;
! basic_block switch_bb, unswitch_on_alt, *bbs, *dom_bbs, dom_bb;
struct loop *nloop;
- int n_dom_bbs, i, j;
- int just_one_edge;
sbitmap zero_bitmap;
/* Some sanity checking. */
--- 956,963 ----
basic_block unswitch_on;
{
edge entry, e, latch_edge;
! basic_block switch_bb, unswitch_on_alt;
struct loop *nloop;
sbitmap zero_bitmap;
/* Some sanity checking. */
*************** unswitch_loop (loops, loop, unswitch_on)
*** 995,1001 ****
/* Make a copy. */
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
! if (!duplicate_loop_to_header_edge (loop, entry, loops, 1, zero_bitmap, 0))
return NULL;
free (zero_bitmap);
--- 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);
*************** unswitch_loop (loops, loop, unswitch_on)
*** 1012,1070 ****
latch_edge = latch_edge->succ_next);
nloop = loopify (loops, latch_edge,
RBI (loop->header)->copy->pred, switch_bb);
!
! /* Remove paths from loop copies and update dominators.
! We rely on the fact that cfg_layout_duplicate_bb reverses
! list of edges here. */
for (e = unswitch_on->succ->succ_next->dest->pred; e; e = e->pred_next)
if (e->src != unswitch_on &&
!dominated_by_p (loops->cfg.dom, e->src, e->dest))
break;
! just_one_edge = (e != NULL);
! remove_path (unswitch_on->succ, loop, loops->cfg.dom, 1);
! remove_path (unswitch_on_alt->succ, nloop, loops->cfg.dom, 0);
/* One of created loops do not have to be subloop of the outer loop now. */
fix_loop_placement (loop);
fix_loop_placement (nloop);
- /* Now fix dominators of outside blocks. */
- bbs = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- if (!just_one_edge &&
- dominated_by_p (loops->cfg.dom, bbs[i], unswitch_on->succ->dest))
- continue;
- n_dom_bbs = get_dominated_by (loops->cfg.dom, bbs[i], &dom_bbs);
- for (j = 0; j < n_dom_bbs; j++)
- {
- dom_bb = dom_bbs[j];
- if (flow_bb_inside_loop_p (loop, dom_bb))
- continue;
- set_immediate_dominator (loops->cfg.dom, dom_bb, switch_bb);
- }
- free (dom_bbs);
- }
- free (bbs);
-
- /* Now the hard case. Dominators of blocks inside loop immediatelly
- dominated by unswitch_on may behave really weird. */
- n_dom_bbs = get_dominated_by (loops->cfg.dom, unswitch_on, &dom_bbs);
- j = 0;
- for (i = 0; i < n_dom_bbs; i++)
- if (flow_bb_inside_loop_p (loop, dom_bbs[i]))
- dom_bbs[j++] = dom_bbs [i];
- iterate_fix_dominators (loops->cfg.dom, dom_bbs, j, 1);
- free (dom_bbs);
-
- n_dom_bbs = get_dominated_by (loops->cfg.dom, unswitch_on_alt, &dom_bbs);
- j = 0;
- for (i = 0; i < n_dom_bbs; i++)
- if (flow_bb_inside_loop_p (nloop, dom_bbs[i]))
- dom_bbs[j++] = dom_bbs [i];
- iterate_fix_dominators (loops->cfg.dom, dom_bbs, j, 1);
- free (dom_bbs);
-
return nloop;
}
--- 1005,1024 ----
latch_edge = latch_edge->succ_next);
nloop = loopify (loops, latch_edge,
RBI (loop->header)->copy->pred, switch_bb);
!
! /* Remove paths from loop copies. We rely on the fact that
! cfg_layout_duplicate_bb reverses list of edges here. */
for (e = unswitch_on->succ->succ_next->dest->pred; e; e = e->pred_next)
if (e->src != unswitch_on &&
!dominated_by_p (loops->cfg.dom, e->src, e->dest))
break;
! remove_path (loops, unswitch_on->succ);
! remove_path (loops, unswitch_on_alt->succ);
/* One of created loops do not have to be subloop of the outer loop now. */
fix_loop_placement (loop);
fix_loop_placement (nloop);
return nloop;
}
Index: loop.h
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56.2.10
diff -c -3 -p -r1.56.2.10 loop.h
*** loop.h 23 Apr 2002 16:24:17 -0000 1.56.2.10
--- loop.h 1 May 2002 12:14:09 -0000
*************** struct loop_desc
*** 446,451 ****
--- 446,453 ----
bool const_iter; /* True if both limits are integer constants. */
enum rtx_code cond; /* Exit condition. */
int neg; /* Set to 1 if loop ends when condition is satisfied. */
+ edge out_edge; /* The exit edge. */
+ edge in_edge; /* And the other one. */
};
bool can_duplicate_loop_p PARAMS ((struct loop *loop));
*************** bool can_duplicate_loop_p PARAMS ((struc
*** 454,457 ****
#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));
!
--- 456,459 ----
#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));
Index: unroll-new.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.16
diff -c -3 -p -r1.1.2.16 unroll-new.c
*** unroll-new.c 30 Apr 2002 18:44:20 -0000 1.1.2.16
--- unroll-new.c 1 May 2002 12:14:09 -0000
*************** simple_condition_p (loop, body, conditio
*** 166,171 ****
--- 166,173 ----
case LEU:
case LTU:
break;
+ default:
+ return false;
}
/* Of integers or pointers. */
*************** simple_loop_p (loops, loop, desc)
*** 324,329 ****
--- 326,332 ----
basic_block exit_bb, *body, mod_bb;
int fallthru_out;
rtx condition;
+ edge ei, eo, tmp;
body = get_loop_body (loop);
*************** simple_loop_p (loops, loop, desc)
*** 331,336 ****
--- 334,350 ----
if (!(exit_bb = simple_exit (loops, loop, body, &fallthru_out)))
goto ret_false;
+ ei = exit_bb->succ;
+ eo = exit_bb->succ->succ_next;
+ if ((ei->flags & EDGE_FALLTHRU) && fallthru_out)
+ {
+ tmp = ei;
+ ei = eo;
+ eo = tmp;
+ }
+ desc->out_edge = eo;
+ desc->in_edge = ei;
+
/* Condition must be a simple comparison in that one of operands
is register and the other one is invariant. */
if (!(condition = get_condition (exit_bb->end, NULL)))
*************** count_loop_iterations (desc, niter, rnit
*** 418,427 ****
unsigned HOST_WIDE_INT abs_diff = 0;
enum rtx_code cond = desc->cond;
if (desc->grow)
{
/* Bypass nonsential tests. */
! if (cond == GE || cond == GT || cond == GEU || cond == GTU)
return false;
if (rniter)
{
--- 432,449 ----
unsigned HOST_WIDE_INT abs_diff = 0;
enum rtx_code cond = desc->cond;
+ /* Ensure that we always handle the condition to stay inside loop. */
+ if (desc->neg)
+ {
+ cond = reverse_condition (cond);
+ if (cond == UNKNOWN)
+ return false;
+ }
+
if (desc->grow)
{
/* Bypass nonsential tests. */
! if (cond == EQ || cond == GE || cond == GT || cond == GEU || cond == GTU)
return false;
if (rniter)
{
*************** count_loop_iterations (desc, niter, rnit
*** 437,443 ****
else
{
/* Bypass nonsential tests. */
! if (cond == LE || cond == LT || cond == LEU || cond == LTU)
return false;
if (rniter)
*rniter = expand_simple_binop (GET_MODE (desc->var), MINUS,
--- 459,465 ----
else
{
/* Bypass nonsential tests. */
! if (cond == EQ || cond == LE || cond == LT || cond == LEU || cond == LTU)
return false;
if (rniter)
*rniter = expand_simple_binop (GET_MODE (desc->var), MINUS,
*************** count_loop_iterations (desc, niter, rnit
*** 458,470 ****
<< (GET_MODE_BITSIZE (GET_MODE (desc->var)) - 1)
<< 1) - 1;
- if (desc->neg)
- {
- cond = reverse_condition (cond);
- if (cond == UNKNOWN)
- return false;
- }
-
delta = 0;
if (!desc->postincr)
delta--;
--- 480,485 ----
*************** count_loop_iterations (desc, niter, rnit
*** 481,494 ****
{
/* We would need HOST_BITS_PER_WIDE_INT + 1 bits. */
if (abs_diff == 0 && delta < 0)
! return 0;
/* Similary we would overflow for loops wrapping around in wide
mode. */
if (GET_MODE_BITSIZE (GET_MODE (desc->var))
> HOST_BITS_PER_WIDE_INT
&& ((desc->init_n >= desc->lim_n && desc->grow)
|| (desc->init_n <= desc->lim_n && !desc->grow)))
! return 0;
}
break;
case LT:
--- 496,509 ----
{
/* We would need HOST_BITS_PER_WIDE_INT + 1 bits. */
if (abs_diff == 0 && delta < 0)
! return false;
/* Similary we would overflow for loops wrapping around in wide
mode. */
if (GET_MODE_BITSIZE (GET_MODE (desc->var))
> HOST_BITS_PER_WIDE_INT
&& ((desc->init_n >= desc->lim_n && desc->grow)
|| (desc->init_n <= desc->lim_n && !desc->grow)))
! return false;
}
break;
case LT:
*************** count_loop_iterations (desc, niter, rnit
*** 503,508 ****
--- 518,524 ----
case GE:
if (desc->init_n - !desc->postincr <= desc->lim_n)
abs_diff = 0;
+ delta++;
case GT:
if (desc->init_n - !desc->postincr < desc->lim_n)
abs_diff = -1;
*************** count_loop_iterations (desc, niter, rnit
*** 522,534 ****
if ((unsigned HOST_WIDE_INT)(desc->init_n - !desc->postincr)
<= (unsigned HOST_WIDE_INT)desc->lim_n)
abs_diff = 0;
case GTU:
if ((unsigned HOST_WIDE_INT)(desc->init_n - !desc->postincr)
< (unsigned HOST_WIDE_INT)desc->lim_n)
abs_diff = -1;
break;
- case EQ:
- return false;
default:
abort ();
}
--- 538,549 ----
if ((unsigned HOST_WIDE_INT)(desc->init_n - !desc->postincr)
<= (unsigned HOST_WIDE_INT)desc->lim_n)
abs_diff = 0;
+ delta++;
case GTU:
if ((unsigned HOST_WIDE_INT)(desc->init_n - !desc->postincr)
< (unsigned HOST_WIDE_INT)desc->lim_n)
abs_diff = -1;
break;
default:
abort ();
}
*************** peel_loop_completely (loops, loop, desc)
*** 559,564 ****
--- 574,580 ----
{
sbitmap wont_exit;
unsigned HOST_WIDE_INT npeel;
+ edge e;
if (!count_loop_iterations (desc, &npeel, NULL))
abort (); /* Tested already. */
*************** peel_loop_completely (loops, loop, desc)
*** 573,578 ****
--- 589,602 ----
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;
+ e = e->succ_next);
+
+ remove_path (loops, e);
+
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Peeled loop completely, %d times\n",npeel);