LCOV - code coverage report
Current view: top level - gcc - graphds.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 181 197 91.9 %
Date: 2020-05-30 12:51:24 Functions: 11 12 91.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.