[CFG] Loop optimizer
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Wed Feb 20 06:44:00 GMT 2002
Hello.
This patch contains fixes of some bugs and some functions for manipulating
loop structure. Bootstrapped on i386.
Zdenek Dvorak
Changelog:
* Makefile.in (cfgloopanal.o): Fix dependencies.
(cfgloop.o): Add dependecy on toplev.h
* basic-block.h (verify_loop_structure, recount_dominator,
redirect_immediate_dominators, create_preheaders,
loop_split_edge_with, force_single_succ_latches,
just_once_each_iteration_p, num_loop_insns): Declare.
(create_preheader): Modified declaration.
* cfganal.c (dfs_enumerate_from): Modified.
* cfgloop.c (glb_enum_p): Modified.
(flow_loop_nodes_find, canonicalize_loop_headers): Fix formating.
(get_loop_body): Modified.
(verify_loop_structure): New.
* cfgloopanal.c (cbp_enum_p): New static function.
(create_preheader): Modified.
(create_preheaders): Fix spelling in comment.
(just_once_each_iteration_p, num_loop_insns, loop_split_edge_with,
force_single_succ_latches): New.
* loop-new.c (recount_dominator): Fix, make global.
(iterate_fix_dominators, redirect_immediate_dominators): New.
(nearest_common_dominator): Fix.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.775.2.23
diff -c -3 -p -r1.775.2.23 Makefile.in
*** Makefile.in 2002/02/09 19:24:21 1.775.2.23
--- Makefile.in 2002/02/19 22:17:33
*************** cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM
*** 1503,1510 ****
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(RECOG_H) $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(BASIC_BLOCK_H) \
hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H)
! cfgloopanal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h $(GGC_H) $(DF_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
--- 1503,1510 ----
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(RECOG_H) $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(BASIC_BLOCK_H) \
hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H)
! cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h $(GGC_H) $(DF_H) cfglayout.h
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
*************** cfgcleanup.o : cfgcleanup.c $(CONFIG_H)
*** 1512,1518 ****
$(BASIC_BLOCK_H) hard-reg-set.h output.h flags.h $(RECOG_H) toplev.h \
$(GGC_H) insn-config.h cselib.h $(TARGET_H) $(TM_P_H)
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h
dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
$(BASIC_BLOCK_H)
combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
--- 1512,1518 ----
$(BASIC_BLOCK_H) hard-reg-set.h output.h flags.h $(RECOG_H) toplev.h \
$(GGC_H) insn-config.h cselib.h $(TARGET_H) $(TM_P_H)
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h toplev.h
dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
$(BASIC_BLOCK_H)
combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.127.2.14
diff -c -3 -p -r1.127.2.14 basic-block.h
*** basic-block.h 2002/02/09 18:07:30 1.127.2.14
--- basic-block.h 2002/02/19 22:17:34
*************** extern void free_aux_for_edges PARAMS (
*** 690,705 ****
extern void verify_flow_info PARAMS ((void));
extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
! extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *, basic_block));
! extern basic_block *get_loop_body PARAMS ((const struct loop *));
! extern int dfs_enumerate_from PARAMS ((basic_block, int,
! bool (*)(basic_block), basic_block *,
! int));
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 *));
typedef struct conflict_graph_def *conflict_graph;
/* Callback function when enumerating conflicts. The arguments are
--- 690,710 ----
extern void verify_flow_info PARAMS ((void));
extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
! extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *, basic_block));
! extern basic_block *get_loop_body PARAMS ((const struct loop *));
! extern int dfs_enumerate_from PARAMS ((basic_block, int,
! bool (*)(basic_block, void *),
! basic_block *, int, void *));
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)
+
typedef struct conflict_graph_def *conflict_graph;
/* Callback function when enumerating conflicts. The arguments are
*************** extern void set_immediate_dominator PARA
*** 750,758 ****
extern basic_block get_immediate_dominator PARAMS ((sbitmap *,
basic_block));
extern bool dominated_by_p PARAMS ((sbitmap *, basic_block, basic_block));
-
extern int get_dominated_by PARAMS ((sbitmap *, basic_block, basic_block **));
!
extern void verify_dominators PARAMS ((void));
/* In cfgloopanal.c */
--- 755,765 ----
extern basic_block get_immediate_dominator PARAMS ((sbitmap *,
basic_block));
extern bool dominated_by_p PARAMS ((sbitmap *, basic_block, basic_block));
extern int get_dominated_by PARAMS ((sbitmap *, basic_block, basic_block **));
! 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 */
*************** struct loop_invariants *init_loop_invari
*** 760,766 ****
void free_loop_invariants PARAMS ((struct loop_invariants *inv));
void test_invariants PARAMS ((struct loops *));
bool loop_invariant_rtx_p PARAMS ((struct loop_invariants *, rtx, rtx));
void create_preheaders PARAMS ((struct loops *));
! basic_block create_preheader PARAMS ((struct loop *, sbitmap *));
#endif /* GCC_BASIC_BLOCK_H */
--- 767,777 ----
void free_loop_invariants PARAMS ((struct loop_invariants *inv));
void test_invariants PARAMS ((struct loops *));
bool loop_invariant_rtx_p PARAMS ((struct loop_invariants *, rtx, rtx));
+ basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
+ void force_single_succ_latches PARAMS ((struct loops *));
void create_preheaders PARAMS ((struct loops *));
! basic_block create_preheader PARAMS ((struct loop *, sbitmap *, int));
! bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, basic_block));
! int num_loop_insns PARAMS ((struct loop *));
#endif /* GCC_BASIC_BLOCK_H */
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.6.2.8
diff -c -3 -p -r1.6.2.8 cfganal.c
*** cfganal.c 2002/02/09 19:24:26 1.6.2.8
--- cfganal.c 2002/02/19 22:17:34
*************** flow_dfs_compute_reverse_finish (data)
*** 1243,1254 ****
if REVERSE, go against direction of edges. Returns number of blocks
found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
int
! dfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max)
basic_block bb;
int reverse;
! bool (*predicate) (basic_block);
basic_block *rslt;
int rslt_max;
{
basic_block *st, lbb;
int sp = 0, tv = 0;
--- 1243,1255 ----
if REVERSE, go against direction of edges. Returns number of blocks
found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
int
! dfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max, data)
basic_block bb;
int reverse;
! bool (*predicate) (basic_block, void *);
basic_block *rslt;
int rslt_max;
+ void *data;
{
basic_block *st, lbb;
int sp = 0, tv = 0;
*************** dfs_enumerate_from (bb, reverse, predica
*** 1260,1274 ****
{
edge e;
lbb = st[--sp];
! for (e = reverse ? lbb->pred : lbb->succ; e;
! e = reverse ? e->pred_next : e->succ_next)
! if (!(e->src->flags & BB_VISITED) && predicate (e->src))
! {
! if (tv == rslt_max)
! abort ();
! rslt[tv++] = st[sp++] = e->src;
! e->src->flags |= BB_VISITED;
! }
}
free (st);
for (sp = 0; sp < tv; sp++)
--- 1261,1288 ----
{
edge e;
lbb = st[--sp];
! if (reverse)
! {
! for (e = lbb->pred; e; e = e->pred_next)
! if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
! {
! if (tv == rslt_max)
! abort ();
! rslt[tv++] = st[sp++] = e->src;
! e->src->flags |= BB_VISITED;
! }
! }
! else
! {
! for (e = lbb->succ; e; e = e->succ_next)
! if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
! {
! if (tv == rslt_max)
! abort ();
! rslt[tv++] = st[sp++] = e->dest;
! e->dest->flags |= BB_VISITED;
! }
! }
}
free (st);
for (sp = 0; sp < tv; sp++)
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.2.2.8
diff -c -3 -p -r1.2.2.8 cfgloop.c
*** cfgloop.c 2002/01/26 01:33:42 1.2.2.8
--- cfgloop.c 2002/02/19 22:17:34
*************** Software Foundation, 59 Temple Place - S
*** 23,28 ****
--- 23,29 ----
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+ #include "toplev.h"
/* Ratio of frequencies of edges so that one of more latch edges is
considered to belong to inner loop with same header. */
*************** static int flow_loops_level_compute PARA
*** 42,48 ****
static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
edge, int));
static void canonicalize_loop_headers PARAMS ((void));
! static bool glb_enum_p PARAMS ((basic_block));
static void redirect_edge_with_latch_update PARAMS ((edge, basic_block));
--- 43,49 ----
static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
edge, int));
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));
*************** flow_loop_nodes_find (header, loop)
*** 345,357 ****
basic_block ancestor = e->src;
if (ancestor != ENTRY_BLOCK_PTR
! && ancestor->loop_father != loop)
! {
! ancestor->loop_father = loop;
! ancestor->loop_depth = loop->depth;
! num_nodes++;
! stack[sp++] = ancestor;
! }
}
}
free (stack);
--- 346,358 ----
basic_block ancestor = e->src;
if (ancestor != ENTRY_BLOCK_PTR
! && ancestor->loop_father != loop)
! {
! ancestor->loop_father = loop;
! ancestor->loop_depth = loop->depth;
! num_nodes++;
! stack[sp++] = ancestor;
! }
}
}
free (stack);
*************** canonicalize_loop_headers ()
*** 648,654 ****
edge fallthru, next_e;
basic_block bb;
/* We could not redirect edges freely here. On the other hand,
! we know that no abnormal edge enters this block, so we can simply
split it into two... */
bb = ENTRY_BLOCK_PTR->succ->dest;
insn = PREV_INSN (first_insn_after_basic_block_note (bb));
--- 649,655 ----
edge fallthru, next_e;
basic_block bb;
/* We could not redirect edges freely here. On the other hand,
! we know that no abnormal edge enters this block, so we can simply
split it into two... */
bb = ENTRY_BLOCK_PTR->succ->dest;
insn = PREV_INSN (first_insn_after_basic_block_note (bb));
*************** canonicalize_loop_headers ()
*** 656,662 ****
/* And redirect all edges to second part. */
for (e = fallthru->src->pred; e; e = next_e)
! {
next_e = e->pred_next;
if (e->src == ENTRY_BLOCK_PTR)
continue;
--- 657,663 ----
/* And redirect all edges to second part. */
for (e = fallthru->src->pred; e; e = next_e)
! {
next_e = e->pred_next;
if (e->src == ENTRY_BLOCK_PTR)
continue;
*************** canonicalize_loop_headers ()
*** 679,685 ****
header = BASIC_BLOCK (b);
if (!HEADER_BLOCK (header))
! {
b++;
continue;
}
--- 680,686 ----
header = BASIC_BLOCK (b);
if (!HEADER_BLOCK (header))
! {
b++;
continue;
}
*************** canonicalize_loop_headers ()
*** 689,695 ****
want_join_latch = (num_latch > 1);
if (!want_join_latch)
! {
b++;
continue;
}
--- 690,696 ----
want_join_latch = (num_latch > 1);
if (!want_join_latch)
! {
b++;
continue;
}
*************** canonicalize_loop_headers ()
*** 708,715 ****
{
if (heavy)
{
! is_heavy = 0;
! break;
}
else
heavy = e;
--- 709,716 ----
{
if (heavy)
{
! is_heavy = 0;
! break;
}
else
heavy = e;
*************** flow_loops_find (loops, flags)
*** 802,811 ****
if (e->flags & EDGE_ABNORMAL)
{
if (more_latches)
! {
RESET_BIT (headers, b);
num_loops--;
! }
break;
}
--- 803,812 ----
if (e->flags & EDGE_ABNORMAL)
{
if (more_latches)
! {
RESET_BIT (headers, b);
num_loops--;
! }
break;
}
*************** flow_loops_find (loops, flags)
*** 818,824 ****
{
/* Shared headers should be eliminated by now. */
if (more_latches)
! abort ();
more_latches = 1;
SET_BIT (headers, b);
num_loops++;
--- 819,825 ----
{
/* Shared headers should be eliminated by now. */
if (more_latches)
! abort ();
more_latches = 1;
SET_BIT (headers, b);
num_loops++;
*************** flow_loop_outside_edge_p (loop, e)
*** 965,976 ****
}
/* Enumeration predicate for get_loop_body. */
- static basic_block glb_header;
static bool
! glb_enum_p (bb)
basic_block bb;
{
! return bb != glb_header;
}
/* Gets basic blocks of a loop. */
--- 966,977 ----
}
/* Enumeration predicate for get_loop_body. */
static bool
! glb_enum_p (bb, glb_header)
basic_block bb;
+ void *glb_header;
{
! return bb != (basic_block) glb_header;
}
/* Gets basic blocks of a loop. */
*************** get_loop_body (loop)
*** 995,1003 ****
}
else if (loop->latch != loop->header)
{
- glb_header = loop->header;
tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
! tovisit + 1, loop->num_nodes - 1) + 1;
}
if (tv != loop->num_nodes)
abort ();
--- 996,1004 ----
}
else if (loop->latch != loop->header)
{
tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
! tovisit + 1, loop->num_nodes - 1,
! loop->header) + 1;
}
if (tv != loop->num_nodes)
abort ();
*************** find_common_loop (loop_s, loop_d)
*** 1052,1054 ****
--- 1053,1152 ----
return loop_s;
}
+ /* Checks that LOOPS are allright:
+ -- sizes of loops are allright
+ -- results of get_loop_body really belong to the loop
+ -- loop header have just single entry edge and single latch edge
+ -- loop latches have only single successor that is header of their loop
+ -- sanity of frequencies */
+ void verify_loop_structure (loops, flags)
+ struct loops *loops;
+ int flags;
+ {
+ int *sizes, i, j;
+ basic_block *bbs;
+ struct loop *loop;
+ int err = 0;
+
+ /* Check sizes. */
+ sizes = xcalloc (loops->num, sizeof (int));
+ sizes[0] = 2;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ for (loop = BASIC_BLOCK (i)->loop_father; loop; loop = loop->outer)
+ 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);
+
+ /* Check get_loop_body. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ bbs = get_loop_body (loop);
+
+ for (j = 0; j < loop->num_nodes; j++)
+ if (!flow_bb_inside_loop_p (loop, bbs[j]))
+ {
+ error ("Bb %d do not belong to loop %d.",
+ bbs[j]->index, i);
+ err = 1;
+ }
+ free (bbs);
+ }
+
+ /* Check headers and latches. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if ((flags & VLS_EXPECT_PREHEADERS)
+ && (!loop->header->pred->pred_next
+ || loop->header->pred->pred_next->pred_next))
+ {
+ error ("Loop %d's header does not have exactly 2 entries.", i);
+ err = 1;
+ }
+ if (flags & VLS_EXPECT_SIMPLE_LATCHES)
+ {
+ if (!loop->latch->succ
+ || loop->latch->succ->succ_next)
+ {
+ error ("Loop %d's latch does not have exactly 1 successor.", i);
+ err = 1;
+ }
+ if (loop->latch->succ->dest != loop->header)
+ {
+ error ("Loop %d's latch does not have header as successor.", i);
+ err = 1;
+ }
+ if (loop->latch->loop_father != loop)
+ {
+ error ("Loop %d's latch does not belong directly to it.", i);
+ err = 1;
+ }
+ }
+ if (loop->header->loop_father != loop)
+ {
+ error ("Loop %d's header does not belong directly to it.", i);
+ err = 1;
+ }
+ }
+
+ /* Check frequencies. */
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK(i)->frequency < 0)
+ {
+ error ("Basic block %d has negative frequency.", i);
+ err = 1;
+ }
+
+ if (err)
+ abort ();
+ }
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/cfgloopanal.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 cfgloopanal.c
*** cfgloopanal.c 2002/02/09 18:07:30 1.1.2.3
--- cfgloopanal.c 2002/02/19 22:17:34
***************
*** 6,11 ****
--- 6,12 ----
#include "df.h"
#include "output.h"
#include "function.h"
+ #include "cfglayout.h"
typedef int (*loop_function) PARAMS ((rtx insn, void *data));
static int for_each_insn_in_loop PARAMS ((struct loop *, loop_function, void *));
*************** static void note_mem_store PARAMS ((rtx
*** 15,20 ****
--- 16,22 ----
static int discover_invariant PARAMS ((rtx insn, void *data));
static int not_invariant_rtx PARAMS ((rtx *rtxp, void *data));
static bool mark_maybe_invariant_set PARAMS ((rtx, rtx, rtx, struct loop_invariants *));
+ static bool cbp_enum_p PARAMS ((basic_block, void *));
static int
for_each_insn_in_loop (loop, fun, data)
*************** test_invariants (loops)
*** 413,423 ****
}
}
! /* Creates a pre-header for a LOOP. Returns newly created block. */
basic_block
! create_preheader (loop, dom)
struct loop *loop;
sbitmap *dom;
{
edge e, fallthru;
basic_block dummy;
--- 415,428 ----
}
}
! /* Creates a pre-header for a LOOP. Returns newly created block. Unless
! SIMPLE_PREHEADER is set, we only force LOOP to have single entry; otherwise
! we also force preheader block to have only one successor. */
basic_block
! create_preheader (loop, dom, simple_preheader)
struct loop *loop;
sbitmap *dom;
+ int simple_preheader;
{
edge e, fallthru;
basic_block dummy;
*************** create_preheader (loop, dom)
*** 426,442 ****
int nentry = 0;
rtx insn;
for (e = loop->header->pred; e; e = e->pred_next)
{
if (e->src == loop->latch)
continue;
- cloop = find_common_loop (cloop, e->src->loop_father);
nentry++;
}
if (!nentry)
abort ();
if (nentry == 1)
! return NULL;
insn = PREV_INSN (first_insn_after_basic_block_note (loop->header));
fallthru = split_block (loop->header, insn);
--- 431,453 ----
int nentry = 0;
rtx insn;
+ cloop = loop->outer;
+
for (e = loop->header->pred; e; e = e->pred_next)
{
if (e->src == loop->latch)
continue;
nentry++;
}
if (!nentry)
abort ();
if (nentry == 1)
! {
! for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next);
! if (!simple_preheader
! || !e->src->succ->succ_next)
! return NULL;
! }
insn = PREV_INSN (first_insn_after_basic_block_note (loop->header));
fallthru = split_block (loop->header, insn);
*************** create_preheader (loop, dom)
*** 464,469 ****
--- 475,481 ----
}
/* Update structures. */
+ redirect_immediate_dominators (dom, dummy, loop->header);
set_immediate_dominator (dom, loop->header, dummy);
loop->header->loop_father = loop;
add_bb_to_loop (dummy, cloop);
*************** create_preheader (loop, dom)
*** 474,485 ****
return dummy;
}
! /* Create preheader each loop. */
void
create_preheaders (loops)
struct loops *loops;
{
int i;
for (i = 1; i < loops->num; i++)
! create_preheader (loops->parray[i], loops->cfg.dom);
}
--- 486,652 ----
return dummy;
}
! /* Create preheaders for each loop. */
void
create_preheaders (loops)
struct loops *loops;
{
int i;
for (i = 1; i < loops->num; i++)
! create_preheader (loops->parray[i], loops->cfg.dom, 0);
! }
!
! /* Enumeration predicate for just_once_each_iteration_p. */
! static bool
! cbp_enum_p (bb, data)
! basic_block bb;
! void *data;
! {
! struct loop *loop = data;
! return bb != loop->header
! && flow_bb_inside_loop_p (loop, bb);
! }
!
! /* Checks whether BB is executed exactly once in each LOOP iteration. */
! bool
! just_once_each_iteration_p (loops, loop, bb)
! struct loops *loops;
! struct loop *loop;
! basic_block bb;
! {
! basic_block *bbs;
! int i, n;
! edge e;
!
! /* It must be executed at least once each iteration. */
! if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
! return false;
!
! /* And just once. */
! if (bb->loop_father != loop)
! return false;
!
! /* But this was not enough. We might have some irreducible loop here. */
! if (bb == loop->header)
! return true;
!
! bbs = xcalloc (loop->num_nodes, sizeof (basic_block));
! n = dfs_enumerate_from (bb, 0, cbp_enum_p, bbs, loop->num_nodes,
! (void *) loop);
! for (i = 0; i < n; i++)
! for (e = bbs[i]->succ; e; e = e->succ_next)
! if (e->dest == bb)
! {
! free (bbs);
! return false;
! }
!
! free (bbs);
! return true;
! }
!
! /* Counts number of insns inside LOOP. */
! int
! num_loop_insns (loop)
! struct loop *loop;
! {
! basic_block *bbs, bb;
! int i, ninsns = 0;
! rtx insn;
!
! bbs = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! {
! bb = bbs[i];
! ninsns++;
! for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
! ninsns++;
! }
! free(bbs);
!
! return ninsns;
}
+
+ /* Functions below are expected to be called between
+ cfg_layout_initialize and cfg_layout_finalize. */
+
+ /* A quite stupid function to put INSNS on E. They are supposed to form
+ just one basic block. Jumps out are not handled, so cfg do not have to
+ be ok after this function. */
+ basic_block
+ loop_split_edge_with (e, insns, loops)
+ edge e;
+ rtx insns;
+ struct loops *loops;
+ {
+ basic_block src, dest, new_bb;
+ struct loop *loop_c;
+ edge new_e;
+
+ src = e->src;
+ dest = e->dest;
+
+ loop_c = find_common_loop (src->loop_father, dest->loop_father);
+
+ /* Create basic block for it. */
+
+ 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;
+ new_e->count = e->count;
+
+ new_bb->count = e->count;
+
+ /* Avoid redirect_edge_and_branch from overactive optimizing. */
+ new_bb->index = n_basic_blocks + 1;
+ new_bb->frequency = EDGE_FREQUENCY (e);
+
+ if (e->flags & EDGE_FALLTHRU)
+ redirect_edge_succ (e, new_bb);
+ else
+ redirect_edge_and_branch (e, new_bb);
+ new_bb->index = n_basic_blocks - 1;
+
+ alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
+ if (insns)
+ {
+ start_sequence ();
+ emit_insn (insns);
+ insns = get_insns ();
+ end_sequence ();
+ emit_insns_after (insns, new_bb->end);
+ }
+
+ set_immediate_dominator (loops->cfg.dom, new_bb, src);
+ set_immediate_dominator (loops->cfg.dom, dest,
+ recount_dominator (loops->cfg.dom, dest));
+
+ if (dest->loop_father->latch == src)
+ dest->loop_father->latch = new_bb;
+
+ return new_bb;
+ }
+
+ /* Forces all loop latches to have only single successor. */
+ void
+ force_single_succ_latches (loops)
+ struct loops *loops;
+ {
+ int i;
+ struct loop *loop;
+ edge e;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop->latch->succ->succ_next)
+ continue;
+
+ for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next);
+ loop_split_edge_with (e, NULL_RTX, loops);
+ }
+ }
+
Index: loop-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-new.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 loop-new.c
*** loop-new.c 2002/02/09 17:21:30 1.1.2.3
--- loop-new.c 2002/02/19 22:17:34
*************** Software Foundation, 59 Temple Place - S
*** 41,48 ****
#include "cfglayout.h"
#include "loop.h"
- static basic_block recount_dominator PARAMS ((sbitmap *, basic_block));
-
/* Stupid definitions of dominator manipulation. */
basic_block
--- 41,46 ----
*************** get_dominated_by (dom, bb, bbs)
*** 81,86 ****
--- 79,97 ----
return n;
}
+ void
+ redirect_immediate_dominators (dom, bb, to)
+ sbitmap *dom __attribute__ ((__unused__));
+ basic_block bb;
+ basic_block to;
+ {
+ int i;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK (i)->dominator == bb)
+ BASIC_BLOCK (i)->dominator = to;
+ }
+
basic_block
nearest_common_dominator (bmp, bb1, bb2)
sbitmap *bmp __attribute__ ((__unused__));
*************** nearest_common_dominator (bmp, bb1, bb2)
*** 90,102 ****
int l1, l2, l;
basic_block ab;
! if (!bb1) return bb2;
! if (!bb2) return bb1;
! for (l1 = 0, ab = bb1; ab; ab = ab->dominator)
l1++;
! for (l2 = 0, ab = bb2; ab; ab = ab->dominator)
l2++;
if (l1 > l2)
{
ab = bb1; bb1 = bb2; bb2= ab;
--- 101,120 ----
int l1, l2, l;
basic_block ab;
! if (!bb1)
! return bb2;
! if (!bb2)
! return bb1;
! for (l1 = 0, ab = bb1; ab && ab != ab->dominator; ab = ab->dominator)
l1++;
! if (ab)
! return bb2;
! for (l2 = 0, ab = bb2; ab && ab != ab->dominator; ab = ab->dominator)
l2++;
+ if (ab)
+ return bb1;
+
if (l1 > l2)
{
ab = bb1; bb1 = bb2; bb2= ab;
*************** verify_dominators (void)
*** 136,172 ****
bb = BASIC_BLOCK (i);
dom_bb = recount_dominator (NULL, bb);
if (dom_bb != bb->dominator)
! {
error ("dominator of %d should be %d, not %d",
bb->index, dom_bb->index, bb->dominator->index);
! err = 1;
! }
}
if (err)
abort ();
}
/* Recount dominator of BB. */
! static basic_block
recount_dominator (dom, bb)
sbitmap *dom;
basic_block bb;
{
! basic_block dom_bb = bb;
edge e;
for (e = bb->pred; e; e = e->pred_next)
dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
return dom_bb;
}
/* Initialize loop optimizer. */
struct loops *
loop_optimizer_init (dumpfile)
FILE *dumpfile;
{
- int i;
struct loops *loops = xcalloc (1, sizeof (struct loops));
/* Find the loops. */
--- 154,241 ----
bb = BASIC_BLOCK (i);
dom_bb = recount_dominator (NULL, bb);
if (dom_bb != bb->dominator)
! {
error ("dominator of %d should be %d, not %d",
bb->index, dom_bb->index, bb->dominator->index);
! err = 1;
! }
}
if (err)
abort ();
}
/* Recount dominator of BB. */
! basic_block
recount_dominator (dom, bb)
sbitmap *dom;
basic_block bb;
{
! basic_block dom_bb = NULL, old_dom_bb;
edge e;
+ old_dom_bb = get_immediate_dominator (dom, bb);
+ set_immediate_dominator (dom, bb, bb);
for (e = bb->pred; e; e = e->pred_next)
dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
+ set_immediate_dominator (dom, bb, old_dom_bb);
+
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]);
+ new_dom = recount_dominator (doms, bbs[i]);
+ if (old_dom != new_dom)
+ {
+ 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);
+ }
+
/* Initialize loop optimizer. */
struct loops *
loop_optimizer_init (dumpfile)
FILE *dumpfile;
{
struct loops *loops = xcalloc (1, sizeof (struct loops));
/* Find the loops. */
*************** loop_optimizer_init (dumpfile)
*** 181,195 ****
/* Create pre-headers. */
create_preheaders (loops);
- #ifdef ENABLE_CHECKING
- verify_dominators ();
- #endif
/* Dump loops. */
flow_loops_dump (loops, dumpfile, NULL, 1);
/* Initialize structures for layout changes. */
cfg_layout_initialize (loops);
return loops;
}
--- 250,269 ----
/* Create pre-headers. */
create_preheaders (loops);
/* Dump loops. */
flow_loops_dump (loops, dumpfile, NULL, 1);
/* Initialize structures for layout changes. */
cfg_layout_initialize (loops);
+
+ /* Force all latches to have only single successor. */
+ force_single_succ_latches (loops);
+
+ #ifdef ENABLE_CHECKING
+ verify_dominators ();
+ verify_loop_structure (loops, VLS_FOR_LOOP_NEW);
+ #endif
return loops;
}
More information about the Gcc-patches
mailing list