[tcb]: Port cleanup_tree_cfg_loop patch to TCB
Daniel Berlin
dberlin@dberlin.org
Tue Nov 23 23:07:00 GMT 2004
Since diego removed the redundant phi optimization pass that was run by
loop_init on tcb, we end up with some redundant phis, and uses of those
phis, which was causing some problems for various high level loop
optimizations. The correct way to fix this is to run copy prop and ccp
to get rid of the redundant phis.
These passes want to run cleanup_cfg, but cleanup_cfg isn't loop safe.
So in order to run those passes during the loop optimizations, i ported
the cleanup_tree_cfg_loop patch that Zdenek wrote to TCB.
I've removed the optimization to rewrite_into_loop_closed_ssa that was in
the original patch, because it wasn't strictly necessary for this change,
and it can always be added later on.
With this patch, TODO_cleanup_cfg has been changed to run
cleanup_tree_cfg_loop when current_loops is non-NULL, so that we don't
need another todo flag (the alternate way of doing this is to have the
execute function for each pass return a set of todo-flags)
I've added a copy-prop and ccp pass right after loop_init, and all is
working well.
Bootstrapped and regtested on i686-pc-linux-gnu
DIego, okay for TCB?
2004-11-22 Daniel Berlin <dberlin@dberlin.org>
Patch by Zdenek Dvorak (dvorakz@suse.cz)
* Makefile.in (tree-optimize.o): Add $(CFGLOOP_H).
* cfgloop.c (flow_loop_nodes_find): Make non-static.
* cfgloop.h (fix_loop_structure): New prototype.
* cfgloopmanip.c (fix_loop_structure): New function.
* tree-cfg.c (cleanup_tree_cfg_loop): New function.
(tree_can_merge_blocks_p): Protect loop latches when current_loops
is non-NULL.
(remove_bb): Handle updating of loop structure when current_loops
is non-NULL.
(tree_forwarder_block_p): Protect loop latches, headers, and
preheaders when current_loops is non-NULL.
* tree-flow.h (cleanup_tree_cfg_loop): New prototype.
* tree-loop-linear (linear_transform_loops): The loop array may
have nulls in it.
* tree-optimize.c (init_tree_optimization_passes): Add CCP and
copy-prop after loop-init.
(execute_todo): Run cleanup_tree_cfg_loop when current_loops is
non-NULL.
* tree-ssa-copy.c (fini_copy_prop): Remove call to cleanup_tree_cfg.
(pass_copy_prop): Add TODO_cleanup_cfg.
* tree-ssa-loop-ivcanon.c (cnaonicalize_induction_variables):
Remove call to cleanup_tree_cfg_loop.
(tree_unroll_loops_completely): Ditto.
* tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Ditto.
* tree-ssa-loop.c (pass_unswitch): Add TODO_cleanup_cfg.
(pass_iv_canon): Ditto.
(pass_complete_unroll): Ditto.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1396.2.7
diff -u -p -r1.1396.2.7 Makefile.in
--- Makefile.in 18 Nov 2004 03:12:08 -0000 1.1396.2.7
+++ Makefile.in 23 Nov 2004 22:20:25 -0000
@@ -1736,7 +1737,7 @@ tree-optimize.o : tree-optimize.c $(TREE
$(GGC_H) output.h diagnostic.h errors.h $(FLAGS_H) \
$(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) toplev.h function.h \
langhooks.h $(FLAGS_H) $(CGRAPH_H) tree-inline.h tree-mudflap.h $(GGC_H) \
- $(CGRAPH_H) tree-pass.h
+ $(CGRAPH_H) tree-pass.h $(CFGLOOP_H)
c-gimplify.o : c-gimplify.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
$(C_TREE_H) $(C_COMMON_H) diagnostic.h $(TREE_GIMPLE_H) varray.h $(FLAGS_H) \
langhooks.h toplev.h rtl.h $(TREE_FLOW_H) langhooks-def.h \
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.39.4.3
diff -u -p -r1.39.4.3 cfgloop.c
--- cfgloop.c 18 Nov 2004 03:12:23 -0000 1.39.4.3
+++ cfgloop.c 23 Nov 2004 22:20:25 -0000
@@ -41,7 +41,6 @@ Software Foundation, 59 Temple Place - S
static void flow_loops_cfg_dump (const struct loops *, FILE *);
static void flow_loop_entry_edges_find (struct loop *);
static void flow_loop_exit_edges_find (struct loop *);
-static int flow_loop_nodes_find (basic_block, struct loop *);
static void flow_loop_pre_header_scan (struct loop *);
static basic_block flow_loop_pre_header_find (basic_block);
static int flow_loop_level_compute (struct loop *);
@@ -329,7 +328,7 @@ flow_loop_exit_edges_find (struct loop *
/* Find the nodes contained within the LOOP with header HEADER.
Return the number of nodes within the loop. */
-static int
+int
flow_loop_nodes_find (basic_block header, struct loop *loop)
{
basic_block *stack;
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.31.2.4
diff -u -p -r1.31.2.4 cfgloop.h
--- cfgloop.h 18 Nov 2004 03:12:23 -0000 1.31.2.4
+++ cfgloop.h 23 Nov 2004 22:20:25 -0000
@@ -272,6 +272,8 @@ extern void flow_loop_dump (const struct
void (*)(const struct loop *, FILE *, int), int);
extern int flow_loop_scan (struct loop *, int);
extern void flow_loop_free (struct loop *);
+int flow_loop_nodes_find (basic_block, struct loop *);
+void fix_loop_structure (struct loops *, bitmap changed_bbs);
void mark_irreducible_loops (struct loops *);
void mark_single_exit_loops (struct loops *);
extern void create_loop_notes (void);
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.31.2.4
diff -u -p -r1.31.2.4 cfgloopmanip.c
--- cfgloopmanip.c 18 Nov 2004 03:12:24 -0000 1.31.2.4
+++ cfgloopmanip.c 23 Nov 2004 22:20:25 -0000
@@ -1357,3 +1357,102 @@ create_loop_notes (void)
}
flow_loops_free (&loops);
}
+
+/* The structure of LOOPS might have changed. Some loops might get removed
+ (and their headers and latches were set to NULL), loop exists might get
+ removed (thus the loop nesting may be wrong), and some blocks and edges
+ were changed (so the information about bb --> loop mapping does not have
+ to be correct). But still for the remaining loops the header dominates
+ the latch, and loops did not get new subloobs (new loops might possibly
+ get created, but we are not interested in them). Fix up the mess.
+
+ If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
+ marked in it. */
+
+void
+fix_loop_structure (struct loops *loops, bitmap changed_bbs)
+{
+ basic_block bb;
+ struct loop *loop, *ploop;
+ unsigned i;
+
+ /* Remove the old bb -> loop mapping. */
+ FOR_EACH_BB (bb)
+ {
+ bb->aux = (void *) (size_t) bb->loop_father->depth;
+ bb->loop_father = loops->tree_root;
+ }
+
+ /* Remove the dead loops from structures. */
+ loops->tree_root->num_nodes = n_basic_blocks + 2;
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ loop->num_nodes = 0;
+ if (loop->header)
+ continue;
+
+ while (loop->inner)
+ {
+ ploop = loop->inner;
+ flow_loop_tree_node_remove (ploop);
+ flow_loop_tree_node_add (loop->outer, ploop);
+ }
+
+ /* Remove the loop and free its data. */
+ flow_loop_tree_node_remove (loop);
+ loops->parray[loop->num] = NULL;
+ flow_loop_free (loop);
+ }
+
+ /* Rescan the bodies of loops, starting from the outermost. */
+ loop = loops->tree_root;
+ while (1)
+ {
+ if (loop->inner)
+ loop = loop->inner;
+ else
+ {
+ while (!loop->next
+ && loop != loops->tree_root)
+ loop = loop->outer;
+ if (loop == loops->tree_root)
+ break;
+
+ loop = loop->next;
+ }
+
+ loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
+ }
+
+ /* Now fix the loop nesting. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ bb = loop_preheader_edge (loop)->src;
+ if (bb->loop_father != loop->outer)
+ {
+ flow_loop_tree_node_remove (loop);
+ flow_loop_tree_node_add (bb->loop_father, loop);
+ }
+ }
+
+ /* Mark the blocks whose loop has changed. */
+ FOR_EACH_BB (bb)
+ {
+ if (changed_bbs
+ && (void *) (size_t) bb->loop_father->depth != bb->aux)
+ bitmap_set_bit (changed_bbs, bb->index);
+
+ bb->aux = NULL;
+ }
+
+ mark_single_exit_loops (loops);
+ mark_irreducible_loops (loops);
+}
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.55.2.8
diff -u -p -r2.55.2.8 tree-cfg.c
--- tree-cfg.c 18 Nov 2004 03:12:52 -0000 2.55.2.8
+++ tree-cfg.c 23 Nov 2004 22:20:26 -0000
@@ -893,6 +893,29 @@ cleanup_tree_cfg (void)
return retval;
}
+/* Cleanup cfg and repair loop structures. */
+
+void
+cleanup_tree_cfg_loop (void)
+{
+ bitmap changed_bbs = BITMAP_XMALLOC ();
+
+ cleanup_tree_cfg ();
+
+ fix_loop_structure (current_loops, changed_bbs);
+
+ /* This usually does nothing. But sometimes parts of cfg that originally
+ were inside a loop get out of it due to edge removal (since they
+ become unreachable by back edges from latch). */
+ rewrite_into_loop_closed_ssa ();
+
+ BITMAP_XFREE (changed_bbs);
+
+#ifdef ENABLE_CHECKING
+ verify_loop_structure (current_loops);
+#endif
+}
+
/* Cleanup useless labels in basic blocks. This is something we wish
to do early because it allows us to group case labels before creating
@@ -1211,6 +1234,11 @@ tree_can_merge_blocks_p (basic_block a,
return false;
}
+ /* Protect the loop latches. */
+ if (current_loops
+ && b->loop_father->latch == b)
+ return false;
+
return true;
}
@@ -1957,6 +1985,20 @@ remove_bb (basic_block bb)
}
}
+ /* If we remove the header or the latch of a loop, mark the loop for
+ removal by setting its header and latch to NULL. */
+ if (current_loops)
+ {
+ struct loop *loop = bb->loop_father;
+
+ if (loop->latch == bb
+ || loop->header == bb)
+ {
+ loop->latch = NULL;
+ loop->header = NULL;
+ }
+ }
+
/* Remove all the instructions in the block. */
for (i = bsi_start (bb); !bsi_end_p (i);)
{
@@ -3887,7 +3929,17 @@ tree_forwarder_block_p (basic_block bb)
return false;
}
}
-
+ if (current_loops)
+ {
+ basic_block dest;
+ /* Protect loop latches, headers and preheaders. */
+ if (bb->loop_father->header == bb)
+ return false;
+ dest = EDGE_SUCC (bb, 0)->dest;
+
+ if (dest->loop_father->header == dest)
+ return false;
+ }
return true;
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.46.2.9
diff -u -p -r2.46.2.9 tree-flow.h
--- tree-flow.h 18 Nov 2004 03:12:53 -0000 2.46.2.9
+++ tree-flow.h 23 Nov 2004 22:20:27 -0000
@@ -468,6 +468,7 @@ extern void print_loop_ir (FILE *);
extern void cleanup_dead_labels (void);
extern void group_case_labels (void);
extern bool cleanup_tree_cfg (void);
+extern void cleanup_tree_cfg_loop (void);
extern tree first_stmt (basic_block);
extern tree last_stmt (basic_block);
extern tree *last_stmt_ptr (basic_block);
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.2.2.1
diff -u -p -r2.2.2.1 tree-loop-linear.c
--- tree-loop-linear.c 5 Nov 2004 17:20:24 -0000 2.2.2.1
+++ tree-loop-linear.c 23 Nov 2004 22:20:27 -0000
@@ -264,7 +265,7 @@ linear_transform_loops (struct loops *lo
...
}
} */
- if (!loop_nest->inner)
+ if (!loop_nest || !loop_nest->inner)
continue;
depth = 1;
for (temp = loop_nest->inner; temp; temp = temp->inner)
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.47.2.9
diff -u -p -r2.47.2.9 tree-optimize.c
--- tree-optimize.c 18 Nov 2004 03:12:53 -0000 2.47.2.9
+++ tree-optimize.c 23 Nov 2004 22:20:27 -0000
@@ -47,7 +47,7 @@ Boston, MA 02111-1307, USA. */
#include "ggc.h"
#include "cgraph.h"
#include "graph.h"
-
+#include "cfgloop.h"
/* Global variables used to communicate with passes. */
int dump_flags;
@@ -397,6 +397,8 @@ init_tree_optimization_passes (void)
p = &pass_loop.sub;
NEXT_PASS (pass_loop_init);
+ NEXT_PASS (pass_ccp);
+ NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_lim);
NEXT_PASS (pass_unswitch);
NEXT_PASS (pass_record_bounds);
@@ -434,7 +436,12 @@ execute_todo (int properties, unsigned i
}
if (flags & TODO_cleanup_cfg)
- cleanup_tree_cfg ();
+ {
+ if (current_loops)
+ cleanup_tree_cfg_loop ();
+ else
+ cleanup_tree_cfg ();
+ }
if ((flags & TODO_dump_func) && dump_file)
{
Index: tree-ssa-copy.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copy.c,v
retrieving revision 2.15.2.8
diff -u -p -r2.15.2.8 tree-ssa-copy.c
--- tree-ssa-copy.c 18 Nov 2004 03:12:55 -0000 2.15.2.8
+++ tree-ssa-copy.c 23 Nov 2004 22:20:29 -0000
@@ -841,7 +841,6 @@ fini_copy_prop (void)
}
substitute_and_fold (copy_of);
- cleanup_tree_cfg ();
free (copy_of);
}
@@ -984,7 +983,8 @@ struct tree_opt_pass pass_copy_prop =
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func
+ TODO_cleanup_cfg
+ | TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_rename_vars, /* todo_flags_finish */
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.3.6.2
diff -u -p -r2.3.6.2 tree-ssa-loop-ivcanon.c
--- tree-ssa-loop-ivcanon.c 13 Oct 2004 16:04:19 -0000 2.3.6.2
+++ tree-ssa-loop-ivcanon.c 23 Nov 2004 22:20:29 -0000
@@ -263,12 +263,6 @@ canonicalize_induction_variables (struct
/* Clean up the information about numbers of iterations, since brute force
evaluation could reveal new information. */
scev_reset ();
-
-#if 0
- /* The necessary infrastructure is not in yet. */
- if (changed)
- cleanup_tree_cfg_loop ();
-#endif
}
/* Unroll LOOPS completely if they iterate just few times. */
@@ -278,7 +272,6 @@ tree_unroll_loops_completely (struct loo
{
unsigned i;
struct loop *loop;
- bool changed = false;
for (i = 1; i < loops->num; i++)
{
@@ -287,18 +280,11 @@ tree_unroll_loops_completely (struct loo
if (!loop)
continue;
- changed |= canonicalize_loop_induction_variables (loops, loop,
- false, true,
- !flag_tree_loop_ivcanon);
+ canonicalize_loop_induction_variables (loops, loop,false, true,
+ !flag_tree_loop_ivcanon);
}
/* Clean up the information about numbers of iterations, since complete
unrolling might have invalidated it. */
scev_reset ();
-
-#if 0
- /* The necessary infrastructure is not in yet. */
- if (changed)
- cleanup_tree_cfg_loop ();
-#endif
}
Index: tree-ssa-loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-unswitch.c,v
retrieving revision 2.3.4.1
diff -u -p -r2.3.4.1 tree-ssa-loop-unswitch.c
--- tree-ssa-loop-unswitch.c 30 Sep 2004 18:42:36 -0000 2.3.4.1
+++ tree-ssa-loop-unswitch.c 23 Nov 2004 22:20:29 -0000
@@ -107,11 +107,6 @@ tree_ssa_unswitch_loops (struct loops *l
#endif
}
-#if 0
- /* The necessary infrastructure is not in yet. */
- if (changed)
- cleanup_tree_cfg_loop ();
-#endif
}
/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.17.2.4
diff -u -p -r2.17.2.4 tree-ssa-loop.c
--- tree-ssa-loop.c 18 Nov 2004 03:12:56 -0000 2.17.2.4
+++ tree-ssa-loop.c 23 Nov 2004 22:20:29 -0000
@@ -188,7 +188,7 @@ struct tree_opt_pass pass_unswitch =
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
+ TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
@@ -292,7 +292,7 @@ struct tree_opt_pass pass_iv_canon =
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
+ TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
@@ -355,7 +355,7 @@ struct tree_opt_pass pass_complete_unrol
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
+ TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
More information about the Gcc-patches
mailing list