LCOV - code coverage report
Current view: top level - gcc - pta-andersen.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 97.7 % 1118 1092
Test Date: 2026-11-14 16:39:50 Functions: 98.0 % 50 49
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Andersen-style solver for tree based points-to analysis
       2              :    Copyright (C) 2005-2026 Free Software Foundation, Inc.
       3              :    Contributed by Daniel Berlin <dberlin@dberlin.org>
       4              : 
       5              :    This file is part of GCC.
       6              : 
       7              :    GCC is free software; you can redistribute it and/or modify
       8              :    under the terms of the GNU General Public License as published by
       9              :    the Free Software Foundation; either version 3 of the License, or
      10              :    (at your option) any later version.
      11              : 
      12              :    GCC is distributed in the hope that it will be useful,
      13              :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      14              :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15              :    GNU General Public License 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 "backend.h"
      25              : 
      26              : #include "tree-ssa-structalias.h"
      27              : #include "pta-andersen.h"
      28              : 
      29              : /* During variable substitution and the offline version of indirect
      30              :    cycle finding, we create nodes to represent dereferences and
      31              :    address taken constraints.  These represent where these start and
      32              :    end.  */
      33              : #define FIRST_REF_NODE (varmap).length ()
      34              : #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
      35              : 
      36              : #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d)        \
      37              :   if (a)                                                \
      38              :     EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
      39              : 
      40              : using namespace pointer_analysis;
      41              : 
      42              : /* Used for predecessor bitmaps.  */
      43              : static bitmap_obstack predbitmap_obstack;
      44              : 
      45              : /* Used for per-solver-iteration bitmaps.  */
      46              : static bitmap_obstack iteration_obstack;
      47              : 
      48              : typedef struct constraint_graph *constraint_graph_t;
      49              : 
      50              : /* The constraint graph is represented as an array of bitmaps
      51              :    containing successor nodes.  */
      52              : 
      53              : struct constraint_graph
      54              : {
      55              :   /* Size of this graph, which may be different than the number of
      56              :      nodes in the variable map.  */
      57              :   unsigned int size;
      58              : 
      59              :   /* Explicit successors of each node.  */
      60              :   bitmap *succs;
      61              : 
      62              :   /* Implicit predecessors of each node (Used for variable
      63              :      substitution). */
      64              :   bitmap *implicit_preds;
      65              : 
      66              :   /* Explicit predecessors of each node (Used for variable substitution).  */
      67              :   bitmap *preds;
      68              : 
      69              :   /* Indirect cycle representatives, or -1 if the node has no indirect
      70              :      cycles.  */
      71              :   int *indirect_cycles;
      72              : 
      73              :   /* Representative node for a node.  rep[a] == a unless the node has
      74              :      been unified.  */
      75              :   unsigned int *rep;
      76              : 
      77              :   /* Equivalence class representative for a label.  This is used for
      78              :      variable substitution.  */
      79              :   int *eq_rep;
      80              : 
      81              :   /* Pointer equivalence label for a node.  All nodes with the same
      82              :      pointer equivalence label can be unified together at some point
      83              :      (either during constraint optimization or after the constraint
      84              :      graph is built).  */
      85              :   unsigned int *pe;
      86              : 
      87              :   /* Pointer equivalence representative for a label.  This is used to
      88              :      handle nodes that are pointer equivalent but not location
      89              :      equivalent.  We can unite these once the addressof constraints
      90              :      are transformed into initial points-to sets.  */
      91              :   int *pe_rep;
      92              : 
      93              :   /* Pointer equivalence label for each node, used during variable
      94              :      substitution.  */
      95              :   unsigned int *pointer_label;
      96              : 
      97              :   /* Location equivalence label for each node, used during location
      98              :      equivalence finding.  */
      99              :   unsigned int *loc_label;
     100              : 
     101              :   /* Pointed-by set for each node, used during location equivalence
     102              :      finding.  This is pointed-by rather than pointed-to, because it
     103              :      is constructed using the predecessor graph.  */
     104              :   bitmap *pointed_by;
     105              : 
     106              :   /* Points to sets for pointer equivalence.  This is *not* the actual
     107              :      points-to sets for nodes.  */
     108              :   bitmap *points_to;
     109              : 
     110              :   /* Bitmap of nodes where the bit is set if the node is a direct
     111              :      node.  Used for variable substitution.  */
     112              :   sbitmap direct_nodes;
     113              : 
     114              :   /* Bitmap of nodes where the bit is set if the node is address
     115              :      taken.  Used for variable substitution.  */
     116              :   bitmap address_taken;
     117              : 
     118              :   /* Vector of complex constraints for each graph node.  Complex
     119              :      constraints are those involving dereferences or offsets that are
     120              :      not 0.  */
     121              :   vec<constraint_t> *complex;
     122              : };
     123              : 
     124              : static constraint_graph_t graph;
     125              : 
     126              : static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
     127              : 
     128              : 
     129              : /* Return the representative node for NODE, if NODE has been unioned
     130              :    with another NODE.
     131              :    This function performs path compression along the way to finding
     132              :    the representative.  */
     133              : 
     134              : static unsigned int
     135   8723047174 : find (unsigned int node)
     136              : {
     137   8723047174 :   gcc_checking_assert (node < graph->size);
     138   8723047174 :   if (graph->rep[node] != node)
     139    428839463 :     return graph->rep[node] = find (graph->rep[node]);
     140              :   return node;
     141              : }
     142              : 
     143              : /* Union the TO and FROM nodes to the TO nodes.
     144              :    Note that at some point in the future, we may want to do
     145              :    union-by-rank, in which case we are going to have to return the
     146              :    node we unified to.  */
     147              : 
     148              : static bool
     149    616713206 : unite (unsigned int to, unsigned int from)
     150              : {
     151    616713206 :   gcc_checking_assert (to < graph->size && from < graph->size);
     152    616713206 :   if (to != from
     153    120740412 :       && graph->rep[from] != to
     154              :       /* Do not merge an artificial variable into another, this will
     155              :          explode solution sets unnecessarily.  */
     156    858072887 :       && (from >= FIRST_REF_NODE || !get_varinfo (from)->is_artificial_var))
     157              :     {
     158     44010917 :       graph->rep[from] = to;
     159     44010917 :       return true;
     160              :     }
     161              :   return false;
     162              : }
     163              : 
     164              : /* Perform path compression for all nodes in the node representatives
     165              :    union-find structure.  */
     166              : 
     167              : static void
     168      4568954 : union_find_compress_all (void)
     169              : {
     170      4568954 :   unsigned int i;
     171    238452916 :   for (i = 0; i < graph->size; i++)
     172    233883962 :     find (i);
     173      4568954 : }
     174              : 
     175              : /* Print the constraint graph in dot format.  */
     176              : 
     177              : static void
     178            6 : dump_constraint_graph (FILE *file)
     179              : {
     180            6 :   unsigned int i;
     181              : 
     182              :   /* Only print the graph if it has already been initialized:  */
     183            6 :   if (!graph)
     184              :     return;
     185              : 
     186              :   /* Prints the header of the dot file:  */
     187            6 :   fprintf (file, "strict digraph {\n");
     188            6 :   fprintf (file, "  node [\n    shape = box\n  ]\n");
     189            6 :   fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");
     190            6 :   fprintf (file, "\n  // List of nodes and complex constraints in "
     191              :            "the constraint graph:\n");
     192              : 
     193              :   /* The next lines print the nodes in the graph together with the
     194              :      complex constraints attached to them.  */
     195           86 :   for (i = 1; i < graph->size; i++)
     196              :     {
     197          148 :       if (i == FIRST_REF_NODE)
     198            0 :         continue;
     199           74 :       if (find (i) != i)
     200            2 :         continue;
     201           72 :       if (i < FIRST_REF_NODE)
     202           72 :         fprintf (file, "\"%s\"", get_varinfo (i)->name);
     203              :       else
     204            0 :         fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
     205           72 :       if (graph->complex[i].exists ())
     206              :         {
     207           16 :           unsigned j;
     208           16 :           constraint_t c;
     209           16 :           fprintf (file, " [label=\"\\N\\n");
     210           70 :           for (j = 0; graph->complex[i].iterate (j, &c); ++j)
     211              :             {
     212           38 :               dump_constraint (file, c);
     213           38 :               fprintf (file, "\\l");
     214              :             }
     215           16 :           fprintf (file, "\"]");
     216              :         }
     217           72 :       fprintf (file, ";\n");
     218              :     }
     219              : 
     220              :   /* Go over the edges.  */
     221            6 :   fprintf (file, "\n  // Edges in the constraint graph:\n");
     222           86 :   for (i = 1; i < graph->size; i++)
     223              :     {
     224           74 :       unsigned j;
     225           74 :       bitmap_iterator bi;
     226           74 :       if (find (i) != i)
     227            2 :         continue;
     228          102 :       EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
     229              :         {
     230           30 :           unsigned to = find (j);
     231           30 :           if (i == to)
     232            0 :             continue;
     233           30 :           if (i < FIRST_REF_NODE)
     234           30 :             fprintf (file, "\"%s\"", get_varinfo (i)->name);
     235              :           else
     236            0 :             fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
     237           30 :           fprintf (file, " -> ");
     238           30 :           if (to < FIRST_REF_NODE)
     239           30 :             fprintf (file, "\"%s\"", get_varinfo (to)->name);
     240              :           else
     241            0 :             fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
     242           30 :           fprintf (file, ";\n");
     243              :         }
     244              :     }
     245              : 
     246              :   /* Prints the tail of the dot file.  */
     247            6 :   fprintf (file, "}\n");
     248              : }
     249              : 
     250              : /* Print out the constraint graph to stderr.  */
     251              : 
     252              : DEBUG_FUNCTION void
     253            0 : debug_constraint_graph (void)
     254              : {
     255            0 :   dump_constraint_graph (stderr);
     256            0 : }
     257              : 
     258              : 
     259              : /* SOLVER FUNCTIONS
     260              : 
     261              :    The solver is a simple worklist solver, that works on the following
     262              :    algorithm:
     263              : 
     264              :    sbitmap changed_nodes = all zeroes;
     265              :    changed_count = 0;
     266              :    For each node that is not already collapsed:
     267              :        changed_count++;
     268              :        set bit in changed nodes
     269              : 
     270              :    while (changed_count > 0)
     271              :    {
     272              :      compute topological ordering for constraint graph
     273              : 
     274              :      find and collapse cycles in the constraint graph (updating
     275              :      changed if necessary)
     276              : 
     277              :      for each node (n) in the graph in topological order:
     278              :        changed_count--;
     279              : 
     280              :        Process each complex constraint associated with the node,
     281              :        updating changed if necessary.
     282              : 
     283              :        For each outgoing edge from n, propagate the solution from n to
     284              :        the destination of the edge, updating changed as necessary.
     285              : 
     286              :    }  */
     287              : 
     288              : /* Return true if two constraint expressions A and B are equal.  */
     289              : 
     290              : static bool
     291     18115123 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
     292              : {
     293     10930502 :   return a.type == b.type && a.var == b.var && a.offset == b.offset;
     294              : }
     295              : 
     296              : /* Return true if constraint expression A is less than constraint expression
     297              :    B.  This is just arbitrary, but consistent, in order to give them an
     298              :    ordering.  */
     299              : 
     300              : static bool
     301    451882329 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
     302              : {
     303            0 :   if (a.type == b.type)
     304              :     {
     305    268878823 :       if (a.var == b.var)
     306    202761601 :         return a.offset < b.offset;
     307              :       else
     308     66117222 :         return a.var < b.var;
     309              :     }
     310              :   else
     311    183003506 :     return a.type < b.type;
     312              : }
     313              : 
     314              : /* Return true if constraint A is less than constraint B.  This is just
     315              :    arbitrary, but consistent, in order to give them an ordering.  */
     316              : 
     317              : static bool
     318    248946286 : constraint_less (const constraint_t &a, const constraint_t &b)
     319              : {
     320    497892572 :   if (constraint_expr_less (a->lhs, b->lhs))
     321              :     return true;
     322    214125360 :   else if (constraint_expr_less (b->lhs, a->lhs))
     323              :     return false;
     324              :   else
     325     95873363 :     return constraint_expr_less (a->rhs, b->rhs);
     326              : }
     327              : 
     328              : /* Return true if two constraints A and B are equal.  */
     329              : 
     330              : static bool
     331     11918293 : constraint_equal (const constraint &a, const constraint &b)
     332              : {
     333     18115123 :   return constraint_expr_equal (a.lhs, b.lhs)
     334     11918293 :     && constraint_expr_equal (a.rhs, b.rhs);
     335              : }
     336              : 
     337              : /* Find a constraint LOOKFOR in the sorted constraint vector VEC.  */
     338              : 
     339              : static constraint_t
     340        12109 : constraint_vec_find (vec<constraint_t> vec,
     341              :                      constraint &lookfor)
     342              : {
     343        12109 :   unsigned int place;
     344        12109 :   constraint_t found;
     345              : 
     346        12109 :   if (!vec.exists ())
     347              :     return NULL;
     348              : 
     349         9929 :   place = vec.lower_bound (&lookfor, constraint_less);
     350         9929 :   if (place >= vec.length ())
     351              :     return NULL;
     352         4276 :   found = vec[place];
     353         4276 :   if (!constraint_equal (*found, lookfor))
     354         4189 :     return NULL;
     355              :   return found;
     356              : }
     357              : 
     358              : /* Union two constraint vectors, TO and FROM.  Put the result in TO.
     359              :    Returns true of TO set is changed.  */
     360              : 
     361              : static bool
     362     43890174 : constraint_set_union (vec<constraint_t> *to,
     363              :                       vec<constraint_t> *from)
     364              : {
     365     43890174 :   int i;
     366     43890174 :   constraint_t c;
     367     43890174 :   bool any_change = false;
     368              : 
     369     43902283 :   FOR_EACH_VEC_ELT (*from, i, c)
     370              :     {
     371        12109 :       if (constraint_vec_find (*to, *c) == NULL)
     372              :         {
     373        12022 :           unsigned int place = to->lower_bound (c, constraint_less);
     374        12022 :           to->safe_insert (place, c);
     375        12022 :           any_change = true;
     376              :         }
     377              :     }
     378     43890174 :   return any_change;
     379              : }
     380              : 
     381              : /* Expands the solution in SET to all sub-fields of variables included.  */
     382              : 
     383              : static bitmap
     384    136701474 : solution_set_expand (bitmap set, bitmap *expanded)
     385              : {
     386    136701474 :   bitmap_iterator bi;
     387    136701474 :   unsigned j;
     388              : 
     389    136701474 :   if (*expanded)
     390              :     return *expanded;
     391              : 
     392     76466681 :   *expanded = BITMAP_ALLOC (&iteration_obstack);
     393              : 
     394              :   /* In a first pass expand variables, once for each head to avoid
     395              :      quadratic behavior, to include all sub-fields.  */
     396     76466681 :   unsigned prev_head = 0;
     397    261223517 :   EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
     398              :     {
     399    184756836 :       varinfo_t v = get_varinfo (j);
     400    184756836 :       if (v->is_artificial_var
     401     91301187 :           || v->is_full_var)
     402    110034770 :         continue;
     403     74722066 :       if (v->head != prev_head)
     404              :         {
     405     19066930 :           varinfo_t head = get_varinfo (v->head);
     406     19066930 :           unsigned num = 1;
     407    112440049 :           for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
     408              :             {
     409     93373119 :               if (n->id != head->id + num)
     410              :                 {
     411              :                   /* Usually sub variables are adjacent but since we
     412              :                      create pointed-to restrict representatives there
     413              :                      can be gaps as well.  */
     414        15541 :                   bitmap_set_range (*expanded, head->id, num);
     415        15541 :                   head = n;
     416        15541 :                   num = 1;
     417              :                 }
     418              :               else
     419     93357578 :                 num++;
     420              :             }
     421              : 
     422     19066930 :           bitmap_set_range (*expanded, head->id, num);
     423     19066930 :           prev_head = v->head;
     424              :         }
     425              :     }
     426              : 
     427              :   /* And finally set the rest of the bits from SET in an efficient way.  */
     428     76466681 :   bitmap_ior_into (*expanded, set);
     429              : 
     430     76466681 :   return *expanded;
     431              : }
     432              : 
     433              : /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
     434              :    process.  */
     435              : 
     436              : static bool
     437     86063713 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
     438              :                           bitmap *expanded_delta)
     439              : {
     440     86063713 :   bool changed = false;
     441     86063713 :   bitmap_iterator bi;
     442     86063713 :   unsigned int i;
     443              : 
     444              :   /* If the solution of DELTA contains anything it is good enough to transfer
     445              :      this to TO.  */
     446     86063713 :   if (bitmap_bit_p (delta, anything_id))
     447      1193451 :     return bitmap_set_bit (to, anything_id);
     448              : 
     449              :   /* If the offset is unknown we have to expand the solution to
     450              :      all subfields.  */
     451     84870262 :   if (inc == UNKNOWN_OFFSET)
     452              :     {
     453     83896770 :       delta = solution_set_expand (delta, expanded_delta);
     454     83896770 :       changed |= bitmap_ior_into (to, delta);
     455     83896770 :       return changed;
     456              :     }
     457              : 
     458              :   /* For non-zero offset union the offsetted solution into the destination.  */
     459      3360001 :   EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
     460              :     {
     461      2386509 :       varinfo_t vi = get_varinfo (i);
     462              : 
     463              :       /* If this is a variable with just one field just set its bit
     464              :          in the result.  */
     465      2386509 :       if (vi->is_artificial_var
     466      1096771 :           || vi->is_unknown_size_var
     467       953579 :           || vi->is_full_var)
     468      1624730 :         changed |= bitmap_set_bit (to, i);
     469              :       else
     470              :         {
     471       761779 :           HOST_WIDE_INT fieldoffset = vi->offset + inc;
     472       761779 :           unsigned HOST_WIDE_INT size = vi->size;
     473              : 
     474              :           /* If the offset makes the pointer point to before the
     475              :              variable use offset zero for the field lookup.  */
     476       761779 :           if (fieldoffset < 0)
     477        47442 :             vi = get_varinfo (vi->head);
     478              :           else
     479       714337 :             vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
     480              : 
     481      1421952 :           do
     482              :             {
     483      1421952 :               changed |= bitmap_set_bit (to, vi->id);
     484      1421952 :               if (vi->is_full_var
     485      1421912 :                   || vi->next == 0)
     486              :                 break;
     487              : 
     488              :               /* We have to include all fields that overlap the current field
     489              :                  shifted by inc.  */
     490       950284 :               vi = vi_next (vi);
     491              :             }
     492       950284 :           while (vi->offset < fieldoffset + size);
     493              :         }
     494              :     }
     495              : 
     496              :   return changed;
     497              : }
     498              : 
     499              : /* Insert constraint C into the list of complex constraints for graph
     500              :    node VAR.  */
     501              : 
     502              : static void
     503    149605289 : insert_into_complex (constraint_graph_t graph,
     504              :                      unsigned int var, constraint_t c)
     505              : {
     506    149605289 :   vec<constraint_t> complex = graph->complex[var];
     507    149605289 :   unsigned int place = complex.lower_bound (c, constraint_less);
     508              : 
     509              :   /* Only insert constraints that do not already exist.  */
     510    149605289 :   if (place >= complex.length ()
     511    101844293 :       || !constraint_equal (*c, *complex[place]))
     512    148115616 :     graph->complex[var].safe_insert (place, c);
     513    149605289 : }
     514              : 
     515              : 
     516              : /* Condense two variable nodes into a single variable node, by moving
     517              :    all associated info from FROM to TO.  Returns true if TO node's
     518              :    constraint set changes after the merge.  */
     519              : 
     520              : static bool
     521     43890174 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
     522              :                         unsigned int from)
     523              : {
     524     43890174 :   unsigned int i;
     525     43890174 :   constraint_t c;
     526     43890174 :   bool any_change = false;
     527              : 
     528     43890174 :   gcc_checking_assert (find (from) == to);
     529              : 
     530              :   /* Move all complex constraints from src node into to node.  */
     531     43902283 :   FOR_EACH_VEC_ELT (graph->complex[from], i, c)
     532              :     {
     533              :       /* In complex constraints for node FROM, we may have either
     534              :          a = *FROM, and *FROM = a, or an offsetted constraint which are
     535              :          always added to the rhs node's constraints.  */
     536              : 
     537        12109 :       if (c->rhs.type == DEREF)
     538         2919 :         c->rhs.var = to;
     539         9190 :       else if (c->lhs.type == DEREF)
     540         4560 :         c->lhs.var = to;
     541              :       else
     542         4630 :         c->rhs.var = to;
     543              : 
     544              :     }
     545     43890174 :   any_change = constraint_set_union (&graph->complex[to],
     546              :                                      &graph->complex[from]);
     547     43890174 :   graph->complex[from].release ();
     548     43890174 :   return any_change;
     549              : }
     550              : 
     551              : /* Remove edges involving NODE from GRAPH.  */
     552              : 
     553              : static void
     554     64191984 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
     555              : {
     556     64191984 :   if (graph->succs[node])
     557       799632 :     BITMAP_FREE (graph->succs[node]);
     558     64191984 : }
     559              : 
     560              : /* Merge GRAPH nodes FROM and TO into node TO.  Return whether TO
     561              :    received new successor edges.  */
     562              : 
     563              : static bool
     564     43890174 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
     565              :                    unsigned int from)
     566              : {
     567     43890174 :   if (graph->indirect_cycles[from] != -1)
     568              :     {
     569              :       /* If we have indirect cycles with the from node, and we have
     570              :          none on the to node, the to node has indirect cycles from the
     571              :          from node now that they are unified.
     572              :          If indirect cycles exist on both, unify the nodes that they
     573              :          are in a cycle with, since we know they are in a cycle with
     574              :          each other.  */
     575          108 :       if (graph->indirect_cycles[to] == -1)
     576           83 :         graph->indirect_cycles[to] = graph->indirect_cycles[from];
     577              :     }
     578              : 
     579              :   /* Merge all the successor edges.  */
     580     43890174 :   bool new_succs = false;
     581     43890174 :   if (graph->succs[from])
     582              :     {
     583       799632 :       if (!graph->succs[to])
     584       414329 :         graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
     585       799632 :       new_succs = bitmap_ior_into (graph->succs[to],
     586       799632 :                                    graph->succs[from]);
     587              :     }
     588              : 
     589     43890174 :   clear_edges_for_node (graph, from);
     590     43890174 :   return new_succs;
     591              : }
     592              : 
     593              : 
     594              : /* Add an indirect graph edge to GRAPH, going from TO to FROM if
     595              :    it doesn't exist in the graph already.  */
     596              : 
     597              : static void
     598    302224916 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
     599              :                          unsigned int from)
     600              : {
     601    302224916 :   if (to == from)
     602              :     return;
     603              : 
     604    302224916 :   if (!graph->implicit_preds[to])
     605    169232890 :     graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
     606              : 
     607    302224916 :   if (bitmap_set_bit (graph->implicit_preds[to], from))
     608    283901628 :     stats.num_implicit_edges++;
     609              : }
     610              : 
     611              : /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
     612              :    it doesn't exist in the graph already.
     613              :    Return false if the edge already existed, true otherwise.  */
     614              : 
     615              : static void
     616    255181244 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
     617              :                      unsigned int from)
     618              : {
     619    255181244 :   if (!graph->preds[to])
     620    150561964 :     graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
     621    255181244 :   bitmap_set_bit (graph->preds[to], from);
     622    255181244 : }
     623              : 
     624              : /* Add a graph edge to GRAPH, going from FROM to TO if
     625              :    it doesn't exist in the graph already.
     626              :    Return false if the edge already existed, true otherwise.  */
     627              : 
     628              : static bool
     629    701720884 : add_graph_edge (constraint_graph_t graph, unsigned int to,
     630              :                 unsigned int from)
     631              : {
     632    701720884 :   if (to == from)
     633              :     {
     634              :       return false;
     635              :     }
     636              :   else
     637              :     {
     638    701442983 :       bool r = false;
     639              : 
     640    701442983 :       if (!graph->succs[from])
     641    103613527 :         graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
     642              : 
     643              :       /* The graph solving process does not avoid "triangles", thus
     644              :          there can be multiple paths from a node to another involving
     645              :          intermediate other nodes.  That causes extra copying which is
     646              :          most difficult to avoid when the intermediate node is ESCAPED
     647              :          because there are no edges added from ESCAPED.  Avoid
     648              :          adding the direct edge FROM -> TO when we have FROM -> ESCAPED
     649              :          and TO contains ESCAPED.
     650              :          ???  Note this is only a heuristic, it does not prevent the
     651              :          situation from occurring.  The heuristic helps PR38474 and
     652              :          PR99912 significantly.  */
     653    701442983 :       if (to < FIRST_REF_NODE
     654    668762750 :           && bitmap_bit_p (graph->succs[from], find (escaped_id))
     655    938628021 :           && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
     656              :         {
     657    204027214 :           stats.num_avoided_edges++;
     658    204027214 :           return false;
     659              :         }
     660              : 
     661    497415769 :       if (bitmap_set_bit (graph->succs[from], to))
     662              :         {
     663    415561818 :           r = true;
     664    415561818 :           if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
     665    370296188 :             stats.num_edges++;
     666              :         }
     667              :       return r;
     668              :     }
     669              : }
     670              : 
     671              : /* Initialize the constraint graph structure to contain SIZE nodes.  */
     672              : 
     673              : static void
     674      4568954 : init_graph (unsigned int size)
     675              : {
     676      4568954 :   unsigned int j;
     677              : 
     678      4568954 :   bitmap_obstack_initialize (&predbitmap_obstack);
     679              : 
     680      4568954 :   graph = XCNEW (struct constraint_graph);
     681      4568954 :   graph->size = size;
     682      4568954 :   graph->succs = XCNEWVEC (bitmap, graph->size);
     683      4568954 :   graph->indirect_cycles = XNEWVEC (int, graph->size);
     684      4568954 :   graph->rep = XNEWVEC (unsigned int, graph->size);
     685              :   /* ??? Macros do not support template types with multiple arguments,
     686              :      so we use a typedef to work around it.  */
     687      4568954 :   typedef vec<constraint_t> vec_constraint_t_heap;
     688      4568954 :   graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
     689      4568954 :   graph->pe = XCNEWVEC (unsigned int, graph->size);
     690      4568954 :   graph->pe_rep = XNEWVEC (int, graph->size);
     691              : 
     692    472336878 :   for (j = 0; j < graph->size; j++)
     693              :     {
     694    467767924 :       graph->rep[j] = j;
     695    467767924 :       graph->pe_rep[j] = -1;
     696    467767924 :       graph->indirect_cycles[j] = -1;
     697              :     }
     698      4568954 : }
     699              : 
     700              : /* Build the constraint graph, adding only predecessor edges right now.  */
     701              : 
     702              : static void
     703      4568954 : build_pred_graph (void)
     704              : {
     705      4568954 :   int i;
     706      4568954 :   constraint_t c;
     707      4568954 :   unsigned int j;
     708              : 
     709      4568954 :   graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
     710      4568954 :   graph->preds = XCNEWVEC (bitmap, graph->size);
     711      4568954 :   graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
     712      4568954 :   graph->loc_label = XCNEWVEC (unsigned int, graph->size);
     713      4568954 :   graph->pointed_by = XCNEWVEC (bitmap, graph->size);
     714      4568954 :   graph->points_to = XCNEWVEC (bitmap, graph->size);
     715      4568954 :   graph->eq_rep = XNEWVEC (int, graph->size);
     716      4568954 :   graph->direct_nodes = sbitmap_alloc (graph->size);
     717      4568954 :   graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
     718      4568954 :   bitmap_clear (graph->direct_nodes);
     719              : 
     720    472336878 :   for (j = 1; j < FIRST_REF_NODE; j++)
     721              :     {
     722    229315008 :       if (!get_varinfo (j)->is_special_var)
     723    206470238 :         bitmap_set_bit (graph->direct_nodes, j);
     724              :     }
     725              : 
     726    472336878 :   for (j = 0; j < graph->size; j++)
     727    467767924 :     graph->eq_rep[j] = -1;
     728              : 
     729    476905832 :   for (j = 0; j < varmap.length (); j++)
     730    233883962 :     graph->indirect_cycles[j] = -1;
     731              : 
     732    457619970 :   FOR_EACH_VEC_ELT (constraints, i, c)
     733              :     {
     734    453051016 :       struct constraint_expr lhs = c->lhs;
     735    453051016 :       struct constraint_expr rhs = c->rhs;
     736    453051016 :       unsigned int lhsvar = lhs.var;
     737    453051016 :       unsigned int rhsvar = rhs.var;
     738              : 
     739    453051016 :       if (lhs.type == DEREF)
     740              :         {
     741              :           /* *x = y.  */
     742     37208542 :           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
     743              :             {
     744     32700282 :               if (lhs.var == anything_id)
     745            0 :                 add_pred_graph_edge (graph, storedanything_id, rhsvar);
     746              :               else
     747     65400564 :                 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
     748              :             }
     749              :         }
     750    415842474 :       else if (rhs.type == DEREF)
     751              :         {
     752              :           /* x = *y */
     753     50172587 :           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
     754     26945280 :             add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
     755              :           else
     756     36699947 :             bitmap_clear_bit (graph->direct_nodes, lhsvar);
     757              :         }
     758    365669887 :       else if (rhs.type == ADDRESSOF)
     759              :         {
     760     93216594 :           varinfo_t v;
     761              : 
     762              :           /* x = &y */
     763     93216594 :           if (graph->points_to[lhsvar] == NULL)
     764     68902047 :             graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
     765     93216594 :           bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
     766              : 
     767     93216594 :           if (graph->pointed_by[rhsvar] == NULL)
     768     22291507 :             graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
     769     93216594 :           bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
     770              : 
     771              :           /* Implicitly, *x = y */
     772    186433188 :           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
     773              : 
     774              :           /* All related variables are no longer direct nodes.  */
     775     93216594 :           bitmap_clear_bit (graph->direct_nodes, rhsvar);
     776     93216594 :           v = get_varinfo (rhsvar);
     777     93216594 :           if (!v->is_full_var)
     778              :             {
     779      7771879 :               v = get_varinfo (v->head);
     780     50504245 :               do
     781              :                 {
     782     50504245 :                   bitmap_clear_bit (graph->direct_nodes, v->id);
     783     50504245 :                   v = vi_next (v);
     784              :                 }
     785     50504245 :               while (v != NULL);
     786              :             }
     787     93216594 :           bitmap_set_bit (graph->address_taken, rhsvar);
     788              :         }
     789    272453293 :       else if (lhsvar > anything_id
     790    272453293 :                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
     791              :         {
     792              :           /* x = y */
     793    209008322 :           add_pred_graph_edge (graph, lhsvar, rhsvar);
     794              :           /* Implicitly, *x = *y */
     795    209008322 :           add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
     796    209008322 :                                    FIRST_REF_NODE + rhsvar);
     797              :         }
     798     63444971 :       else if (lhs.offset != 0 || rhs.offset != 0)
     799              :         {
     800     63272644 :           if (rhs.offset != 0)
     801     63272644 :             bitmap_clear_bit (graph->direct_nodes, lhs.var);
     802            0 :           else if (lhs.offset != 0)
     803            0 :             bitmap_clear_bit (graph->direct_nodes, rhs.var);
     804              :         }
     805              :     }
     806      4568954 : }
     807              : 
     808              : /* Build the constraint graph, adding successor edges.  */
     809              : 
     810              : static void
     811      4568954 : build_succ_graph (void)
     812              : {
     813      4568954 :   unsigned i, t;
     814      4568954 :   constraint_t c;
     815              : 
     816    457619970 :   FOR_EACH_VEC_ELT (constraints, i, c)
     817              :     {
     818    453051016 :       struct constraint_expr lhs;
     819    453051016 :       struct constraint_expr rhs;
     820    453051016 :       unsigned int lhsvar;
     821    453051016 :       unsigned int rhsvar;
     822              : 
     823    453051016 :       if (!c)
     824      2516795 :         continue;
     825              : 
     826    450534221 :       lhs = c->lhs;
     827    450534221 :       rhs = c->rhs;
     828    450534221 :       lhsvar = find (lhs.var);
     829    450534221 :       rhsvar = find (rhs.var);
     830              : 
     831    450534221 :       if (lhs.type == DEREF)
     832              :         {
     833     37169019 :           if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
     834              :             {
     835     32680233 :               if (lhs.var == anything_id)
     836            0 :                 add_graph_edge (graph, storedanything_id, rhsvar);
     837              :               else
     838     65360466 :                 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
     839              :             }
     840              :         }
     841    413365202 :       else if (rhs.type == DEREF)
     842              :         {
     843     50171657 :           if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
     844     26943806 :             add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
     845              :         }
     846    363193545 :       else if (rhs.type == ADDRESSOF)
     847              :         {
     848              :           /* x = &y */
     849     93216594 :           gcc_checking_assert (find (rhs.var) == rhs.var);
     850     93216594 :           bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
     851              :         }
     852    269976951 :       else if (lhsvar > anything_id
     853    269976951 :                && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
     854              :         {
     855    179287531 :           add_graph_edge (graph, lhsvar, rhsvar);
     856              :         }
     857              :     }
     858              : 
     859              :   /* Add edges from STOREDANYTHING to all nodes that can receive pointers.  */
     860      4568954 :   t = find (storedanything_id);
     861    201901284 :   for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
     862              :     {
     863    192763376 :       if (get_varinfo (i)->may_have_pointers)
     864    192739491 :         add_graph_edge (graph, find (i), t);
     865              :     }
     866              : 
     867              :   /* Everything stored to ANYTHING also potentially escapes.  */
     868      4568954 :   add_graph_edge (graph, find (escaped_id), t);
     869      4568954 : }
     870              : 
     871              : 
     872              : /* Changed variables on the last iteration.  */
     873              : static bitmap changed;
     874              : 
     875              : /* Strongly Connected Component visitation info.  */
     876              : 
     877              : class scc_info
     878              : {
     879              : public:
     880              :   scc_info (size_t size);
     881              :   ~scc_info ();
     882              : 
     883              :   auto_sbitmap visited;
     884              :   auto_sbitmap deleted;
     885              :   unsigned int *dfs;
     886              :   unsigned int *node_mapping;
     887              :   int current_index;
     888              :   auto_vec<unsigned> scc_stack;
     889              : };
     890              : 
     891              : 
     892              : /* Recursive routine to find strongly connected components in GRAPH.
     893              :    SI is the SCC info to store the information in, and N is the id of current
     894              :    graph node we are processing.
     895              : 
     896              :    This is Tarjan's strongly connected component finding algorithm, as
     897              :    modified by Nuutila to keep only non-root nodes on the stack.
     898              :    The algorithm can be found in "On finding the strongly connected
     899              :    connected components in a directed graph" by Esko Nuutila and Eljas
     900              :    Soisalon-Soininen, in Information Processing Letters volume 49,
     901              :    number 1, pages 9-14.  */
     902              : 
     903              : static void
     904    420343679 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
     905              : {
     906    420343679 :   unsigned int i;
     907    420343679 :   bitmap_iterator bi;
     908    420343679 :   unsigned int my_dfs;
     909              : 
     910    420343679 :   bitmap_set_bit (si->visited, n);
     911    420343679 :   si->dfs[n] = si->current_index ++;
     912    420343679 :   my_dfs = si->dfs[n];
     913              : 
     914              :   /* Visit all the successors.  */
     915    776071727 :   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
     916              :     {
     917    355728048 :       unsigned int w;
     918              : 
     919    711456096 :       if (i > LAST_REF_NODE)
     920              :         break;
     921              : 
     922    355728048 :       w = find (i);
     923    355728048 :       if (bitmap_bit_p (si->deleted, w))
     924    172930573 :         continue;
     925              : 
     926    182797475 :       if (!bitmap_bit_p (si->visited, w))
     927    181856751 :         scc_visit (graph, si, w);
     928              : 
     929    182797475 :       unsigned int t = find (w);
     930    182797475 :       gcc_checking_assert (find (n) == n);
     931    182797475 :       if (si->dfs[t] < si->dfs[n])
     932       635776 :         si->dfs[n] = si->dfs[t];
     933              :     }
     934              : 
     935              :   /* See if any components have been identified.  */
     936    420343679 :   if (si->dfs[n] == my_dfs)
     937              :     {
     938    419710097 :       if (si->scc_stack.length () > 0
     939    419710097 :           && si->dfs[si->scc_stack.last ()] >= my_dfs)
     940              :         {
     941       189537 :           bitmap scc = BITMAP_ALLOC (NULL);
     942       189537 :           unsigned int lowest_node;
     943       189537 :           bitmap_iterator bi;
     944              : 
     945       189537 :           bitmap_set_bit (scc, n);
     946              : 
     947       189537 :           while (si->scc_stack.length () != 0
     948       594982 :                  && si->dfs[si->scc_stack.last ()] >= my_dfs)
     949              :             {
     950       405445 :               unsigned int w = si->scc_stack.pop ();
     951              : 
     952       405445 :               bitmap_set_bit (scc, w);
     953              :             }
     954              : 
     955       189537 :           lowest_node = bitmap_first_set_bit (scc);
     956       189537 :           gcc_assert (lowest_node < FIRST_REF_NODE);
     957              : 
     958              :           /* Collapse the SCC nodes into a single node, and mark the
     959              :              indirect cycles.  */
     960       784519 :           EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
     961              :             {
     962       594982 :               if (i < FIRST_REF_NODE)
     963              :                 {
     964       474239 :                   if (unite (lowest_node, i))
     965        14237 :                     unify_nodes (graph, lowest_node, i, false);
     966              :                 }
     967              :               else
     968              :                 {
     969       120743 :                   if (unite (lowest_node, i))
     970       241486 :                     graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
     971              :                 }
     972              :             }
     973       189537 :           bitmap_set_bit (si->deleted, lowest_node);
     974              :         }
     975              :       else
     976    419520560 :         bitmap_set_bit (si->deleted, n);
     977              :     }
     978              :   else
     979       633582 :     si->scc_stack.safe_push (n);
     980    420343679 : }
     981              : 
     982              : /* Unify node FROM into node TO, updating the changed count if
     983              :    necessary when UPDATE_CHANGED is true.  */
     984              : 
     985              : static void
     986     43890174 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
     987              :              bool update_changed)
     988              : {
     989     43890174 :   gcc_checking_assert (to != from && find (to) == to);
     990              : 
     991     43890174 :   if (dump_file && (dump_flags & TDF_DETAILS))
     992          573 :     fprintf (dump_file, "Unifying %s to %s\n",
     993          573 :              get_varinfo (from)->name,
     994          573 :              get_varinfo (to)->name);
     995              : 
     996     43890174 :   if (update_changed)
     997        60180 :     stats.unified_vars_dynamic++;
     998              :   else
     999     43829994 :     stats.unified_vars_static++;
    1000              : 
    1001     43890174 :   varinfo_t tovi = get_varinfo (to);
    1002     43890174 :   if (merge_graph_nodes (graph, to, from))
    1003              :     {
    1004              :       /* If from brings new successors and the TO solution is not a
    1005              :          subset of FROM we have to forward the TO solution along these
    1006              :          edges.  */
    1007       757683 :       if (update_changed)
    1008        17270 :         bitmap_set_bit (changed, to);
    1009              :     }
    1010     43890174 :   if (merge_node_constraints (graph, to, from))
    1011              :     {
    1012         3815 :       if (update_changed)
    1013         1268 :         bitmap_set_bit (changed, to);
    1014              :     }
    1015              : 
    1016              :   /* Mark TO as changed if FROM was changed.  If TO was already marked
    1017              :      as changed, decrease the changed count.  */
    1018              : 
    1019     43887627 :   if (update_changed
    1020     43887627 :       && bitmap_clear_bit (changed, from))
    1021        22711 :     bitmap_set_bit (changed, to);
    1022     43890174 :   varinfo_t fromvi = get_varinfo (from);
    1023     43890174 :   if (fromvi->solution)
    1024              :     {
    1025              :       /* If the solution changes because of the merging, we need to mark
    1026              :          the variable as changed.  */
    1027     43890174 :       if (bitmap_ior_into (tovi->solution, fromvi->solution))
    1028              :         {
    1029       377219 :           if (update_changed)
    1030         9338 :             bitmap_set_bit (changed, to);
    1031              :         }
    1032              : 
    1033     43890174 :       BITMAP_FREE (fromvi->solution);
    1034     43890174 :       if (fromvi->oldsolution)
    1035        40154 :         BITMAP_FREE (fromvi->oldsolution);
    1036              : 
    1037     43890174 :       if (stats.iterations > 0
    1038        60180 :           && tovi->oldsolution)
    1039         4938 :         BITMAP_FREE (tovi->oldsolution);
    1040              :     }
    1041     43890174 :   if (graph->succs[to])
    1042       865032 :     bitmap_clear_bit (graph->succs[to], to);
    1043     43890174 : }
    1044              : 
    1045              : /* Add a copy edge FROM -> TO, optimizing special cases.  Returns TRUE
    1046              :    if the solution of TO changed.  */
    1047              : 
    1048              : static bool
    1049    328579558 : solve_add_graph_edge (constraint_graph_t graph, unsigned int to,
    1050              :                       unsigned int from)
    1051              : {
    1052              :   /* Adding edges from the special vars is pointless.
    1053              :      They don't have sets that can change.  */
    1054    328579558 :   if (get_varinfo (from)->is_special_var)
    1055     63164432 :     return bitmap_ior_into (get_varinfo (to)->solution,
    1056    126328864 :                             get_varinfo (from)->solution);
    1057              :   /* Merging the solution from ESCAPED needlessly increases
    1058              :      the set.  Use ESCAPED as representative instead.  */
    1059    265415126 :   else if (from == find (escaped_id))
    1060     30632170 :     return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
    1061    234782956 :   else if (get_varinfo (from)->may_have_pointers
    1062    234782956 :            && add_graph_edge (graph, to, from))
    1063     85549342 :     return bitmap_ior_into (get_varinfo (to)->solution,
    1064     85549342 :                             get_varinfo (from)->solution);
    1065              :   return false;
    1066              : }
    1067              : 
    1068              : /* Process a constraint C that represents x = *(y + off), using DELTA as the
    1069              :    starting solution for y.  */
    1070              : 
    1071              : static void
    1072     69950866 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
    1073              :                   bitmap delta, bitmap *expanded_delta)
    1074              : {
    1075     69950866 :   unsigned int lhs = c->lhs.var;
    1076     69950866 :   bool flag = false;
    1077     69950866 :   bitmap sol = get_varinfo (lhs)->solution;
    1078     69950866 :   unsigned int j;
    1079     69950866 :   bitmap_iterator bi;
    1080     69950866 :   HOST_WIDE_INT roffset = c->rhs.offset;
    1081              : 
    1082              :   /* Our IL does not allow this.  */
    1083     69950866 :   gcc_checking_assert (c->lhs.offset == 0);
    1084              : 
    1085              :   /* If the solution of Y contains anything it is good enough to transfer
    1086              :      this to the LHS.  */
    1087     69950866 :   if (bitmap_bit_p (delta, anything_id))
    1088              :     {
    1089       565963 :       flag |= bitmap_set_bit (sol, anything_id);
    1090       565963 :       goto done;
    1091              :     }
    1092              : 
    1093              :   /* If we do not know at with offset the rhs is dereferenced compute
    1094              :      the reachability set of DELTA, conservatively assuming it is
    1095              :      dereferenced at all valid offsets.  */
    1096     69384903 :   if (roffset == UNKNOWN_OFFSET)
    1097              :     {
    1098     51104806 :       delta = solution_set_expand (delta, expanded_delta);
    1099              :       /* No further offset processing is necessary.  */
    1100     51104806 :       roffset = 0;
    1101              :     }
    1102              : 
    1103              :   /* For each variable j in delta (Sol(y)), add
    1104              :      an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
    1105    275069798 :   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
    1106              :     {
    1107    205684895 :       varinfo_t v = get_varinfo (j);
    1108    205684895 :       HOST_WIDE_INT fieldoffset = v->offset + roffset;
    1109    205684895 :       unsigned HOST_WIDE_INT size = v->size;
    1110    205684895 :       unsigned int t;
    1111              : 
    1112    205684895 :       if (v->is_full_var)
    1113              :         ;
    1114    109704122 :       else if (roffset != 0)
    1115              :         {
    1116      3555196 :           if (fieldoffset < 0)
    1117        32255 :             v = get_varinfo (v->head);
    1118              :           else
    1119      3522941 :             v = first_or_preceding_vi_for_offset (v, fieldoffset);
    1120              :         }
    1121              : 
    1122              :       /* We have to include all fields that overlap the current field
    1123              :          shifted by roffset.  */
    1124    206351199 :       do
    1125              :         {
    1126    206351199 :           t = find (v->id);
    1127              : 
    1128    206351199 :           flag |= solve_add_graph_edge (graph, lhs, t);
    1129              : 
    1130    206351199 :           if (v->is_full_var
    1131    110370231 :               || v->next == 0)
    1132              :             break;
    1133              : 
    1134     90250254 :           v = vi_next (v);
    1135              :         }
    1136     90250254 :       while (v->offset < fieldoffset + size);
    1137              :     }
    1138              : 
    1139     69384903 : done:
    1140              :   /* If the LHS solution changed, mark the var as changed.  */
    1141     69950866 :   if (flag)
    1142     29444159 :     bitmap_set_bit (changed, lhs);
    1143     69950866 : }
    1144              : 
    1145              : /* Process a constraint C that represents *(x + off) = y using DELTA
    1146              :    as the starting solution for x.  */
    1147              : 
    1148              : static void
    1149     55935449 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
    1150              : {
    1151     55935449 :   unsigned int rhs = c->rhs.var;
    1152     55935449 :   bitmap sol = get_varinfo (rhs)->solution;
    1153     55935449 :   unsigned int j;
    1154     55935449 :   bitmap_iterator bi;
    1155     55935449 :   HOST_WIDE_INT loff = c->lhs.offset;
    1156     55935449 :   bool escaped_p = false;
    1157              : 
    1158              :   /* Our IL does not allow this.  */
    1159     55935449 :   gcc_checking_assert (c->rhs.offset == 0);
    1160              : 
    1161              :   /* If the solution of y contains ANYTHING simply use the ANYTHING
    1162              :      solution.  This avoids needlessly increasing the points-to sets.  */
    1163     55935449 :   if (bitmap_bit_p (sol, anything_id))
    1164       397625 :     sol = get_varinfo (find (anything_id))->solution;
    1165              : 
    1166              :   /* If the solution for x contains ANYTHING we have to merge the
    1167              :      solution of y into all pointer variables which we do via
    1168              :      STOREDANYTHING.  */
    1169     55935449 :   if (bitmap_bit_p (delta, anything_id))
    1170              :     {
    1171       447878 :       unsigned t = find (storedanything_id);
    1172       447878 :       if (solve_add_graph_edge (graph, t, rhs))
    1173        36033 :         bitmap_set_bit (changed, t);
    1174       447878 :       return;
    1175              :     }
    1176              : 
    1177              :   /* If we do not know at with offset the rhs is dereferenced compute
    1178              :      the reachability set of DELTA, conservatively assuming it is
    1179              :      dereferenced at all valid offsets.  */
    1180     55487571 :   if (loff == UNKNOWN_OFFSET)
    1181              :     {
    1182      1699898 :       delta = solution_set_expand (delta, expanded_delta);
    1183      1699898 :       loff = 0;
    1184              :     }
    1185              : 
    1186              :   /* For each member j of delta (Sol(x)), add an edge from y to j and
    1187              :      union Sol(y) into Sol(j) */
    1188    214851088 :   EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
    1189              :     {
    1190    159363517 :       varinfo_t v = get_varinfo (j);
    1191    159363517 :       unsigned int t;
    1192    159363517 :       HOST_WIDE_INT fieldoffset = v->offset + loff;
    1193    159363517 :       unsigned HOST_WIDE_INT size = v->size;
    1194              : 
    1195    159363517 :       if (v->is_full_var)
    1196              :         ;
    1197     80092570 :       else if (loff != 0)
    1198              :         {
    1199      5226741 :           if (fieldoffset < 0)
    1200         6308 :             v = get_varinfo (v->head);
    1201              :           else
    1202      5220433 :             v = first_or_preceding_vi_for_offset (v, fieldoffset);
    1203              :         }
    1204              : 
    1205              :       /* We have to include all fields that overlap the current field
    1206              :          shifted by loff.  */
    1207    161258988 :       do
    1208              :         {
    1209    161258988 :           if (v->may_have_pointers)
    1210              :             {
    1211              :               /* If v is a global variable then this is an escape point.  */
    1212    149820710 :               if (v->is_global_var
    1213    115318850 :                   && !escaped_p)
    1214              :                 {
    1215     44190217 :                   t = find (escaped_id);
    1216     44190217 :                   if (add_graph_edge (graph, t, rhs)
    1217     60504420 :                       && bitmap_ior_into (get_varinfo (t)->solution, sol))
    1218      1310552 :                     bitmap_set_bit (changed, t);
    1219              :                   /* Enough to let rhs escape once.  */
    1220              :                   escaped_p = true;
    1221              :                 }
    1222              : 
    1223    149820710 :               if (v->is_special_var)
    1224              :                 break;
    1225              : 
    1226    121780481 :               t = find (v->id);
    1227              : 
    1228    121780481 :               if (solve_add_graph_edge (graph, t, rhs))
    1229     12629534 :                 bitmap_set_bit (changed, t);
    1230              :             }
    1231              : 
    1232    133218759 :           if (v->is_full_var
    1233     81987896 :               || v->next == 0)
    1234              :             break;
    1235              : 
    1236     66655578 :           v = vi_next (v);
    1237              :         }
    1238     66655578 :       while (v->offset < fieldoffset + size);
    1239              :     }
    1240              : }
    1241              : 
    1242              : /* Handle a non-simple (simple meaning requires no iteration),
    1243              :    constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved).  */
    1244              : 
    1245              : static void
    1246    211950083 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
    1247              :                        bitmap *expanded_delta)
    1248              : {
    1249    211950083 :   if (c->lhs.type == DEREF)
    1250              :     {
    1251     55935449 :       if (c->rhs.type == ADDRESSOF)
    1252              :         {
    1253            0 :           gcc_unreachable ();
    1254              :         }
    1255              :       else
    1256              :         {
    1257              :           /* *x = y */
    1258     55935449 :           do_ds_constraint (c, delta, expanded_delta);
    1259              :         }
    1260              :     }
    1261    156014634 :   else if (c->rhs.type == DEREF)
    1262              :     {
    1263              :       /* x = *y */
    1264     69950921 :       if (!(get_varinfo (c->lhs.var)->is_special_var))
    1265     69950866 :         do_sd_constraint (graph, c, delta, expanded_delta);
    1266              :     }
    1267              :   else
    1268              :     {
    1269     86063713 :       bitmap tmp;
    1270     86063713 :       bool flag = false;
    1271              : 
    1272     86063713 :       gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
    1273              :                            && c->rhs.offset != 0 && c->lhs.offset == 0);
    1274     86063713 :       tmp = get_varinfo (c->lhs.var)->solution;
    1275              : 
    1276     86063713 :       flag = set_union_with_increment (tmp, delta, c->rhs.offset,
    1277              :                                        expanded_delta);
    1278              : 
    1279     86063713 :       if (flag)
    1280     21839470 :         bitmap_set_bit (changed, c->lhs.var);
    1281              :     }
    1282    211950083 : }
    1283              : 
    1284              : /* Initialize and return a new SCC info structure.  */
    1285              : 
    1286      9137908 : scc_info::scc_info (size_t size) :
    1287      9137908 :   visited (size), deleted (size), current_index (0), scc_stack (1)
    1288              : {
    1289      9137908 :   bitmap_clear (visited);
    1290      9137908 :   bitmap_clear (deleted);
    1291      9137908 :   node_mapping = XNEWVEC (unsigned int, size);
    1292      9137908 :   dfs = XCNEWVEC (unsigned int, size);
    1293              : 
    1294    944673756 :   for (size_t i = 0; i < size; i++)
    1295    935535848 :     node_mapping[i] = i;
    1296      9137908 : }
    1297              : 
    1298              : /* Free an SCC info structure pointed to by SI.  */
    1299              : 
    1300      9137908 : scc_info::~scc_info ()
    1301              : {
    1302      9137908 :   free (node_mapping);
    1303      9137908 :   free (dfs);
    1304      9137908 : }
    1305              : 
    1306              : 
    1307              : /* Find indirect cycles in GRAPH that occur, using strongly connected
    1308              :    components, and note them in the indirect cycles map.
    1309              : 
    1310              :    This technique comes from Ben Hardekopf and Calvin Lin,
    1311              :    "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
    1312              :    Lines of Code", submitted to PLDI 2007.  */
    1313              : 
    1314              : static void
    1315      4568954 : find_indirect_cycles (constraint_graph_t graph)
    1316              : {
    1317      4568954 :   unsigned int i;
    1318      4568954 :   unsigned int size = graph->size;
    1319      4568954 :   scc_info si (size);
    1320              : 
    1321    940104802 :   for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
    1322    463198970 :     if (!bitmap_bit_p (si.visited, i) && find (i) == i)
    1323    238486928 :       scc_visit (graph, &si, i);
    1324      4568954 : }
    1325              : 
    1326              : /* Visit the graph in topological order starting at node N, and store the
    1327              :    order in TOPO_ORDER using VISITED to indicate visited nodes.  */
    1328              : 
    1329              : static void
    1330    461996715 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
    1331              :             sbitmap visited, unsigned int n)
    1332              : {
    1333    461996715 :   bitmap_iterator bi;
    1334    461996715 :   unsigned int j;
    1335              : 
    1336    461996715 :   bitmap_set_bit (visited, n);
    1337              : 
    1338    461996715 :   if (graph->succs[n])
    1339   1121648838 :     EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
    1340              :       {
    1341    905756506 :         unsigned k = find (j);
    1342    905756506 :         if (!bitmap_bit_p (visited, k))
    1343    351159542 :           topo_visit (graph, topo_order, visited, k);
    1344              :       }
    1345              : 
    1346              :   /* Also consider copy with offset complex constraints as implicit edges.  */
    1347    908965432 :   for (auto c : graph->complex[n])
    1348              :     {
    1349              :       /* Constraints are ordered so that SCALAR = SCALAR appear first.  */
    1350    258844161 :       if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
    1351              :         break;
    1352    145359399 :       gcc_checking_assert (c->rhs.var == n);
    1353    145359399 :       unsigned k = find (c->lhs.var);
    1354    145359399 :       if (!bitmap_bit_p (visited, k))
    1355     38876625 :         topo_visit (graph, topo_order, visited, k);
    1356              :     }
    1357              : 
    1358    461996715 :   topo_order.quick_push (n);
    1359    461996715 : }
    1360              : 
    1361              : /* Compute a topological ordering for GRAPH, and return the result.  */
    1362              : 
    1363              : static auto_vec<unsigned>
    1364      8129517 : compute_topo_order (constraint_graph_t graph)
    1365              : {
    1366      8129517 :   unsigned int i;
    1367      8129517 :   unsigned int size = graph->size;
    1368              : 
    1369      8129517 :   auto_sbitmap visited (size);
    1370      8129517 :   bitmap_clear (visited);
    1371              : 
    1372              :   /* For the heuristic in add_graph_edge to work optimally make sure to
    1373              :      first visit the connected component of the graph containing
    1374              :      ESCAPED.  Do this by extracting the connected component
    1375              :      with ESCAPED and append that to all other components as solve_graph
    1376              :      pops from the order.  */
    1377      8129517 :   auto_vec<unsigned> tail (size);
    1378      8129517 :   topo_visit (graph, tail, visited, find (escaped_id));
    1379              : 
    1380      8129517 :   auto_vec<unsigned> topo_order (size);
    1381              : 
    1382    589613880 :   for (i = 0; i != size; ++i)
    1383    573354846 :     if (!bitmap_bit_p (visited, i) && find (i) == i)
    1384     63831031 :       topo_visit (graph, topo_order, visited, i);
    1385              : 
    1386      8129517 :   topo_order.splice (tail);
    1387      8129517 :   return topo_order;
    1388      8129517 : }
    1389              : 
    1390              : /* Structure used to for hash value numbering of pointer equivalence
    1391              :    classes.  */
    1392              : 
    1393              : typedef struct equiv_class_label
    1394              : {
    1395              :   hashval_t hashcode;
    1396              :   unsigned int equivalence_class;
    1397              :   bitmap labels;
    1398              : } *equiv_class_label_t;
    1399              : typedef const struct equiv_class_label *const_equiv_class_label_t;
    1400              : 
    1401              : /* Equiv_class_label hashtable helpers.  */
    1402              : 
    1403              : struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label>
    1404              : {
    1405              :   static inline hashval_t hash (const equiv_class_label *);
    1406              :   static inline bool equal (const equiv_class_label *,
    1407              :                             const equiv_class_label *);
    1408              : };
    1409              : 
    1410              : /* A hashtable for mapping a bitmap of labels->pointer equivalence
    1411              :    classes.  */
    1412              : static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
    1413              : 
    1414              : /* A hashtable for mapping a bitmap of labels->location equivalence
    1415              :    classes.  */
    1416              : static hash_table<equiv_class_hasher> *location_equiv_class_table;
    1417              : 
    1418              : /* Hash function for a equiv_class_label_t.  */
    1419              : 
    1420              : inline hashval_t
    1421    194211308 : equiv_class_hasher::hash (const equiv_class_label *ecl)
    1422              : {
    1423    194211308 :   return ecl->hashcode;
    1424              : }
    1425              : 
    1426              : /* Equality function for two equiv_class_label_t's.  */
    1427              : 
    1428              : inline bool
    1429    251556898 : equiv_class_hasher::equal (const equiv_class_label *eql1,
    1430              :                            const equiv_class_label *eql2)
    1431              : {
    1432    251556898 :   return (eql1->hashcode == eql2->hashcode
    1433    251556898 :           && bitmap_equal_p (eql1->labels, eql2->labels));
    1434              : }
    1435              : 
    1436              : struct obstack equiv_class_obstack;
    1437              : 
    1438              : /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
    1439              :    hash HAS it contains.  Sets *REF_LABELS to the bitmap LABELS
    1440              :    is equivalent to.  */
    1441              : 
    1442              : static equiv_class_label *
    1443    199825081 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
    1444              :                            bitmap labels)
    1445              : {
    1446    199825081 :   equiv_class_label **slot;
    1447    199825081 :   equiv_class_label ecl;
    1448              : 
    1449    199825081 :   ecl.labels = labels;
    1450    199825081 :   ecl.hashcode = bitmap_hash (labels);
    1451    199825081 :   slot = table->find_slot (&ecl, INSERT);
    1452    199825081 :   if (!*slot)
    1453              :     {
    1454    167249470 :       *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
    1455    167249470 :       (*slot)->labels = labels;
    1456    167249470 :       (*slot)->hashcode = ecl.hashcode;
    1457    167249470 :       (*slot)->equivalence_class = 0;
    1458              :     }
    1459              : 
    1460    199825081 :   return *slot;
    1461              : }
    1462              : 
    1463              : 
    1464              : /* Perform offline variable substitution.
    1465              : 
    1466              :    This is a worst case quadratic time way of identifying variables
    1467              :    that must have equivalent points-to sets, including those caused by
    1468              :    static cycles, and single entry subgraphs, in the constraint graph.
    1469              : 
    1470              :    The technique is described in "Exploiting Pointer and Location
    1471              :    Equivalence to Optimize Pointer Analysis.  In the 14th International
    1472              :    Static Analysis Symposium (SAS), August 2007."  It is known as the
    1473              :    "HU" algorithm, and is equivalent to value numbering the collapsed
    1474              :    constraint graph including evaluating unions.
    1475              : 
    1476              :    The general method of finding equivalence classes is as follows:
    1477              :    Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
    1478              :    Initialize all non-REF nodes to be direct nodes.
    1479              :    For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
    1480              :    variable}
    1481              :    For each constraint containing the dereference, we also do the same
    1482              :    thing.
    1483              : 
    1484              :    We then compute SCC's in the graph and unify nodes in the same SCC,
    1485              :    including pts sets.
    1486              : 
    1487              :    For each non-collapsed node x:
    1488              :     Visit all unvisited explicit incoming edges.
    1489              :     Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
    1490              :     where y->x.
    1491              :     Lookup the equivalence class for pts(x).
    1492              :      If we found one, equivalence_class(x) = found class.
    1493              :      Otherwise, equivalence_class(x) = new class, and new_class is
    1494              :     added to the lookup table.
    1495              : 
    1496              :    All direct nodes with the same equivalence class can be replaced
    1497              :    with a single representative node.
    1498              :    All unlabeled nodes (label == 0) are not pointers and all edges
    1499              :    involving them can be eliminated.
    1500              :    We perform these optimizations during rewrite_constraints
    1501              : 
    1502              :    In addition to pointer equivalence class finding, we also perform
    1503              :    location equivalence class finding.  This is the set of variables
    1504              :    that always appear together in points-to sets.  We use this to
    1505              :    compress the size of the points-to sets.  */
    1506              : 
    1507              : /* Current maximum pointer equivalence class id.  */
    1508              : static int pointer_equiv_class;
    1509              : 
    1510              : /* Current maximum location equivalence class id.  */
    1511              : static int location_equiv_class;
    1512              : 
    1513              : /* Recursive routine to find strongly connected components in GRAPH,
    1514              :    and label it's nodes with DFS numbers.  */
    1515              : 
    1516              : static void
    1517    273363783 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
    1518              : {
    1519    273363783 :   unsigned int i;
    1520    273363783 :   bitmap_iterator bi;
    1521    273363783 :   unsigned int my_dfs;
    1522              : 
    1523    273363783 :   gcc_checking_assert (si->node_mapping[n] == n);
    1524    273363783 :   bitmap_set_bit (si->visited, n);
    1525    273363783 :   si->dfs[n] = si->current_index ++;
    1526    273363783 :   my_dfs = si->dfs[n];
    1527              : 
    1528              :   /* Visit all the successors.  */
    1529    502567777 :   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
    1530              :     {
    1531    229203994 :       unsigned int w = si->node_mapping[i];
    1532              : 
    1533    229203994 :       if (bitmap_bit_p (si->deleted, w))
    1534    145585148 :         continue;
    1535              : 
    1536     83618846 :       if (!bitmap_bit_p (si->visited, w))
    1537     82131745 :         condense_visit (graph, si, w);
    1538              : 
    1539     83618846 :       unsigned int t = si->node_mapping[w];
    1540     83618846 :       gcc_checking_assert (si->node_mapping[n] == n);
    1541     83618846 :       if (si->dfs[t] < si->dfs[n])
    1542      2640083 :         si->dfs[n] = si->dfs[t];
    1543              :     }
    1544              : 
    1545              :   /* Visit all the implicit predecessors.  */
    1546    333092385 :   EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
    1547              :     {
    1548     59728602 :       unsigned int w = si->node_mapping[i];
    1549              : 
    1550     59728602 :       if (bitmap_bit_p (si->deleted, w))
    1551     19733605 :         continue;
    1552              : 
    1553     39994997 :       if (!bitmap_bit_p (si->visited, w))
    1554     35035118 :         condense_visit (graph, si, w);
    1555              : 
    1556     39994997 :       unsigned int t = si->node_mapping[w];
    1557     39994997 :       gcc_assert (si->node_mapping[n] == n);
    1558     39994997 :       if (si->dfs[t] < si->dfs[n])
    1559      8445570 :         si->dfs[n] = si->dfs[t];
    1560              :     }
    1561              : 
    1562              :   /* See if any components have been identified.  */
    1563    273363783 :   if (si->dfs[n] == my_dfs)
    1564              :     {
    1565    262445380 :       if (si->scc_stack.length () != 0
    1566    262445380 :           && si->dfs[si->scc_stack.last ()] >= my_dfs)
    1567              :         {
    1568              :           /* Find the first node of the SCC and do non-bitmap work.  */
    1569     10918403 :           bool direct_p = true;
    1570     10918403 :           unsigned first = si->scc_stack.length ();
    1571     10918403 :           do
    1572              :             {
    1573     10918403 :               --first;
    1574     10918403 :               unsigned int w = si->scc_stack[first];
    1575     10918403 :               si->node_mapping[w] = n;
    1576     10918403 :               if (!bitmap_bit_p (graph->direct_nodes, w))
    1577      8802997 :                 direct_p = false;
    1578              :             }
    1579              :           while (first > 0
    1580     12305755 :                  && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
    1581      1387352 :           if (!direct_p)
    1582       872996 :             bitmap_clear_bit (graph->direct_nodes, n);
    1583              : 
    1584              :           /* Want to reduce to node n, push that first.  */
    1585      1387352 :           si->scc_stack.reserve (1);
    1586      1387352 :           si->scc_stack.quick_push (si->scc_stack[first]);
    1587      1387352 :           si->scc_stack[first] = n;
    1588              : 
    1589      1387352 :           unsigned scc_size = si->scc_stack.length () - first;
    1590      1387352 :           unsigned split = scc_size / 2;
    1591      1387352 :           unsigned carry = scc_size - split * 2;
    1592      4848672 :           while (split > 0)
    1593              :             {
    1594     14379723 :               for (unsigned i = 0; i < split; ++i)
    1595              :                 {
    1596     10918403 :                   unsigned a = si->scc_stack[first + i];
    1597     10918403 :                   unsigned b = si->scc_stack[first + split + carry + i];
    1598              : 
    1599              :                   /* Unify our nodes.  */
    1600     10918403 :                   if (graph->preds[b])
    1601              :                     {
    1602      4786829 :                       if (!graph->preds[a])
    1603       997232 :                         std::swap (graph->preds[a], graph->preds[b]);
    1604              :                       else
    1605      3789597 :                         bitmap_ior_into_and_free (graph->preds[a],
    1606              :                                                   &graph->preds[b]);
    1607              :                     }
    1608     10918403 :                   if (graph->implicit_preds[b])
    1609              :                     {
    1610      8702346 :                       if (!graph->implicit_preds[a])
    1611       877707 :                         std::swap (graph->implicit_preds[a],
    1612              :                                    graph->implicit_preds[b]);
    1613              :                       else
    1614      7824639 :                         bitmap_ior_into_and_free (graph->implicit_preds[a],
    1615              :                                                   &graph->implicit_preds[b]);
    1616              :                     }
    1617     10918403 :                   if (graph->points_to[b])
    1618              :                     {
    1619       530316 :                       if (!graph->points_to[a])
    1620       235518 :                         std::swap (graph->points_to[a], graph->points_to[b]);
    1621              :                       else
    1622       294798 :                         bitmap_ior_into_and_free (graph->points_to[a],
    1623              :                                                   &graph->points_to[b]);
    1624              :                     }
    1625              :                 }
    1626      3461320 :               unsigned remain = split + carry;
    1627      3461320 :               split = remain / 2;
    1628      3461320 :               carry = remain - split * 2;
    1629              :             }
    1630              :           /* Actually pop the SCC.  */
    1631      1387352 :           si->scc_stack.truncate (first);
    1632              :         }
    1633    262445380 :       bitmap_set_bit (si->deleted, n);
    1634              :     }
    1635              :   else
    1636     10918403 :     si->scc_stack.safe_push (n);
    1637    273363783 : }
    1638              : 
    1639              : /* Label pointer equivalences.
    1640              : 
    1641              :    This performs a value numbering of the constraint graph to
    1642              :    discover which variables will always have the same points-to sets
    1643              :    under the current set of constraints.
    1644              : 
    1645              :    The way it value numbers is to store the set of points-to bits
    1646              :    generated by the constraints and graph edges.  This is just used as a
    1647              :    hash and equality comparison.  The *actual set of points-to bits* is
    1648              :    completely irrelevant, in that we don't care about being able to
    1649              :    extract them later.
    1650              : 
    1651              :    The equality values (currently bitmaps) just have to satisfy a few
    1652              :    constraints, the main ones being:
    1653              :    1. The combining operation must be order independent.
    1654              :    2. The end result of a given set of operations must be unique iff the
    1655              :       combination of input values is unique
    1656              :    3. Hashable.  */
    1657              : 
    1658              : static void
    1659    238762835 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
    1660              : {
    1661    238762835 :   unsigned int i, first_pred;
    1662    238762835 :   bitmap_iterator bi;
    1663              : 
    1664    238762835 :   bitmap_set_bit (si->visited, n);
    1665              : 
    1666              :   /* Label and union our incoming edges's points to sets.  */
    1667    238762835 :   first_pred = -1U;
    1668    462635369 :   EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
    1669              :     {
    1670    223872534 :       unsigned int w = si->node_mapping[i];
    1671    223872534 :       if (!bitmap_bit_p (si->visited, w))
    1672     77401785 :         label_visit (graph, si, w);
    1673              : 
    1674              :       /* Skip unused edges.  */
    1675    223872534 :       if (w == n || graph->pointer_label[w] == 0)
    1676      5244427 :         continue;
    1677              : 
    1678    218628107 :       if (graph->points_to[w])
    1679              :         {
    1680    218628107 :           if (!graph->points_to[n])
    1681              :             {
    1682    152483109 :               if (first_pred == -1U)
    1683              :                 first_pred = w;
    1684              :               else
    1685              :                 {
    1686     42282805 :                   graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
    1687     42282805 :                   bitmap_ior (graph->points_to[n],
    1688     42282805 :                               graph->points_to[first_pred],
    1689     42282805 :                               graph->points_to[w]);
    1690              :                 }
    1691              :             }
    1692              :           else
    1693     66144998 :             bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
    1694              :         }
    1695              :     }
    1696              : 
    1697              :   /* Indirect nodes get fresh variables and a new pointer equiv class.  */
    1698    238762835 :   if (!bitmap_bit_p (graph->direct_nodes, n))
    1699              :     {
    1700    115636590 :       if (!graph->points_to[n])
    1701              :         {
    1702     66643520 :           graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
    1703     66643520 :           if (first_pred != -1U)
    1704     26988533 :             bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
    1705              :         }
    1706    231273180 :       bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
    1707    115636590 :       graph->pointer_label[n] = pointer_equiv_class++;
    1708    115636590 :       equiv_class_label_t ecl;
    1709    231273180 :       ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
    1710    115636590 :                                        graph->points_to[n]);
    1711    115636590 :       ecl->equivalence_class = graph->pointer_label[n];
    1712    176865851 :       return;
    1713              :     }
    1714              : 
    1715              :   /* If there was only a single non-empty predecessor the pointer equiv
    1716              :      class is the same.  */
    1717    123126245 :   if (!graph->points_to[n])
    1718              :     {
    1719     61229261 :       if (first_pred != -1U)
    1720              :         {
    1721     40928966 :           graph->pointer_label[n] = graph->pointer_label[first_pred];
    1722     40928966 :           graph->points_to[n] = graph->points_to[first_pred];
    1723              :         }
    1724              :       return;
    1725              :     }
    1726              : 
    1727     61896984 :   if (!bitmap_empty_p (graph->points_to[n]))
    1728              :     {
    1729     61896984 :       equiv_class_label_t ecl;
    1730     61896984 :       ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
    1731              :                                        graph->points_to[n]);
    1732     61896984 :       if (ecl->equivalence_class == 0)
    1733     29773633 :         ecl->equivalence_class = pointer_equiv_class++;
    1734              :       else
    1735              :         {
    1736     32123351 :           BITMAP_FREE (graph->points_to[n]);
    1737     32123351 :           graph->points_to[n] = ecl->labels;
    1738              :         }
    1739     61896984 :       graph->pointer_label[n] = ecl->equivalence_class;
    1740              :     }
    1741              : }
    1742              : 
    1743              : /* Print the pred graph in dot format.  */
    1744              : 
    1745              : static void
    1746            3 : dump_pred_graph (class scc_info *si, FILE *file)
    1747              : {
    1748            3 :   unsigned int i;
    1749              : 
    1750              :   /* Only print the graph if it has already been initialized:  */
    1751            3 :   if (!graph)
    1752              :     return;
    1753              : 
    1754              :   /* Prints the header of the dot file:  */
    1755            3 :   fprintf (file, "strict digraph {\n");
    1756            3 :   fprintf (file, "  node [\n    shape = box\n  ]\n");
    1757            3 :   fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");
    1758            3 :   fprintf (file, "\n  // List of nodes and complex constraints in "
    1759              :            "the constraint graph:\n");
    1760              : 
    1761              :   /* The next lines print the nodes in the graph together with the
    1762              :      complex constraints attached to them.  */
    1763           83 :   for (i = 1; i < graph->size; i++)
    1764              :     {
    1765          154 :       if (i == FIRST_REF_NODE)
    1766            3 :         continue;
    1767           74 :       if (si->node_mapping[i] != i)
    1768            0 :         continue;
    1769           74 :       if (i < FIRST_REF_NODE)
    1770           37 :         fprintf (file, "\"%s\"", get_varinfo (i)->name);
    1771              :       else
    1772           37 :         fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
    1773           74 :       if (graph->points_to[i]
    1774           74 :           && !bitmap_empty_p (graph->points_to[i]))
    1775              :         {
    1776           11 :           if (i < FIRST_REF_NODE)
    1777           11 :             fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
    1778              :           else
    1779            0 :             fprintf (file, "[label=\"*%s = {",
    1780            0 :                      get_varinfo (i - FIRST_REF_NODE)->name);
    1781           11 :           unsigned j;
    1782           11 :           bitmap_iterator bi;
    1783           25 :           EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
    1784           14 :             fprintf (file, " %d", j);
    1785           11 :           fprintf (file, " }\"]");
    1786              :         }
    1787           74 :       fprintf (file, ";\n");
    1788              :     }
    1789              : 
    1790              :   /* Go over the edges.  */
    1791            3 :   fprintf (file, "\n  // Edges in the constraint graph:\n");
    1792           83 :   for (i = 1; i < graph->size; i++)
    1793              :     {
    1794           77 :       unsigned j;
    1795           77 :       bitmap_iterator bi;
    1796           77 :       if (si->node_mapping[i] != i)
    1797            0 :         continue;
    1798           92 :       EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
    1799              :         {
    1800           15 :           unsigned from = si->node_mapping[j];
    1801           15 :           if (from < FIRST_REF_NODE)
    1802            7 :             fprintf (file, "\"%s\"", get_varinfo (from)->name);
    1803              :           else
    1804            8 :             fprintf (file, "\"*%s\"",
    1805            8 :                      get_varinfo (from - FIRST_REF_NODE)->name);
    1806           15 :           fprintf (file, " -> ");
    1807           15 :           if (i < FIRST_REF_NODE)
    1808           11 :             fprintf (file, "\"%s\"", get_varinfo (i)->name);
    1809              :           else
    1810            8 :             fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
    1811           15 :           fprintf (file, ";\n");
    1812              :         }
    1813              :     }
    1814              : 
    1815              :   /* Prints the tail of the dot file.  */
    1816            3 :   fprintf (file, "}\n");
    1817              : }
    1818              : 
    1819              : /* Perform offline variable substitution, discovering equivalence
    1820              :    classes, and eliminating non-pointer variables.  */
    1821              : 
    1822              : static class scc_info *
    1823      4568954 : perform_var_substitution (constraint_graph_t graph)
    1824              : {
    1825      4568954 :   unsigned int i;
    1826      4568954 :   unsigned int size = graph->size;
    1827      4568954 :   scc_info *si = new scc_info (size);
    1828              : 
    1829      4568954 :   bitmap_obstack_initialize (&iteration_obstack);
    1830      4568954 :   gcc_obstack_init (&equiv_class_obstack);
    1831      4568954 :   pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
    1832      4568954 :   location_equiv_class_table
    1833      4568954 :     = new hash_table<equiv_class_hasher> (511);
    1834      4568954 :   pointer_equiv_class = 1;
    1835      4568954 :   location_equiv_class = 1;
    1836              : 
    1837              :   /* Condense the nodes, which means to find SCC's, count incoming
    1838              :      predecessors, and unite nodes in SCC's.  */
    1839    233883962 :   for (i = 1; i < FIRST_REF_NODE; i++)
    1840    229315008 :     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
    1841    156196920 :       condense_visit (graph, si, si->node_mapping[i]);
    1842              : 
    1843      4568954 :   if (dump_file && (dump_flags & TDF_GRAPH))
    1844              :     {
    1845            3 :       fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
    1846              :                "in dot format:\n");
    1847            3 :       dump_pred_graph (si, dump_file);
    1848            3 :       fprintf (dump_file, "\n\n");
    1849              :     }
    1850              : 
    1851      4568954 :   bitmap_clear (si->visited);
    1852              :   /* Actually the label the nodes for pointer equivalences.  */
    1853    472336878 :   for (i = 1; i < FIRST_REF_NODE; i++)
    1854    229315008 :     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
    1855    161361050 :       label_visit (graph, si, si->node_mapping[i]);
    1856              : 
    1857              :   /* Calculate location equivalence labels.  */
    1858    233883962 :   for (i = 1; i < FIRST_REF_NODE; i++)
    1859              :     {
    1860    229315008 :       bitmap pointed_by;
    1861    229315008 :       bitmap_iterator bi;
    1862    229315008 :       unsigned int j;
    1863              : 
    1864    229315008 :       if (!graph->pointed_by[i])
    1865    207023501 :         continue;
    1866     22291507 :       pointed_by = BITMAP_ALLOC (&iteration_obstack);
    1867              : 
    1868              :       /* Translate the pointed-by mapping for pointer equivalence
    1869              :          labels.  */
    1870    100380554 :       EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
    1871              :         {
    1872     78089047 :           bitmap_set_bit (pointed_by,
    1873     78089047 :                           graph->pointer_label[si->node_mapping[j]]);
    1874              :         }
    1875              :       /* The original pointed_by is now dead.  */
    1876     22291507 :       BITMAP_FREE (graph->pointed_by[i]);
    1877              : 
    1878              :       /* Look up the location equivalence label if one exists, or make
    1879              :          one otherwise.  */
    1880     22291507 :       equiv_class_label_t ecl;
    1881     22291507 :       ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
    1882     22291507 :       if (ecl->equivalence_class == 0)
    1883     21839247 :         ecl->equivalence_class = location_equiv_class++;
    1884              :       else
    1885              :         {
    1886       452260 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1887           55 :             fprintf (dump_file, "Found location equivalence for node %s\n",
    1888           55 :                      get_varinfo (i)->name);
    1889       452260 :           BITMAP_FREE (pointed_by);
    1890              :         }
    1891     22291507 :       graph->loc_label[i] = ecl->equivalence_class;
    1892              : 
    1893              :     }
    1894              : 
    1895      4568954 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1896         6830 :     for (i = 1; i < FIRST_REF_NODE; i++)
    1897              :       {
    1898         6529 :         unsigned j = si->node_mapping[i];
    1899         6529 :         if (j != i)
    1900              :           {
    1901           21 :             fprintf (dump_file, "%s node id %d ",
    1902           21 :                      bitmap_bit_p (graph->direct_nodes, i)
    1903              :                      ? "Direct" : "Indirect", i);
    1904           21 :             if (i < FIRST_REF_NODE)
    1905           21 :               fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
    1906              :             else
    1907            0 :               fprintf (dump_file, "\"*%s\"",
    1908            0 :                        get_varinfo (i - FIRST_REF_NODE)->name);
    1909           21 :             fprintf (dump_file, " mapped to SCC leader node id %d ", j);
    1910           21 :             if (j < FIRST_REF_NODE)
    1911           21 :               fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
    1912              :             else
    1913            0 :               fprintf (dump_file, "\"*%s\"\n",
    1914            0 :                        get_varinfo (j - FIRST_REF_NODE)->name);
    1915              :           }
    1916              :         else
    1917              :           {
    1918        10023 :             fprintf (dump_file,
    1919              :                      "Equivalence classes for %s node id %d ",
    1920         6508 :                      bitmap_bit_p (graph->direct_nodes, i)
    1921              :                      ? "direct" : "indirect", i);
    1922         6508 :             if (i < FIRST_REF_NODE)
    1923         6508 :               fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
    1924              :             else
    1925            0 :               fprintf (dump_file, "\"*%s\"",
    1926            0 :                        get_varinfo (i - FIRST_REF_NODE)->name);
    1927         6508 :             fprintf (dump_file,
    1928              :                      ": pointer %d, location %d\n",
    1929         6508 :                      graph->pointer_label[i], graph->loc_label[i]);
    1930              :           }
    1931              :       }
    1932              : 
    1933              :   /* Quickly eliminate our non-pointer variables.  */
    1934              : 
    1935    233883962 :   for (i = 1; i < FIRST_REF_NODE; i++)
    1936              :     {
    1937    229315008 :       unsigned int node = si->node_mapping[i];
    1938              : 
    1939    229315008 :       if (graph->pointer_label[node] == 0)
    1940              :         {
    1941     20301810 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1942          926 :             fprintf (dump_file,
    1943              :                      "%s is a non-pointer variable, eliminating edges.\n",
    1944          926 :                      get_varinfo (node)->name);
    1945     20301810 :           stats.nonpointer_vars++;
    1946     20301810 :           clear_edges_for_node (graph, node);
    1947              :         }
    1948              :     }
    1949              : 
    1950      4568954 :   return si;
    1951              : }
    1952              : 
    1953              : /* Free information that was only necessary for variable
    1954              :    substitution.  */
    1955              : 
    1956              : static void
    1957      4568954 : free_var_substitution_info (class scc_info *si)
    1958              : {
    1959      4568954 :   delete si;
    1960      4568954 :   free (graph->pointer_label);
    1961      4568954 :   free (graph->loc_label);
    1962      4568954 :   free (graph->pointed_by);
    1963      4568954 :   free (graph->points_to);
    1964      4568954 :   free (graph->eq_rep);
    1965      4568954 :   sbitmap_free (graph->direct_nodes);
    1966      4568954 :   delete pointer_equiv_class_table;
    1967      4568954 :   pointer_equiv_class_table = NULL;
    1968      4568954 :   delete location_equiv_class_table;
    1969      4568954 :   location_equiv_class_table = NULL;
    1970      4568954 :   obstack_free (&equiv_class_obstack, NULL);
    1971      4568954 :   bitmap_obstack_release (&iteration_obstack);
    1972      4568954 : }
    1973              : 
    1974              : /* Return an existing node that is equivalent to NODE, which has
    1975              :    equivalence class LABEL, if one exists.  Return NODE otherwise.  */
    1976              : 
    1977              : static unsigned int
    1978    901068442 : find_equivalent_node (constraint_graph_t graph,
    1979              :                       unsigned int node, unsigned int label)
    1980              : {
    1981              :   /* If the address version of this variable is unused, we can
    1982              :      substitute it for anything else with the same label.
    1983              :      Otherwise, we know the pointers are equivalent, but not the
    1984              :      locations, and we can unite them later.  */
    1985              : 
    1986    901068442 :   if (!bitmap_bit_p (graph->address_taken, node))
    1987              :     {
    1988    700842480 :       gcc_checking_assert (label < graph->size);
    1989              : 
    1990    700842480 :       if (graph->eq_rep[label] != -1)
    1991              :         {
    1992              :           /* Unify the two variables since we know they are equivalent.  */
    1993    593311835 :           if (unite (graph->eq_rep[label], node))
    1994              :             {
    1995     43025134 :               unify_nodes (graph, graph->eq_rep[label], node, false);
    1996     43025134 :               return graph->eq_rep[label];
    1997              :             }
    1998              :         }
    1999              :       else
    2000              :         {
    2001    107530645 :           graph->eq_rep[label] = node;
    2002    107530645 :           graph->pe_rep[label] = node;
    2003              :         }
    2004              :     }
    2005              :   else
    2006              :     {
    2007    200225962 :       gcc_checking_assert (label < graph->size);
    2008    200225962 :       graph->pe[node] = label;
    2009    200225962 :       if (graph->pe_rep[label] == -1)
    2010     22201416 :         graph->pe_rep[label] = node;
    2011              :     }
    2012              : 
    2013              :   return node;
    2014              : }
    2015              : 
    2016              : /* Unite pointer equivalent but not location equivalent nodes in
    2017              :    GRAPH.  This may only be performed once variable substitution is
    2018              :    finished.  */
    2019              : 
    2020              : static void
    2021      4568954 : unite_pointer_equivalences (constraint_graph_t graph)
    2022              : {
    2023      4568954 :   unsigned int i;
    2024              : 
    2025              :   /* Go through the pointer equivalences and unite them to their
    2026              :      representative, if they aren't already.  */
    2027    233883962 :   for (i = 1; i < FIRST_REF_NODE; i++)
    2028              :     {
    2029    229315008 :       unsigned int label = graph->pe[i];
    2030    229315008 :       if (label)
    2031              :         {
    2032     22291507 :           int label_rep = graph->pe_rep[label];
    2033              : 
    2034     22291507 :           if (label_rep == -1)
    2035            0 :             continue;
    2036              : 
    2037     22291507 :           label_rep = find (label_rep);
    2038     22291507 :           if (label_rep >= 0 && unite (label_rep, find (i)))
    2039       790623 :             unify_nodes (graph, label_rep, i, false);
    2040              :         }
    2041              :     }
    2042      4568954 : }
    2043              : 
    2044              : /* Move complex constraints to the GRAPH nodes they belong to.  */
    2045              : 
    2046              : static void
    2047      4568954 : move_complex_constraints (constraint_graph_t graph)
    2048              : {
    2049      4568954 :   int i;
    2050      4568954 :   constraint_t c;
    2051              : 
    2052    457619970 :   FOR_EACH_VEC_ELT (constraints, i, c)
    2053              :     {
    2054    453051016 :       if (c)
    2055              :         {
    2056    450534221 :           struct constraint_expr lhs = c->lhs;
    2057    450534221 :           struct constraint_expr rhs = c->rhs;
    2058              : 
    2059    450534221 :           if (lhs.type == DEREF)
    2060              :             {
    2061     37169019 :               insert_into_complex (graph, lhs.var, c);
    2062              :             }
    2063    413365202 :           else if (rhs.type == DEREF)
    2064              :             {
    2065     50171657 :               if (!(get_varinfo (lhs.var)->is_special_var))
    2066     50171654 :                 insert_into_complex (graph, rhs.var, c);
    2067              :             }
    2068    363193545 :           else if (rhs.type != ADDRESSOF && lhs.var > anything_id
    2069    269815918 :                    && (lhs.offset != 0 || rhs.offset != 0))
    2070              :             {
    2071     62264616 :               insert_into_complex (graph, rhs.var, c);
    2072              :             }
    2073              :         }
    2074              :     }
    2075      4568954 : }
    2076              : 
    2077              : /* Optimize and rewrite complex constraints while performing
    2078              :    collapsing of equivalent nodes.  SI is the SCC_INFO that is the
    2079              :    result of perform_variable_substitution.  */
    2080              : 
    2081              : static void
    2082      4568954 : rewrite_constraints (constraint_graph_t graph,
    2083              :                      class scc_info *si)
    2084              : {
    2085      4568954 :   int i;
    2086      4568954 :   constraint_t c;
    2087              : 
    2088      4568954 :   if (flag_checking)
    2089              :     {
    2090    472333730 :       for (unsigned int j = 0; j < graph->size; j++)
    2091    467764836 :         gcc_assert (find (j) == j);
    2092              :     }
    2093              : 
    2094    457619970 :   FOR_EACH_VEC_ELT (constraints, i, c)
    2095              :     {
    2096    453051016 :       struct constraint_expr lhs = c->lhs;
    2097    453051016 :       struct constraint_expr rhs = c->rhs;
    2098    453051016 :       unsigned int lhsvar = find (lhs.var);
    2099    453051016 :       unsigned int rhsvar = find (rhs.var);
    2100    453051016 :       unsigned int lhsnode, rhsnode;
    2101    453051016 :       unsigned int lhslabel, rhslabel;
    2102              : 
    2103    453051016 :       lhsnode = si->node_mapping[lhsvar];
    2104    453051016 :       rhsnode = si->node_mapping[rhsvar];
    2105    453051016 :       lhslabel = graph->pointer_label[lhsnode];
    2106    453051016 :       rhslabel = graph->pointer_label[rhsnode];
    2107              : 
    2108              :       /* See if it is really a non-pointer variable, and if so, ignore
    2109              :          the constraint.  */
    2110    453051016 :       if (lhslabel == 0)
    2111              :         {
    2112       791346 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2113              :             {
    2114              : 
    2115           44 :               fprintf (dump_file, "%s is a non-pointer variable, "
    2116              :                        "ignoring constraint:",
    2117           22 :                        get_varinfo (lhs.var)->name);
    2118           22 :               dump_constraint (dump_file, c);
    2119           22 :               fprintf (dump_file, "\n");
    2120              :             }
    2121       791346 :           constraints[i] = NULL;
    2122    453051016 :           continue;
    2123              :         }
    2124              : 
    2125    452259670 :       if (rhslabel == 0)
    2126              :         {
    2127      1725449 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2128              :             {
    2129              : 
    2130           90 :               fprintf (dump_file, "%s is a non-pointer variable, "
    2131              :                        "ignoring constraint:",
    2132           45 :                        get_varinfo (rhs.var)->name);
    2133           45 :               dump_constraint (dump_file, c);
    2134           45 :               fprintf (dump_file, "\n");
    2135              :             }
    2136      1725449 :           constraints[i] = NULL;
    2137      1725449 :           continue;
    2138              :         }
    2139              : 
    2140    450534221 :       lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
    2141    450534221 :       rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
    2142    450534221 :       c->lhs.var = lhsvar;
    2143    450534221 :       c->rhs.var = rhsvar;
    2144              :     }
    2145      4568954 : }
    2146              : 
    2147              : /* Eliminate indirect cycles involving NODE.  Return true if NODE was
    2148              :    part of an SCC, false otherwise.  */
    2149              : 
    2150              : static bool
    2151    461976542 : eliminate_indirect_cycles (unsigned int node)
    2152              : {
    2153    461976542 :   if (graph->indirect_cycles[node] != -1
    2154    462308672 :       && !bitmap_empty_p (get_varinfo (node)->solution))
    2155              :     {
    2156       298290 :       unsigned int i;
    2157       298290 :       auto_vec<unsigned> queue;
    2158       298290 :       int queuepos;
    2159       298290 :       unsigned int to = find (graph->indirect_cycles[node]);
    2160       298290 :       bitmap_iterator bi;
    2161              : 
    2162              :       /* We can't touch the solution set and call unify_nodes
    2163              :          at the same time, because unify_nodes is going to do
    2164              :          bitmap unions into it.  */
    2165              : 
    2166      1132859 :       EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
    2167              :         {
    2168       834569 :           if (find (i) == i && i != to)
    2169              :             {
    2170       514882 :               if (unite (to, i))
    2171        60180 :                 queue.safe_push (i);
    2172              :             }
    2173              :         }
    2174              : 
    2175        60180 :       for (queuepos = 0;
    2176       373201 :            queue.iterate (queuepos, &i);
    2177              :            queuepos++)
    2178              :         {
    2179        60180 :           unify_nodes (graph, to, i, true);
    2180              :         }
    2181       298290 :       return true;
    2182       298290 :     }
    2183              :   return false;
    2184              : }
    2185              : 
    2186              : /* Solve the constraint graph GRAPH using our worklist solver.
    2187              :    This is based on the PW* family of solvers from the "Efficient Field
    2188              :    Sensitive Pointer Analysis for C" paper.
    2189              :    It works by iterating over all the graph nodes, processing the complex
    2190              :    constraints and propagating the copy constraints, until everything stops
    2191              :    changed.  This corresponds to steps 6-8 in the solving list given above.  */
    2192              : 
    2193              : static void
    2194      4568954 : solve_graph (constraint_graph_t graph)
    2195              : {
    2196      4568954 :   unsigned int size = graph->size;
    2197      4568954 :   unsigned int i;
    2198      4568954 :   bitmap pts;
    2199              : 
    2200      4568954 :   changed = BITMAP_ALLOC (NULL);
    2201              : 
    2202              :   /* Mark all initial non-collapsed nodes as changed.  */
    2203    233883962 :   for (i = 1; i < size; i++)
    2204              :     {
    2205    229315008 :       varinfo_t ivi = get_varinfo (i);
    2206    414800022 :       if (find (i) == i && !bitmap_empty_p (ivi->solution)
    2207    287402305 :           && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
    2208    237232223 :               || graph->complex[i].length () > 0))
    2209     37134833 :         bitmap_set_bit (changed, i);
    2210              :     }
    2211              : 
    2212              :   /* Allocate a bitmap to be used to store the changed bits.  */
    2213      4568954 :   pts = BITMAP_ALLOC (&pta_obstack);
    2214              : 
    2215     17267425 :   while (!bitmap_empty_p (changed))
    2216              :     {
    2217      8129517 :       unsigned int i;
    2218      8129517 :       stats.iterations++;
    2219              : 
    2220      8129517 :       bitmap_obstack_initialize (&iteration_obstack);
    2221              : 
    2222      8129517 :       auto_vec<unsigned> topo_order = compute_topo_order (graph);
    2223    478255749 :       while (topo_order.length () != 0)
    2224              :         {
    2225    461996715 :           i = topo_order.pop ();
    2226              : 
    2227              :           /* If this variable is not a representative, skip it.  */
    2228    461996715 :           if (find (i) != i)
    2229        20173 :             continue;
    2230              : 
    2231              :           /* In certain indirect cycle cases, we may merge this
    2232              :              variable to another.  */
    2233    461976542 :           if (eliminate_indirect_cycles (i) && find (i) != i)
    2234           93 :             continue;
    2235              : 
    2236              :           /* If the node has changed, we need to process the
    2237              :              complex constraints and outgoing edges again.  For complex
    2238              :              constraints that modify i itself, like the common group of
    2239              :                callarg = callarg + UNKNOWN;
    2240              :                callarg = *callarg + UNKNOWN;
    2241              :                *callarg = callescape;
    2242              :              make sure to iterate immediately because that maximizes
    2243              :              cache reuse and expands the graph quickest, leading to
    2244              :              better visitation order in the next iteration.  */
    2245    634875080 :           while (bitmap_clear_bit (changed, i))
    2246              :             {
    2247    173159219 :               bitmap solution;
    2248    173159219 :               vec<constraint_t> &complex = graph->complex[i];
    2249    173159219 :               varinfo_t vi = get_varinfo (i);
    2250    173159219 :               bool solution_empty;
    2251              : 
    2252              :               /* Compute the changed set of solution bits.  If anything
    2253              :                  is in the solution just propagate that.  */
    2254    173159219 :               if (bitmap_bit_p (vi->solution, anything_id))
    2255              :                 {
    2256              :                   /* If anything is also in the old solution there is
    2257              :                      nothing to do.
    2258              :                      ???  But we shouldn't ended up with "changed" set ...  */
    2259      2734285 :                   if (vi->oldsolution
    2260      2734285 :                       && bitmap_bit_p (vi->oldsolution, anything_id))
    2261              :                     break;
    2262      2473697 :                   bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
    2263              :                 }
    2264    170424934 :               else if (vi->oldsolution)
    2265     35999332 :                 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
    2266              :               else
    2267    134425602 :                 bitmap_copy (pts, vi->solution);
    2268              : 
    2269    172898631 :               if (bitmap_empty_p (pts))
    2270              :                 break;
    2271              : 
    2272    172898631 :               if (vi->oldsolution)
    2273     37225510 :                 bitmap_ior_into (vi->oldsolution, pts);
    2274              :               else
    2275              :                 {
    2276    135673121 :                   vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
    2277    135673121 :                   bitmap_copy (vi->oldsolution, pts);
    2278              :                 }
    2279              : 
    2280    172898631 :               solution = vi->solution;
    2281    172898631 :               solution_empty = bitmap_empty_p (solution);
    2282              : 
    2283              :               /* Process the complex constraints.  */
    2284    172898631 :               hash_set<constraint_t> *cvisited = nullptr;
    2285    172898631 :               if (flag_checking)
    2286    172897782 :                 cvisited = new hash_set<constraint_t>;
    2287    172898631 :               bitmap expanded_pts = NULL;
    2288    384889810 :               for (unsigned j = 0; j < complex.length (); ++j)
    2289              :                 {
    2290    211991179 :                   constraint_t c = complex[j];
    2291              :                   /* At unification time only the directly involved nodes
    2292              :                      will get their complex constraints updated.  Update
    2293              :                      our complex constraints now but keep the constraint
    2294              :                      vector sorted and clear of duplicates.  Also make
    2295              :                      sure to evaluate each prevailing constraint only once.  */
    2296    211991179 :                   unsigned int new_lhs = find (c->lhs.var);
    2297    211991179 :                   unsigned int new_rhs = find (c->rhs.var);
    2298    211991179 :                   if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
    2299              :                     {
    2300        94078 :                       constraint tem = *c;
    2301        94078 :                       tem.lhs.var = new_lhs;
    2302        94078 :                       tem.rhs.var = new_rhs;
    2303        94078 :                       unsigned int place
    2304        94078 :                         = complex.lower_bound (&tem, constraint_less);
    2305        94078 :                       c->lhs.var = new_lhs;
    2306        94078 :                       c->rhs.var = new_rhs;
    2307        94078 :                       if (place != j)
    2308              :                         {
    2309        85263 :                           complex.ordered_remove (j);
    2310        85263 :                           if (j < place)
    2311        72681 :                             --place;
    2312        85263 :                           if (place < complex.length ())
    2313              :                             {
    2314        30723 :                               if (constraint_equal (*complex[place], *c))
    2315              :                                 {
    2316        12726 :                                   j--;
    2317        41096 :                                   continue;
    2318              :                                 }
    2319              :                               else
    2320        17997 :                                 complex.safe_insert (place, c);
    2321              :                             }
    2322              :                           else
    2323        54540 :                             complex.quick_push (c);
    2324        72537 :                           if (place > j)
    2325              :                             {
    2326        28370 :                               j--;
    2327        28370 :                               continue;
    2328              :                             }
    2329              :                         }
    2330              :                     }
    2331              : 
    2332              :                   /* The only complex constraint that can change our
    2333              :                      solution to non-empty, given an empty solution,
    2334              :                      is a constraint where the lhs side is receiving
    2335              :                      some set from elsewhere.  */
    2336    211950083 :                   if (cvisited && cvisited->add (c))
    2337            0 :                     gcc_unreachable ();
    2338    211950083 :                   if (!solution_empty || c->lhs.type != DEREF)
    2339    211950083 :                     do_complex_constraint (graph, c, pts, &expanded_pts);
    2340              :                 }
    2341    172898631 :               if (cvisited)
    2342              :                 {
    2343              :                   /* When checking, verify the order of constraints is
    2344              :                      maintained and each constraint is evaluated exactly
    2345              :                      once.  */
    2346    302521803 :                   for (unsigned j = 1; j < complex.length (); ++j)
    2347    129624021 :                     gcc_assert (constraint_less (complex[j-1], complex[j]));
    2348    255222784 :                   gcc_assert (cvisited->elements () == complex.length ());
    2349    172897782 :                   delete cvisited;
    2350              :                 }
    2351    172898631 :               BITMAP_FREE (expanded_pts);
    2352              : 
    2353    172898631 :               solution_empty = bitmap_empty_p (solution);
    2354              : 
    2355    172898631 :               if (!solution_empty)
    2356              :                 {
    2357    172898631 :                   bitmap_iterator bi;
    2358    172898631 :                   unsigned eff_escaped_id = find (escaped_id);
    2359    172898631 :                   unsigned j;
    2360              : 
    2361              :                   /* Propagate solution to all successors.  */
    2362    172898631 :                   unsigned to_remove = ~0U;
    2363    456141398 :                   EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
    2364              :                                                 0, j, bi)
    2365              :                     {
    2366    283242767 :                       if (to_remove != ~0U)
    2367              :                         {
    2368       775651 :                           bitmap_clear_bit (graph->succs[i], to_remove);
    2369       775651 :                           to_remove = ~0U;
    2370              :                         }
    2371    283242767 :                       unsigned int to = find (j);
    2372    283242767 :                       if (to != j)
    2373              :                         {
    2374              :                           /* Update the succ graph, avoiding duplicate
    2375              :                              work.  */
    2376       837669 :                           to_remove = j;
    2377       837669 :                           if (! bitmap_set_bit (graph->succs[i], to))
    2378       128143 :                             continue;
    2379              :                           /* We eventually end up processing 'to' twice
    2380              :                              as it is undefined whether bitmap iteration
    2381              :                              iterates over bits set during iteration.
    2382              :                              Play safe instead of doing tricks.  */
    2383              :                         }
    2384              :                       /* Don't try to propagate to ourselves.  */
    2385    283114624 :                       if (to == i)
    2386              :                         {
    2387       117469 :                           to_remove = j;
    2388       117469 :                           continue;
    2389              :                         }
    2390              :                       /* Early node unification can lead to edges from
    2391              :                          escaped - remove them.  */
    2392    282997155 :                       if (i == eff_escaped_id)
    2393              :                         {
    2394        20122 :                           to_remove = j;
    2395        20122 :                           if (bitmap_set_bit (get_varinfo (to)->solution,
    2396              :                                               escaped_id))
    2397        19340 :                             bitmap_set_bit (changed, to);
    2398        20122 :                           continue;
    2399              :                         }
    2400              : 
    2401    282977033 :                       if (bitmap_ior_into (get_varinfo (to)->solution, pts))
    2402    140879270 :                         bitmap_set_bit (changed, to);
    2403              :                     }
    2404    107306283 :                   if (to_remove != ~0U)
    2405       133863 :                     bitmap_clear_bit (graph->succs[i], to_remove);
    2406              :                 }
    2407              :             }
    2408              :         }
    2409      8129517 :       bitmap_obstack_release (&iteration_obstack);
    2410      8129517 :     }
    2411              : 
    2412      4568954 :   BITMAP_FREE (pts);
    2413      4568954 :   BITMAP_FREE (changed);
    2414      4568954 :   bitmap_obstack_release (&oldpta_obstack);
    2415      4568954 : }
    2416              : 
    2417              : void
    2418      4568954 : delete_graph (void)
    2419              : {
    2420      4568954 :   unsigned int i;
    2421    238452916 :   for (i = 0; i < graph->size; i++)
    2422    233883962 :     graph->complex[i].release ();
    2423      4568954 :   free (graph->complex);
    2424              : 
    2425      4568954 :   free (graph->succs);
    2426      4568954 :   free (graph->pe);
    2427      4568954 :   free (graph->pe_rep);
    2428      4568954 :   free (graph->indirect_cycles);
    2429              :   /* We are not doing free (graph->rep) since the representatives mapping is
    2430              :      needed outside of the solver too.  */
    2431      4568954 :   free (graph);
    2432      4568954 : }
    2433              : 
    2434              : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
    2435              :    predecessor edges.  */
    2436              : 
    2437              : static void
    2438      4568954 : remove_preds_and_fake_succs (constraint_graph_t graph)
    2439              : {
    2440      4568954 :   unsigned int i;
    2441              : 
    2442              :   /* Clear the implicit ref and address nodes from the successor
    2443              :      lists.  */
    2444    233883962 :   for (i = 1; i < FIRST_REF_NODE; i++)
    2445              :     {
    2446    229315008 :       if (graph->succs[i])
    2447     74586847 :         bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
    2448     74586847 :                             FIRST_REF_NODE * 2);
    2449              :     }
    2450              : 
    2451              :   /* Free the successor list for the non-ref nodes.  */
    2452    238452916 :   for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
    2453              :     {
    2454    229315008 :       if (graph->succs[i])
    2455     12162317 :         BITMAP_FREE (graph->succs[i]);
    2456              :     }
    2457              : 
    2458              :   /* Now reallocate the size of the successor list as, and blow away
    2459              :      the predecessor bitmaps.  */
    2460      4568954 :   graph->size = varmap.length ();
    2461      4568954 :   graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
    2462              : 
    2463      4568954 :   free (graph->implicit_preds);
    2464      4568954 :   graph->implicit_preds = NULL;
    2465      4568954 :   free (graph->preds);
    2466      4568954 :   graph->preds = NULL;
    2467      4568954 :   bitmap_obstack_release (&predbitmap_obstack);
    2468      4568954 : }
    2469              : 
    2470              : namespace pointer_analysis {
    2471              : 
    2472              : /* Solve the constraint set.  The entry function of the solver.  */
    2473              : 
    2474              : void
    2475      4568954 : solve_constraints (void)
    2476              : {
    2477      4568954 :   class scc_info *si;
    2478              : 
    2479              :   /* Sort varinfos so that ones that cannot be pointed to are last.
    2480              :      This makes bitmaps more efficient.  */
    2481      4568954 :   unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
    2482     50258494 :   for (unsigned i = 0; i < integer_id + 1; ++i)
    2483     41120586 :     map[i] = i;
    2484              :   /* Start with address-taken vars, followed by not address-taken vars
    2485              :      to move vars never appearing in the points-to solution bitmaps last.  */
    2486              :   unsigned j = integer_id + 1;
    2487    394664660 :   for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
    2488    192763376 :     if (varmap[varmap[i]->head]->address_taken)
    2489     15827253 :       map[i] = j++;
    2490    197332330 :   for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
    2491    192763376 :     if (! varmap[varmap[i]->head]->address_taken)
    2492    176936123 :       map[i] = j++;
    2493              :   /* Shuffle varmap according to map.  */
    2494    197332330 :   for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
    2495              :     {
    2496    287062261 :       while (map[varmap[i]->id] != i)
    2497     94298885 :         std::swap (varmap[i], varmap[map[varmap[i]->id]]);
    2498    192763376 :       gcc_assert (bitmap_empty_p (varmap[i]->solution));
    2499    192763376 :       varmap[i]->id = i;
    2500    192763376 :       varmap[i]->next = map[varmap[i]->next];
    2501    192763376 :       varmap[i]->head = map[varmap[i]->head];
    2502              :     }
    2503              :   /* Finally rewrite constraints.  */
    2504    457619970 :   for (unsigned i = 0; i < constraints.length (); ++i)
    2505              :     {
    2506    453051016 :       constraints[i]->lhs.var = map[constraints[i]->lhs.var];
    2507    453051016 :       constraints[i]->rhs.var = map[constraints[i]->rhs.var];
    2508              :     }
    2509      4568954 :   free (map);
    2510              : 
    2511      4568954 :   if (dump_file)
    2512          489 :     fprintf (dump_file,
    2513              :              "\nCollapsing static cycles and doing variable "
    2514              :              "substitution\n");
    2515              : 
    2516      9137908 :   init_graph (varmap.length () * 2);
    2517              : 
    2518      4568954 :   if (dump_file)
    2519          489 :     fprintf (dump_file, "Building predecessor graph\n");
    2520      4568954 :   build_pred_graph ();
    2521              : 
    2522      4568954 :   if (dump_file)
    2523          489 :     fprintf (dump_file, "Detecting pointer and location "
    2524              :              "equivalences\n");
    2525      4568954 :   si = perform_var_substitution (graph);
    2526              : 
    2527      4568954 :   if (dump_file)
    2528          489 :     fprintf (dump_file, "Rewriting constraints and unifying "
    2529              :              "variables\n");
    2530      4568954 :   rewrite_constraints (graph, si);
    2531              : 
    2532      4568954 :   build_succ_graph ();
    2533              : 
    2534      4568954 :   free_var_substitution_info (si);
    2535              : 
    2536              :   /* Attach complex constraints to graph nodes.  */
    2537      4568954 :   move_complex_constraints (graph);
    2538              : 
    2539      4568954 :   if (dump_file)
    2540          489 :     fprintf (dump_file, "Uniting pointer but not location equivalent "
    2541              :              "variables\n");
    2542      4568954 :   unite_pointer_equivalences (graph);
    2543              : 
    2544      4568954 :   if (dump_file)
    2545          489 :     fprintf (dump_file, "Finding indirect cycles\n");
    2546      4568954 :   find_indirect_cycles (graph);
    2547              : 
    2548              :   /* Implicit nodes and predecessors are no longer necessary at this
    2549              :      point.  */
    2550      4568954 :   remove_preds_and_fake_succs (graph);
    2551              : 
    2552      4568954 :   if (dump_file && (dump_flags & TDF_GRAPH))
    2553              :     {
    2554            3 :       fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
    2555              :                "in dot format:\n");
    2556            3 :       dump_constraint_graph (dump_file);
    2557            3 :       fprintf (dump_file, "\n\n");
    2558              :     }
    2559              : 
    2560      4568954 :   if (dump_file)
    2561          489 :     fprintf (dump_file, "Solving graph\n");
    2562              : 
    2563      4568954 :   solve_graph (graph);
    2564              : 
    2565      4568954 :   if (dump_file && (dump_flags & TDF_GRAPH))
    2566              :     {
    2567            3 :       fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
    2568              :                "in dot format:\n");
    2569            3 :       dump_constraint_graph (dump_file);
    2570            3 :       fprintf (dump_file, "\n\n");
    2571              :     }
    2572              : 
    2573              :   /* The mapping node -> representative is one of the outputs of the
    2574              :      solver.  */
    2575      4568954 :   union_find_compress_all ();
    2576      4568954 :   var_rep = graph->rep;
    2577              : 
    2578      4568954 :   delete_graph ();
    2579      4568954 : }
    2580              : 
    2581              : } // namespace pointer_analysis
        

Generated by: LCOV version 2.5.0-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.