OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [graphds.c] - Blame information for rev 328

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Graph representation and manipulation functions.
2
   Copyright (C) 2007
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "obstack.h"
25
#include "bitmap.h"
26
#include "vec.h"
27
#include "vecprim.h"
28
#include "graphds.h"
29
 
30
/* Dumps graph G into F.  */
31
 
32
void
33
dump_graph (FILE *f, struct graph *g)
34
{
35
  int i;
36
  struct graph_edge *e;
37
 
38
  for (i = 0; i < g->n_vertices; i++)
39
    {
40
      if (!g->vertices[i].pred
41
          && !g->vertices[i].succ)
42
        continue;
43
 
44
      fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
45
      for (e = g->vertices[i].pred; e; e = e->pred_next)
46
        fprintf (f, " %d", e->src);
47
      fprintf (f, "\n");
48
 
49
      fprintf (f, "\t->");
50
      for (e = g->vertices[i].succ; e; e = e->succ_next)
51
        fprintf (f, " %d", e->dest);
52
      fprintf (f, "\n");
53
    }
54
}
55
 
56
/* Creates a new graph with N_VERTICES vertices.  */
57
 
58
struct graph *
59
new_graph (int n_vertices)
60
{
61
  struct graph *g = XNEW (struct graph);
62
 
63
  g->n_vertices = n_vertices;
64
  g->vertices = XCNEWVEC (struct vertex, n_vertices);
65
 
66
  return g;
67
}
68
 
69
/* Adds an edge from F to T to graph G.  The new edge is returned.  */
70
 
71
struct graph_edge *
72
add_edge (struct graph *g, int f, int t)
73
{
74
  struct graph_edge *e = XNEW (struct graph_edge);
75
  struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
76
 
77
 
78
  e->src = f;
79
  e->dest = t;
80
 
81
  e->pred_next = vt->pred;
82
  vt->pred = e;
83
 
84
  e->succ_next = vf->succ;
85
  vf->succ = e;
86
 
87
  return e;
88
}
89
 
90
/* Moves all the edges incident with U to V.  */
91
 
92
void
93
identify_vertices (struct graph *g, int v, int u)
94
{
95
  struct vertex *vv = &g->vertices[v];
96
  struct vertex *uu = &g->vertices[u];
97
  struct graph_edge *e, *next;
98
 
99
  for (e = uu->succ; e; e = next)
100
    {
101
      next = e->succ_next;
102
 
103
      e->src = v;
104
      e->succ_next = vv->succ;
105
      vv->succ = e;
106
    }
107
  uu->succ = NULL;
108
 
109
  for (e = uu->pred; e; e = next)
110
    {
111
      next = e->pred_next;
112
 
113
      e->dest = v;
114
      e->pred_next = vv->pred;
115
      vv->pred = e;
116
    }
117
  uu->pred = NULL;
118
}
119
 
120
/* Helper function for graphds_dfs.  Returns the source vertex of E, in the
121
   direction given by FORWARD.  */
122
 
123
static inline int
124
dfs_edge_src (struct graph_edge *e, bool forward)
125
{
126
  return forward ? e->src : e->dest;
127
}
128
 
129
/* Helper function for graphds_dfs.  Returns the destination vertex of E, in
130
   the direction given by FORWARD.  */
131
 
132
static inline int
133
dfs_edge_dest (struct graph_edge *e, bool forward)
134
{
135
  return forward ? e->dest : e->src;
136
}
137
 
138
/* Helper function for graphds_dfs.  Returns the first edge after E (including
139
   E), in the graph direction given by FORWARD, that belongs to SUBGRAPH.  */
140
 
141
static inline struct graph_edge *
142
foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
143
{
144
  int d;
145
 
146
  if (!subgraph)
147
    return e;
148
 
149
  while (e)
150
    {
151
      d = dfs_edge_dest (e, forward);
152
      if (bitmap_bit_p (subgraph, d))
153
        return e;
154
 
155
      e = forward ? e->succ_next : e->pred_next;
156
    }
157
 
158
  return e;
159
}
160
 
161
/* Helper function for graphds_dfs.  Select the first edge from V in G, in the
162
   direction given by FORWARD, that belongs to SUBGRAPH.  */
163
 
164
static inline struct graph_edge *
165
dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
166
{
167
  struct graph_edge *e;
168
 
169
  e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
170
  return foll_in_subgraph (e, forward, subgraph);
171
}
172
 
173
/* Helper function for graphds_dfs.  Returns the next edge after E, in the
174
   graph direction given by FORWARD, that belongs to SUBGRAPH.  */
175
 
176
static inline struct graph_edge *
177
dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
178
{
179
  return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
180
                           forward, subgraph);
181
}
182
 
183
/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
184
   The vertices in postorder are stored into QT.  If FORWARD is false,
185
   backward dfs is run.  If SUBGRAPH is not NULL, it specifies the
186
   subgraph of G to run DFS on.  Returns the number of the components
187
   of the graph (number of the restarts of DFS).  */
188
 
189
int
190
graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
191
             bool forward, bitmap subgraph)
192
{
193
  int i, tick = 0, v, comp = 0, top;
194
  struct graph_edge *e;
195
  struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
196
  bitmap_iterator bi;
197
  unsigned av;
198
 
199
  if (subgraph)
200
    {
201
      EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
202
        {
203
          g->vertices[av].component = -1;
204
          g->vertices[av].post = -1;
205
        }
206
    }
207
  else
208
    {
209
      for (i = 0; i < g->n_vertices; i++)
210
        {
211
          g->vertices[i].component = -1;
212
          g->vertices[i].post = -1;
213
        }
214
    }
215
 
216
  for (i = 0; i < nq; i++)
217
    {
218
      v = qs[i];
219
      if (g->vertices[v].post != -1)
220
        continue;
221
 
222
      g->vertices[v].component = comp++;
223
      e = dfs_fst_edge (g, v, forward, subgraph);
224
      top = 0;
225
 
226
      while (1)
227
        {
228
          while (e)
229
            {
230
              if (g->vertices[dfs_edge_dest (e, forward)].component
231
                  == -1)
232
                break;
233
              e = dfs_next_edge (e, forward, subgraph);
234
            }
235
 
236
          if (!e)
237
            {
238
              if (qt)
239
                VEC_safe_push (int, heap, *qt, v);
240
              g->vertices[v].post = tick++;
241
 
242
              if (!top)
243
                break;
244
 
245
              e = stack[--top];
246
              v = dfs_edge_src (e, forward);
247
              e = dfs_next_edge (e, forward, subgraph);
248
              continue;
249
            }
250
 
251
          stack[top++] = e;
252
          v = dfs_edge_dest (e, forward);
253
          e = dfs_fst_edge (g, v, forward, subgraph);
254
          g->vertices[v].component = comp - 1;
255
        }
256
    }
257
 
258
  free (stack);
259
 
260
  return comp;
261
}
262
 
263
/* Determines the strongly connected components of G, using the algorithm of
264
   Tarjan -- first determine the postorder dfs numbering in reversed graph,
265
   then run the dfs on the original graph in the order given by decreasing
266
   numbers assigned by the previous pass.  If SUBGRAPH is not NULL, it
267
   specifies the subgraph of G whose strongly connected components we want
268
   to determine.
269
 
270
   After running this function, v->component is the number of the strongly
271
   connected component for each vertex of G.  Returns the number of the
272
   sccs of G.  */
273
 
274
int
275
graphds_scc (struct graph *g, bitmap subgraph)
276
{
277
  int *queue = XNEWVEC (int, g->n_vertices);
278
  VEC (int, heap) *postorder = NULL;
279
  int nq, i, comp;
280
  unsigned v;
281
  bitmap_iterator bi;
282
 
283
  if (subgraph)
284
    {
285
      nq = 0;
286
      EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
287
        {
288
          queue[nq++] = v;
289
        }
290
    }
291
  else
292
    {
293
      for (i = 0; i < g->n_vertices; i++)
294
        queue[i] = i;
295
      nq = g->n_vertices;
296
    }
297
 
298
  graphds_dfs (g, queue, nq, &postorder, false, subgraph);
299
  gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
300
 
301
  for (i = 0; i < nq; i++)
302
    queue[i] = VEC_index (int, postorder, nq - i - 1);
303
  comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
304
 
305
  free (queue);
306
  VEC_free (int, heap, postorder);
307
 
308
  return comp;
309
}
310
 
311
/* Runs CALLBACK for all edges in G.  */
312
 
313
void
314
for_each_edge (struct graph *g, graphds_edge_callback callback)
315
{
316
  struct graph_edge *e;
317
  int i;
318
 
319
  for (i = 0; i < g->n_vertices; i++)
320
    for (e = g->vertices[i].succ; e; e = e->succ_next)
321
      callback (g, e);
322
}
323
 
324
/* Releases the memory occupied by G.  */
325
 
326
void
327
free_graph (struct graph *g)
328
{
329
  struct graph_edge *e, *n;
330
  struct vertex *v;
331
  int i;
332
 
333
  for (i = 0; i < g->n_vertices; i++)
334
    {
335
      v = &g->vertices[i];
336
      for (e = v->succ; e; e = n)
337
        {
338
          n = e->succ_next;
339
          free (e);
340
        }
341
    }
342
  free (g->vertices);
343
  free (g);
344
}
345
 
346
/* Returns the nearest common ancestor of X and Y in tree whose parent
347
   links are given by PARENT.  MARKS is the array used to mark the
348
   vertices of the tree, and MARK is the number currently used as a mark.  */
349
 
350
static int
351
tree_nca (int x, int y, int *parent, int *marks, int mark)
352
{
353
  if (x == -1 || x == y)
354
    return y;
355
 
356
  /* We climb with X and Y up the tree, marking the visited nodes.  When
357
     we first arrive to a marked node, it is the common ancestor.  */
358
  marks[x] = mark;
359
  marks[y] = mark;
360
 
361
  while (1)
362
    {
363
      x = parent[x];
364
      if (x == -1)
365
        break;
366
      if (marks[x] == mark)
367
        return x;
368
      marks[x] = mark;
369
 
370
      y = parent[y];
371
      if (y == -1)
372
        break;
373
      if (marks[y] == mark)
374
        return y;
375
      marks[y] = mark;
376
    }
377
 
378
  /* If we reached the root with one of the vertices, continue
379
     with the other one till we reach the marked part of the
380
     tree.  */
381
  if (x == -1)
382
    {
383
      for (y = parent[y]; marks[y] != mark; y = parent[y])
384
        continue;
385
 
386
      return y;
387
    }
388
  else
389
    {
390
      for (x = parent[x]; marks[x] != mark; x = parent[x])
391
        continue;
392
 
393
      return x;
394
    }
395
}
396
 
397
/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
398
   arrays), where the entry node is ENTRY.  */
399
 
400
void
401
graphds_domtree (struct graph *g, int entry,
402
                 int *parent, int *son, int *brother)
403
{
404
  VEC (int, heap) *postorder = NULL;
405
  int *marks = XCNEWVEC (int, g->n_vertices);
406
  int mark = 1, i, v, idom;
407
  bool changed = true;
408
  struct graph_edge *e;
409
 
410
  /* We use a slight modification of the standard iterative algorithm, as
411
     described in
412
 
413
     K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
414
        Algorithm
415
 
416
     sort vertices in reverse postorder
417
     foreach v
418
       dom(v) = everything
419
     dom(entry) = entry;
420
 
421
     while (anything changes)
422
       foreach v
423
         dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
424
 
425
     The sets dom(v) are represented by the parent links in the current version
426
     of the dominance tree.  */
427
 
428
  for (i = 0; i < g->n_vertices; i++)
429
    {
430
      parent[i] = -1;
431
      son[i] = -1;
432
      brother[i] = -1;
433
    }
434
  graphds_dfs (g, &entry, 1, &postorder, true, NULL);
435
  gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
436
  gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
437
 
438
  while (changed)
439
    {
440
      changed = false;
441
 
442
      for (i = g->n_vertices - 2; i >= 0; i--)
443
        {
444
          v = VEC_index (int, postorder, i);
445
          idom = -1;
446
          for (e = g->vertices[v].pred; e; e = e->pred_next)
447
            {
448
              if (e->src != entry
449
                  && parent[e->src] == -1)
450
                continue;
451
 
452
              idom = tree_nca (idom, e->src, parent, marks, mark++);
453
            }
454
 
455
          if (idom != parent[v])
456
            {
457
              parent[v] = idom;
458
              changed = true;
459
            }
460
        }
461
    }
462
 
463
  free (marks);
464
  VEC_free (int, heap, postorder);
465
 
466
  for (i = 0; i < g->n_vertices; i++)
467
    if (parent[i] != -1)
468
      {
469
        brother[i] = son[parent[i]];
470
        son[parent[i]] = i;
471
      }
472
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.