LCOV - code coverage report
Current view: top level - gcc - value-relation.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.0 % 1061 944
Test Date: 2026-11-14 16:39:50 Functions: 86.8 % 91 79
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Header file for the value range relational processing.
       2              :    Copyright (C) 2020-2026 Free Software Foundation, Inc.
       3              :    Contributed by Andrew MacLeod <amacleod@redhat.com>
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it under
       8              : the terms of the GNU General Public License as published by the Free
       9              : Software Foundation; either version 3, or (at your option) any later
      10              : version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15              :  for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : #include "config.h"
      22              : #include "system.h"
      23              : #include "coretypes.h"
      24              : #include "backend.h"
      25              : #include "tree.h"
      26              : #include "gimple.h"
      27              : #include "ssa.h"
      28              : 
      29              : #include "gimple-range.h"
      30              : #include "tree-pretty-print.h"
      31              : #include "gimple-pretty-print.h"
      32              : #include "alloc-pool.h"
      33              : #include "dominance.h"
      34              : 
      35              : static const char *const kind_string[VREL_LAST] =
      36              : { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
      37              :   "pe32", "pe64" };
      38              : 
      39              : // Print a relation_kind REL to file F.
      40              : 
      41              : void
      42        39911 : print_relation (FILE *f, relation_kind rel)
      43              : {
      44        39911 :   fprintf (f, " %s ", kind_string[rel]);
      45        39911 : }
      46              : 
      47              : // This table is used to negate the operands.  op1 REL op2 -> !(op1 REL op2).
      48              : // Partial equivalence can't be negated, so VARYING is correct.
      49              : static const unsigned char rr_negate_table[VREL_LAST] = {
      50              :   VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
      51              :   VREL_EQ, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING };
      52              : 
      53              : // Negate the relation, as in logical negation.
      54              : 
      55              : relation_kind
      56            0 : relation_negate (relation_kind r)
      57              : {
      58            0 :   return relation_kind (rr_negate_table [r]);
      59              : }
      60              : 
      61              : // This table is used to swap the operands.  op1 REL op2 -> op2 REL op1.
      62              : // Partial equivalences swap to themselves as the low N bits are equal.
      63              : static const unsigned char rr_swap_table[VREL_LAST] = {
      64              :   VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
      65              :   VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 };
      66              : 
      67              : // Return the relation as if the operands were swapped.
      68              : 
      69              : relation_kind
      70     58055072 : relation_swap (relation_kind r)
      71              : {
      72     58055072 :   return relation_kind (rr_swap_table [r]);
      73              : }
      74              : 
      75              : // This table is used to perform an intersection between 2 relations.
      76              : // EQ is a full equivalency, and thus replaces any partial equivalence.
      77              : // Likewise, the higher bit PE is more "equivalent" than the lower bit version
      78              : // and thus more restrictive.
      79              : 
      80              : static const unsigned char rr_intersect_table[VREL_LAST][VREL_LAST] = {
      81              : // VREL_VARYING
      82              :   { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
      83              :     VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
      84              : // VREL_UNDEFINED
      85              :   { VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
      86              :     VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
      87              :     VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
      88              : // VREL_LT
      89              :   { VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
      90              :     VREL_UNDEFINED, VREL_LT,
      91              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
      92              : // VREL_LE
      93              :   { VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
      94              :     VREL_EQ, VREL_LT,
      95              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
      96              : // VREL_GT
      97              :   { VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
      98              :     VREL_UNDEFINED, VREL_GT,
      99              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     100              : // VREL_GE
     101              :   { VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
     102              :     VREL_EQ, VREL_GT,
     103              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     104              : // VREL_EQ
     105              :   { VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
     106              :     VREL_EQ, VREL_UNDEFINED,
     107              :     VREL_EQ, VREL_EQ, VREL_EQ, VREL_EQ },
     108              : // VREL_NE
     109              :   { VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
     110              :     VREL_UNDEFINED, VREL_NE,
     111              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     112              : // VREL_PE8
     113              :   { VREL_PE8, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     114              :     VREL_VARYING, VREL_EQ, VREL_VARYING,
     115              :     VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
     116              : // VREL_PE16
     117              :   { VREL_PE16, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     118              :     VREL_VARYING, VREL_EQ, VREL_VARYING,
     119              :     VREL_PE16, VREL_PE16, VREL_PE32, VREL_PE64 },
     120              : // VREL_PE32
     121              :   { VREL_PE32, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     122              :     VREL_VARYING, VREL_EQ, VREL_VARYING,
     123              :     VREL_PE32, VREL_PE32, VREL_PE32, VREL_PE64 },
     124              : // VREL_PE64
     125              :   { VREL_PE64, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     126              :     VREL_VARYING, VREL_EQ, VREL_VARYING,
     127              :     VREL_PE64, VREL_PE64, VREL_PE64, VREL_PE64 } };
     128              : 
     129              : 
     130              : // Intersect relation R1 with relation R2 and return the resulting relation.
     131              : 
     132              : relation_kind
     133    127416510 : relation_intersect (relation_kind r1, relation_kind r2)
     134              : {
     135    127416510 :   return relation_kind (rr_intersect_table[r1][r2]);
     136              : }
     137              : 
     138              : 
     139              : // This table is used to perform a union between 2 relations.
     140              : // EQ unions with a PE to produce the same PE, and likewise whichever PE
     141              : // has the least common bits forms the union.
     142              : 
     143              : static const unsigned char rr_union_table[VREL_LAST][VREL_LAST] = {
     144              : // VREL_VARYING
     145              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     146              :     VREL_VARYING, VREL_VARYING, VREL_VARYING,
     147              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     148              : // VREL_UNDEFINED
     149              :   { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE,
     150              :     VREL_EQ, VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
     151              : // VREL_LT
     152              :   { VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
     153              :     VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     154              : // VREL_LE
     155              :   { VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
     156              :     VREL_LE, VREL_VARYING,
     157              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     158              : // VREL_GT
     159              :   { VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
     160              :     VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     161              : // VREL_GE
     162              :   { VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
     163              :     VREL_GE, VREL_VARYING,
     164              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     165              : // VREL_EQ
     166              :   { VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
     167              :     VREL_VARYING, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
     168              : // VREL_NE
     169              :   { VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
     170              :     VREL_VARYING, VREL_NE,
     171              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     172              : // VREL_PE8
     173              :   { VREL_VARYING, VREL_PE8, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     174              :     VREL_VARYING, VREL_PE8, VREL_VARYING,
     175              :     VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
     176              : // VREL_PE16
     177              :   { VREL_VARYING, VREL_PE16, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     178              :     VREL_VARYING, VREL_PE16, VREL_VARYING,
     179              :     VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
     180              : // VREL_PE32
     181              :   { VREL_VARYING, VREL_PE32, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     182              :     VREL_VARYING, VREL_PE32, VREL_VARYING,
     183              :     VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
     184              : // VREL_PE64
     185              :   { VREL_VARYING, VREL_PE64, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     186              :     VREL_VARYING, VREL_PE64, VREL_VARYING,
     187              :     VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
     188              : 
     189              : // Union relation R1 with relation R2 and return the result.
     190              : 
     191              : relation_kind
     192     91528087 : relation_union (relation_kind r1, relation_kind r2)
     193              : {
     194     91528087 :   return relation_kind (rr_union_table[r1][r2]);
     195              : }
     196              : 
     197              : 
     198              : // This table is used to determine transitivity between 2 relations.
     199              : // (A relation0 B) and (B relation1 C) implies  (A result C)
     200              : // Chaining two partial equivalences leaves only the bits both agree on, ie
     201              : // the narrower of the two.
     202              : 
     203              : static const unsigned char rr_transitive_table[VREL_LAST][VREL_LAST] = {
     204              : // VREL_VARYING
     205              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     206              :     VREL_VARYING, VREL_VARYING, VREL_VARYING,
     207              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     208              : // VREL_UNDEFINED
     209              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     210              :     VREL_VARYING, VREL_VARYING, VREL_VARYING,
     211              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     212              : // VREL_LT
     213              :   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
     214              :     VREL_LT, VREL_VARYING,
     215              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     216              : // VREL_LE
     217              :   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
     218              :     VREL_LE, VREL_VARYING,
     219              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     220              : // VREL_GT
     221              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
     222              :     VREL_GT, VREL_VARYING,
     223              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     224              : // VREL_GE
     225              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
     226              :     VREL_GE, VREL_VARYING,
     227              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     228              : // VREL_EQ
     229              :   { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
     230              :     VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
     231              : // VREL_NE
     232              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     233              :     VREL_VARYING, VREL_NE, VREL_VARYING,
     234              :     VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
     235              : // VREL_PE8
     236              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     237              :     VREL_VARYING, VREL_PE8, VREL_VARYING,
     238              :     VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
     239              : // VREL_PE16
     240              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     241              :     VREL_VARYING, VREL_PE16, VREL_VARYING,
     242              :     VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
     243              : // VREL_PE32
     244              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     245              :     VREL_VARYING, VREL_PE32, VREL_VARYING,
     246              :     VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
     247              : // VREL_PE64
     248              :   { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
     249              :     VREL_VARYING, VREL_PE64, VREL_VARYING,
     250              :     VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
     251              : 
     252              : // Apply transitive operation between relation R1 and relation R2, and
     253              : // return the resulting relation, if any.
     254              : 
     255              : relation_kind
     256     54344758 : relation_transitive (relation_kind r1, relation_kind r2)
     257              : {
     258     54344758 :   return relation_kind (rr_transitive_table[r1][r2]);
     259              : }
     260              : 
     261              : // When one name is an equivalence of another, ensure the equivalence
     262              : // range is correct.  Specifically for floating point, a +0 is also
     263              : // equivalent to a -0 which may not be reflected.  See PR 111694.
     264              : 
     265              : void
     266      2512309 : adjust_equivalence_range (vrange &range)
     267              : {
     268      2512309 :   if (range.undefined_p () || !is_a<frange> (range))
     269      2474664 :     return;
     270              : 
     271        37645 :   frange fr = as_a<frange> (range);
     272              :   // If range includes 0 make sure both signs of zero are included.
     273        37645 :   if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
     274              :     {
     275        19296 :       frange zeros (range.type (), dconstm0, dconst0);
     276        19296 :       range.union_ (zeros);
     277        19296 :     }
     278        37645 :  }
     279              : 
     280              : // Given an equivalence set EQUIV, set all the bits in B that are still valid
     281              : // members of EQUIV in basic block BB.
     282              : 
     283              : void
     284     24708382 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
     285              : {
     286     24708382 :   unsigned i;
     287     24708382 :   bitmap_iterator bi;
     288     52104663 :   EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
     289              :     {
     290     27396281 :       tree ssa = ssa_name (i);
     291     54792562 :       if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
     292              :         {
     293     27396281 :           const_bitmap ssa_equiv = equiv_set (ssa, bb);
     294     27396281 :           if (ssa_equiv == equivs)
     295     27105002 :             bitmap_set_bit (b, i);
     296              :         }
     297              :     }
     298     24708382 : }
     299              : 
     300              : // Return any known relation between SSA1 and SSA2 before stmt S is executed.
     301              : // If GET_RANGE is true, query the range of both operands first to ensure
     302              : // the definitions have been processed and any relations have be created.
     303              : 
     304              : relation_kind
     305    139818933 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
     306              : {
     307    139818933 :   if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
     308              :     return VREL_VARYING;
     309     60304893 :   return query (gimple_bb (s), ssa1, ssa2);
     310              : }
     311              : 
     312              : // Return any known relation between SSA1 and SSA2 on edge E.
     313              : // If GET_RANGE is true, query the range of both operands first to ensure
     314              : // the definitions have been processed and any relations have be created.
     315              : 
     316              : relation_kind
     317     49305569 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
     318              : {
     319     49305569 :   basic_block bb;
     320     49305569 :   if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
     321              :     return VREL_VARYING;
     322              : 
     323              :   // Use destination block if it has a single predecessor, and this picks
     324              :   // up any relation on the edge.
     325              :   // Otherwise choose the src edge and the result is the same as on-exit.
     326     36200883 :   if (!single_pred_p (e->dest))
     327     34256564 :     bb = e->src;
     328              :   else
     329              :     bb = e->dest;
     330              : 
     331     36200883 :   return query (bb, ssa1, ssa2);
     332              : }
     333              : // -------------------------------------------------------------------------
     334              : 
     335              : // The very first element in the m_equiv chain is actually just a summary
     336              : // element in which the m_names bitmap is used to indicate that an ssa_name
     337              : // has an equivalence set in this block.
     338              : // This allows for much faster traversal of the DOM chain, as a search for
     339              : // SSA_NAME simply requires walking the DOM chain until a block is found
     340              : // which has the bit for SSA_NAME set. Then scan for the equivalency set in
     341              : // that block.   No previous lists need be searched.
     342              : 
     343              : // If SSA has an equivalence in this list, find and return it.
     344              : // Otherwise return NULL.
     345              : 
     346              : equiv_chain *
     347    216294095 : equiv_chain::find (unsigned ssa)
     348              : {
     349    216294095 :   equiv_chain *ptr = NULL;
     350              :   // If there are equiv sets and SSA is in one in this list, find it.
     351              :   // Otherwise return NULL.
     352    216294095 :   if (bitmap_bit_p (m_names, ssa))
     353              :     {
     354    246675340 :       for (ptr = m_next; ptr; ptr = ptr->m_next)
     355    246675340 :         if (bitmap_bit_p (ptr->m_names, ssa))
     356              :           break;
     357              :     }
     358    216294095 :   return ptr;
     359              : }
     360              : 
     361              : // Dump the names in this equivalence set.
     362              : 
     363              : void
     364           10 : equiv_chain::dump (FILE *f) const
     365              : {
     366           10 :   bitmap_iterator bi;
     367           10 :   unsigned i;
     368              : 
     369           10 :   if (!m_names || bitmap_empty_p (m_names))
     370            1 :     return;
     371            9 :   fprintf (f, "Equivalence set : [");
     372            9 :   unsigned c = 0;
     373           24 :   EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
     374              :     {
     375           15 :       if (ssa_name (i))
     376              :         {
     377           15 :           if (c++)
     378            6 :             fprintf (f, ", ");
     379           15 :           print_generic_expr (f, ssa_name (i), TDF_SLIM);
     380              :         }
     381              :     }
     382            9 :   fprintf (f, "]\n");
     383              : }
     384              : 
     385              : // Instantiate an equivalency oracle.
     386              : 
     387     27589038 : equiv_oracle::equiv_oracle ()
     388              : {
     389     27589038 :   bitmap_obstack_initialize (&m_bitmaps);
     390     27589038 :   m_equiv.create (0);
     391     27589038 :   m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
     392     27589038 :   m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
     393     27589038 :   bitmap_tree_view (m_equiv_set);
     394     27589038 :   obstack_init (&m_chain_obstack);
     395     27589038 :   m_name_info.create (0);
     396     55178076 :   m_name_info.safe_grow_cleared (num_ssa_names + 1);
     397     27589038 :   m_partial.create (0);
     398     55178076 :   m_partial.safe_grow_cleared (num_ssa_names + 1);
     399              :   // Create a bitmap to avoid registering multiple equivalences from a LHS.
     400              :   // See PR 124809.
     401     27589038 :   m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
     402     27589038 :   bitmap_tree_view (m_lhs_equiv_set_p);
     403     27589038 : }
     404              : 
     405              : // Destruct an equivalency oracle.
     406              : 
     407     27589038 : equiv_oracle::~equiv_oracle ()
     408              : {
     409     27589038 :   m_partial.release ();
     410     27589038 :   m_name_info.release ();
     411     27589038 :   obstack_free (&m_chain_obstack, NULL);
     412     27589038 :   m_equiv.release ();
     413     27589038 :   bitmap_obstack_release (&m_bitmaps);
     414     27589038 : }
     415              : 
     416              : // Add a partial equivalence R between OP1 and OP2.  Return false if no
     417              : // new relation is added.
     418              : 
     419              : bool
     420     10518482 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
     421              : {
     422     10518482 :   int v1 = SSA_NAME_VERSION (op1);
     423     10518482 :   int v2 = SSA_NAME_VERSION (op2);
     424     10518482 :   int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
     425     10518482 :   int bits = pe_to_bits (r);
     426     10518482 :   gcc_checking_assert (bits && prec2 >= bits);
     427              : 
     428     21036964 :   if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
     429         9956 :     m_partial.safe_grow_cleared (num_ssa_names + 1);
     430     21036964 :   gcc_checking_assert (v1 < (int)m_partial.length ()
     431              :                        && v2 < (int)m_partial.length ());
     432              : 
     433     10518482 :   pe_slice &pe1 = m_partial[v1];
     434     10518482 :   pe_slice &pe2 = m_partial[v2];
     435              : 
     436     10518482 :   if (pe1.members)
     437              :     {
     438              :       // If the definition pe1 already has an entry, either the stmt is
     439              :       // being re-evaluated, or the def was used before being registered.
     440              :       // In either case, if PE2 has an entry, we simply do nothing.
     441          209 :       if (pe2.members)
     442              :         return false;
     443              :       // If there are no uses of op2, do not register.
     444          185 :       if (has_zero_uses (op2))
     445              :         return false;
     446              :       // PE1 is the LHS and already has members, so everything in the set
     447              :       // should be a slice of PE2 rather than PE1.
     448          185 :       pe2.code = pe_min (r, pe1.code);
     449          185 :       pe2.ssa_base = op2;
     450          185 :       pe2.members = pe1.members;
     451          185 :       bitmap_iterator bi;
     452          185 :       unsigned x;
     453          563 :       EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
     454              :         {
     455          378 :           m_partial[x].ssa_base = op2;
     456          378 :           m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
     457              :         }
     458          185 :       bitmap_set_bit (pe1.members, v2);
     459          185 :       return true;
     460              :     }
     461     10518273 :   if (pe2.members)
     462              :     {
     463              :       // If there are no uses of op1, do not register.
     464       781640 :       if (has_zero_uses (op1))
     465              :         return false;
     466       766984 :       pe1.ssa_base = pe2.ssa_base;
     467              :       // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
     468              :       // more than an 8 bit equivalence here, so choose MIN value.
     469       766984 :       pe1.code = pe_min (r, pe2.code);
     470       766984 :       pe1.members = pe2.members;
     471       766984 :       bitmap_set_bit (pe1.members, v1);
     472              :     }
     473              :   else
     474              :     {
     475              :       // If there are no uses of either operand, do not register.
     476      9736633 :       if (has_zero_uses (op1) || has_zero_uses (op2))
     477              :         return false;
     478              :       // Neither name has an entry, simply create op1 as slice of op2.
     479      9581742 :       pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
     480      9581742 :       if (pe2.code == VREL_VARYING)
     481              :         return false;
     482      9520593 :       pe2.ssa_base = op2;
     483      9520593 :       pe2.members = BITMAP_ALLOC (&m_bitmaps);
     484      9520593 :       bitmap_set_bit (pe2.members, v2);
     485      9520593 :       pe1.ssa_base = op2;
     486      9520593 :       pe1.code = r;
     487      9520593 :       pe1.members = pe2.members;
     488      9520593 :       bitmap_set_bit (pe1.members, v1);
     489              :     }
     490              :   return true;
     491              : }
     492              : 
     493              : // Return the set of partial equivalences associated with NAME.  The bitmap
     494              : // will be NULL if there are none.
     495              : 
     496              : const pe_slice *
     497     64475234 : equiv_oracle::partial_equiv_set (tree name)
     498              : {
     499     64475234 :   int v = SSA_NAME_VERSION (name);
     500    128950468 :   if (v >= (int)m_partial.length ())
     501              :     return NULL;
     502     64475234 :   return &m_partial[v];
     503              : }
     504              : 
     505              : // Query if there is a partial equivalence between SSA1 and SSA2.  Return
     506              : // VREL_VARYING if there is not one.  If BASE is non-null, return the base
     507              : // ssa-name this is a slice of.
     508              : 
     509              : relation_kind
     510    109402056 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
     511              : {
     512    109402056 :   int v1 = SSA_NAME_VERSION (ssa1);
     513    109402056 :   int v2 = SSA_NAME_VERSION (ssa2);
     514              : 
     515    218804112 :   if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
     516              :     return VREL_VARYING;
     517              : 
     518    109400913 :   const pe_slice &pe1 = m_partial[v1];
     519    109400913 :   const pe_slice &pe2 = m_partial[v2];
     520    109400913 :   if (pe1.members && pe2.members == pe1.members)
     521              :     {
     522        36667 :       if (base)
     523            0 :         *base = pe1.ssa_base;
     524        36667 :       return pe_min (pe1.code, pe2.code);
     525              :     }
     526              :   return VREL_VARYING;
     527              : }
     528              : 
     529              : void
     530     21053115 : equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
     531              : {
     532     21053115 :   if (v >= m_name_info.length ())
     533           60 :     m_name_info.safe_grow_cleared (num_ssa_names + 1);
     534              : 
     535     21053115 :   if (!m_name_info[v].m_block_list)
     536      9619101 :     m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
     537              : 
     538     21053115 :   bitmap_set_bit (m_name_info[v].m_block_list, bbi);
     539     21053115 : }
     540              : 
     541              : void
     542     15627263 : equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
     543              : {
     544     15627263 :   bitmap_iterator bi;
     545     15627263 :   unsigned v;
     546              : 
     547     36649965 :   EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
     548     21022702 :     register_equiv_block (v, bb->index);
     549     15627263 : }
     550              : 
     551              : // Find and return the equivalency set for SSA along the dominators of BB.
     552              : // This is the external API.
     553              : 
     554              : const_bitmap
     555    180807448 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
     556              : {
     557              :   // Search the dominator tree for an equivalency.
     558    180807448 :   equiv_chain *equiv = find_equiv_dom (ssa, bb);
     559    180807448 :   if (equiv)
     560     22772071 :     return equiv->m_names;
     561              : 
     562              :   // Otherwise return a cached equiv set containing just this SSA.
     563    158035377 :   unsigned v = SSA_NAME_VERSION (ssa);
     564    158035377 :   if (v >= m_name_info.length ())
     565         9630 :     m_name_info.safe_grow_cleared (num_ssa_names + 1);
     566              : 
     567    158035377 :   if (!m_name_info[v].m_self_equiv)
     568              :     {
     569     39303903 :       m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
     570     39303903 :       bitmap_set_bit (m_name_info[v].m_self_equiv, v);
     571              :     }
     572    158035377 :   return m_name_info[v].m_self_equiv;
     573              : }
     574              : 
     575              : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
     576              : 
     577              : relation_kind
     578            0 : equiv_oracle::query (basic_block bb, tree ssa1, tree ssa2)
     579              : {
     580              :   // If the 2 ssa names share the same equiv set, they are equal.
     581            0 :   if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
     582              :     return VREL_EQ;
     583              : 
     584              :   // Check if there is a partial equivalence.
     585            0 :   return partial_equiv (ssa1, ssa2);
     586              : }
     587              : 
     588              : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
     589              : 
     590              : relation_kind
     591            0 : equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
     592              :                      const_bitmap e2)
     593              : {
     594              :   // If the 2 ssa names share the same equiv set, they are equal.
     595            0 :   if (bitmap_equal_p (e1, e2))
     596            0 :     return VREL_EQ;
     597              :   return VREL_VARYING;
     598              : }
     599              : 
     600              : // If SSA has an equivalence in block BB, find and return it.
     601              : // Otherwise return NULL.
     602              : 
     603              : equiv_chain *
     604    159470552 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
     605              : {
     606    318941104 :   if (bb >= (int)m_equiv.length () || !m_equiv[bb])
     607              :     return NULL;
     608              : 
     609     72051482 :   return m_equiv[bb]->find (ssa);
     610              : }
     611              : 
     612              : // Starting at block BB, walk the dominator chain looking for the nearest
     613              : // equivalence set containing NAME.
     614              : 
     615              : equiv_chain *
     616    201105301 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
     617              : {
     618    201105301 :   unsigned v = SSA_NAME_VERSION (name);
     619              :   // Short circuit looking for names which have no equivalences.
     620              :   // Saves time looking for something which does not exist.
     621    201105301 :   if (!bitmap_bit_p (m_equiv_set, v))
     622              :     return NULL;
     623              : 
     624              :   // NAME has at least once equivalence set, check to see if it has one along
     625              :   // the dominator tree.
     626    161915159 :   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
     627              :     {
     628    159470552 :       equiv_chain *ptr = find_equiv_block (v, bb->index);
     629    159470552 :       if (ptr)
     630              :         return ptr;
     631              :     }
     632              :   return NULL;
     633              : }
     634              : 
     635              : // Register equivalence between ssa_name V and set EQUIV in block BB,
     636              : 
     637              : bitmap
     638        91343 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
     639              : {
     640              :   // V will have an equivalency now.
     641        91343 :   bitmap_set_bit (m_equiv_set, v);
     642              : 
     643              :   // If that equiv chain is in this block, simply use it.
     644        91343 :   if (equiv->m_bb == bb)
     645              :     {
     646        30413 :       bitmap_set_bit (equiv->m_names, v);
     647        30413 :       bitmap_set_bit (m_equiv[bb->index]->m_names, v);
     648              :       // Add BB to V.
     649        30413 :       register_equiv_block (v, bb->index);
     650        30413 :       return NULL;
     651              :     }
     652              : 
     653              :   // Otherwise create an equivalence for this block which is a copy
     654              :   // of equiv, the add V to the set.
     655        60930 :   bitmap b = BITMAP_ALLOC (&m_bitmaps);
     656        60930 :   valid_equivs (b, equiv->m_names, bb);
     657        60930 :   bitmap_set_bit (b, v);
     658              :   // Add BB to the all the equiv names.
     659        60930 :   register_equiv_block (b, bb);
     660        60930 :   return b;
     661              : }
     662              : 
     663              : // Register equivalence between set equiv_1 and equiv_2 in block BB.
     664              : // Return NULL if either name can be merged with the other.  Otherwise
     665              : // return a pointer to the combined bitmap of names.  This allows the
     666              : // caller to do any setup required for a new element.
     667              : 
     668              : bitmap
     669      5281825 : equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
     670              :                               equiv_chain *equiv_2)
     671              : {
     672              :   // If equiv_1 is already in BB, use it as the combined set.
     673      5281825 :   if (equiv_1->m_bb == bb)
     674              :     {
     675      3461484 :       valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
     676              :       // Its hard to delete from a single linked list, so
     677              :       // just clear the second one.
     678      3461484 :       if (equiv_2->m_bb == bb)
     679      1131878 :         bitmap_clear (equiv_2->m_names);
     680              :       else
     681              :         {
     682              :           // Ensure the new names are in the summary for BB.
     683      2329606 :           bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
     684              :           // Add BB to the names in equiv2.
     685      2329606 :           register_equiv_block (equiv_2->m_names, bb);
     686              :         }
     687              :       return NULL;
     688              :     }
     689              :   // If equiv_2 is in BB, use it for the combined set.
     690      1820341 :   if (equiv_2->m_bb == bb)
     691              :     {
     692         2494 :       valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
     693              :       // Ensure the new names are in the summary.
     694         2494 :       bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
     695              :       // Add BB to the names in equiv1.
     696         2494 :       register_equiv_block (equiv_1->m_names, bb);
     697         2494 :       return NULL;
     698              :     }
     699              : 
     700              :   // At this point, neither equivalence is from this block.
     701      1817847 :   bitmap b = BITMAP_ALLOC (&m_bitmaps);
     702      1817847 :   valid_equivs (b, equiv_1->m_names, bb);
     703      1817847 :   valid_equivs (b, equiv_2->m_names, bb);
     704              :   // Add BB to the all the equiv names.
     705      1817847 :   register_equiv_block (b, bb);
     706      1817847 :   return b;
     707              : }
     708              : 
     709              : // Create an equivalency set containing only SSA in its definition block.
     710              : // This is done the first time SSA is registered in an equivalency and blocks
     711              : // any DOM searches past the definition.
     712              : 
     713              : void
     714      9619101 : equiv_oracle::register_initial_def (tree ssa)
     715              : {
     716      9619101 :   if (SSA_NAME_IS_DEFAULT_DEF (ssa))
     717              :     return;
     718      9526638 :   basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
     719              : 
     720              :   // If defining stmt is not in the IL, simply return.
     721      9526638 :   if (!bb)
     722              :     return;
     723      9526637 :   gcc_checking_assert (!find_equiv_dom (ssa, bb));
     724              : 
     725      9526637 :   unsigned v = SSA_NAME_VERSION (ssa);
     726      9526637 :   bitmap_set_bit (m_equiv_set, v);
     727      9526637 :   bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
     728      9526637 :   bitmap_set_bit (equiv_set, v);
     729      9526637 :   add_equiv_to_block (bb, equiv_set);
     730              : }
     731              : 
     732              : // Clear the equivalence lists and partial equivalencs for NAME.
     733              : 
     734              : void
     735       268535 : equiv_oracle::clear (tree name)
     736              : {
     737       268535 :   unsigned v = SSA_NAME_VERSION (name);
     738              :   // Remove NAME from any blocks it is an equivalence in.
     739       268535 :   if (bitmap_bit_p (m_equiv_set, v))
     740              :     {
     741          170 :       gcc_checking_assert (m_name_info[v].m_block_list);
     742          170 :       bitmap_iterator bi;
     743          170 :       unsigned bbi;
     744              : 
     745          442 :       EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
     746              :         {
     747          272 :           if (bbi >= m_equiv.length ())
     748              :             break;
     749          272 :           if (!m_equiv[bbi])
     750            0 :             continue;
     751          272 :           equiv_chain *ptr = m_equiv[bbi]->find (v);
     752          272 :           if (ptr)
     753              :             {
     754          272 :               bitmap_clear_bit (ptr->m_names, v);
     755          272 :               bitmap_clear_bit (m_equiv[bbi]->m_names, v);
     756              :             }
     757              :         }
     758          170 :       bitmap_clear_bit (m_equiv_set, v);
     759          170 :       bitmap_clear (m_name_info[v].m_block_list);
     760              :     }
     761              :   // Eliminate any partial equivs.
     762       268535 :   if (v < m_partial.length ())
     763       208867 :     m_partial[v].members = NULL;
     764       268535 : }
     765              : 
     766              : 
     767              : // Register an equivalence between SSA1 and SSA2 in block BB.
     768              : // The equivalence oracle maintains a vector of equivalencies indexed by basic
     769              : // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
     770              : // a query is made as to what equivalences both names have already, and
     771              : // any preexisting equivalences are merged to create a single equivalence
     772              : // containing all the ssa_names in this basic block.
     773              : // Return false if no new relation is added.
     774              : 
     775              : bool
     776     15904090 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
     777              : {
     778              :   // Process partial equivalencies.
     779     15904090 :   if (relation_partial_equiv_p (k))
     780     10518482 :     return add_partial_equiv (k, ssa1, ssa2);
     781              : 
     782              :   // Only handle equality relations.
     783      5385608 :   if (k != VREL_EQ)
     784              :     return false;
     785              : 
     786      5385608 :   unsigned v1 = SSA_NAME_VERSION (ssa1);
     787      5385608 :   unsigned v2 = SSA_NAME_VERSION (ssa2);
     788              : 
     789              :   // If this is the first time an ssa_name has an equivalency registered
     790              :   // create a self-equivalency record in the def block.
     791      5385608 :   if (!bitmap_bit_p (m_equiv_set, v1))
     792      5203740 :     register_initial_def (ssa1);
     793      5385608 :   if (!bitmap_bit_p (m_equiv_set, v2))
     794      4415361 :     register_initial_def (ssa2);
     795              : 
     796      5385608 :   equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
     797      5385608 :   equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
     798              : 
     799              :   // Check if they are the same set
     800      5385608 :   if (equiv_1 && equiv_1 == equiv_2)
     801              :     return false;
     802              : 
     803      5384140 :   bitmap equiv_set;
     804              : 
     805              :   // Case where we have 2 SSA_NAMEs that are not in any set.
     806      5384140 :   if (!equiv_1 && !equiv_2)
     807              :     {
     808        10972 :       bitmap_set_bit (m_equiv_set, v1);
     809        10972 :       bitmap_set_bit (m_equiv_set, v2);
     810              : 
     811        10972 :       equiv_set = BITMAP_ALLOC (&m_bitmaps);
     812        10972 :       bitmap_set_bit (equiv_set, v1);
     813        10972 :       bitmap_set_bit (equiv_set, v2);
     814              :     }
     815      5373168 :   else if (!equiv_1 && equiv_2)
     816        23210 :     equiv_set = register_equiv (bb, v1, equiv_2);
     817      5349958 :   else if (equiv_1 && !equiv_2)
     818        68133 :     equiv_set = register_equiv (bb, v2, equiv_1);
     819              :   else
     820      5281825 :     equiv_set = register_equiv (bb, equiv_1, equiv_2);
     821              : 
     822              :   // A non-null return is a bitmap that is to be added to the current
     823              :   // block as a new equivalence.
     824      5384140 :   if (!equiv_set)
     825              :     return false;
     826              : 
     827      1889749 :   add_equiv_to_block (bb, equiv_set);
     828      1889749 :   return true;
     829              : }
     830              : 
     831              : // Add an equivalency record in block BB containing bitmap EQUIV_SET.
     832              : // Note the internal caller is responsible for allocating EQUIV_SET properly.
     833              : 
     834              : void
     835     11416386 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
     836              : {
     837     11416386 :   equiv_chain *ptr;
     838              : 
     839              :   // Check if this is the first time a block has an equivalence added.
     840              :   // and create a header block. And set the summary for this block.
     841     11416386 :   limit_check (bb);
     842     11416386 :   if (!m_equiv[bb->index])
     843              :     {
     844      6601335 :       ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
     845              :                                            sizeof (equiv_chain));
     846      6601335 :       ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
     847      6601335 :       bitmap_copy (ptr->m_names, equiv_set);
     848      6601335 :       ptr->m_bb = bb;
     849      6601335 :       ptr->m_next = NULL;
     850      6601335 :       m_equiv[bb->index] = ptr;
     851              :     }
     852              : 
     853              :   // Now create the element for this equiv set and initialize it.
     854     11416386 :   ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
     855     11416386 :   ptr->m_names = equiv_set;
     856     11416386 :   ptr->m_bb = bb;
     857     22832772 :   gcc_checking_assert (bb->index < (int)m_equiv.length ());
     858     11416386 :   ptr->m_next = m_equiv[bb->index]->m_next;
     859     11416386 :   m_equiv[bb->index]->m_next = ptr;
     860     11416386 :   bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
     861              :   // Add BB to the equiv set.
     862     11416386 :   register_equiv_block (equiv_set, bb);
     863     11416386 : }
     864              : 
     865              : // Make sure the BB vector is big enough and grow it if needed.
     866              : 
     867              : void
     868     11416386 : equiv_oracle::limit_check (basic_block bb)
     869              : {
     870     11416386 :   int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
     871     22832772 :   if (i >= (int)m_equiv.length ())
     872           47 :     m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
     873     11416386 : }
     874              : 
     875              : // Dump the equivalence sets in BB to file F.
     876              : 
     877              : void
     878          257 : equiv_oracle::dump (FILE *f, basic_block bb) const
     879              : {
     880          514 :   if (bb->index >= (int)m_equiv.length ())
     881              :     return;
     882              :   // Process equivalences.
     883          257 :   if (m_equiv[bb->index])
     884              :     {
     885            8 :       equiv_chain *ptr = m_equiv[bb->index]->m_next;
     886           18 :       for (; ptr; ptr = ptr->m_next)
     887           10 :         ptr->dump (f);
     888              :     }
     889              :   // Look for partial equivalences defined in this block..
     890        12774 :   for (unsigned i = 0; i < num_ssa_names; i++)
     891              :     {
     892        12517 :       tree name = ssa_name (i);
     893        17757 :       if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
     894         7277 :         continue;
     895         5240 :       if (i >= m_partial.length ())
     896              :         break;
     897         5240 :      tree base = m_partial[i].ssa_base;
     898         5240 :       if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
     899              :         {
     900           42 :           relation_kind k = partial_equiv (name, base);
     901           42 :           if (k != VREL_VARYING)
     902              :             {
     903           42 :               value_relation vr (k, name, base);
     904           42 :               fprintf (f, "Partial equiv ");
     905           42 :               vr.dump (f);
     906           42 :               fputc ('\n',f);
     907              :             }
     908              :         }
     909              :     }
     910              : }
     911              : 
     912              : // Dump all equivalence sets known to the oracle.
     913              : 
     914              : void
     915            0 : equiv_oracle::dump (FILE *f) const
     916              : {
     917            0 :   fprintf (f, "Equivalency dump\n");
     918            0 :   for (unsigned i = 0; i < m_equiv.length (); i++)
     919            0 :     if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
     920              :       {
     921            0 :         fprintf (f, "BB%d\n", i);
     922            0 :         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
     923              :       }
     924            0 : }
     925              : 
     926              : 
     927              : // --------------------------------------------------------------------------
     928              : 
     929              : // Adjust the relation by Swapping the operands and relation.
     930              : 
     931              : void
     932            0 : value_relation::swap ()
     933              : {
     934            0 :   related = relation_swap (related);
     935            0 :   tree tmp = name1;
     936            0 :   name1 = name2;
     937            0 :   name2 = tmp;
     938            0 : }
     939              : 
     940              : // Perform an intersection between 2 relations. *this &&= p.
     941              : // Return false if the relations cannot be intersected.
     942              : 
     943              : bool
     944     12116809 : value_relation::intersect (value_relation &p)
     945              : {
     946              :   // Save previous value
     947     12116809 :   relation_kind old = related;
     948              : 
     949     12116809 :   if (p.op1 () == op1 () && p.op2 () == op2 ())
     950     12023988 :     related = relation_intersect (kind (), p.kind ());
     951        92821 :   else if (p.op2 () == op1 () && p.op1 () == op2 ())
     952        92821 :     related = relation_intersect (kind (), relation_swap (p.kind ()));
     953              :   else
     954              :     return false;
     955              : 
     956     12116809 :   return old != related;
     957              : }
     958              : 
     959              : // Perform a union between 2 relations. *this ||= p.
     960              : 
     961              : bool
     962            0 : value_relation::union_ (value_relation &p)
     963              : {
     964              :   // Save previous value
     965            0 :   relation_kind old = related;
     966              : 
     967            0 :   if (p.op1 () == op1 () && p.op2 () == op2 ())
     968            0 :     related = relation_union (kind(), p.kind());
     969            0 :   else if (p.op2 () == op1 () && p.op1 () == op2 ())
     970            0 :     related = relation_union (kind(), relation_swap (p.kind ()));
     971              :   else
     972              :     return false;
     973              : 
     974            0 :   return old != related;
     975              : }
     976              : 
     977              : // Identify and apply any transitive relations between REL
     978              : // and THIS.  Return true if there was a transformation.
     979              : 
     980              : bool
     981     55814563 : value_relation::apply_transitive (const value_relation &rel)
     982              : {
     983     55814563 :   relation_kind k = VREL_VARYING;
     984              : 
     985              :   // Identify any common operand, and normalize the relations to
     986              :   // the form : A < B  B < C produces A < C
     987     55814563 :   if (rel.op1 () == name2)
     988              :     {
     989              :       // A < B   B < C
     990     55814563 :       if (rel.op2 () == name1)
     991              :         return false;
     992     42163728 :       k = relation_transitive (kind (), rel.kind ());
     993     42163728 :       if (k != VREL_VARYING)
     994              :         {
     995     29459207 :           related = k;
     996     29459207 :           name2 = rel.op2 ();
     997     29459207 :           return true;
     998              :         }
     999              :     }
    1000            0 :   else if (rel.op1 () == name1)
    1001              :     {
    1002              :       // B > A   B < C
    1003            0 :       if (rel.op2 () == name2)
    1004              :         return false;
    1005            0 :       k = relation_transitive (relation_swap (kind ()), rel.kind ());
    1006            0 :       if (k != VREL_VARYING)
    1007              :         {
    1008            0 :           related = k;
    1009            0 :           name1 = name2;
    1010            0 :           name2 = rel.op2 ();
    1011            0 :           return true;
    1012              :         }
    1013              :     }
    1014            0 :   else if (rel.op2 () == name2)
    1015              :     {
    1016              :        // A < B   C > B
    1017            0 :        if (rel.op1 () == name1)
    1018              :          return false;
    1019            0 :       k = relation_transitive (kind (), relation_swap (rel.kind ()));
    1020            0 :       if (k != VREL_VARYING)
    1021              :         {
    1022            0 :           related = k;
    1023            0 :           name2 = rel.op1 ();
    1024            0 :           return true;
    1025              :         }
    1026              :     }
    1027            0 :   else if (rel.op2 () == name1)
    1028              :     {
    1029              :       // B > A  C > B
    1030            0 :       if (rel.op1 () == name2)
    1031              :         return false;
    1032            0 :       k = relation_transitive (relation_swap (kind ()),
    1033              :                                relation_swap (rel.kind ()));
    1034            0 :       if (k != VREL_VARYING)
    1035              :         {
    1036            0 :           related = k;
    1037            0 :           name1 = name2;
    1038            0 :           name2 = rel.op1 ();
    1039            0 :           return true;
    1040              :         }
    1041              :     }
    1042              :   return false;
    1043              : }
    1044              : 
    1045              : // Create a trio from this value relation given LHS, OP1 and OP2.
    1046              : 
    1047              : relation_trio
    1048     89705248 : value_relation::create_trio (tree lhs, tree op1, tree op2)
    1049              : {
    1050     89705248 :   relation_kind lhs_1;
    1051     89705248 :   if (lhs == name1 && op1 == name2)
    1052       122122 :     lhs_1 = related;
    1053     89583126 :   else if (lhs == name2 && op1 == name1)
    1054       378887 :     lhs_1 = relation_swap (related);
    1055              :   else
    1056              :     lhs_1 = VREL_VARYING;
    1057              : 
    1058     89705248 :   relation_kind lhs_2;
    1059     89705248 :   if (lhs == name1 && op2 == name2)
    1060       161733 :     lhs_2 = related;
    1061     89543515 :   else if (lhs == name2 && op2 == name1)
    1062       834191 :     lhs_2 = relation_swap (related);
    1063              :   else
    1064              :     lhs_2 = VREL_VARYING;
    1065              : 
    1066     89705248 :   relation_kind op_op;
    1067     89705248 :   if (op1 == name1 && op2 == name2)
    1068     59658688 :     op_op = related;
    1069     30046560 :   else if (op1 == name2 && op2 == name1)
    1070            0 :     op_op = relation_swap (related);
    1071     30046560 :   else if  (op1 == op2)
    1072              :     op_op = VREL_EQ;
    1073              :   else
    1074     30018044 :     op_op = VREL_VARYING;
    1075              : 
    1076     89705248 :   return relation_trio (lhs_1, lhs_2, op_op);
    1077              : }
    1078              : 
    1079              : // Dump the relation to file F.
    1080              : 
    1081              : void
    1082        39751 : value_relation::dump (FILE *f) const
    1083              : {
    1084        39751 :   if (!name1 || !name2)
    1085              :     {
    1086            0 :       fprintf (f, "no relation registered");
    1087            0 :       return;
    1088              :     }
    1089        39751 :   fputc ('(', f);
    1090        39751 :   print_generic_expr (f, op1 (), TDF_SLIM);
    1091        39751 :   print_relation (f, kind ());
    1092        39751 :   print_generic_expr (f, op2 (), TDF_SLIM);
    1093        39751 :   fputc(')', f);
    1094              : }
    1095              : 
    1096              : // This container is used to link relations in a chain.
    1097              : 
    1098              : class relation_chain : public value_relation
    1099              : {
    1100              : public:
    1101              :   relation_chain *m_next;
    1102              : };
    1103              : 
    1104              : // Given relation record PTR in block BB, return the next relation in the
    1105              : // list.  If PTR is NULL, retrieve the first relation in BB.
    1106              : // If NAME is sprecified, return only relations which include NAME.
    1107              : // Return NULL when there are no relations left.
    1108              : 
    1109              : relation_chain *
    1110           90 : dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
    1111              :                            tree name) const
    1112              : {
    1113           90 :   relation_chain *p;
    1114              :   // No value_relation pointer is used to initialize the iterator.
    1115           90 :   if (!ptr)
    1116              :     {
    1117           39 :       int bbi = bb->index;
    1118           78 :       if (bbi >= (int)m_relations.length())
    1119              :         return NULL;
    1120              :       else
    1121           39 :         p = m_relations[bbi].m_head;
    1122              :     }
    1123              :   else
    1124           51 :     p = ptr->m_next;
    1125              : 
    1126           90 :   if (name)
    1127            0 :     for ( ; p; p = p->m_next)
    1128            0 :       if (p->op1 () == name || p->op2 () == name)
    1129              :         break;
    1130              :   return p;
    1131              : }
    1132              : 
    1133              : // Instantiate a block relation iterator to iterate over the relations
    1134              : // on exit from block BB in ORACLE.  Limit this to relations involving NAME
    1135              : // if specified.  Return the first such relation in VR if there is one.
    1136              : 
    1137           39 : block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
    1138              :                                                   basic_block bb,
    1139              :                                                   value_relation &vr,
    1140              :                                                   tree name)
    1141              : {
    1142           39 :   m_oracle = oracle;
    1143           39 :   m_bb = bb;
    1144           39 :   m_name = name;
    1145           39 :   m_ptr = oracle->next_relation (bb, NULL, m_name);
    1146           39 :   if (m_ptr)
    1147              :     {
    1148           39 :       m_done = false;
    1149           39 :       vr = *m_ptr;
    1150              :     }
    1151              :   else
    1152            0 :     m_done = true;
    1153           39 : }
    1154              : 
    1155              : // Retrieve the next relation from the iterator and return it in VR.
    1156              : 
    1157              : void
    1158           51 : block_relation_iterator::get_next_relation (value_relation &vr)
    1159              : {
    1160           51 :   m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
    1161           51 :   if (m_ptr)
    1162              :     {
    1163           12 :       vr = *m_ptr;
    1164           12 :       if (m_name)
    1165              :         {
    1166            0 :           if (vr.op1 () != m_name)
    1167              :             {
    1168            0 :               gcc_checking_assert (vr.op2 () == m_name);
    1169            0 :               vr.swap ();
    1170              :             }
    1171              :         }
    1172              :     }
    1173              :   else
    1174           39 :     m_done = true;
    1175           51 : }
    1176              : 
    1177              : // ------------------------------------------------------------------------
    1178              : 
    1179              : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
    1180              : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
    1181              : 
    1182              : relation_kind
    1183     88020835 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
    1184              : {
    1185     88020835 :   if (!m_names)
    1186              :     return VREL_VARYING;
    1187              : 
    1188              :   // If both b1 and b2 aren't referenced in this block, cant be a relation
    1189     62753890 :   if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
    1190              :     return VREL_VARYING;
    1191              : 
    1192              :   // Search for the first relation that contains BOTH an element from B1
    1193              :   // and B2, and return that relation.
    1194      8250916 :   for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
    1195              :     {
    1196      7240252 :       unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
    1197      7240252 :       unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
    1198      7240252 :       if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
    1199      3298618 :         return ptr->kind ();
    1200      3941634 :       if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
    1201       169468 :         return relation_swap (ptr->kind ());
    1202              :     }
    1203              : 
    1204              :   return VREL_VARYING;
    1205              : }
    1206              : 
    1207              : // ------------------------------------------------------------------------
    1208              : // frontier_data methods - what one side of a bidirectional search knows.
    1209              : 
    1210              : // Construct frontier data allocating the bitmap from OBSTACK and side flag RHS.
    1211              : 
    1212     55178076 : frontier_data::frontier_data (bitmap_obstack *obstack, bool rhs)
    1213              : {
    1214     55178076 :   m_known.create (0);
    1215     55178076 :   m_visited = BITMAP_ALLOC (obstack);
    1216     55178076 :   m_root = NULL_TREE;
    1217     55178076 :   m_rhs = rhs;
    1218     55178076 : }
    1219              : 
    1220              : // Record that the root of this search is related to ssa version V by REL.
    1221              : 
    1222              : void
    1223     74933760 : frontier_data::set_known (unsigned v, relation_kind rel)
    1224              : {
    1225     74933760 :   if (m_known.length () <= v)
    1226      8453086 :     m_known.safe_grow_cleared (num_ssa_names + 1);
    1227     74933760 :   m_known[v] = rel;
    1228     74933760 : }
    1229              : 
    1230              : // Return what the root of this search is known to be relative to ssa version V.
    1231              : 
    1232              : relation_kind
    1233     34668434 : frontier_data::known_relation (unsigned v) const
    1234              : {
    1235     34668434 :   if (v < m_known.length ())
    1236     34668434 :     return m_known[v];
    1237              :   return VREL_VARYING;
    1238              : }
    1239              : 
    1240              : // Reset for the next search.  Only the entries which were actually set need
    1241              : // to be put back, and m_visited lists exactly those.
    1242              : 
    1243              : void
    1244     55452882 : frontier_data::clear_search ()
    1245              : {
    1246     55452882 :   unsigned i;
    1247     55452882 :   bitmap_iterator bi;
    1248    130361150 :   EXECUTE_IF_SET_IN_BITMAP (m_visited, 0, i, bi)
    1249              :     {
    1250    149816536 :       if (i < m_known.length ())
    1251     74908268 :         m_known[i] = VREL_VARYING;
    1252              :     }
    1253     55452882 :   bitmap_clear (m_visited);
    1254     55452882 :   m_root = NULL_TREE;
    1255     55452882 : }
    1256              : 
    1257              : // ------------------------------------------------------------------------
    1258              : // Instantiate a relation oracle.
    1259              : 
    1260     55178076 : dom_oracle::dom_oracle () : m_lhs_search (&m_bitmaps, false),
    1261     27589038 :                             m_rhs_search (&m_bitmaps, true)
    1262              : {
    1263     27589038 :   m_relations.create (0);
    1264     27589038 :   m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
    1265     27589038 :   m_relation_set = BITMAP_ALLOC (&m_bitmaps);
    1266     27589038 :   m_block_list.create (0);
    1267     55178076 :   m_block_list.safe_grow_cleared (num_ssa_names + 1);
    1268     27589038 :   m_tmp = BITMAP_ALLOC (&m_bitmaps);
    1269     27589038 :   m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
    1270     27589038 :   m_near.create (0);
    1271     27589038 :   m_worklist.create (0);
    1272     27589038 :   m_wl_ix = 0;
    1273     27589038 : }
    1274              : 
    1275              : // Destruct a relation oracle.
    1276              : 
    1277     55178076 : dom_oracle::~dom_oracle ()
    1278              : {
    1279     27589038 :   m_worklist.release ();
    1280     27589038 :   m_near.release ();
    1281     27589038 :   m_block_list.release ();
    1282     27589038 :   m_relations.release ();
    1283     55178076 : }
    1284              : 
    1285              : // Remove any relations with NAME from this list.
    1286              : 
    1287              : void
    1288          717 : relation_chain_head::clear (tree name)
    1289              : {
    1290          717 :   unsigned v = SSA_NAME_VERSION (name);
    1291          717 :   if (!m_names || !bitmap_bit_p (m_names, v))
    1292              :     return;
    1293              : 
    1294          717 :   relation_chain *ptr, *last = NULL;;
    1295              : 
    1296         1465 :   for (ptr = m_head; ptr; ptr = ptr->m_next)
    1297              :     {
    1298          748 :       tree op1 = ptr->op1 ();
    1299          748 :       tree op2 = ptr->op2 ();
    1300              :       // Delink any elements with NAME.
    1301          748 :       if (op1 == name || op2 == name)
    1302              :         {
    1303          672 :           if (!last)
    1304          613 :             m_head = ptr->m_next;
    1305              :           else
    1306           59 :             last->m_next = ptr->m_next;
    1307          672 :           m_num_relations--;
    1308              :         }
    1309              :       else
    1310              :         last = ptr;
    1311              :     }
    1312              :   // And remove name from the possible relations in this block bitfield.
    1313          717 :   bitmap_clear_bit (m_names, v);
    1314              : }
    1315              : 
    1316              : // Remove any relations involving NAME from the DOM oracle
    1317              : 
    1318              : void
    1319       268535 : dom_oracle::clear (tree name)
    1320              : {
    1321       268535 :   equiv_oracle::clear (name);
    1322       268535 :   unsigned v = SSA_NAME_VERSION (name);
    1323       268535 :   if (bitmap_bit_p (m_relation_set, v))
    1324              :     {
    1325          475 :       gcc_checking_assert (m_block_list[v]);
    1326          475 :       bitmap_iterator bi;
    1327          475 :       unsigned bbi;
    1328              : 
    1329         1192 :       EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
    1330              :         {
    1331          717 :           if (bbi >= m_relations.length())
    1332              :             break;
    1333          717 :           m_relations[bbi].clear (name);
    1334              :         }
    1335          475 :       bitmap_clear_bit (m_relation_set, v);
    1336          475 :       bitmap_clear (m_block_list[v]);
    1337              :     }
    1338       268535 : }
    1339              : 
    1340              : // Register relation K between ssa_name OP1 and OP2 on STMT.
    1341              : // Return false if no new relation is added.
    1342              : 
    1343              : bool
    1344     34419937 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
    1345              : {
    1346     34419937 :   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
    1347     34419937 :   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
    1348     34419937 :   gcc_checking_assert (stmt && gimple_bb (stmt));
    1349              : 
    1350              :   // Don't register lack of a relation.
    1351     34419937 :   if (k == VREL_VARYING)
    1352              :     return false;
    1353              : 
    1354              :   // If an equivalence is being added between a PHI and one of its arguments
    1355              :   // make sure that that argument is not defined in the same block.
    1356              :   // This can happen along back edges and the equivalence will not be
    1357              :   // applicable as it would require a use before def.
    1358     34419937 :   if (k == VREL_EQ && is_a<gphi *> (stmt))
    1359              :     {
    1360      2156475 :       tree phi_def = gimple_phi_result (stmt);
    1361      2156475 :       gcc_checking_assert (phi_def == op1 || phi_def == op2);
    1362      2156475 :       tree arg = op2;
    1363      2156475 :       if (phi_def == op2)
    1364            0 :         arg = op1;
    1365      2156475 :       if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
    1366              :         return false;
    1367              :     }
    1368              : 
    1369              :   // If the LHS of a statement has already been processed and an equivalence
    1370              :   // registered, do not register another one.  See PR 124809.
    1371     82847603 :   if (m_lhs_equiv_set_p && relation_equiv_p (k)
    1372     49076515 :       && gimple_get_lhs (stmt) == op1)
    1373              :     {
    1374     14656578 :       if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
    1375              :         return false;
    1376              :     }
    1377     33771088 :   bool ret = record (gimple_bb (stmt), k, op1, op2);
    1378              : 
    1379     33771088 :   if (ret && dump_file && (dump_flags & TDF_DETAILS))
    1380              :     {
    1381        39232 :       value_relation vr (k, op1, op2);
    1382        39232 :       fprintf (dump_file, " Registering value_relation ");
    1383        39232 :       vr.dump (dump_file);
    1384        39232 :       fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
    1385        39232 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1386              :     }
    1387              :   return ret;
    1388              : }
    1389              : 
    1390              : // Register relation K between ssa_name OP1 and OP2 on edge E.
    1391              : // Return false if no new relation is added.
    1392              : 
    1393              : bool
    1394      7459190 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
    1395              : {
    1396      7459190 :   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
    1397      7459190 :   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
    1398              : 
    1399              :   // Do not register lack of relation, or blocks which have more than
    1400              :   // edge E for a predecessor.
    1401      7459190 :   if (k == VREL_VARYING || !single_pred_p (e->dest))
    1402              :     return false;
    1403              : 
    1404      7459190 :   bool ret = record (e->dest, k, op1, op2);
    1405              : 
    1406      7459190 :   if (ret && dump_file && (dump_flags & TDF_DETAILS))
    1407              :     {
    1408          122 :       value_relation vr (k, op1, op2);
    1409          122 :       fprintf (dump_file, " Registering value_relation ");
    1410          122 :       vr.dump (dump_file);
    1411          122 :       fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
    1412              :     }
    1413              :   return ret;
    1414              : }
    1415              : 
    1416              : // Register relation K between OP! and OP2 in block BB.
    1417              : // This creates the record and searches for existing records in the dominator
    1418              : // tree to merge with.  Return false if no new relation is added.
    1419              : 
    1420              : bool
    1421     40168164 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
    1422              : {
    1423              :   // If the 2 ssa_names are the same, do nothing.  An equivalence is implied,
    1424              :   // and no other relation makes sense.
    1425     40168164 :   if (op1 == op2)
    1426              :     return false;
    1427              : 
    1428              :   // Do not register an impossible relation.
    1429     40157302 :   if (k == VREL_UNDEFINED)
    1430              :     return false;
    1431              : 
    1432              :   // Equivalencies are handled by the equivalence oracle.
    1433     40157302 :   if (relation_equiv_p (k))
    1434     15904090 :     return equiv_oracle::record (bb, k, op1, op2);
    1435              :   else
    1436              :     {
    1437     24253212 :       relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
    1438     24253212 :       return ptr != NULL;
    1439              :     }
    1440              : }
    1441              : 
    1442              : void
    1443     46953976 : dom_oracle::record_relation_block (unsigned v, unsigned bbi)
    1444              : {
    1445     46953976 :   if (v>= m_block_list.length ())
    1446        10504 :     m_block_list.safe_grow_cleared (num_ssa_names + 1);
    1447              : 
    1448     46953976 :   if (!m_block_list[v])
    1449     32289528 :     m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
    1450              : 
    1451     46953976 :   bitmap_set_bit (m_block_list[v], bbi);
    1452     46953976 : }
    1453              : 
    1454              : // Register relation K between OP1 and OP2 in block BB by creating a new
    1455              : // record.  It is an error for there to be an existing record.
    1456              : // Return the record, or NULL if no record was created.
    1457              : 
    1458              : relation_chain *
    1459     23520032 : dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
    1460              :                                    tree op2)
    1461              : {
    1462     23520032 :   int bbi = bb->index;
    1463              : 
    1464     47040064 :   if (bbi >= (int)m_relations.length())
    1465          126 :     m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
    1466              : 
    1467     23520032 :   if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
    1468              :     return NULL;
    1469     23476988 :   m_relations[bbi].m_num_relations++;
    1470              :   // Check for an existing relation further up the DOM chain.
    1471              :   // By including dominating relations, The first one found in any search
    1472              :   // will be the aggregate of all the previous ones.
    1473              : 
    1474     23476988 :   relation_chain *ptr;
    1475              : 
    1476              :   // Summary bitmap indicating what ssa_names have relations in this BB.
    1477     23476988 :   bitmap bm = m_relations[bbi].m_names;
    1478     23476988 :   if (!bm)
    1479     16817459 :     bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
    1480     23476988 :   unsigned v1 = SSA_NAME_VERSION (op1);
    1481     23476988 :   unsigned v2 = SSA_NAME_VERSION (op2);
    1482              : 
    1483              :   // Assert there is no existing relation.
    1484     23476988 :   gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
    1485              :                        == VREL_VARYING);
    1486              : 
    1487     23476988 :   bitmap_set_bit (bm, v1);
    1488     23476988 :   bitmap_set_bit (bm, v2);
    1489     23476988 :   bitmap_set_bit (m_relation_set, v1);
    1490     23476988 :   bitmap_set_bit (m_relation_set, v2);
    1491     23476988 :   record_relation_block (v1, bbi);
    1492     23476988 :   record_relation_block (v2, bbi);
    1493              : 
    1494     23476988 :   ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
    1495              :                                           sizeof (relation_chain));
    1496     23476988 :   ptr->set_relation (k, op1, op2);
    1497     23476988 :   ptr->m_next = m_relations[bbi].m_head;
    1498     23476988 :   m_relations[bbi].m_head = ptr;
    1499     23476988 :   return ptr;
    1500              : }
    1501              : 
    1502              : // Register relation K between OP1 and OP2 in block BB by searching the
    1503              : // dominator tree for any existing record to merge with.  If there were
    1504              : // none, create a new record.
    1505              : // Return the record, or NULL if no record was found or created.
    1506              : 
    1507              : relation_chain *
    1508     35636843 : dom_oracle::search_and_merge_relation (basic_block bb, relation_kind k,
    1509              :                                        tree op1, tree op2)
    1510              : {
    1511              :   // Check for invalid relations to register.
    1512     35636843 :   gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED
    1513              :                        && k != VREL_EQ);
    1514              : 
    1515     35636843 :   relation_chain *ptr;
    1516     35636843 :   relation_kind curr = find_relation_block (bb->index, op1, op2, &ptr);
    1517              : 
    1518              :   // If there is an existing relation in this block, just intersect with it.
    1519     35636843 :   if (curr != VREL_VARYING)
    1520              :     {
    1521              :       // If K contradicts what is already recorded, the block is unreachable.
    1522              :       // Leave the existing relation alone rather than replacing it with
    1523              :       // UNDEFINED, matching what the dominator merge below does.
    1524     12116811 :       if (relation_intersect (curr, k) == VREL_UNDEFINED)
    1525              :         return NULL;
    1526              :       // If there was no change, return no record.
    1527     12116809 :       value_relation vr (k, op1, op2);
    1528     12116809 :       if (!ptr->intersect (vr))
    1529              :         return NULL;
    1530       215452 :       return ptr;
    1531              :     }
    1532              : 
    1533              :   // Create the relation in this block.
    1534     23520032 :   ptr = create_relation_in_bb (bb, k, op1, op2);
    1535     23520032 :   if (ptr)
    1536              :     {
    1537              :       // Check for an existing relation further up the DOM chain.
    1538              :       // By including dominating relations, The first one found in any search
    1539              :       // will be the aggregate of all the previous ones.
    1540     23476988 :       curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
    1541              :                                 op1, op2);
    1542     23476988 :       if (curr != VREL_VARYING)
    1543              :         {
    1544      2992586 :           curr = relation_intersect (curr, k);
    1545              :           // Intersect the new relation with the existing one, unless the
    1546              :           // result is UNDEFINED.  Then just leave it.
    1547      2992586 :           if (curr != k && curr != VREL_UNDEFINED)
    1548       158627 :             ptr->set_relation (curr, op1, op2);
    1549              :         }
    1550              :     }
    1551     23520032 :   return ptr;
    1552              : }
    1553              : 
    1554              : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
    1555              : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
    1556              : 
    1557              : relation_kind
    1558     34679649 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
    1559              :                                       const_bitmap b2) const
    1560              : {
    1561     34679649 :   if (bb >= m_relations.length())
    1562              :     return VREL_VARYING;
    1563              : 
    1564     34679649 :   return m_relations[bb].find_relation (b1, b2);
    1565              : }
    1566              : 
    1567              : // Search the DOM tree for a relation between an element of equivalency set B1
    1568              : // and B2, starting with block BB.
    1569              : 
    1570              : relation_kind
    1571     12109701 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
    1572              : {
    1573     12109701 :   relation_kind r;
    1574     12109701 :   if (bitmap_equal_p (b1, b2))
    1575              :     return VREL_EQ;
    1576              : 
    1577              :   // If either name does not occur in a relation anywhere, there isn't one.
    1578     12109701 :   if (!bitmap_intersect_p (m_relation_set, b1)
    1579     12109701 :       || !bitmap_intersect_p (m_relation_set, b2))
    1580              :     return VREL_VARYING;
    1581              : 
    1582              :   // Search each block in the DOM tree checking.
    1583     36472396 :   for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
    1584              :     {
    1585     34679649 :       r = find_relation_block (bb->index, b1, b2);
    1586     34679649 :       if (r != VREL_VARYING)
    1587              :         return r;
    1588              :     }
    1589              :   return VREL_VARYING;
    1590              : 
    1591              : }
    1592              : 
    1593              : // Find a relation in block BB between ssa version V1 and V2.  If a relation
    1594              : // is found, return a pointer to the chain object in OBJ.
    1595              : 
    1596              : relation_kind
    1597    673190407 : dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
    1598              :                                      relation_chain **obj) const
    1599              : {
    1600   1346380814 :   if (bb >= (int)m_relations.length())
    1601              :     return VREL_VARYING;
    1602              : 
    1603    673178566 :   const_bitmap bm = m_relations[bb].m_names;
    1604    673178566 :   if (!bm)
    1605              :     return VREL_VARYING;
    1606              : 
    1607    273763596 :   unsigned v1 = SSA_NAME_VERSION (ssa1);
    1608    273763596 :   unsigned v2 = SSA_NAME_VERSION (ssa2);
    1609              : 
    1610              :   // If both b1 and b2 aren't referenced in this block, cant be a relation
    1611    273763596 :   if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
    1612              :     return VREL_VARYING;
    1613              : 
    1614     15402728 :   relation_chain *ptr;
    1615     24373225 :   for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
    1616              :     {
    1617     24079894 :       tree op1 = ptr->op1 ();
    1618     24079894 :       tree op2 = ptr->op2 ();
    1619     24079894 :       if (ssa1 == op1 && ssa2 == op2)
    1620              :         {
    1621     14919504 :           if (obj)
    1622     12023990 :             *obj = ptr;
    1623     14919504 :           return ptr->kind ();
    1624              :         }
    1625      9160390 :       if (ssa1 == op2 && ssa2 == op1)
    1626              :         {
    1627       189893 :           if (obj)
    1628        92821 :             *obj = ptr;
    1629       189893 :           return relation_swap (ptr->kind ());
    1630              :         }
    1631              :     }
    1632              : 
    1633              :   return VREL_VARYING;
    1634              : }
    1635              : 
    1636              : // See if a relation can be found between SSA1 and SSA2 in basic block BB based
    1637              : // on values as they exist in basic block ORIG.   This will only occur
    1638              : // if SSA1 and SSA2 occur in the same statement together.
    1639              : 
    1640              : relation_kind
    1641     27726441 : dom_oracle::recomputed_relation (basic_block orig_bb, tree ssa1,
    1642              :                                  tree ssa2) const
    1643              : {
    1644     27726441 :   if (ssa1 == ssa2)
    1645              :     return VREL_EQ;
    1646     27726441 :   if (!orig_bb)
    1647              :     return VREL_VARYING;
    1648     55452882 :   gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
    1649     27726441 :   if (!gori_ssa)
    1650              :     return VREL_VARYING;
    1651     40559552 :   gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
    1652              : 
    1653              :   // Both ssa1 and ssa2 must be exported somewhere.
    1654     20279776 :   if (!gori_ssa->is_export_p (ssa1) || !gori_ssa->is_export_p (ssa2))
    1655              :     return VREL_VARYING;
    1656              : 
    1657     13632017 :   relation_kind result = VREL_VARYING;
    1658     13632017 :   use_operand_p use_p;
    1659     13632017 :   imm_use_iterator iter;
    1660              : 
    1661              :   // Any statement with both SSA1 and SSA2 as operands may imply a relation
    1662              :   // between them, once the range of its LHS at ORIG_BB is known.
    1663    101059792 :   FOR_EACH_IMM_USE_FAST (use_p, iter, ssa1)
    1664              :     {
    1665     87427775 :       bool reversed = false;
    1666     87427775 :       gimple *s = USE_STMT (use_p);
    1667              : 
    1668              :       // S must be a binary assignment LHS = op1 op2
    1669     87427775 :       if (!is_gimple_assign (s) || gimple_num_ops (s) != 3)
    1670     87245154 :         continue;
    1671              : 
    1672              :       // S must strictly dominate ORIG_BB.  DOMINATED_BY_P is block granular,
    1673              :       // so the same-block case must be excluded.
    1674     12006887 :       basic_block sbb = gimple_bb (s);
    1675     21632727 :       if (!sbb || sbb == orig_bb
    1676     12006887 :           || !dominated_by_p (CDI_DOMINATORS, orig_bb, sbb))
    1677      9625840 :         continue;
    1678              : 
    1679      2381047 :       gimple_range_op_handler s_handler (s);
    1680      2381047 :       if (!s_handler)
    1681           83 :         continue;
    1682              : 
    1683      2380964 :       if (s_handler.operand1 () == ssa1)
    1684              :         {
    1685              :           // op1 == ssa1, move on if op2 != ssa2.
    1686      1803099 :           if (s_handler.operand2 () != ssa2)
    1687      1602845 :             continue;
    1688              :         }
    1689              :       // Otherwise only move on if op1 == ssa2 && op2 == ssa1.
    1690       577865 :       else if (s_handler.operand1 () != ssa2 || s_handler.operand2 () != ssa1)
    1691       520255 :         continue;
    1692              :       else
    1693              :         reversed = true;
    1694              : 
    1695              : 
    1696              :       // Find the outgoing edge of SBB which must have been taken to reach
    1697              :       // ORIG_BB.  SINGLE_PRED_P is required as well as dominance: if E->dest
    1698              :       // has another predecessor, it can dominate ORIG_BB via a path which
    1699              :       // never traversed E, and E's range would not apply.
    1700              : 
    1701       257864 :       edge e = NULL, se;
    1702       257864 :       edge_iterator ei;
    1703       425322 :       FOR_EACH_EDGE (se, ei, sbb->succs)
    1704       551399 :       if (single_pred_p (se->dest)
    1705       383941 :           && dominated_by_p (CDI_DOMINATORS, orig_bb, se->dest))
    1706              :         {
    1707              :           e = se;
    1708              :           break;
    1709              :         }
    1710       257864 :       if (!e)
    1711        41381 :         continue;
    1712              : 
    1713       216483 :       int_range_max edge_range;
    1714       216483 :       gimple *stmt = gori.edge_range_p (edge_range, e);
    1715       216483 :       if (!stmt)
    1716         1869 :         continue;
    1717              : 
    1718              :       // Walk back from the terminator of SBB towards S, recalculating each
    1719              :       // value as it would be in ORIG_BB rather than as it is on E.  This is
    1720              :       // the whole point: RANGE_ON_ENTRY cannot supply S's LHS at ORIG_BB
    1721              :       // because it evaluates each dominating edge using the values available
    1722              :       // at that edge's source.
    1723       214614 :       tree lhs_s = s_handler.lhs ();
    1724       214614 :       value_range lhs_range (edge_range);
    1725              : 
    1726       771629 :       while (stmt && stmt != s)
    1727              :         {
    1728       374394 :           bool ret;
    1729       374394 :           gimple_range_op_handler handler (stmt);
    1730       374394 :           if (!handler)
    1731              :             break;
    1732              : 
    1733       373648 :           tree op1 = handler.operand1 ();
    1734       373648 :           tree op2 = handler.operand2 ();
    1735       373648 :           value_range op1_range (TREE_TYPE (op1));
    1736       373648 :           value_range op2_range;
    1737              : 
    1738              :           // Follow the operand whose dependency chain reaches S's LHS.
    1739       373648 :           bool op1_dep = gimple_range_ssa_p (op1)
    1740       373648 :                          && (op1 == lhs_s || gori_ssa->in_chain_p (lhs_s, op1));
    1741       373648 :           bool op2_dep = gimple_range_ssa_p (op2)
    1742       373648 :                          && (op2 == lhs_s || gori_ssa->in_chain_p (lhs_s, op2));
    1743       373648 :           if (op1_dep == op2_dep)
    1744              :             break;
    1745              : 
    1746       346015 :           if (op1_dep)
    1747              :             {
    1748       233960 :               if (!op2)
    1749        28015 :                 ret = handler.calc_op1 (op1_range, lhs_range);
    1750              :               else
    1751              :                 {
    1752       205945 :                   op2_range.set_range_class (TREE_TYPE (op2));
    1753       411890 :                   get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
    1754              :                                                           op2);
    1755       205945 :                   ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
    1756              :                 }
    1757       233960 :               if (!ret)
    1758              :                 break;
    1759       230658 :               lhs_range = op1_range;
    1760       230658 :               stmt = SSA_NAME_DEF_STMT (op1);
    1761              :             }
    1762              :           else
    1763              :             {
    1764       112055 :               op2_range.set_range_class (TREE_TYPE (op2));
    1765       224110 :               get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
    1766       112055 :               ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
    1767       112055 :               if (!ret)
    1768              :                 break;
    1769       111743 :               lhs_range = op2_range;
    1770       111743 :               stmt = SSA_NAME_DEF_STMT (op2);
    1771              :             }
    1772              : 
    1773              :           // Bail if the chain leaves SBB.
    1774       342401 :           if (!stmt || gimple_bb (stmt) != sbb)
    1775              :             break;
    1776       373648 :         }
    1777              : 
    1778       214614 :       if (stmt != s)
    1779        31993 :         continue;
    1780              : 
    1781              :       // LHS_RANGE is now S's LHS as it is known in ORIG_BB.
    1782       182621 :       value_range op1_range (TREE_TYPE (s_handler.operand1 ()));
    1783       182621 :       value_range op2_range (TREE_TYPE (s_handler.operand2 ()));
    1784       365242 :       get_range_query (cfun)->range_on_entry (op1_range, orig_bb,
    1785              :                                             s_handler.operand1 ());
    1786       365242 :       get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
    1787              :                                             s_handler.operand2 ());
    1788       182621 :       relation_kind r = s_handler.op1_op2_relation (lhs_range, op1_range,
    1789       182621 :                                                   op2_range);
    1790       182621 :       if (reversed)
    1791        41561 :         r = relation_swap (r);
    1792       182621 :       relation_kind k = relation_intersect (result, r);
    1793       182621 :       if (k != VREL_UNDEFINED)
    1794       182621 :         result = k;
    1795       216483 :     }
    1796     13632017 :   return result;
    1797              : }
    1798              : 
    1799              : // Find a relation between SSA1 and SSA2 in the dominator tree starting with
    1800              : // block BB
    1801              : 
    1802              : relation_kind
    1803     23476988 : dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
    1804              : {
    1805     23476988 :   relation_kind r;
    1806     23476988 :   unsigned v1 = SSA_NAME_VERSION (ssa1);
    1807     23476988 :   unsigned v2 = SSA_NAME_VERSION (ssa2);
    1808              :   // IF either name does not occur in a relation anywhere, there isn't one.
    1809     23476988 :   if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
    1810              :     return VREL_VARYING;
    1811    611083990 :   for (basic_block bb = start_bb;
    1812    634560978 :        bb;
    1813    611083990 :        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
    1814              :     {
    1815    614076576 :       r = find_relation_block (bb->index, ssa1, ssa2);
    1816    614076576 :       if (r != VREL_VARYING)
    1817              :         return r;
    1818              :     }
    1819              :   return VREL_VARYING;
    1820              : }
    1821              : 
    1822              : // Starting with basic block BB, look for the next block in the dominator
    1823              : // tree which contains a relation involving NAME.  There can be more than one,
    1824              : // and they are returned in the class local m_near vector.  The block in which
    1825              : // the relations are found are returned.  If no relations are found, NULL is
    1826              : // returned and the m_near vector is empty.
    1827              : 
    1828              : basic_block
    1829     81990311 : dom_oracle::nearest_relations (tree name, basic_block bb)
    1830              : {
    1831     81990311 :   if (TREE_CODE (name) != SSA_NAME)
    1832              :     return NULL;
    1833              : 
    1834     81990311 :   unsigned v = SSA_NAME_VERSION (name);
    1835     81990311 :   if (!bitmap_bit_p (m_relation_set, v))
    1836              :     return NULL;
    1837              : 
    1838              :   // A relation involving NAME can only be registered in a block
    1839              :   // dominated by NAME's definition.  Relations occurring *in* the def block
    1840              :   // are attached to the def block itself, so once that block has been
    1841              :   // examined there is nothing left to find and the walk can terminate.
    1842     77680235 :   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
    1843     77680235 :   bool at_def = false;
    1844              : 
    1845     77680235 :   m_near.truncate (0);
    1846   1485893860 :   for (; bb && !at_def; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
    1847              :     {
    1848   1379845453 :       at_def = (bb == def_bb);
    1849              : 
    1850   2759690906 :       if (bb->index >= (int) m_relations.length ())
    1851         1616 :         continue;
    1852              : 
    1853   1379843837 :       const_bitmap bm = m_relations[bb->index].m_names;
    1854   1379843837 :       if (!bm || !bitmap_bit_p (bm, v))
    1855   1330531768 :         continue;
    1856              : 
    1857     49312069 :       for (relation_chain *ptr = m_relations[bb->index].m_head;
    1858    182756585 :            ptr; ptr = ptr->m_next)
    1859              :         {
    1860    133444516 :           if (v == SSA_NAME_VERSION (ptr->op1 ())
    1861    133444516 :               && !SSA_NAME_IN_FREE_LIST (ptr->op2 ()))
    1862     33641515 :             m_near.safe_push ({ ptr->kind (), ptr->op2 (), bb });
    1863     99803001 :           else if (v == SSA_NAME_VERSION (ptr->op2 ())
    1864     99803001 :                    && !SSA_NAME_IN_FREE_LIST (ptr->op1 ()))
    1865     44918760 :             m_near.safe_push ({ relation_swap (ptr->kind ()),
    1866     22459380 :                                 ptr->op1 (), bb });
    1867              :         }
    1868              : 
    1869   1379845457 :       if (!m_near.is_empty ())
    1870              :         return bb;
    1871              :     }
    1872              : 
    1873              :   return NULL;
    1874              : }
    1875              : 
    1876              : // Record relation K between OP1 and OP2, discovered by a search in block BB,
    1877              : // so subsequent queries in BB or anything it dominates find it directly.
    1878              : // Use SEARCH_AND_MERGE_RELATION rather than CREATE_RELATION_IN_BB.  The pair
    1879              : // may already have a record in BB from an earlier query, in which case the
    1880              : // two must be intersected rather than a second record created.
    1881              : 
    1882              : void
    1883     27726441 : dom_oracle::cache_relation (basic_block bb, relation_kind k, tree op1,
    1884              :                             tree op2)
    1885              : {
    1886     27726441 :   if (!bb || op1 == op2)
    1887              :     return;
    1888              :   // There is nothing useful to record for VARYING or UNDEFINED and
    1889              :   // Equivalences belong to the equivalence oracle.
    1890     27726441 :   if (k == VREL_VARYING || k == VREL_UNDEFINED || relation_equiv_p (k))
    1891              :     return;
    1892     11383631 :   search_and_merge_relation (bb, k, op1, op2);
    1893              : }
    1894              : 
    1895              : // Begin the search for SIDE at its root ROOT, whose equivalence set is
    1896              : // EQUIV, in block BB.  Every name equivalent to ROOT is an equally good
    1897              : // starting point, so seed them all.
    1898              : 
    1899              : void
    1900     55452882 : dom_oracle::start_search (frontier_data &side, tree root, const_bitmap equiv,
    1901              :                           basic_block bb)
    1902              : {
    1903     55452882 :   side.m_root = root;
    1904              : 
    1905     55452882 :   unsigned root_v = SSA_NAME_VERSION (root);
    1906     55452882 :   m_worklist.safe_push ({ VREL_EQ, root, bb, side.m_rhs });
    1907     55452882 :   bitmap_set_bit (side.m_visited, root_v);
    1908     55452882 :   side.set_known (root_v, VREL_EQ);
    1909              : 
    1910     55452882 :   unsigned i;
    1911     55452882 :   bitmap_iterator bi;
    1912    114405921 :   EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi)
    1913              :     {
    1914              :       // Equivalences are maintained lazily, so ensure they are still
    1915              :       // valid before adding them to the frontier.
    1916     58953039 :       tree name = ssa_name (i);
    1917     62453195 :       if (i == root_v || !name || SSA_NAME_IN_FREE_LIST (name))
    1918     55452883 :         continue;
    1919      3500156 :       m_worklist.safe_push ({ VREL_EQ, name, bb, side.m_rhs });
    1920      3500156 :       bitmap_set_bit (side.m_visited, i);
    1921      3500156 :       side.set_known (i, VREL_EQ);
    1922              :     }
    1923     55452882 : }
    1924              : 
    1925              : // SIDE's root has been shown to be related to NAME by REL.  Queue NAME for
    1926              : // expansion starting at block BB.
    1927              : 
    1928              : void
    1929     18052625 : dom_oracle::add_to_frontier (frontier_data &side, tree name, relation_kind rel,
    1930              :                              basic_block bb)
    1931              : {
    1932     18052625 :   unsigned v = SSA_NAME_VERSION (name);
    1933     18052625 :   if (!side.visited_p (v))
    1934              :     {
    1935     15955230 :       bitmap_set_bit (side.m_visited, v);
    1936     15955230 :       side.set_known (v, rel);
    1937     15955230 :       m_worklist.safe_push ({ rel, name, bb, side.m_rhs });
    1938     15955230 :       return;
    1939              :     }
    1940              : 
    1941              :   // NAME already had a relation, so intersect the two and requeue NAME if
    1942              :   // there is an improvement.
    1943      2097395 :   relation_kind curr = side.known_relation (v);
    1944      2097395 :   relation_kind k = relation_intersect (curr, rel);
    1945      2097395 :   if (k != curr && k != VREL_UNDEFINED)
    1946              :     {
    1947        25492 :       side.set_known (v, k);
    1948        25492 :       m_worklist.safe_push ({ k, name, bb, side.m_rhs });
    1949              :     }
    1950              : }
    1951              : 
    1952              : // Expand worklist entry W, looking for a name the other side of the search
    1953              : // has already reached.  BB is the block the query was made in.  Return true
    1954              : // and set RESULT if a match was found.  W is passed by value as
    1955              : // add_to_frontier may realloc the vector.
    1956              : 
    1957              : bool
    1958     81990311 : dom_oracle::expand_frontier (frontier_element w, basic_block bb,
    1959              :                              relation_kind &result)
    1960              : {
    1961     81990311 :   frontier_data &self = w.rhs ? m_rhs_search : m_lhs_search;
    1962     81990311 :   frontier_data &other = w.rhs ? m_lhs_search : m_rhs_search;
    1963              : 
    1964     81990311 :   if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
    1965              :     {
    1966            0 :       fprintf (dump_file, "  %s frontier expanding: ", w.rhs ? "RHS" : "LHS");
    1967            0 :       print_generic_expr (dump_file, w.name, TDF_SLIM);
    1968            0 :       fprintf (dump_file, " (rel: %d)\n", w.rel);
    1969              :     }
    1970              : 
    1971     81990311 :   basic_block found = nearest_relations (w.name, w.bb);
    1972     81990311 :   if (!found)
    1973              :     return false;
    1974              : 
    1975     93720044 :   for (unsigned i = 0; i < m_near.length (); ++i)
    1976              :     {
    1977              :       // nearest_relations sets m_near[i].rel as "w.name <rel> m_near.name",
    1978              :       // so composing it with "root <w.rel> w.name" gives "root <kind> next".
    1979     55814563 :       value_relation path (w.rel, self.m_root, w.name);
    1980     55814563 :       value_relation near_rel (m_near[i].rel, w.name, m_near[i].name);
    1981              : 
    1982     55814563 :       if (!path.apply_transitive (near_rel))
    1983     26355356 :         continue;
    1984              : 
    1985     29459207 :       relation_kind kind = path.kind ();
    1986     29459207 :       tree next = path.op2 ();
    1987     29459207 :       unsigned nv = SSA_NAME_VERSION (next);
    1988              : 
    1989              :       // If the other side has reached NEXT it knows "other_root <rel> next",
    1990              :       // which composes with what is known here to relate the two roots.
    1991     29459207 :       if (other.visited_p (nv))
    1992              :         {
    1993     12180934 :           relation_kind k
    1994     12180934 :             = relation_transitive (kind,
    1995              :                                    relation_swap (other.known_relation (nv)));
    1996              :           // If the result is not VARYING, we have a match.
    1997     12180934 :           if (k != VREL_VARYING)
    1998              :             {
    1999     11406582 :               result = w.rhs ? relation_swap (k) : k;
    2000     11406582 :               if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
    2001              :                 {
    2002            0 :                   fprintf (dump_file, "  %s frontier found connection at: ",
    2003              :                            w.rhs ? "RHS" : "LHS");
    2004            0 :                   print_generic_expr (dump_file, next, TDF_SLIM);
    2005            0 :                   fprintf (dump_file, ", combined relation: ");
    2006            0 :                   print_relation (dump_file, result);
    2007            0 :                   fputc ('\n', dump_file);
    2008              :                 }
    2009     11406582 :               return true;
    2010              :             }
    2011              :         }
    2012              : 
    2013              :       // Add to this side's frontier if it has not visited NEXT yet.
    2014     18052625 :       add_to_frontier (self, next, kind, bb);
    2015              :     }
    2016              : 
    2017              :   // Keep searching for NAME in the dominator tree.  Do not search past
    2018              :   // the def block as that is pointless.  Do search the def block however
    2019              :   // as relations within the body of the block are stored there.
    2020              :   // Use whatever the latest known relation value is.
    2021     37905481 :   basic_block idom = get_immediate_dominator (CDI_DOMINATORS, found);
    2022     37905481 :   if (idom && gimple_bb (SSA_NAME_DEF_STMT (w.name)) != found)
    2023     20390105 :     m_worklist.safe_push ({ self.known_relation (SSA_NAME_VERSION (w.name)),
    2024              :                             w.name, idom, w.rhs });
    2025              : 
    2026              :   return false;
    2027              : }
    2028              : 
    2029              : // Search for a relation between LHS and RHS in block BB or one of its
    2030              : // dominators, expanding a frontier from both names until the two meet.
    2031              : // LHS_EQUIV and RHS_EQUIV are the equivalence sets of LHS and RHS.
    2032              : 
    2033              : relation_kind
    2034     27726441 : dom_oracle::relation_search (basic_block bb, tree lhs, const_bitmap lhs_equiv,
    2035              :                              tree rhs, const_bitmap rhs_equiv)
    2036              : {
    2037              :   // Initialize both search frontiers.
    2038     27726441 :   start_search (m_lhs_search, lhs, lhs_equiv, bb);
    2039     27726441 :   start_search (m_rhs_search, rhs, rhs_equiv, bb);
    2040              : 
    2041     27726441 :   relation_kind result = VREL_VARYING;
    2042              : 
    2043              :   // Each expansion walks the dominator tree looking for the next block with
    2044              :   // a relation.
    2045     27726441 :   unsigned budget = param_transitive_relations_work_bound;
    2046              : 
    2047     27726441 :   if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
    2048              :     {
    2049            0 :       fprintf (dump_file, "Bidirectional relation search: ");
    2050            0 :       print_generic_expr (dump_file, lhs, TDF_SLIM);
    2051            0 :       fprintf (dump_file, " vs ");
    2052            0 :       print_generic_expr (dump_file, rhs, TDF_SLIM);
    2053            0 :       fprintf (dump_file, " in bb%d\n", bb ? bb->index : -1);
    2054              :     }
    2055              : 
    2056              :   // Expand until exhausted or until a connection is found.
    2057     98310170 :   while (m_wl_ix < m_worklist.length ())
    2058              :     {
    2059     82010073 :       if (!budget--)
    2060              :         {
    2061        19762 :           if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
    2062            0 :             fprintf (dump_file, "  search budget exhausted\n");
    2063              :           break;
    2064              :         }
    2065              : 
    2066     81990311 :       if (expand_frontier (m_worklist[m_wl_ix++], bb, result))
    2067              :         break;
    2068              :     }
    2069              : 
    2070              :   // Clear search state for reuse.
    2071     27726441 :   m_worklist.truncate (0);
    2072     27726441 :   m_wl_ix = 0;
    2073     27726441 :   m_lhs_search.clear_search ();
    2074     27726441 :   m_rhs_search.clear_search ();
    2075              : 
    2076              :   // Check to see if any new relations can be formed by recomputing an
    2077              :   // expression using LHS and RHS.
    2078              :   // This call must come after the worklists are cleared above.  The call
    2079              :   // may invoke range_on_entry which may trigger another relation search,
    2080              :   // and thus the current search must be cleared before making this call.
    2081     27726441 :   relation_kind rel = recomputed_relation (bb, lhs, rhs);
    2082              : 
    2083     27726441 :   if (rel != VREL_VARYING)
    2084              :     {
    2085       144814 :       rel = relation_intersect (result, rel);
    2086       144814 :       if (rel != VREL_UNDEFINED)
    2087       144814 :         result = rel;
    2088              :     }
    2089              : 
    2090              :   // Record whatever was found so the next query for this pair is a direct
    2091              :   // lookup rather than another search.
    2092     27726441 :   cache_relation (bb, result, lhs, rhs);
    2093              : 
    2094     27726441 :   if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION)
    2095            0 :       && result != VREL_VARYING)
    2096              :     {
    2097            0 :       fprintf (dump_file, "  relation_search returning: ");
    2098            0 :       print_generic_expr (dump_file, lhs, TDF_SLIM);
    2099            0 :       print_relation (dump_file, result);
    2100            0 :       print_generic_expr (dump_file, rhs, TDF_SLIM);
    2101            0 :       fprintf (dump_file, "\n");
    2102              :     }
    2103              : 
    2104     27726441 :   return result;
    2105              : }
    2106              : 
    2107              : // Query if there is a relation between SSA1 and SS2 in block BB or a
    2108              : // dominator of BB
    2109              : 
    2110              : relation_kind
    2111    121062121 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
    2112              : {
    2113    121062121 :   relation_kind kind;
    2114    121062121 :   unsigned v1 = SSA_NAME_VERSION (ssa1);
    2115    121062121 :   unsigned v2 = SSA_NAME_VERSION (ssa2);
    2116    121062121 :   if (v1 == v2)
    2117              :     return VREL_EQ;
    2118              : 
    2119              :   // If v1 or v2 do not have any relations or equivalences, a partial
    2120              :   // equivalence is the only possibility.
    2121    203336271 :   if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
    2122    124718314 :       || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
    2123     93083752 :     return partial_equiv (ssa1, ssa2);
    2124              : 
    2125              :   // Check for equivalence first.  They must be in each equivalency set.
    2126     27876586 :   const_bitmap equiv1 = equiv_set (ssa1, bb);
    2127     27876586 :   const_bitmap equiv2 = equiv_set (ssa2, bb);
    2128     27876586 :   if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
    2129              :     return VREL_EQ;
    2130              : 
    2131              :   // A statement such as c = a & 0xff makes a partial equivalence between
    2132              :   // c and a, and an ordinary comparison can then relate the same pair.
    2133              :   // If both exist, prefer the relation, so look for that first.
    2134     27726441 :   kind = relation_search (bb, ssa1, equiv1, ssa2, equiv2);
    2135              : 
    2136              :   // Finally look for partial equivalences.
    2137     27726441 :   if (kind == VREL_VARYING)
    2138     16318262 :     kind = partial_equiv (ssa1, ssa2);
    2139              :   return kind;
    2140              : }
    2141              : 
    2142              : // Dump all the relations in block BB to file F.
    2143              : 
    2144              : void
    2145          257 : dom_oracle::dump (FILE *f, basic_block bb) const
    2146              : {
    2147          257 :   equiv_oracle::dump (f,bb);
    2148              : 
    2149          514 :   if (bb->index >= (int)m_relations.length ())
    2150          218 :     return;
    2151          257 :   if (!m_relations[bb->index].m_names)
    2152              :     return;
    2153              : 
    2154           39 :   value_relation vr;
    2155           90 :   FOR_EACH_RELATION_BB (this, bb, vr)
    2156              :     {
    2157           51 :       fprintf (f, "Relational : ");
    2158           51 :       vr.dump (f);
    2159           51 :       fprintf (f, "\n");
    2160              :     }
    2161              : }
    2162              : 
    2163              : // Dump all the relations known to file F.
    2164              : 
    2165              : void
    2166            0 : dom_oracle::dump (FILE *f) const
    2167              : {
    2168            0 :   fprintf (f, "Relation dump\n");
    2169            0 :   for (unsigned i = 0; i < m_relations.length (); i++)
    2170            0 :     if (BASIC_BLOCK_FOR_FN (cfun, i))
    2171              :       {
    2172            0 :         fprintf (f, "BB%d\n", i);
    2173            0 :         dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
    2174              :       }
    2175            0 : }
    2176              : 
    2177              : void
    2178            0 : relation_oracle::debug () const
    2179              : {
    2180            0 :   dump (stderr);
    2181            0 : }
    2182              : 
    2183      9400721 : path_oracle::path_oracle (relation_oracle *oracle)
    2184              : {
    2185      9400721 :   set_root_oracle (oracle);
    2186      9400721 :   bitmap_obstack_initialize (&m_bitmaps);
    2187      9400721 :   obstack_init (&m_chain_obstack);
    2188              : 
    2189              :   // Initialize header records.
    2190      9400721 :   m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
    2191      9400721 :   m_equiv.m_bb = NULL;
    2192      9400721 :   m_equiv.m_next = NULL;
    2193      9400721 :   m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
    2194      9400721 :   m_relations.m_head = NULL;
    2195      9400721 :   m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
    2196      9400721 : }
    2197              : 
    2198     18801442 : path_oracle::~path_oracle ()
    2199              : {
    2200      9400721 :   obstack_free (&m_chain_obstack, NULL);
    2201      9400721 :   bitmap_obstack_release (&m_bitmaps);
    2202     18801442 : }
    2203              : 
    2204              : // Clear any range info and relations associated with NAME.
    2205              : 
    2206              : void
    2207            0 : path_oracle::clear (tree name)
    2208              : {
    2209            0 :   if (m_root)
    2210            0 :     m_root->clear (name);
    2211              : 
    2212            0 :   m_relations.clear (name);
    2213              : 
    2214            0 :   unsigned v = SSA_NAME_VERSION (name);
    2215            0 :   equiv_chain *ptr = m_equiv.find (v);
    2216            0 :   if (ptr)
    2217            0 :     bitmap_clear_bit (ptr->m_names, v);
    2218            0 : }
    2219              : 
    2220              : // Return the equiv set for SSA, and if there isn't one, check for equivs
    2221              : // starting in block BB.
    2222              : 
    2223              : const_bitmap
    2224    144242341 : path_oracle::equiv_set (tree ssa, basic_block bb)
    2225              : {
    2226              :   // Check the list first.
    2227    144242341 :   equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
    2228    144242341 :   if (ptr)
    2229     77335320 :     return ptr->m_names;
    2230              : 
    2231              :   // Otherwise defer to the root oracle.
    2232     66907021 :   if (m_root)
    2233     60499689 :     return m_root->equiv_set (ssa, bb);
    2234              : 
    2235              :   // Allocate a throw away bitmap if there isn't a root oracle.
    2236      6407332 :   bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
    2237      6407332 :   bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
    2238      6407332 :   return tmp;
    2239              : }
    2240              : 
    2241              : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
    2242              : // block BB.  Return false if no new equivalence was added.
    2243              : 
    2244              : bool
    2245      8794497 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
    2246              : {
    2247      8794497 :   const_bitmap equiv_1 = equiv_set (ssa1, bb);
    2248      8794497 :   const_bitmap equiv_2 = equiv_set (ssa2, bb);
    2249              : 
    2250              :   // Check if they are the same set, if so, we're done.
    2251      8794497 :   if (bitmap_equal_p (equiv_1, equiv_2))
    2252              :     return false;
    2253              : 
    2254              :   // Don't mess around, simply create a new record and insert it first.
    2255      8773890 :   bitmap b = BITMAP_ALLOC (&m_bitmaps);
    2256      8773890 :   valid_equivs (b, equiv_1, bb);
    2257      8773890 :   valid_equivs (b, equiv_2, bb);
    2258              : 
    2259      8773890 :   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
    2260              :                                                     sizeof (equiv_chain));
    2261      8773890 :   ptr->m_names = b;
    2262      8773890 :   ptr->m_bb = NULL;
    2263      8773890 :   ptr->m_next = m_equiv.m_next;
    2264      8773890 :   m_equiv.m_next = ptr;
    2265      8773890 :   bitmap_ior_into (m_equiv.m_names, b);
    2266      8773890 :   return true;
    2267              : }
    2268              : 
    2269              : // Register killing definition of an SSA_NAME.
    2270              : 
    2271              : void
    2272     62351886 : path_oracle::killing_def (tree ssa)
    2273              : {
    2274     62351886 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2275              :     {
    2276          990 :       fprintf (dump_file, " Registering killing_def (path_oracle) ");
    2277          990 :       print_generic_expr (dump_file, ssa, TDF_SLIM);
    2278          990 :       fprintf (dump_file, "\n");
    2279              :     }
    2280              : 
    2281     62351886 :   unsigned v = SSA_NAME_VERSION (ssa);
    2282              : 
    2283     62351886 :   bitmap_set_bit (m_killed_defs, v);
    2284     62351886 :   bitmap_set_bit (m_equiv.m_names, v);
    2285              : 
    2286              :   // Now add an equivalency with itself so we don't look to the root oracle.
    2287     62351886 :   bitmap b = BITMAP_ALLOC (&m_bitmaps);
    2288     62351886 :   bitmap_set_bit (b, v);
    2289     62351886 :   equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
    2290              :                                                     sizeof (equiv_chain));
    2291     62351886 :   ptr->m_names = b;
    2292     62351886 :   ptr->m_bb = NULL;
    2293     62351886 :   ptr->m_next = m_equiv.m_next;
    2294     62351886 :   m_equiv.m_next = ptr;
    2295              : 
    2296              :   // Walk the relation list and remove SSA from any relations.
    2297     62351886 :   if (!bitmap_bit_p (m_relations.m_names, v))
    2298              :     return;
    2299              : 
    2300       411971 :   bitmap_clear_bit (m_relations.m_names, v);
    2301       411971 :   relation_chain **prev = &(m_relations.m_head);
    2302       411971 :   relation_chain *next = NULL;
    2303       943995 :   for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
    2304              :     {
    2305       532024 :       gcc_checking_assert (*prev == ptr);
    2306       532024 :       next = ptr->m_next;
    2307       532024 :       if (SSA_NAME_VERSION (ptr->op1 ()) == v
    2308       532024 :           || SSA_NAME_VERSION (ptr->op2 ()) == v)
    2309       340437 :         *prev = ptr->m_next;
    2310              :       else
    2311       191587 :         prev = &(ptr->m_next);
    2312              :     }
    2313              : }
    2314              : 
    2315              : // Register relation K between SSA1 and SSA2, resolving unknowns by
    2316              : // querying from BB.  Return false if no new relation is registered.
    2317              : 
    2318              : bool
    2319     32829044 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
    2320              : {
    2321              :   // If the 2 ssa_names are the same, do nothing.  An equivalence is implied,
    2322              :   // and no other relation makes sense.
    2323     32829044 :   if (ssa1 == ssa2)
    2324              :     return false;
    2325              : 
    2326              :   // Partial equivalences are tracked in the root equivalence oracle rather
    2327              :   // than on the path.  Registering a partial equivalence in the path would
    2328              :   // cause normal relations to collapse to VARYING.
    2329     32783915 :   if (relation_partial_equiv_p (k))
    2330              :     return false;
    2331              : 
    2332     28957377 :   relation_kind curr = query (bb, ssa1, ssa2);
    2333              :   // Likewise, a partial equivalency result should not be combined with K
    2334              :   // or the result drops to VARYING.
    2335     28957377 :   if (curr != VREL_VARYING && !relation_partial_equiv_p (curr))
    2336      4529840 :     k = relation_intersect (curr, k);
    2337              : 
    2338              :   // Do not register an impossible relation.
    2339     28957377 :   if (k == VREL_UNDEFINED)
    2340              :     return false;
    2341              : 
    2342     26657769 :   bool ret;
    2343     26657769 :   if (k == VREL_EQ)
    2344      8794497 :     ret = register_equiv (bb, ssa1, ssa2);
    2345              :   else
    2346              :     {
    2347     17863272 :       bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
    2348     17863272 :       bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
    2349     17863272 :       relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
    2350              :                                                           sizeof (relation_chain));
    2351     17863272 :       ptr->set_relation (k, ssa1, ssa2);
    2352     17863272 :       ptr->m_next = m_relations.m_head;
    2353     17863272 :       m_relations.m_head = ptr;
    2354     17863272 :       ret = true;
    2355              :     }
    2356              : 
    2357     26657769 :   if (ret && dump_file && (dump_flags & TDF_DETAILS))
    2358              :     {
    2359          304 :       value_relation vr (k, ssa1, ssa2);
    2360          304 :       fprintf (dump_file, " Registering value_relation (path_oracle) ");
    2361          304 :       vr.dump (dump_file);
    2362          304 :       fprintf (dump_file, " (root: bb%d)\n", bb->index);
    2363              :     }
    2364              :   return ret;
    2365              : }
    2366              : 
    2367              : // Query for a relationship between equiv set B1 and B2, resolving unknowns
    2368              : // starting at block BB.
    2369              : 
    2370              : relation_kind
    2371     53341186 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
    2372              : {
    2373     53341186 :   if (bitmap_equal_p (b1, b2))
    2374              :     return VREL_EQ;
    2375              : 
    2376     53341186 :   relation_kind k = m_relations.find_relation (b1, b2);
    2377              : 
    2378              :   // Do not look at the root oracle for names that have been killed
    2379              :   // along the path.
    2380     53341186 :   if (bitmap_intersect_p (m_killed_defs, b1)
    2381     53341186 :       || bitmap_intersect_p (m_killed_defs, b2))
    2382              :     return k;
    2383              : 
    2384              :   // Query the root oracle for relations with path local equivalencies.
    2385     14640921 :   if (k == VREL_VARYING && m_root)
    2386     12109701 :     k = m_root->query (bb, b1, b2);
    2387              : 
    2388              :   return k;
    2389              : }
    2390              : 
    2391              : // Query for a relationship between SSA1 and SSA2, resolving unknowns
    2392              : // starting at block BB.
    2393              : 
    2394              : relation_kind
    2395     54015977 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
    2396              : {
    2397     54015977 :   unsigned v1 = SSA_NAME_VERSION (ssa1);
    2398     54015977 :   unsigned v2 = SSA_NAME_VERSION (ssa2);
    2399              : 
    2400     54015977 :   if (v1 == v2)
    2401              :     return VREL_EQ;
    2402              : 
    2403     53921741 :   const_bitmap equiv_1 = equiv_set (ssa1, bb);
    2404     53921741 :   const_bitmap equiv_2 = equiv_set (ssa2, bb);
    2405     53921741 :   if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
    2406              :     return VREL_EQ;
    2407              : 
    2408     53341186 :   relation_kind rel = query (bb, equiv_1, equiv_2);
    2409              : 
    2410              :   // If the path relation query fails, check for relations in the root oracle.
    2411     53341186 :   if (rel == VREL_VARYING && m_root)
    2412     46242710 :       rel = m_root->query (bb, ssa1, ssa2);
    2413              :   return rel;
    2414              : }
    2415              : 
    2416              : // Reset any relations registered on this path.  ORACLE is the root
    2417              : // oracle to use.
    2418              : 
    2419              : void
    2420     40108582 : path_oracle::reset_path (relation_oracle *oracle)
    2421              : {
    2422     40108582 :   set_root_oracle (oracle);
    2423     40108582 :   m_equiv.m_next = NULL;
    2424     40108582 :   bitmap_clear (m_equiv.m_names);
    2425     40108582 :   m_relations.m_head = NULL;
    2426     40108582 :   bitmap_clear (m_relations.m_names);
    2427     40108582 :   bitmap_clear (m_killed_defs);
    2428     40108582 : }
    2429              : 
    2430              : // Dump relation in basic block... Do nothing here.
    2431              : 
    2432              : void
    2433            0 : path_oracle::dump (FILE *, basic_block) const
    2434              : {
    2435            0 : }
    2436              : 
    2437              : // Dump the relations and equivalencies found in the path.
    2438              : 
    2439              : void
    2440            0 : path_oracle::dump (FILE *f) const
    2441              : {
    2442            0 :   equiv_chain *ptr = m_equiv.m_next;
    2443            0 :   relation_chain *ptr2 = m_relations.m_head;
    2444              : 
    2445            0 :   if (ptr || ptr2)
    2446            0 :     fprintf (f, "\npath_oracle:\n");
    2447              : 
    2448            0 :   for (; ptr; ptr = ptr->m_next)
    2449            0 :     ptr->dump (f);
    2450              : 
    2451            0 :   for (; ptr2; ptr2 = ptr2->m_next)
    2452              :     {
    2453            0 :       fprintf (f, "Relational : ");
    2454            0 :       ptr2->dump (f);
    2455            0 :       fprintf (f, "\n");
    2456              :     }
    2457            0 : }
    2458              : 
    2459              : // ------------------------------------------------------------------------
    2460              : //  EQUIV iterator.  Although we have bitmap iterators, don't expose that it
    2461              : //  is currently a bitmap.  Use an export iterator to hide future changes.
    2462              : 
    2463              : // Construct a basic iterator over an equivalence bitmap.
    2464              : 
    2465     55968172 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
    2466              :                                                   basic_block bb, tree name,
    2467              :                                                   bool full, bool partial)
    2468              : {
    2469     55968172 :   m_name = name;
    2470     55968172 :   m_oracle = oracle;
    2471     55968172 :   m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
    2472     55968172 :   m_bm = NULL;
    2473     55968172 :   if (full)
    2474     55968172 :     m_bm = oracle->equiv_set (name, bb);
    2475     55968172 :   if (!m_bm && m_pe)
    2476            0 :     m_bm = m_pe->members;
    2477     55968172 :   if (m_bm)
    2478     55968171 :     bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
    2479     55968172 : }
    2480              : 
    2481              : // Move to the next export bitmap spot.
    2482              : 
    2483              : void
    2484     73988935 : equiv_relation_iterator::next ()
    2485              : {
    2486     73988935 :   bmp_iter_next (&m_bi, &m_y);
    2487     73988935 : }
    2488              : 
    2489              : // Fetch the name of the next export in the export list.  Return NULL if
    2490              : // iteration is done.
    2491              : 
    2492              : tree
    2493     67337856 : equiv_relation_iterator::get_name (relation_kind *rel)
    2494              : {
    2495     73988778 :   if (!m_bm)
    2496              :     return NULL_TREE;
    2497              : 
    2498    136608028 :   while (bmp_iter_set (&m_bi, &m_y))
    2499              :     {
    2500              :       // Do not return self.
    2501     73988935 :       tree t = ssa_name (m_y);
    2502     73988935 :       if (t && t != m_name)
    2503              :         {
    2504     11369700 :           relation_kind k = VREL_EQ;
    2505     11369700 :           if (m_pe && m_bm == m_pe->members)
    2506              :             {
    2507      8507063 :               const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
    2508      8507063 :               if (equiv_pe && equiv_pe->members == m_pe->members)
    2509      8507047 :                 k = pe_min (m_pe->code, equiv_pe->code);
    2510              :               else
    2511              :                 k = VREL_VARYING;
    2512              :             }
    2513      8507063 :           if (relation_equiv_p (k))
    2514              :             {
    2515     11369684 :               if (rel)
    2516     11369684 :                 *rel = k;
    2517              :               return t;
    2518              :             }
    2519              :         }
    2520     62619251 :       next ();
    2521              :     }
    2522              : 
    2523              :   // Process partial equivs after full equivs if both were requested.
    2524     62619093 :   if (m_pe && m_bm != m_pe->members)
    2525              :     {
    2526     55968171 :       m_bm = m_pe->members;
    2527     55968171 :       if (m_bm)
    2528              :         {
    2529              :           // Recursively call back to process First PE.
    2530      6650922 :           bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
    2531      6650922 :           return get_name (rel);
    2532              :         }
    2533              :     }
    2534              :   return NULL_TREE;
    2535              : }
    2536              : 
    2537              : #if CHECKING_P
    2538              : #include "selftest.h"
    2539              : 
    2540              : namespace selftest
    2541              : {
    2542              : void
    2543            4 : relation_tests ()
    2544              : {
    2545              :   // rr_*_table tables use unsigned char rather than relation_kind.
    2546            4 :   ASSERT_LT (VREL_LAST, UCHAR_MAX);
    2547           52 :   for (relation_kind r1 = VREL_VARYING; r1 < VREL_LAST;
    2548           48 :        r1 = relation_kind (r1 + 1))
    2549              :     {
    2550              :       // Swapping the operands twice is a no-op.
    2551           48 :       ASSERT_EQ (relation_swap (relation_swap (r1)), r1);
    2552              : 
    2553              :       // VARYING intersect X is X.
    2554              :       // UNDEFINED intersect X is UNDEFINED.
    2555           48 :       ASSERT_EQ (relation_intersect (VREL_VARYING, r1), r1);
    2556           48 :       ASSERT_EQ (relation_intersect (VREL_UNDEFINED, r1), VREL_UNDEFINED);
    2557              : 
    2558              :       // UNDEFINED union X is X.
    2559              :       // VARYING union X is VARYING.
    2560           48 :       ASSERT_EQ (relation_union (VREL_UNDEFINED, r1), r1);
    2561           48 :       ASSERT_EQ (relation_union (VREL_VARYING, r1), VREL_VARYING);
    2562              : 
    2563              :       // Verify commutativity of relation_intersect and relation_union.
    2564          624 :       for (relation_kind r2 = VREL_VARYING; r2 < VREL_LAST;
    2565          576 :            r2 = relation_kind (r2 + 1))
    2566              :         {
    2567          576 :           ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
    2568          576 :           ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
    2569              :         }
    2570              :     }
    2571              : 
    2572              :   // Verify partial equivalence properties.
    2573           20 :   for (relation_kind r1 = VREL_PE8; r1 <= VREL_PE64;
    2574           16 :        r1 = relation_kind (r1 + 1))
    2575              :     {
    2576           16 :       ASSERT_EQ (relation_swap (r1), r1);
    2577           16 :       ASSERT_EQ (relation_intersect (VREL_EQ, r1), VREL_EQ);
    2578           16 :       ASSERT_EQ (relation_union (VREL_EQ, r1), r1);
    2579           16 :       ASSERT_EQ (relation_transitive (VREL_EQ, r1), r1);
    2580           16 :       ASSERT_EQ (relation_transitive (r1, VREL_EQ), r1);
    2581           80 :       for (relation_kind r2 = VREL_PE8; r2 <= VREL_PE64;
    2582           64 :            r2 = relation_kind (r2 + 1))
    2583              :         {
    2584           64 :           ASSERT_EQ (relation_intersect (r1, r2), MAX (r1, r2));
    2585           64 :           ASSERT_EQ (relation_union (r1, r2), pe_min (r1, r2));
    2586           64 :           ASSERT_EQ (relation_transitive (r1, r2), pe_min (r1, r2));
    2587              :         }
    2588              :     }
    2589            4 : }
    2590              : 
    2591              : } // namespace selftest
    2592              : 
    2593              : #endif // CHECKING_P
        

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.