From df62c1c110e8532b995b23540b7e3695729c0779 Mon Sep 17 00:00:00 2001 From: Jing Yu Date: Thu, 5 Nov 2009 15:11:04 -0800 Subject: Check in gcc sources for prebuilt toolchains in Eclair. --- gcc-4.4.0/gcc/graphds.c | 472 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 472 insertions(+) create mode 100644 gcc-4.4.0/gcc/graphds.c (limited to 'gcc-4.4.0/gcc/graphds.c') diff --git a/gcc-4.4.0/gcc/graphds.c b/gcc-4.4.0/gcc/graphds.c new file mode 100644 index 000000000..7dcb04c13 --- /dev/null +++ b/gcc-4.4.0/gcc/graphds.c @@ -0,0 +1,472 @@ +/* Graph representation and manipulation functions. + Copyright (C) 2007 + Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "obstack.h" +#include "bitmap.h" +#include "vec.h" +#include "vecprim.h" +#include "graphds.h" + +/* Dumps graph G into F. */ + +void +dump_graph (FILE *f, struct graph *g) +{ + int i; + struct graph_edge *e; + + for (i = 0; i < g->n_vertices; i++) + { + if (!g->vertices[i].pred + && !g->vertices[i].succ) + continue; + + fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component); + for (e = g->vertices[i].pred; e; e = e->pred_next) + fprintf (f, " %d", e->src); + fprintf (f, "\n"); + + fprintf (f, "\t->"); + for (e = g->vertices[i].succ; e; e = e->succ_next) + fprintf (f, " %d", e->dest); + fprintf (f, "\n"); + } +} + +/* Creates a new graph with N_VERTICES vertices. */ + +struct graph * +new_graph (int n_vertices) +{ + struct graph *g = XNEW (struct graph); + + g->n_vertices = n_vertices; + g->vertices = XCNEWVEC (struct vertex, n_vertices); + + return g; +} + +/* Adds an edge from F to T to graph G. The new edge is returned. */ + +struct graph_edge * +add_edge (struct graph *g, int f, int t) +{ + struct graph_edge *e = XNEW (struct graph_edge); + struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t]; + + + e->src = f; + e->dest = t; + + e->pred_next = vt->pred; + vt->pred = e; + + e->succ_next = vf->succ; + vf->succ = e; + + return e; +} + +/* Moves all the edges incident with U to V. */ + +void +identify_vertices (struct graph *g, int v, int u) +{ + struct vertex *vv = &g->vertices[v]; + struct vertex *uu = &g->vertices[u]; + struct graph_edge *e, *next; + + for (e = uu->succ; e; e = next) + { + next = e->succ_next; + + e->src = v; + e->succ_next = vv->succ; + vv->succ = e; + } + uu->succ = NULL; + + for (e = uu->pred; e; e = next) + { + next = e->pred_next; + + e->dest = v; + e->pred_next = vv->pred; + vv->pred = e; + } + uu->pred = NULL; +} + +/* Helper function for graphds_dfs. Returns the source vertex of E, in the + direction given by FORWARD. */ + +static inline int +dfs_edge_src (struct graph_edge *e, bool forward) +{ + return forward ? e->src : e->dest; +} + +/* Helper function for graphds_dfs. Returns the destination vertex of E, in + the direction given by FORWARD. */ + +static inline int +dfs_edge_dest (struct graph_edge *e, bool forward) +{ + return forward ? e->dest : e->src; +} + +/* Helper function for graphds_dfs. Returns the first edge after E (including + E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct graph_edge * +foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph) +{ + int d; + + if (!subgraph) + return e; + + while (e) + { + d = dfs_edge_dest (e, forward); + if (bitmap_bit_p (subgraph, d)) + return e; + + e = forward ? e->succ_next : e->pred_next; + } + + return e; +} + +/* Helper function for graphds_dfs. Select the first edge from V in G, in the + direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct graph_edge * +dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph) +{ + struct graph_edge *e; + + e = (forward ? g->vertices[v].succ : g->vertices[v].pred); + return foll_in_subgraph (e, forward, subgraph); +} + +/* Helper function for graphds_dfs. Returns the next edge after E, in the + graph direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct graph_edge * +dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph) +{ + return foll_in_subgraph (forward ? e->succ_next : e->pred_next, + forward, subgraph); +} + +/* Runs dfs search over vertices of G, from NQ vertices in queue QS. + The vertices in postorder are stored into QT. If FORWARD is false, + backward dfs is run. If SUBGRAPH is not NULL, it specifies the + subgraph of G to run DFS on. Returns the number of the components + of the graph (number of the restarts of DFS). */ + +int +graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt, + bool forward, bitmap subgraph) +{ + int i, tick = 0, v, comp = 0, top; + struct graph_edge *e; + struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices); + bitmap_iterator bi; + unsigned av; + + if (subgraph) + { + EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi) + { + g->vertices[av].component = -1; + g->vertices[av].post = -1; + } + } + else + { + for (i = 0; i < g->n_vertices; i++) + { + g->vertices[i].component = -1; + g->vertices[i].post = -1; + } + } + + for (i = 0; i < nq; i++) + { + v = qs[i]; + if (g->vertices[v].post != -1) + continue; + + g->vertices[v].component = comp++; + e = dfs_fst_edge (g, v, forward, subgraph); + top = 0; + + while (1) + { + while (e) + { + if (g->vertices[dfs_edge_dest (e, forward)].component + == -1) + break; + e = dfs_next_edge (e, forward, subgraph); + } + + if (!e) + { + if (qt) + VEC_safe_push (int, heap, *qt, v); + g->vertices[v].post = tick++; + + if (!top) + break; + + e = stack[--top]; + v = dfs_edge_src (e, forward); + e = dfs_next_edge (e, forward, subgraph); + continue; + } + + stack[top++] = e; + v = dfs_edge_dest (e, forward); + e = dfs_fst_edge (g, v, forward, subgraph); + g->vertices[v].component = comp - 1; + } + } + + free (stack); + + return comp; +} + +/* Determines the strongly connected components of G, using the algorithm of + Tarjan -- first determine the postorder dfs numbering in reversed graph, + then run the dfs on the original graph in the order given by decreasing + numbers assigned by the previous pass. If SUBGRAPH is not NULL, it + specifies the subgraph of G whose strongly connected components we want + to determine. + + After running this function, v->component is the number of the strongly + connected component for each vertex of G. Returns the number of the + sccs of G. */ + +int +graphds_scc (struct graph *g, bitmap subgraph) +{ + int *queue = XNEWVEC (int, g->n_vertices); + VEC (int, heap) *postorder = NULL; + int nq, i, comp; + unsigned v; + bitmap_iterator bi; + + if (subgraph) + { + nq = 0; + EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi) + { + queue[nq++] = v; + } + } + else + { + for (i = 0; i < g->n_vertices; i++) + queue[i] = i; + nq = g->n_vertices; + } + + graphds_dfs (g, queue, nq, &postorder, false, subgraph); + gcc_assert (VEC_length (int, postorder) == (unsigned) nq); + + for (i = 0; i < nq; i++) + queue[i] = VEC_index (int, postorder, nq - i - 1); + comp = graphds_dfs (g, queue, nq, NULL, true, subgraph); + + free (queue); + VEC_free (int, heap, postorder); + + return comp; +} + +/* Runs CALLBACK for all edges in G. */ + +void +for_each_edge (struct graph *g, graphds_edge_callback callback) +{ + struct graph_edge *e; + int i; + + for (i = 0; i < g->n_vertices; i++) + for (e = g->vertices[i].succ; e; e = e->succ_next) + callback (g, e); +} + +/* Releases the memory occupied by G. */ + +void +free_graph (struct graph *g) +{ + struct graph_edge *e, *n; + struct vertex *v; + int i; + + for (i = 0; i < g->n_vertices; i++) + { + v = &g->vertices[i]; + for (e = v->succ; e; e = n) + { + n = e->succ_next; + free (e); + } + } + free (g->vertices); + free (g); +} + +/* Returns the nearest common ancestor of X and Y in tree whose parent + links are given by PARENT. MARKS is the array used to mark the + vertices of the tree, and MARK is the number currently used as a mark. */ + +static int +tree_nca (int x, int y, int *parent, int *marks, int mark) +{ + if (x == -1 || x == y) + return y; + + /* We climb with X and Y up the tree, marking the visited nodes. When + we first arrive to a marked node, it is the common ancestor. */ + marks[x] = mark; + marks[y] = mark; + + while (1) + { + x = parent[x]; + if (x == -1) + break; + if (marks[x] == mark) + return x; + marks[x] = mark; + + y = parent[y]; + if (y == -1) + break; + if (marks[y] == mark) + return y; + marks[y] = mark; + } + + /* If we reached the root with one of the vertices, continue + with the other one till we reach the marked part of the + tree. */ + if (x == -1) + { + for (y = parent[y]; marks[y] != mark; y = parent[y]) + continue; + + return y; + } + else + { + for (x = parent[x]; marks[x] != mark; x = parent[x]) + continue; + + return x; + } +} + +/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER + arrays), where the entry node is ENTRY. */ + +void +graphds_domtree (struct graph *g, int entry, + int *parent, int *son, int *brother) +{ + VEC (int, heap) *postorder = NULL; + int *marks = XCNEWVEC (int, g->n_vertices); + int mark = 1, i, v, idom; + bool changed = true; + struct graph_edge *e; + + /* We use a slight modification of the standard iterative algorithm, as + described in + + K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance + Algorithm + + sort vertices in reverse postorder + foreach v + dom(v) = everything + dom(entry) = entry; + + while (anything changes) + foreach v + dom(v) = {v} union (intersection of dom(p) over all predecessors of v) + + The sets dom(v) are represented by the parent links in the current version + of the dominance tree. */ + + for (i = 0; i < g->n_vertices; i++) + { + parent[i] = -1; + son[i] = -1; + brother[i] = -1; + } + graphds_dfs (g, &entry, 1, &postorder, true, NULL); + gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices); + gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry); + + while (changed) + { + changed = false; + + for (i = g->n_vertices - 2; i >= 0; i--) + { + v = VEC_index (int, postorder, i); + idom = -1; + for (e = g->vertices[v].pred; e; e = e->pred_next) + { + if (e->src != entry + && parent[e->src] == -1) + continue; + + idom = tree_nca (idom, e->src, parent, marks, mark++); + } + + if (idom != parent[v]) + { + parent[v] = idom; + changed = true; + } + } + } + + free (marks); + VEC_free (int, heap, postorder); + + for (i = 0; i < g->n_vertices; i++) + if (parent[i] != -1) + { + brother[i] = son[parent[i]]; + son[parent[i]] = i; + } +} -- cgit v1.2.3