Author: cgrawls
Date: Sun Aug 14 20:57:58 2005
New Revision: 8966
Modified:
trunk/imcc/cfg.c
trunk/imcc/cfg.h
trunk/imcc/debug.c
trunk/imcc/debug.h
trunk/imcc/reg_alloc.c
trunk/imcc/unit.h
Log:
This patch adds support for "dominance frontiers" in imcc, including:
-Array of Sets for dominance frontiers
-An efficient algorithm described in "A Simple, Fast Dominance
Algorithm", Cooper et al. (2001)
-Free and dump functions
Modified: trunk/imcc/cfg.c
==============================================================================
--- trunk/imcc/cfg.c (original)
+++ trunk/imcc/cfg.c Sun Aug 14 20:57:58 2005
@@ -941,6 +941,52 @@ compute_dominators (Parrot_Interp interp
#endif
}
+/* Algorithm to find dominance frontiers described in paper
+ * "A Simple, Fast Dominance Algorithm", Cooper et al. (2001)
+ */
+void
+compute_dominance_frontiers (Parrot_Interp interpreter, IMC_Unit * unit)
+{
+ int i, n, b, runner;
+ Edge *edge;
+ Set** dominance_frontiers;
+
+ n = unit->n_basic_blocks;
+ IMCC_info(interpreter, 2, "compute_dominance_frontiers\n");
+ dominance_frontiers = unit->dominance_frontiers = malloc(sizeof(Set*) * n);
+
+ dominance_frontiers[0] = set_make(n);
+ for (i = 1; i < n; i++) {
+ dominance_frontiers[i] = set_make(n);
+ }
+
+ /* for all nodes, b */
+ for (b = 1; b < n; b++) {
+ edge = unit->bb_list[b]->pred_list;
+ /* if the number of predecessors of b >= 2 */
+ if (edge && edge->pred_next) {
+ /* for all predecessors, p, of b */
+ for (; edge; edge = edge->pred_next) {
+ /* runner = p */
+ runner = edge->from->index;
+ /* while runner != idoms[b] */
+ while (runner >= 0 && runner != unit->idoms[b]) {
+ /* add b to runner's dominance frontier set */
+ set_add(unit->dominance_frontiers[runner], b);
+ /* runner = idoms[runner] */
+ if (runner == 0)
+ runner = -1;
+ else
+ runner = unit->idoms[runner];
+ }
+ }
+ }
+ }
+
+ if (IMCC_INFO(interpreter)->debug & DEBUG_CFG)
+ dump_dominance_frontiers(unit);
+}
+
static void
free_dominators(IMC_Unit * unit)
{
@@ -956,6 +1002,20 @@ free_dominators(IMC_Unit * unit)
free(unit->idoms);
}
+static void
+free_dominance_frontiers(IMC_Unit * unit)
+{
+ int i;
+
+ if (!unit->dominance_frontiers)
+ return;
+ for (i=0; i < unit->n_basic_blocks; i++) {
+ set_free (unit->dominance_frontiers[i]);
+ }
+ free(unit->dominance_frontiers);
+ unit->dominance_frontiers = 0;
+}
+
static void
sort_loops(Parrot_Interp interpreter, IMC_Unit * unit)
@@ -1212,6 +1272,7 @@ clear_basic_blocks(IMC_Unit * unit)
}
free_edge(unit);
free_dominators(unit);
+ free_dominance_frontiers(unit);
free_loops(unit);
}
Modified: trunk/imcc/cfg.h
==============================================================================
--- trunk/imcc/cfg.h (original)
+++ trunk/imcc/cfg.h Sun Aug 14 20:57:58 2005
@@ -47,7 +47,8 @@ struct _IMC_Unit;
void find_basic_blocks (Parrot_Interp, struct _IMC_Unit *, int first);
void build_cfg(Parrot_Interp, struct _IMC_Unit *);
-void compute_dominators(Parrot_Interp interpreter, struct _IMC_Unit *);
+void compute_dominators(Parrot_Interp, struct _IMC_Unit *);
+void compute_dominance_frontiers(Parrot_Interp, struct _IMC_Unit *);
int natural_preheader (struct _IMC_Unit *, Loop_info*);
void find_loops(Parrot_Interp, struct _IMC_Unit *);
void search_predecessors_not_in(Basic_block*, Set*);
Modified: trunk/imcc/debug.c
==============================================================================
--- trunk/imcc/debug.c (original)
+++ trunk/imcc/debug.c Sun Aug 14 20:57:58 2005
@@ -321,6 +321,28 @@ dump_dominators(IMC_Unit * unit)
fprintf(stderr, "\n");
}
+void
+dump_dominance_frontiers(IMC_Unit * unit)
+{
+ int i, j;
+
+ fprintf(stderr, "\nDumping the Dominance Frontiers:"
+ "\n-------------------------------\n");
+ for (i = 0; i < unit->n_basic_blocks; i++) {
+ fprintf (stderr, "%2d <-", i);
+
+ for(j = 0; j < unit->n_basic_blocks; j++) {
+ if (set_contains(unit->dominance_frontiers[i], j)) {
+ fprintf(stderr, " %2d", j);
+ }
+ }
+
+ fprintf(stderr, "\n");
+ }
+
+ fprintf(stderr, "\n");
+}
+
/*
* Local variables:
* c-indentation-style: bsd
Modified: trunk/imcc/debug.h
==============================================================================
--- trunk/imcc/debug.h (original)
+++ trunk/imcc/debug.h Sun Aug 14 20:57:58 2005
@@ -32,6 +32,7 @@ void dump_labels(IMC_Unit *);
void dump_symreg(IMC_Unit *);
void dump_interference_graph(IMC_Unit *);
void dump_dominators(IMC_Unit *);
+void dump_dominance_frontiers(IMC_Unit *);
void dump_liveness_status(IMC_Unit *);
void dump_liveness_status_var(IMC_Unit *, SymReg*);
Modified: trunk/imcc/reg_alloc.c
==============================================================================
--- trunk/imcc/reg_alloc.c (original)
+++ trunk/imcc/reg_alloc.c Sun Aug 14 20:57:58 2005
@@ -155,6 +155,7 @@ imc_reg_alloc(Interp *interpreter, IMC_U
} while (cfg_optimize(interpreter, unit));
compute_dominators(interpreter, unit);
+ compute_dominance_frontiers(interpreter, unit);
find_loops(interpreter, unit);
build_reglist(interpreter, unit, 1);
Modified: trunk/imcc/unit.h
==============================================================================
--- trunk/imcc/unit.h (original)
+++ trunk/imcc/unit.h Sun Aug 14 20:57:58 2005
@@ -27,6 +27,7 @@ typedef struct _IMC_Unit {
Basic_block **bb_list;
Set** dominators;
int* idoms;
+ Set** dominance_frontiers;
int n_loops;
Loop_info ** loop_info;
Edge * edge_list;
