From 410538ea80a50d7e16bb169230a05606fbda8315 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 16 Aug 1999 22:14:51 +0000 Subject: [PATCH] basic-block.h (struct edge_list): Stucture to maintain a vector of edges. * basic-block.h (struct edge_list): Stucture to maintain a vector of edges. (EDGE_INDEX_NO_EDGE, EDGE_INDEX, INDEX_EDGE_PRED_BB, INDEX_EDGE_SUCC_BB, INDEX_EDGE, NUM_EDGES): New Macros for accessing edge list. (create_edge_list, free_edge-List, print_edge_list, verify_edge_list): New function prototypes. * flow.c (create_edge_list): Function to create an edge list. (free_edge_list): Discards memory used by an edge list. (print_edge_list): Debug output showing an edge list. (verify_edge_list): Internal consistency check for an edge list. From-SVN: r28732 --- gcc/ChangeLog | 14 +++ gcc/basic-block.h | 32 +++++++ gcc/flow.c | 265 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 311 insertions(+) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0306225..0758117 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +Mon Aug 16 18:08:22 EDT 1999 Andrew MacLeod + + * basic-block.h (struct edge_list): Stucture to maintain a vector + of edges. + (EDGE_INDEX_NO_EDGE, EDGE_INDEX, INDEX_EDGE_PRED_BB, INDEX_EDGE_SUCC_BB, + INDEX_EDGE, NUM_EDGES): New Macros for accessing edge list. + (create_edge_list, free_edge-List, print_edge_list, verify_edge_list): + New function prototypes. + * flow.c (create_edge_list): Function to create an edge list. + (free_edge_list): Discards memory used by an edge list. + (print_edge_list): Debug output showing an edge list. + (verify_edge_list): Internal consistency check for an edge list. + (find_edge_index): Function to find an edge index for a pred and succ. + Mon Aug 16 11:56:36 1999 Mark Mitchell * tree.c (type_hash_add): Use permalloc to allocate nodes in the diff --git a/gcc/basic-block.h b/gcc/basic-block.h index fa3d56f..c6a9065 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -244,6 +244,38 @@ extern basic_block split_edge PROTO ((edge)); extern void insert_insn_on_edge PROTO ((rtx, edge)); extern void commit_edge_insertions PROTO ((void)); +/* This structure maintains an edge list vector. */ +struct edge_list +{ + int num_blocks; + int num_edges; + edge *index_to_edge; +}; + +/* This is the value which indicates no edge is present. */ +#define EDGE_INDEX_NO_EDGE -1 + +/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE + if there is no edge between the 2 basic blocks. */ +#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) + +/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic + block which is either the pred or succ end of the indexed edge. */ +#define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) +#define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) + +/* INDEX_EDGE returns a pointer to the edge. */ +#define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) + +/* Number of edges in the compressed edge list. */ +#define NUM_EDGES(el) ((el)->num_edges) + +struct edge_list * create_edge_list PROTO ((void)); +void free_edge_list PROTO ((struct edge_list *)); +void print_edge_list PROTO ((FILE *, struct edge_list *)); +void verify_edge_list PROTO ((FILE *, struct edge_list *)); +int find_edge_index PROTO ((struct edge_list *, int, int)); + extern void compute_preds_succs PROTO ((int_list_ptr *, int_list_ptr *, int *, int *)); extern void compute_dominators PROTO ((sbitmap *, sbitmap *, diff --git a/gcc/flow.c b/gcc/flow.c index ccec792..e63481d 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -5243,3 +5243,268 @@ verify_flow_info () x = NEXT_INSN (x); } } + +/* Functions to access an edge list with a vector representation. + Enough data is kept such that given an index number, the + pred and succ that edge reprsents can be determined, or + given a pred and a succ, it's index number can be returned. + This allows algorithms which comsume a lot of memory to + represent the normally full matrix of edge (pred,succ) with a + single indexed vector, edge (EDGE_INDEX (pred, succ)), with no + wasted space in the client code due to sparse flow graphs. */ + +/* This functions initializes the edge list. Basically the entire + flowgraph is processed, and all edges are assigned a number, + and the data structure is filed in. */ +struct edge_list * +create_edge_list () +{ + struct edge_list *elist; + edge e; + int num_edges; + int x,y; + int_list_ptr ptr; + int block_count; + + block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */ + + num_edges = 0; + + /* Determine the number of edges in the flow graph by counting successor + edges on each basic block. */ + for (x = 0; x < n_basic_blocks; x++) + { + basic_block bb = BASIC_BLOCK (x); + + for (e = bb->succ; e; e = e->succ_next) + num_edges++; + } + /* Don't forget successors of the entry block. */ + for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) + num_edges++; + + elist = malloc (sizeof (struct edge_list)); + elist->num_blocks = block_count; + elist->num_edges = num_edges; + elist->index_to_edge = malloc (sizeof (edge) * num_edges); + + num_edges = 0; + + /* Follow successors of the entry block, and register these edges. */ + for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) + { + elist->index_to_edge[num_edges] = e; + num_edges++; + } + + for (x = 0; x < n_basic_blocks; x++) + { + basic_block bb = BASIC_BLOCK (x); + + /* Follow all successors of blocks, and register these edges. */ + for (e = bb->succ; e; e = e->succ_next) + { + elist->index_to_edge[num_edges] = e; + num_edges++; + } + } + return elist; +} + +/* This function free's memory associated with an edge list. */ +void +free_edge_list (elist) + struct edge_list *elist; +{ + if (elist) + { + free (elist->index_to_edge); + free (elist); + } +} + +/* This function provides debug output showing an edge list. */ +void +print_edge_list (f, elist) + FILE *f; + struct edge_list *elist; +{ + int x; + fprintf(f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", + elist->num_blocks - 2, elist->num_edges); + + for (x = 0; x < elist->num_edges; x++) + { + fprintf (f, " %-4d - edge(", x); + if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) + fprintf (f,"entry,"); + else + fprintf (f,"%d,", INDEX_EDGE_PRED_BB (elist, x)->index); + + if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) + fprintf (f,"exit)\n"); + else + fprintf (f,"%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); + } +} + +/* This function provides an internal consistancy check of an edge list, + verifying that all edges are present, and that there are no + extra edges. */ +void +verify_edge_list (f, elist) + FILE *f; + struct edge_list *elist; +{ + int x, pred, succ, index; + int_list_ptr ptr; + int flawed = 0; + edge e; + + for (x = 0; x < n_basic_blocks; x++) + { + basic_block bb = BASIC_BLOCK (x); + + for (e = bb->succ; e; e = e->succ_next) + { + pred = e->src->index; + succ = e->dest->index; + index = EDGE_INDEX (elist, pred, succ); + if (index == EDGE_INDEX_NO_EDGE) + { + fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ); + continue; + } + if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) + fprintf (f, "*p* Pred for index %d should be %d not %d\n", + index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); + if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) + fprintf (f, "*p* Succ for index %d should be %d not %d\n", + index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); + } + } + for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) + { + pred = e->src->index; + succ = e->dest->index; + index = EDGE_INDEX (elist, pred, succ); + if (index == EDGE_INDEX_NO_EDGE) + { + fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ); + continue; + } + if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) + fprintf (f, "*p* Pred for index %d should be %d not %d\n", + index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); + if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) + fprintf (f, "*p* Succ for index %d should be %d not %d\n", + index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); + } + /* We've verified that all the edges are in the list, no lets make sure + there are no spurious edges in the list. */ + + for (pred = 0 ; pred < n_basic_blocks; pred++) + for (succ = 0 ; succ < n_basic_blocks; succ++) + { + basic_block p = BASIC_BLOCK (pred); + basic_block s = BASIC_BLOCK (succ); + + int found_edge = 0; + + for (e = p->succ; e; e = e->succ_next) + if (e->dest == s) + { + found_edge = 1; + break; + } + for (e = s->pred; e; e = e->pred_next) + if (e->src == p) + { + found_edge = 1; + break; + } + if (EDGE_INDEX (elist, pred, succ) == EDGE_INDEX_NO_EDGE + && found_edge != 0) + fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", + pred, succ); + if (EDGE_INDEX (elist, pred, succ) != EDGE_INDEX_NO_EDGE + && found_edge == 0) + fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", + pred, succ, EDGE_INDEX (elist, pred, succ)); + } + for (succ = 0 ; succ < n_basic_blocks; succ++) + { + basic_block p = ENTRY_BLOCK_PTR; + basic_block s = BASIC_BLOCK (succ); + + int found_edge = 0; + + for (e = p->succ; e; e = e->succ_next) + if (e->dest == s) + { + found_edge = 1; + break; + } + for (e = s->pred; e; e = e->pred_next) + if (e->src == p) + { + found_edge = 1; + break; + } + if (EDGE_INDEX (elist, ENTRY_BLOCK, succ) == EDGE_INDEX_NO_EDGE + && found_edge != 0) + fprintf (f, "*** Edge (entry, %d) appears to not have an index\n", + succ); + if (EDGE_INDEX (elist, ENTRY_BLOCK, succ) != EDGE_INDEX_NO_EDGE + && found_edge == 0) + fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n", + succ, EDGE_INDEX (elist, ENTRY_BLOCK, succ)); + } + for (pred = 0 ; pred < n_basic_blocks; pred++) + { + basic_block p = BASIC_BLOCK (pred); + basic_block s = EXIT_BLOCK_PTR; + + int found_edge = 0; + + for (e = p->succ; e; e = e->succ_next) + if (e->dest == s) + { + found_edge = 1; + break; + } + for (e = s->pred; e; e = e->pred_next) + if (e->src == p) + { + found_edge = 1; + break; + } + if (EDGE_INDEX (elist, pred, EXIT_BLOCK) == EDGE_INDEX_NO_EDGE + && found_edge != 0) + fprintf (f, "*** Edge (%d, exit) appears to not have an index\n", + pred); + if (EDGE_INDEX (elist, pred, EXIT_BLOCK) != EDGE_INDEX_NO_EDGE + && found_edge == 0) + fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n", + pred, EDGE_INDEX (elist, pred, EXIT_BLOCK)); + } +} + +/* This routine will determine what, if any, edge there is between + a specified predecessor and successor. */ + +int +find_edge_index (edge_list, pred, succ) + struct edge_list *edge_list; + int pred, succ; +{ + int x; + for (x = 0; x < NUM_EDGES (edge_list); x++) + { + if (INDEX_EDGE_PRED_BB (edge_list, x)->index == pred + && INDEX_EDGE_SUCC_BB (edge_list, x)->index == succ) + return x; + } + return (EDGE_INDEX_NO_EDGE); +} + -- 2.7.4