* df.h (struct df): Add rts_order variable.
* df.c (df_visit_next_rts): New function.
(df_visit_next): Renamed to df_visit_next_rc
(df_analyse_1): Allocate/compute/free rts_order as well.
(df_rd_global_compute): Use df_visit_next_rc instead of
df_visit_next.
(df_ru_global_compute): Use df_visit_next_rts instead of
df_visit_next.
* flow.c (flow_reverse_top_sort_order_compute): New function.
* basic-block.h: Add prototype.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@45246
138bc75d-0d04-0410-961f-
82ee72b054a4
2001-08-28 Daniel Berlin <dan@cgsoftware.com>
+ * df.h (struct df): Add rts_order variable.
+
+ * df.c (df_visit_next_rts): New function.
+ (df_visit_next): Renamed to df_visit_next_rc
+ (df_analyse_1): Allocate/compute/free rts_order as well.
+ (df_rd_global_compute): Use df_visit_next_rc instead of
+ df_visit_next.
+ (df_ru_global_compute): Use df_visit_next_rts instead of
+ df_visit_next.
+
+ * flow.c (flow_reverse_top_sort_order_compute): New function.
+
+ * basic-block.h: Add prototype.
+
+2001-08-28 Daniel Berlin <dan@cgsoftware.com>
+
* ssa-ccp.c (ssa_ccp_df_delete_unreachable_insns): For unreachable
blocks, the BB_REACHABLE is now set, rather than aux being
non-NULL. Update the test to reflect this.
extern void merge_blocks_nomove PARAMS ((basic_block, basic_block));
extern void tidy_fallthru_edge PARAMS ((edge, basic_block,
basic_block));
+extern void flow_reverse_top_sort_order_compute PARAMS ((int *));
extern int flow_depth_first_order_compute PARAMS ((int *, int *));
extern void dump_edge_info PARAMS ((FILE *, edge, int));
extern void clear_edges PARAMS ((void));
static void df_bb_refs_record PARAMS((struct df *, basic_block));
static void df_refs_record PARAMS((struct df *, bitmap));
-static int df_visit_next PARAMS ((struct df *, sbitmap));
+static int df_visit_next_rc PARAMS ((struct df *, sbitmap));
+static int df_visit_next_rts PARAMS ((struct df *, sbitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
}
\f
-/* Use depth first order, and the worklist, to figure out what block
+/* Use reverse completion order, and the worklist, to figure out what block
to look at next. */
static int
-df_visit_next (df, blocks)
+df_visit_next_rc (df, blocks)
struct df *df ATTRIBUTE_UNUSED;
sbitmap blocks;
{
return sbitmap_first_set_bit (blocks);
}
+/* Use reverse topsort order, and the worklist, to figure out what block
+ to look at next. */
+
+static int
+df_visit_next_rts (df, blocks)
+ struct df *df ATTRIBUTE_UNUSED;
+ sbitmap blocks;
+{
+ int i=0;
+ for (i = 0; i < n_basic_blocks; i++)
+ if (TEST_BIT (blocks, df->rts_order[i]))
+ return df->rts_order[i];
+ return sbitmap_first_set_bit (blocks);
+}
+
+
/* Calculate reaching defs for each basic block in BLOCKS, i.e., the
defs that are live at the start of a basic block. */
static void
bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
});
- while ((i = df_visit_next (df, worklist)) >= 0)
+ while ((i = df_visit_next_rc (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
});
- while ((i = df_visit_next (df, worklist)) >= 0)
+ while ((i = df_visit_next_rts (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
+ df->rts_order = xmalloc (sizeof(int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
-
+ flow_reverse_top_sort_order_compute (df->rts_order);
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
}
free (df->dfs_order);
free (df->rc_order);
+ free (df->rts_order);
}
bitmap *dom;
int * dfs_order;
int * rc_order;
+ int * rts_order;
};
return num_nodes;
}
+/* Compute reverse top sort order */
+void
+flow_reverse_top_sort_order_compute (rts_order)
+ int *rts_order;
+{
+ edge *stack;
+ int sp;
+ int postnum = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (n_basic_blocks);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+ while (sp)
+ {
+ edge e;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ e = stack[sp - 1];
+ src = e->src;
+ dest = e->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ rts_order[postnum++] = dest->index;
+ }
+ else
+ {
+ if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ rts_order[postnum++] = src->index;
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+}
+
/* Compute the depth first search order and store in the array
DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
RC_ORDER is non-zero, return the reverse completion number for each
OSDN Git Service
