LCOV - code coverage report
Current view: top level - gcc - ipa-icf.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1517 1713 88.6 %
Date: 2020-05-30 12:51:24 Functions: 94 99 94.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Interprocedural Identical Code Folding pass
       2                 :            :    Copyright (C) 2014-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            :    Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
       5                 :            : 
       6                 :            : This file is part of GCC.
       7                 :            : 
       8                 :            : GCC is free software; you can redistribute it and/or modify it under
       9                 :            : the terms of the GNU General Public License as published by the Free
      10                 :            : Software Foundation; either version 3, or (at your option) any later
      11                 :            : version.
      12                 :            : 
      13                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      14                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16                 :            : for more details.
      17                 :            : 
      18                 :            : You should have received a copy of the GNU General Public License
      19                 :            : along with GCC; see the file COPYING3.  If not see
      20                 :            : <http://www.gnu.org/licenses/>.  */
      21                 :            : 
      22                 :            : /* Interprocedural Identical Code Folding for functions and
      23                 :            :    read-only variables.
      24                 :            : 
      25                 :            :    The goal of this transformation is to discover functions and read-only
      26                 :            :    variables which do have exactly the same semantics.
      27                 :            : 
      28                 :            :    In case of functions,
      29                 :            :    we could either create a virtual clone or do a simple function wrapper
      30                 :            :    that will call equivalent function. If the function is just locally visible,
      31                 :            :    all function calls can be redirected. For read-only variables, we create
      32                 :            :    aliases if possible.
      33                 :            : 
      34                 :            :    Optimization pass arranges as follows:
      35                 :            :    1) All functions and read-only variables are visited and internal
      36                 :            :       data structure, either sem_function or sem_variables is created.
      37                 :            :    2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
      38                 :            :       saved and matched to corresponding sem_items.
      39                 :            :    3) These declaration are ignored for equality check and are solved
      40                 :            :       by Value Numbering algorithm published by Alpert, Zadeck in 1992.
      41                 :            :    4) We compute hash value for each symbol.
      42                 :            :    5) Congruence classes are created based on hash value. If hash value are
      43                 :            :       equal, equals function is called and symbols are deeply compared.
      44                 :            :       We must prove that all SSA names, declarations and other items
      45                 :            :       correspond.
      46                 :            :    6) Value Numbering is executed for these classes. At the end of the process
      47                 :            :       all symbol members in remaining classes can be merged.
      48                 :            :    7) Merge operation creates alias in case of read-only variables. For
      49                 :            :       callgraph node, we must decide if we can redirect local calls,
      50                 :            :       create an alias or a thunk.
      51                 :            : 
      52                 :            : */
      53                 :            : 
      54                 :            : #include "config.h"
      55                 :            : #include "system.h"
      56                 :            : #include "coretypes.h"
      57                 :            : #include "backend.h"
      58                 :            : #include "target.h"
      59                 :            : #include "rtl.h"
      60                 :            : #include "tree.h"
      61                 :            : #include "gimple.h"
      62                 :            : #include "alloc-pool.h"
      63                 :            : #include "tree-pass.h"
      64                 :            : #include "ssa.h"
      65                 :            : #include "cgraph.h"
      66                 :            : #include "coverage.h"
      67                 :            : #include "gimple-pretty-print.h"
      68                 :            : #include "data-streamer.h"
      69                 :            : #include "fold-const.h"
      70                 :            : #include "calls.h"
      71                 :            : #include "varasm.h"
      72                 :            : #include "gimple-iterator.h"
      73                 :            : #include "tree-cfg.h"
      74                 :            : #include "symbol-summary.h"
      75                 :            : #include "ipa-prop.h"
      76                 :            : #include "ipa-fnsummary.h"
      77                 :            : #include "except.h"
      78                 :            : #include "attribs.h"
      79                 :            : #include "print-tree.h"
      80                 :            : #include "ipa-utils.h"
      81                 :            : #include "ipa-icf-gimple.h"
      82                 :            : #include "fibonacci_heap.h"
      83                 :            : #include "ipa-icf.h"
      84                 :            : #include "stor-layout.h"
      85                 :            : #include "dbgcnt.h"
      86                 :            : #include "tree-vector-builder.h"
      87                 :            : 
      88                 :            : using namespace ipa_icf_gimple;
      89                 :            : 
      90                 :            : namespace ipa_icf {
      91                 :            : 
      92                 :            : /* Initialization and computation of symtab node hash, there data
      93                 :            :    are propagated later on.  */
      94                 :            : 
      95                 :            : static sem_item_optimizer *optimizer = NULL;
      96                 :            : 
      97                 :            : /* Constructor.  */
      98                 :            : 
      99                 :    1118750 : symbol_compare_collection::symbol_compare_collection (symtab_node *node)
     100                 :            : {
     101                 :    1118750 :   m_references.create (0);
     102                 :    1118750 :   m_interposables.create (0);
     103                 :            : 
     104                 :    1118750 :   ipa_ref *ref;
     105                 :            : 
     106                 :    1967480 :   if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
     107                 :    1118750 :     return;
     108                 :            : 
     109                 :    1435610 :   for (unsigned i = 0; node->iterate_reference (i, ref); i++)
     110                 :            :     {
     111                 :     317018 :       if (ref->address_matters_p ())
     112                 :     271302 :         m_references.safe_push (ref->referred);
     113                 :            : 
     114                 :     317018 :       if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
     115                 :            :         {
     116                 :     251219 :           if (ref->address_matters_p ())
     117                 :     248052 :             m_references.safe_push (ref->referred);
     118                 :            :           else
     119                 :       3167 :             m_interposables.safe_push (ref->referred);
     120                 :            :         }
     121                 :            :     }
     122                 :            : 
     123                 :    1118600 :   if (is_a <cgraph_node *> (node))
     124                 :            :     {
     125                 :     270028 :       cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
     126                 :            : 
     127                 :     563624 :       for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
     128                 :     293596 :         if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
     129                 :     101670 :           m_interposables.safe_push (e->callee);
     130                 :            :     }
     131                 :            : }
     132                 :            : 
     133                 :            : /* Constructor for key value pair, where _ITEM is key and _INDEX is a target.  */
     134                 :            : 
     135                 :   25725700 : sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
     136                 :   25725700 : : item (_item), index (_index)
     137                 :            : {
     138                 :   25725700 : }
     139                 :            : 
     140                 :          0 : sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack)
     141                 :          0 : : type (_type), referenced_by_count (0), m_hash (-1), m_hash_set (false)
     142                 :            : {
     143                 :          0 :   setup (stack);
     144                 :          0 : }
     145                 :            : 
     146                 :    2738810 : sem_item::sem_item (sem_item_type _type, symtab_node *_node,
     147                 :    2738810 :                     bitmap_obstack *stack)
     148                 :            : : type (_type), node (_node), referenced_by_count (0), m_hash (-1),
     149                 :    2738810 :   m_hash_set (false)
     150                 :            : {
     151                 :    2738810 :   decl = node->decl;
     152                 :    2738810 :   setup (stack);
     153                 :    2738810 : }
     154                 :            : 
     155                 :            : /* Add reference to a semantic TARGET.  */
     156                 :            : 
     157                 :            : void
     158                 :    3680520 : sem_item::add_reference (ref_map *refs,
     159                 :            :                          sem_item *target)
     160                 :            : {
     161                 :    3680520 :   unsigned index = reference_count++;
     162                 :    3680520 :   bool existed;
     163                 :            : 
     164                 :    3680520 :   vec<sem_item *> &v
     165                 :    3680520 :     = refs->get_or_insert (new sem_usage_pair (target, index), &existed);
     166                 :    3680520 :   v.safe_push (this);
     167                 :    3680520 :   bitmap_set_bit (target->usage_index_bitmap, index);
     168                 :    3680520 :   refs_set.add (target->node);
     169                 :    3680520 :   ++target->referenced_by_count;
     170                 :    3680520 : }
     171                 :            : 
     172                 :            : /* Initialize internal data structures. Bitmap STACK is used for
     173                 :            :    bitmap memory allocation process.  */
     174                 :            : 
     175                 :            : void
     176                 :    2738810 : sem_item::setup (bitmap_obstack *stack)
     177                 :            : {
     178                 :    2738810 :   gcc_checking_assert (node);
     179                 :            : 
     180                 :    2738810 :   reference_count = 0;
     181                 :    2738810 :   tree_refs.create (0);
     182                 :    2738810 :   usage_index_bitmap = BITMAP_ALLOC (stack);
     183                 :    2738810 : }
     184                 :            : 
     185                 :    7774520 : sem_item::~sem_item ()
     186                 :            : {
     187                 :    2591500 :   tree_refs.release ();
     188                 :            : 
     189                 :    2591500 :   BITMAP_FREE (usage_index_bitmap);
     190                 :    2591500 : }
     191                 :            : 
     192                 :            : /* Dump function for debugging purpose.  */
     193                 :            : 
     194                 :            : DEBUG_FUNCTION void
     195                 :          0 : sem_item::dump (void)
     196                 :            : {
     197                 :          0 :   if (dump_file)
     198                 :            :     {
     199                 :          0 :       fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var",
     200                 :          0 :                node->dump_name (), (void *) node->decl);
     201                 :          0 :       fprintf (dump_file, "  hash: %u\n", get_hash ());
     202                 :            :     }
     203                 :          0 : }
     204                 :            : 
     205                 :            : /* Return true if target supports alias symbols.  */
     206                 :            : 
     207                 :            : bool
     208                 :     364321 : sem_item::target_supports_symbol_aliases_p (void)
     209                 :            : {
     210                 :            : #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
     211                 :            :   return false;
     212                 :            : #else
     213                 :     364321 :   return true;
     214                 :            : #endif
     215                 :            : }
     216                 :            : 
     217                 :    6823860 : void sem_item::set_hash (hashval_t hash)
     218                 :            : {
     219                 :    6823860 :   m_hash = hash;
     220                 :    6823860 :   m_hash_set = true;
     221                 :    6823860 : }
     222                 :            : 
     223                 :            : hash_map<const_tree, hashval_t> sem_item::m_type_hash_cache;
     224                 :            : 
     225                 :            : /* Semantic function constructor that uses STACK as bitmap memory stack.  */
     226                 :            : 
     227                 :          0 : sem_function::sem_function (bitmap_obstack *stack)
     228                 :          0 : : sem_item (FUNC, stack), m_checker (NULL), m_compared_func (NULL)
     229                 :            : {
     230                 :          0 :   bb_sizes.create (0);
     231                 :          0 :   bb_sorted.create (0);
     232                 :          0 : }
     233                 :            : 
     234                 :     838643 : sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
     235                 :     838643 : : sem_item (FUNC, node, stack), m_checker (NULL), m_compared_func (NULL)
     236                 :            : {
     237                 :     838643 :   bb_sizes.create (0);
     238                 :     838643 :   bb_sorted.create (0);
     239                 :     838643 : }
     240                 :            : 
     241                 :    3210027 : sem_function::~sem_function ()
     242                 :            : {
     243                 :   13699000 :   for (unsigned i = 0; i < bb_sorted.length (); i++)
     244                 :    6062920 :     delete (bb_sorted[i]);
     245                 :            : 
     246                 :     802507 :   bb_sizes.release ();
     247                 :    1573190 :   bb_sorted.release ();
     248                 :    1605014 : }
     249                 :            : 
     250                 :            : /* Calculates hash value based on a BASIC_BLOCK.  */
     251                 :            : 
     252                 :            : hashval_t
     253                 :    5793480 : sem_function::get_bb_hash (const sem_bb *basic_block)
     254                 :            : {
     255                 :    5793480 :   inchash::hash hstate;
     256                 :            : 
     257                 :    5793480 :   hstate.add_int (basic_block->nondbg_stmt_count);
     258                 :    5793480 :   hstate.add_int (basic_block->edge_count);
     259                 :            : 
     260                 :    5793480 :   return hstate.end ();
     261                 :            : }
     262                 :            : 
     263                 :            : /* References independent hash function.  */
     264                 :            : 
     265                 :            : hashval_t
     266                 :    8400010 : sem_function::get_hash (void)
     267                 :            : {
     268                 :    8400010 :   if (!m_hash_set)
     269                 :            :     {
     270                 :     774166 :       inchash::hash hstate;
     271                 :     774166 :       hstate.add_int (177454); /* Random number for function type.  */
     272                 :            : 
     273                 :     774166 :       hstate.add_int (arg_count);
     274                 :     774166 :       hstate.add_int (cfg_checksum);
     275                 :     774166 :       hstate.add_int (gcode_hash);
     276                 :            : 
     277                 :   13135300 :       for (unsigned i = 0; i < bb_sorted.length (); i++)
     278                 :    5793480 :         hstate.merge_hash (get_bb_hash (bb_sorted[i]));
     279                 :            : 
     280                 :   13135300 :       for (unsigned i = 0; i < bb_sizes.length (); i++)
     281                 :    5793480 :         hstate.add_int (bb_sizes[i]);
     282                 :            : 
     283                 :            :       /* Add common features of declaration itself.  */
     284                 :     774166 :       if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
     285                 :     100543 :         hstate.add_hwi
     286                 :     100543 :          (cl_target_option_hash
     287                 :     100543 :            (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
     288                 :     774166 :       if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
     289                 :      91059 :         hstate.add_hwi
     290                 :      91059 :          (cl_optimization_hash
     291                 :      91059 :            (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
     292                 :     774166 :       hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
     293                 :     774166 :       hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
     294                 :            : 
     295                 :     774166 :       set_hash (hstate.end ());
     296                 :            :     }
     297                 :            : 
     298                 :    8400010 :   return m_hash;
     299                 :            : }
     300                 :            : 
     301                 :            : /* Compare properties of symbols N1 and N2 that does not affect semantics of
     302                 :            :    symbol itself but affects semantics of its references from USED_BY (which
     303                 :            :    may be NULL if it is unknown).  If comparison is false, symbols
     304                 :            :    can still be merged but any symbols referring them can't.
     305                 :            : 
     306                 :            :    If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
     307                 :            : 
     308                 :            :    TODO: We can also split attributes to those that determine codegen of
     309                 :            :    a function body/variable constructor itself and those that are used when
     310                 :            :    referring to it.  */
     311                 :            : 
     312                 :            : bool
     313                 :     410700 : sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
     314                 :            :                                                 symtab_node *n1,
     315                 :            :                                                 symtab_node *n2,
     316                 :            :                                                 bool address)
     317                 :            : {
     318                 :     410700 :   if (is_a <cgraph_node *> (n1))
     319                 :            :     {
     320                 :            :       /* Inline properties matters: we do now want to merge uses of inline
     321                 :            :          function to uses of normal function because inline hint would be lost.
     322                 :            :          We however can merge inline function to noinline because the alias
     323                 :            :          will keep its DECL_DECLARED_INLINE flag.
     324                 :            : 
     325                 :            :          Also ignore inline flag when optimizing for size or when function
     326                 :            :          is known to not be inlinable.
     327                 :            : 
     328                 :            :          TODO: the optimize_size checks can also be assumed to be true if
     329                 :            :          unit has no !optimize_size functions. */
     330                 :            : 
     331                 :    1101500 :       if ((!used_by || address || !is_a <cgraph_node *> (used_by)
     332                 :     294947 :            || !opt_for_fn (used_by->decl, optimize_size))
     333                 :     399363 :           && !opt_for_fn (n1->decl, optimize_size)
     334                 :     389002 :           && n1->get_availability () > AVAIL_INTERPOSABLE
     335                 :     547862 :           && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
     336                 :            :         {
     337                 :      53426 :           if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
     338                 :      53426 :               != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
     339                 :          0 :             return return_false_with_msg
     340                 :            :                      ("DECL_DISREGARD_INLINE_LIMITS are different");
     341                 :            : 
     342                 :      53426 :           if (DECL_DECLARED_INLINE_P (n1->decl)
     343                 :      53426 :               != DECL_DECLARED_INLINE_P (n2->decl))
     344                 :        342 :             return return_false_with_msg ("inline attributes are different");
     345                 :            :         }
     346                 :            : 
     347                 :     406852 :       if (DECL_IS_OPERATOR_NEW_P (n1->decl)
     348                 :     406852 :           != DECL_IS_OPERATOR_NEW_P (n2->decl))
     349                 :          0 :         return return_false_with_msg ("operator new flags are different");
     350                 :            : 
     351                 :     406852 :       if (DECL_IS_REPLACEABLE_OPERATOR (n1->decl)
     352                 :     406852 :           != DECL_IS_REPLACEABLE_OPERATOR (n2->decl))
     353                 :         84 :         return return_false_with_msg ("replaceable operator flags are different");
     354                 :            :     }
     355                 :            : 
     356                 :            :   /* Merging two definitions with a reference to equivalent vtables, but
     357                 :            :      belonging to a different type may result in ipa-polymorphic-call analysis
     358                 :            :      giving a wrong answer about the dynamic type of instance.  */
     359                 :     410274 :   if (is_a <varpool_node *> (n1))
     360                 :            :     {
     361                 :       5380 :       if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
     362                 :       1632 :           && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
     363                 :       1632 :               || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
     364                 :       1632 :                                               DECL_CONTEXT (n2->decl)))
     365                 :       6708 :           && (!used_by || !is_a <cgraph_node *> (used_by) || address
     366                 :       1570 :               || opt_for_fn (used_by->decl, flag_devirtualize)))
     367                 :       1632 :         return return_false_with_msg
     368                 :            :                  ("references to virtual tables cannot be merged");
     369                 :            : 
     370                 :       1874 :       if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
     371                 :          0 :         return return_false_with_msg ("alignment mismatch");
     372                 :            : 
     373                 :            :       /* For functions we compare attributes in equals_wpa, because we do
     374                 :            :          not know what attributes may cause codegen differences, but for
     375                 :            :          variables just compare attributes for references - the codegen
     376                 :            :          for constructors is affected only by those attributes that we lower
     377                 :            :          to explicit representation (such as DECL_ALIGN or DECL_SECTION).  */
     378                 :       1874 :       if (!attribute_list_equal (DECL_ATTRIBUTES (n1->decl),
     379                 :       1874 :                                  DECL_ATTRIBUTES (n2->decl)))
     380                 :          0 :         return return_false_with_msg ("different var decl attributes");
     381                 :       1874 :       if (comp_type_attributes (TREE_TYPE (n1->decl),
     382                 :       1874 :                                 TREE_TYPE (n2->decl)) != 1)
     383                 :          0 :         return return_false_with_msg ("different var type attributes");
     384                 :            :     }
     385                 :            : 
     386                 :            :   /* When matching virtual tables, be sure to also match information
     387                 :            :      relevant for polymorphic call analysis.  */
     388                 :     822107 :   if (used_by && is_a <varpool_node *> (used_by)
     389                 :     411407 :       && DECL_VIRTUAL_P (used_by->decl))
     390                 :            :     {
     391                 :       2761 :       if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
     392                 :          0 :         return return_false_with_msg ("virtual flag mismatch");
     393                 :       2761 :       if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
     394                 :       4251 :           && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
     395                 :          0 :         return return_false_with_msg ("final flag mismatch");
     396                 :            :     }
     397                 :            :   return true;
     398                 :            : }
     399                 :            : 
     400                 :            : /* Hash properties that are compared by compare_referenced_symbol_properties. */
     401                 :            : 
     402                 :            : void
     403                 :    5159720 : sem_item::hash_referenced_symbol_properties (symtab_node *ref,
     404                 :            :                                              inchash::hash &hstate,
     405                 :            :                                              bool address)
     406                 :            : {
     407                 :    5159720 :   if (is_a <cgraph_node *> (ref))
     408                 :            :     {
     409                 :    1097060 :       if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
     410                 :    1338250 :           && !opt_for_fn (ref->decl, optimize_size)
     411                 :    2684020 :           && !DECL_UNINLINABLE (ref->decl))
     412                 :            :         {
     413                 :    1042860 :           hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
     414                 :    1042860 :           hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
     415                 :            :         }
     416                 :    1362260 :       hstate.add_flag (DECL_IS_OPERATOR_NEW_P (ref->decl));
     417                 :            :     }
     418                 :    3797450 :   else if (is_a <varpool_node *> (ref))
     419                 :            :     {
     420                 :    3797450 :       hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
     421                 :    3797450 :       if (address)
     422                 :    2875380 :         hstate.add_int (DECL_ALIGN (ref->decl));
     423                 :            :     }
     424                 :    5159720 : }
     425                 :            : 
     426                 :            : 
     427                 :            : /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
     428                 :            :    point to a same function. Comparison can be skipped if IGNORED_NODES
     429                 :            :    contains these nodes.  ADDRESS indicate if address is taken.  */
     430                 :            : 
     431                 :            : bool
     432                 :     567626 : sem_item::compare_symbol_references (
     433                 :            :     hash_map <symtab_node *, sem_item *> &ignored_nodes,
     434                 :            :     symtab_node *n1, symtab_node *n2, bool address)
     435                 :            : {
     436                 :     567626 :   enum availability avail1, avail2;
     437                 :            : 
     438                 :     567626 :   if (n1 == n2)
     439                 :            :     return true;
     440                 :            : 
     441                 :            :   /* Never match variable and function.  */
     442                 :     899862 :   if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
     443                 :            :     return false;
     444                 :            : 
     445                 :     299954 :   if (!compare_referenced_symbol_properties (node, n1, n2, address))
     446                 :            :     return false;
     447                 :     297926 :   if (address && n1->equal_address_to (n2) == 1)
     448                 :            :     return true;
     449                 :     297926 :   if (!address && n1->semantically_equivalent_p (n2))
     450                 :            :     return true;
     451                 :            : 
     452                 :     297924 :   n1 = n1->ultimate_alias_target (&avail1);
     453                 :     297924 :   n2 = n2->ultimate_alias_target (&avail2);
     454                 :            : 
     455                 :     596371 :   if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
     456                 :     345617 :       && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
     457                 :            :     return true;
     458                 :            : 
     459                 :     250754 :   return return_false_with_msg ("different references");
     460                 :            : }
     461                 :            : 
     462                 :            : /* If cgraph edges E1 and E2 are indirect calls, verify that
     463                 :            :    ECF flags are the same.  */
     464                 :            : 
     465                 :     186268 : bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
     466                 :            : {
     467                 :     186268 :   if (e1->indirect_info && e2->indirect_info)
     468                 :            :     {
     469                 :       8571 :       int e1_flags = e1->indirect_info->ecf_flags;
     470                 :       8571 :       int e2_flags = e2->indirect_info->ecf_flags;
     471                 :            : 
     472                 :       8571 :       if (e1_flags != e2_flags)
     473                 :          0 :         return return_false_with_msg ("ICF flags are different");
     474                 :            :     }
     475                 :     177697 :   else if (e1->indirect_info || e2->indirect_info)
     476                 :          0 :     return false;
     477                 :            : 
     478                 :            :   return true;
     479                 :            : }
     480                 :            : 
     481                 :            : /* Return true if parameter I may be used.  */
     482                 :            : 
     483                 :            : bool
     484                 :    1684520 : sem_function::param_used_p (unsigned int i)
     485                 :            : {
     486                 :    1684520 :   if (ipa_node_params_sum == NULL)
     487                 :            :     return true;
     488                 :            : 
     489                 :    3369040 :   class ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
     490                 :            : 
     491                 :    3354400 :   if (!parms_info || vec_safe_length (parms_info->descriptors) <= i)
     492                 :     377802 :     return true;
     493                 :            : 
     494                 :    3920160 :   return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
     495                 :            : }
     496                 :            : 
     497                 :            : /* Perform additional check needed to match types function parameters that are
     498                 :            :    used.  Unlike for normal decls it matters if type is TYPE_RESTRICT and we
     499                 :            :    make an assumption that REFERENCE_TYPE parameters are always non-NULL.  */
     500                 :            : 
     501                 :            : bool
     502                 :    1538920 : sem_function::compatible_parm_types_p (tree parm1, tree parm2)
     503                 :            : {
     504                 :            :   /* Be sure that parameters are TBAA compatible.  */
     505                 :    1538920 :   if (!func_checker::compatible_types_p (parm1, parm2))
     506                 :        434 :     return return_false_with_msg ("parameter type is not compatible");
     507                 :            : 
     508                 :    1538490 :   if (POINTER_TYPE_P (parm1)
     509                 :    1933960 :       && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
     510                 :          0 :     return return_false_with_msg ("argument restrict flag mismatch");
     511                 :            : 
     512                 :            :   /* nonnull_arg_p implies non-zero range to REFERENCE types.  */
     513                 :    1538490 :   if (POINTER_TYPE_P (parm1)
     514                 :     395473 :       && TREE_CODE (parm1) != TREE_CODE (parm2)
     515                 :    1538490 :       && opt_for_fn (decl, flag_delete_null_pointer_checks))
     516                 :          0 :     return return_false_with_msg ("pointer wrt reference mismatch");
     517                 :            : 
     518                 :            :   return true;
     519                 :            : }
     520                 :            : 
     521                 :            : /* Fast equality function based on knowledge known in WPA.  */
     522                 :            : 
     523                 :            : bool
     524                 :    1362810 : sem_function::equals_wpa (sem_item *item,
     525                 :            :                           hash_map <symtab_node *, sem_item *> &ignored_nodes)
     526                 :            : {
     527                 :    1362810 :   gcc_assert (item->type == FUNC);
     528                 :    1362810 :   cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
     529                 :    1362810 :   cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
     530                 :            : 
     531                 :    1362810 :   m_compared_func = static_cast<sem_function *> (item);
     532                 :            : 
     533                 :    1362810 :   if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
     534                 :          0 :     return return_false_with_msg ("thunk_p mismatch");
     535                 :            : 
     536                 :    1362810 :   if (cnode->thunk.thunk_p)
     537                 :            :     {
     538                 :          0 :       if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
     539                 :          0 :         return return_false_with_msg ("thunk fixed_offset mismatch");
     540                 :          0 :       if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
     541                 :          0 :         return return_false_with_msg ("thunk virtual_value mismatch");
     542                 :          0 :       if (cnode->thunk.indirect_offset != cnode2->thunk.indirect_offset)
     543                 :          0 :         return return_false_with_msg ("thunk indirect_offset mismatch");
     544                 :          0 :       if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
     545                 :          0 :         return return_false_with_msg ("thunk this_adjusting mismatch");
     546                 :          0 :       if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
     547                 :          0 :         return return_false_with_msg ("thunk virtual_offset_p mismatch");
     548                 :            :     }
     549                 :            : 
     550                 :            :   /* Compare special function DECL attributes.  */
     551                 :    1362810 :   if (DECL_FUNCTION_PERSONALITY (decl)
     552                 :    1362810 :       != DECL_FUNCTION_PERSONALITY (item->decl))
     553                 :          0 :     return return_false_with_msg ("function personalities are different");
     554                 :            : 
     555                 :    1362810 :   if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
     556                 :    1362810 :        != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
     557                 :          0 :     return return_false_with_msg ("instrument function entry exit "
     558                 :            :                                   "attributes are different");
     559                 :            : 
     560                 :    1362810 :   if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
     561                 :          0 :     return return_false_with_msg ("no stack limit attributes are different");
     562                 :            : 
     563                 :    1362810 :   if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
     564                 :       1680 :     return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
     565                 :            : 
     566                 :    1361130 :   if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
     567                 :         85 :     return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
     568                 :            : 
     569                 :            :   /* TODO: pure/const flags mostly matters only for references, except for
     570                 :            :      the fact that codegen takes LOOPING flag as a hint that loops are
     571                 :            :      finite.  We may arrange the code to always pick leader that has least
     572                 :            :      specified flags and then this can go into comparing symbol properties.  */
     573                 :    1361050 :   if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
     574                 :      70233 :     return return_false_with_msg ("decl_or_type flags are different");
     575                 :            : 
     576                 :            :   /* Do not match polymorphic constructors of different types.  They calls
     577                 :            :      type memory location for ipa-polymorphic-call and we do not want
     578                 :            :      it to get confused by wrong type.  */
     579                 :    1290810 :   if (DECL_CXX_CONSTRUCTOR_P (decl)
     580                 :    1290810 :       && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
     581                 :            :     {
     582                 :       5203 :       if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
     583                 :          0 :         return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
     584                 :       5203 :       else if (!func_checker::compatible_polymorphic_types_p
     585                 :       5203 :                  (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
     586                 :       5203 :                   TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
     587                 :       2399 :         return return_false_with_msg ("ctor polymorphic type mismatch");
     588                 :            :     }
     589                 :            : 
     590                 :            :   /* Checking function TARGET and OPTIMIZATION flags.  */
     591                 :    1288420 :   cl_target_option *tar1 = target_opts_for_fn (decl);
     592                 :    1288420 :   cl_target_option *tar2 = target_opts_for_fn (item->decl);
     593                 :            : 
     594                 :    1288420 :   if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
     595                 :            :     {
     596                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     597                 :            :         {
     598                 :          0 :           fprintf (dump_file, "target flags difference");
     599                 :          0 :           cl_target_option_print_diff (dump_file, 2, tar1, tar2);
     600                 :            :         }
     601                 :            : 
     602                 :          0 :       return return_false_with_msg ("Target flags are different");
     603                 :            :     }
     604                 :            : 
     605                 :    1288420 :   cl_optimization *opt1 = opts_for_fn (decl);
     606                 :    1288420 :   cl_optimization *opt2 = opts_for_fn (item->decl);
     607                 :            : 
     608                 :    1288420 :   if (opt1 != opt2 && !cl_optimization_option_eq (opt1, opt2))
     609                 :            :     {
     610                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     611                 :            :         {
     612                 :          0 :           fprintf (dump_file, "optimization flags difference");
     613                 :          0 :           cl_optimization_print_diff (dump_file, 2, opt1, opt2);
     614                 :            :         }
     615                 :            : 
     616                 :          0 :       return return_false_with_msg ("optimization flags are different");
     617                 :            :     }
     618                 :            : 
     619                 :            :   /* Result type checking.  */
     620                 :    1288420 :   if (!func_checker::compatible_types_p
     621                 :    1288420 :          (TREE_TYPE (TREE_TYPE (decl)),
     622                 :    1288420 :           TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
     623                 :     734968 :     return return_false_with_msg ("result types are different");
     624                 :            : 
     625                 :            :   /* Checking types of arguments.  */
     626                 :     553447 :   tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
     627                 :     553447 :        list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
     628                 :    3066680 :   for (unsigned i = 0; list1 && list2;
     629                 :    1256620 :        list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
     630                 :            :     {
     631                 :    1423750 :       tree parm1 = TREE_VALUE (list1);
     632                 :    1423750 :       tree parm2 = TREE_VALUE (list2);
     633                 :            : 
     634                 :            :       /* This guard is here for function pointer with attributes (pr59927.c).  */
     635                 :    1423750 :       if (!parm1 || !parm2)
     636                 :          0 :         return return_false_with_msg ("NULL argument type");
     637                 :            : 
     638                 :            :       /* Verify that types are compatible to ensure that both functions
     639                 :            :          have same calling conventions.  */
     640                 :    1423750 :       if (!types_compatible_p (parm1, parm2))
     641                 :     166699 :         return return_false_with_msg ("parameter types are not compatible");
     642                 :            : 
     643                 :    1257050 :       if (!param_used_p (i))
     644                 :      37954 :         continue;
     645                 :            : 
     646                 :            :       /* Perform additional checks for used parameters.  */
     647                 :    1219100 :       if (!compatible_parm_types_p (parm1, parm2))
     648                 :            :         return false;
     649                 :            :     }
     650                 :            : 
     651                 :     386314 :   if (list1 || list2)
     652                 :         75 :     return return_false_with_msg ("Mismatched number of parameters");
     653                 :            : 
     654                 :     426005 :   if (node->num_references () != item->node->num_references ())
     655                 :          0 :     return return_false_with_msg ("different number of references");
     656                 :            : 
     657                 :            :   /* Checking function attributes.
     658                 :            :      This is quadratic in number of attributes  */
     659                 :     386239 :   if (comp_type_attributes (TREE_TYPE (decl),
     660                 :     386239 :                             TREE_TYPE (item->decl)) != 1)
     661                 :          5 :     return return_false_with_msg ("different type attributes");
     662                 :     386234 :   if (!attribute_list_equal (DECL_ATTRIBUTES (decl),
     663                 :     386234 :                              DECL_ATTRIBUTES (item->decl)))
     664                 :       2093 :     return return_false_with_msg ("different decl attributes");
     665                 :            : 
     666                 :            :   /* The type of THIS pointer type memory location for
     667                 :            :      ipa-polymorphic-call-analysis.  */
     668                 :     384141 :   if (opt_for_fn (decl, flag_devirtualize)
     669                 :     384070 :       && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
     670                 :     353607 :           || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
     671                 :      30495 :       && param_used_p (0)
     672                 :     411856 :       && compare_polymorphic_p ())
     673                 :            :     {
     674                 :      19601 :       if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
     675                 :          0 :         return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
     676                 :      19601 :       if (!func_checker::compatible_polymorphic_types_p
     677                 :      19601 :            (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
     678                 :      39202 :             TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
     679                 :       6319 :         return return_false_with_msg ("THIS pointer ODR type mismatch");
     680                 :            :     }
     681                 :            : 
     682                 :     412916 :   ipa_ref *ref = NULL, *ref2 = NULL;
     683                 :     412916 :   for (unsigned i = 0; node->iterate_reference (i, ref); i++)
     684                 :            :     {
     685                 :      36664 :       item->node->iterate_reference (i, ref2);
     686                 :            : 
     687                 :      36664 :       if (ref->use != ref2->use)
     688                 :          0 :         return return_false_with_msg ("reference use mismatch");
     689                 :            : 
     690                 :      36664 :       if (!compare_symbol_references (ignored_nodes, ref->referred,
     691                 :            :                                       ref2->referred,
     692                 :      36664 :                                       ref->address_matters_p ()))
     693                 :            :         return false;
     694                 :            :     }
     695                 :            : 
     696                 :     376252 :   cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
     697                 :     752504 :   cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
     698                 :            : 
     699                 :     553949 :   while (e1 && e2)
     700                 :            :     {
     701                 :     428828 :       if (!compare_symbol_references (ignored_nodes, e1->callee,
     702                 :     428828 :                                       e2->callee, false))
     703                 :            :         return false;
     704                 :     177697 :       if (!compare_edge_flags (e1, e2))
     705                 :            :         return false;
     706                 :            : 
     707                 :     177697 :       e1 = e1->next_callee;
     708                 :     177697 :       e2 = e2->next_callee;
     709                 :            :     }
     710                 :            : 
     711                 :     125121 :   if (e1 || e2)
     712                 :          0 :     return return_false_with_msg ("different number of calls");
     713                 :            : 
     714                 :     125121 :   e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
     715                 :     250242 :   e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
     716                 :            : 
     717                 :     133692 :   while (e1 && e2)
     718                 :            :     {
     719                 :       8571 :       if (!compare_edge_flags (e1, e2))
     720                 :            :         return false;
     721                 :            : 
     722                 :       8571 :       e1 = e1->next_callee;
     723                 :       8571 :       e2 = e2->next_callee;
     724                 :            :     }
     725                 :            : 
     726                 :     125121 :   if (e1 || e2)
     727                 :          0 :     return return_false_with_msg ("different number of indirect calls");
     728                 :            : 
     729                 :            :   return true;
     730                 :            : }
     731                 :            : 
     732                 :            : /* Update hash by address sensitive references. We iterate over all
     733                 :            :    sensitive references (address_matters_p) and we hash ultimate alias
     734                 :            :    target of these nodes, which can improve a semantic item hash.
     735                 :            : 
     736                 :            :    Also hash in referenced symbols properties.  This can be done at any time
     737                 :            :    (as the properties should not change), but it is convenient to do it here
     738                 :            :    while we walk the references anyway.  */
     739                 :            : 
     740                 :            : void
     741                 :    2026120 : sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
     742                 :            :                                     sem_item *> &m_symtab_node_map)
     743                 :            : {
     744                 :    2026120 :   ipa_ref* ref;
     745                 :    2026120 :   inchash::hash hstate (get_hash ());
     746                 :            : 
     747                 :    6208050 :   for (unsigned i = 0; node->iterate_reference (i, ref); i++)
     748                 :            :     {
     749                 :    4181930 :       hstate.add_int (ref->use);
     750                 :    4181930 :       hash_referenced_symbol_properties (ref->referred, hstate,
     751                 :    4181930 :                                          ref->use == IPA_REF_ADDR);
     752                 :    4181930 :       if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
     753                 :    4191780 :         hstate.add_int (ref->referred->ultimate_alias_target ()->order);
     754                 :            :     }
     755                 :            : 
     756                 :    2026120 :   if (is_a <cgraph_node *> (node))
     757                 :            :     {
     758                 :    1775900 :       for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
     759                 :     977791 :            e = e->next_caller)
     760                 :            :         {
     761                 :     977791 :           sem_item **result = m_symtab_node_map.get (e->callee);
     762                 :     977791 :           hash_referenced_symbol_properties (e->callee, hstate, false);
     763                 :     977791 :           if (!result)
     764                 :     977791 :             hstate.add_int (e->callee->ultimate_alias_target ()->order);
     765                 :            :         }
     766                 :            :     }
     767                 :            : 
     768                 :    2026120 :   set_hash (hstate.end ());
     769                 :    2026120 : }
     770                 :            : 
     771                 :            : /* Update hash by computed local hash values taken from different
     772                 :            :    semantic items.
     773                 :            :    TODO: stronger SCC based hashing would be desirable here.  */
     774                 :            : 
     775                 :            : void
     776                 :    2026120 : sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
     777                 :            :                                      sem_item *> &m_symtab_node_map)
     778                 :            : {
     779                 :    2026120 :   ipa_ref* ref;
     780                 :    2026120 :   inchash::hash state (get_hash ());
     781                 :            : 
     782                 :    6208050 :   for (unsigned j = 0; node->iterate_reference (j, ref); j++)
     783                 :            :     {
     784                 :    4181930 :       sem_item **result = m_symtab_node_map.get (ref->referring);
     785                 :    4181930 :       if (result)
     786                 :    4181930 :         state.merge_hash ((*result)->get_hash ());
     787                 :            :     }
     788                 :            : 
     789                 :    2026120 :   if (type == FUNC)
     790                 :            :     {
     791                 :    3979280 :       for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
     792                 :    3181170 :            e = e->next_callee)
     793                 :            :         {
     794                 :    3181170 :           sem_item **result = m_symtab_node_map.get (e->caller);
     795                 :          0 :           if (result)
     796                 :    3181170 :             state.merge_hash ((*result)->get_hash ());
     797                 :            :         }
     798                 :            :     }
     799                 :            : 
     800                 :    2026120 :   global_hash = state.end ();
     801                 :    2026120 : }
     802                 :            : 
     803                 :            : /* Returns true if the item equals to ITEM given as argument.  */
     804                 :            : 
     805                 :            : bool
     806                 :     270461 : sem_function::equals (sem_item *item,
     807                 :            :                       hash_map <symtab_node *, sem_item *> &)
     808                 :            : {
     809                 :     270461 :   gcc_assert (item->type == FUNC);
     810                 :     270461 :   bool eq = equals_private (item);
     811                 :            : 
     812                 :     270461 :   if (m_checker != NULL)
     813                 :            :     {
     814                 :     270461 :       delete m_checker;
     815                 :     270461 :       m_checker = NULL;
     816                 :            :     }
     817                 :            : 
     818                 :     270461 :   if (dump_file && (dump_flags & TDF_DETAILS))
     819                 :         36 :     fprintf (dump_file,
     820                 :            :              "Equals called for: %s:%s with result: %s\n\n",
     821                 :         18 :              node->dump_name (),
     822                 :         18 :              item->node->dump_name (),
     823                 :            :              eq ? "true" : "false");
     824                 :            : 
     825                 :     270461 :   return eq;
     826                 :            : }
     827                 :            : 
     828                 :            : /* Processes function equality comparison.  */
     829                 :            : 
     830                 :            : bool
     831                 :     270461 : sem_function::equals_private (sem_item *item)
     832                 :            : {
     833                 :     270461 :   if (item->type != FUNC)
     834                 :            :     return false;
     835                 :            : 
     836                 :     270461 :   basic_block bb1, bb2;
     837                 :     270461 :   edge e1, e2;
     838                 :     270461 :   edge_iterator ei1, ei2;
     839                 :     270461 :   bool result = true;
     840                 :     270461 :   tree arg1, arg2;
     841                 :            : 
     842                 :     270461 :   m_compared_func = static_cast<sem_function *> (item);
     843                 :            : 
     844                 :     270461 :   gcc_assert (decl != item->decl);
     845                 :            : 
     846                 :     540922 :   if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
     847                 :     270461 :       || edge_count != m_compared_func->edge_count
     848                 :     540922 :       || cfg_checksum != m_compared_func->cfg_checksum)
     849                 :          0 :     return return_false ();
     850                 :            : 
     851                 :     540922 :   m_checker = new func_checker (decl, m_compared_func->decl,
     852                 :            :                                 false,
     853                 :            :                                 &refs_set,
     854                 :     270461 :                                 &m_compared_func->refs_set);
     855                 :     270461 :   arg1 = DECL_ARGUMENTS (decl);
     856                 :     270461 :   arg2 = DECL_ARGUMENTS (m_compared_func->decl);
     857                 :     621244 :   for (unsigned i = 0;
     858                 :     621244 :        arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
     859                 :            :     {
     860                 :     351026 :       if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
     861                 :        243 :         return return_false_with_msg ("argument types are not compatible");
     862                 :     350783 :       if (!param_used_p (i))
     863                 :      30961 :         continue;
     864                 :            :       /* Perform additional checks for used parameters.  */
     865                 :     319822 :       if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
     866                 :            :         return false;
     867                 :     319822 :       if (!m_checker->compare_decl (arg1, arg2))
     868                 :          0 :         return return_false ();
     869                 :            :     }
     870                 :     270218 :   if (arg1 || arg2)
     871                 :          0 :     return return_false_with_msg ("Mismatched number of arguments");
     872                 :            : 
     873                 :     540436 :   if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
     874                 :            :     return true;
     875                 :            : 
     876                 :            :   /* Fill-up label dictionary.  */
     877                 :    3390250 :   for (unsigned i = 0; i < bb_sorted.length (); ++i)
     878                 :            :     {
     879                 :    1424900 :       m_checker->parse_labels (bb_sorted[i]);
     880                 :    1424900 :       m_checker->parse_labels (m_compared_func->bb_sorted[i]);
     881                 :            :     }
     882                 :            : 
     883                 :            :   /* Checking all basic blocks.  */
     884                 :    1610670 :   for (unsigned i = 0; i < bb_sorted.length (); ++i)
     885                 :     728678 :     if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
     886                 :     193562 :       return return_false ();
     887                 :            : 
     888                 :      76656 :   auto_vec <int> bb_dict;
     889                 :            : 
     890                 :            :   /* Basic block edges check.  */
     891                 :     792920 :   for (unsigned i = 0; i < bb_sorted.length (); ++i)
     892                 :            :     {
     893                 :     319804 :       bb1 = bb_sorted[i]->bb;
     894                 :     319804 :       bb2 = m_compared_func->bb_sorted[i]->bb;
     895                 :            : 
     896                 :     319804 :       ei2 = ei_start (bb2->preds);
     897                 :            : 
     898                 :     723276 :       for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
     899                 :            :         {
     900                 :     403472 :           ei_cond (ei2, &e2);
     901                 :            : 
     902                 :     403472 :           if (e1->flags != e2->flags)
     903                 :          0 :             return return_false_with_msg ("flags comparison returns false");
     904                 :            : 
     905                 :     403472 :           if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
     906                 :          0 :             return return_false_with_msg ("edge comparison returns false");
     907                 :            : 
     908                 :     403472 :           if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
     909                 :          0 :             return return_false_with_msg ("BB comparison returns false");
     910                 :            : 
     911                 :     403472 :           if (!m_checker->compare_edge (e1, e2))
     912                 :          0 :             return return_false_with_msg ("edge comparison returns false");
     913                 :            : 
     914                 :     403472 :           ei_next (&ei2);
     915                 :            :         }
     916                 :            :     }
     917                 :            : 
     918                 :            :   /* Basic block PHI nodes comparison.  */
     919                 :     767170 :   for (unsigned i = 0; i < bb_sorted.length (); i++)
     920                 :     308532 :     if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
     921                 :       1603 :       return return_false_with_msg ("PHI node comparison returns false");
     922                 :            : 
     923                 :            :   return result;
     924                 :            : }
     925                 :            : 
     926                 :            : /* Set LOCAL_P of NODE to true if DATA is non-NULL.
     927                 :            :    Helper for call_for_symbol_thunks_and_aliases.  */
     928                 :            : 
     929                 :            : static bool
     930                 :      39125 : set_local (cgraph_node *node, void *data)
     931                 :            : {
     932                 :      39125 :   node->local = data != NULL;
     933                 :      39125 :   return false;
     934                 :            : }
     935                 :            : 
     936                 :            : /* TREE_ADDRESSABLE of NODE to true.
     937                 :            :    Helper for call_for_symbol_thunks_and_aliases.  */
     938                 :            : 
     939                 :            : static bool
     940                 :         11 : set_addressable (varpool_node *node, void *)
     941                 :            : {
     942                 :         11 :   TREE_ADDRESSABLE (node->decl) = 1;
     943                 :         11 :   return false;
     944                 :            : }
     945                 :            : 
     946                 :            : /* Clear DECL_RTL of NODE. 
     947                 :            :    Helper for call_for_symbol_thunks_and_aliases.  */
     948                 :            : 
     949                 :            : static bool
     950                 :      17043 : clear_decl_rtl (symtab_node *node, void *)
     951                 :            : {
     952                 :      17043 :   SET_DECL_RTL (node->decl, NULL);
     953                 :      17043 :   return false;
     954                 :            : }
     955                 :            : 
     956                 :            : /* Redirect all callers of N and its aliases to TO.  Remove aliases if
     957                 :            :    possible.  Return number of redirections made.  */
     958                 :            : 
     959                 :            : static int
     960                 :      16655 : redirect_all_callers (cgraph_node *n, cgraph_node *to)
     961                 :            : {
     962                 :      16655 :   int nredirected = 0;
     963                 :      16655 :   ipa_ref *ref;
     964                 :      16655 :   cgraph_edge *e = n->callers;
     965                 :            : 
     966                 :      17045 :   while (e)
     967                 :            :     {
     968                 :            :       /* Redirecting thunks to interposable symbols or symbols in other sections
     969                 :            :          may not be supported by target output code.  Play safe for now and
     970                 :            :          punt on redirection.  */
     971                 :        390 :       if (!e->caller->thunk.thunk_p)
     972                 :            :         {
     973                 :        390 :           struct cgraph_edge *nexte = e->next_caller;
     974                 :        390 :           e->redirect_callee (to);
     975                 :        390 :           e = nexte;
     976                 :        390 :           nredirected++;
     977                 :            :         }
     978                 :            :       else
     979                 :          0 :         e = e->next_callee;
     980                 :            :     }
     981                 :      16683 :   for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
     982                 :            :     {
     983                 :          6 :       bool removed = false;
     984                 :          6 :       cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
     985                 :            : 
     986                 :          6 :       if ((DECL_COMDAT_GROUP (n->decl)
     987                 :          0 :            && (DECL_COMDAT_GROUP (n->decl)
     988                 :          0 :                == DECL_COMDAT_GROUP (n_alias->decl)))
     989                 :          6 :           || (n_alias->get_availability () > AVAIL_INTERPOSABLE
     990                 :          6 :               && n->get_availability () > AVAIL_INTERPOSABLE))
     991                 :            :         {
     992                 :          6 :           nredirected += redirect_all_callers (n_alias, to);
     993                 :          6 :           if (n_alias->can_remove_if_no_direct_calls_p ()
     994                 :          0 :               && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
     995                 :            :                                                         NULL, true)
     996                 :          6 :               && !n_alias->has_aliases_p ())
     997                 :          0 :             n_alias->remove ();
     998                 :            :         }
     999                 :          6 :       if (!removed)
    1000                 :          6 :         i++;
    1001                 :            :     }
    1002                 :      16655 :   return nredirected;
    1003                 :            : }
    1004                 :            : 
    1005                 :            : /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
    1006                 :            :    be applied.  */
    1007                 :            : 
    1008                 :            : bool
    1009                 :      74176 : sem_function::merge (sem_item *alias_item)
    1010                 :            : {
    1011                 :      74176 :   gcc_assert (alias_item->type == FUNC);
    1012                 :            : 
    1013                 :      74176 :   sem_function *alias_func = static_cast<sem_function *> (alias_item);
    1014                 :            : 
    1015                 :      74176 :   cgraph_node *original = get_node ();
    1016                 :      74176 :   cgraph_node *local_original = NULL;
    1017                 :      74176 :   cgraph_node *alias = alias_func->get_node ();
    1018                 :            : 
    1019                 :      74176 :   bool create_wrapper = false;
    1020                 :      74176 :   bool create_alias = false;
    1021                 :      74176 :   bool redirect_callers = false;
    1022                 :      74176 :   bool remove = false;
    1023                 :            : 
    1024                 :      74176 :   bool original_discardable = false;
    1025                 :      74176 :   bool original_discarded = false;
    1026                 :            : 
    1027                 :      74176 :   bool original_address_matters = original->address_matters_p ();
    1028                 :      74176 :   bool alias_address_matters = alias->address_matters_p ();
    1029                 :            : 
    1030                 :      74176 :   AUTO_DUMP_SCOPE ("merge",
    1031                 :            :                    dump_user_location_t::from_function_decl (decl));
    1032                 :            : 
    1033                 :      74176 :   if (DECL_EXTERNAL (alias->decl))
    1034                 :            :     {
    1035                 :        583 :       if (dump_enabled_p ())
    1036                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1037                 :            :                      "Not unifying; alias is external.\n");
    1038                 :        583 :       return false;
    1039                 :            :     }
    1040                 :            : 
    1041                 :      73593 :   if (DECL_NO_INLINE_WARNING_P (original->decl)
    1042                 :      73593 :       != DECL_NO_INLINE_WARNING_P (alias->decl))
    1043                 :            :     {
    1044                 :        455 :       if (dump_enabled_p ())
    1045                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1046                 :            :                      "Not unifying; DECL_NO_INLINE_WARNING mismatch.\n");
    1047                 :        455 :       return false;
    1048                 :            :     }
    1049                 :            : 
    1050                 :            :   /* Do not attempt to mix functions from different user sections;
    1051                 :            :      we do not know what user intends with those.  */
    1052                 :      73146 :   if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
    1053                 :      73138 :        || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
    1054                 :      73138 :       && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
    1055                 :            :     {
    1056                 :          0 :       if (dump_enabled_p ())
    1057                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1058                 :            :                      "Not unifying; "
    1059                 :            :                      "original and alias are in different sections.\n");
    1060                 :          0 :       return false;
    1061                 :            :     }
    1062                 :            : 
    1063                 :      73138 :   if (!original->in_same_comdat_group_p (alias)
    1064                 :      73138 :       || original->comdat_local_p ())
    1065                 :            :     {
    1066                 :       6393 :       if (dump_enabled_p ())
    1067                 :          4 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1068                 :            :                      "Not unifying; alias nor wrapper cannot be created; "
    1069                 :            :                      "across comdat group boundary\n");
    1070                 :       6393 :       return false;
    1071                 :            :     }
    1072                 :            : 
    1073                 :            :   /* See if original is in a section that can be discarded if the main
    1074                 :            :      symbol is not used.  */
    1075                 :            : 
    1076                 :      66745 :   if (original->can_be_discarded_p ())
    1077                 :          2 :     original_discardable = true;
    1078                 :            :   /* Also consider case where we have resolution info and we know that
    1079                 :            :      original's definition is not going to be used.  In this case we cannot
    1080                 :            :      create alias to original.  */
    1081                 :      66745 :   if (node->resolution != LDPR_UNKNOWN
    1082                 :      66745 :       && !decl_binds_to_current_def_p (node->decl))
    1083                 :            :     original_discardable = original_discarded = true;
    1084                 :            : 
    1085                 :            :   /* Creating a symtab alias is the optimal way to merge.
    1086                 :            :      It however cannot be used in the following cases:
    1087                 :            : 
    1088                 :            :      1) if ORIGINAL and ALIAS may be possibly compared for address equality.
    1089                 :            :      2) if ORIGINAL is in a section that may be discarded by linker or if
    1090                 :            :         it is an external functions where we cannot create an alias
    1091                 :            :         (ORIGINAL_DISCARDABLE)
    1092                 :            :      3) if target do not support symbol aliases.
    1093                 :            :      4) original and alias lie in different comdat groups.
    1094                 :            : 
    1095                 :            :      If we cannot produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
    1096                 :            :      and/or redirect all callers from ALIAS to ORIGINAL.  */
    1097                 :      66745 :   if ((original_address_matters && alias_address_matters)
    1098                 :      11374 :       || (original_discardable
    1099                 :          2 :           && (!DECL_COMDAT_GROUP (alias->decl)
    1100                 :          0 :               || (DECL_COMDAT_GROUP (alias->decl)
    1101                 :          0 :                   != DECL_COMDAT_GROUP (original->decl))))
    1102                 :      11372 :       || original_discarded
    1103                 :      11372 :       || !sem_item::target_supports_symbol_aliases_p ()
    1104                 :      78117 :       || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
    1105                 :            :     {
    1106                 :            :       /* First see if we can produce wrapper.  */
    1107                 :            : 
    1108                 :            :       /* Symbol properties that matter for references must be preserved.
    1109                 :            :          TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
    1110                 :            :          with proper properties.  */
    1111                 :      55373 :       if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
    1112                 :      55373 :                                                            alias->address_taken))
    1113                 :            :         {
    1114                 :         15 :           if (dump_enabled_p ())
    1115                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1116                 :            :                          "Wrapper cannot be created because referenced symbol "
    1117                 :            :                          "properties mismatch\n");
    1118                 :            :         }
    1119                 :            :       /* Do not turn function in one comdat group into wrapper to another
    1120                 :            :          comdat group. Other compiler producing the body of the
    1121                 :            :          another comdat group may make opposite decision and with unfortunate
    1122                 :            :          linker choices this may close a loop.  */
    1123                 :      55358 :       else if (DECL_COMDAT_GROUP (original->decl)
    1124                 :          0 :                && DECL_COMDAT_GROUP (alias->decl)
    1125                 :      55358 :                && (DECL_COMDAT_GROUP (alias->decl)
    1126                 :          0 :                    != DECL_COMDAT_GROUP (original->decl)))
    1127                 :            :         {
    1128                 :          0 :           if (dump_enabled_p ())
    1129                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1130                 :            :                          "Wrapper cannot be created because of COMDAT\n");
    1131                 :            :         }
    1132                 :      55358 :       else if (DECL_STATIC_CHAIN (alias->decl)
    1133                 :      55358 :                || DECL_STATIC_CHAIN (original->decl))
    1134                 :            :         {
    1135                 :        560 :           if (dump_enabled_p ())
    1136                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1137                 :            :                          "Cannot create wrapper of nested function.\n");
    1138                 :            :         }
    1139                 :            :       /* TODO: We can also deal with variadic functions never calling
    1140                 :            :          VA_START.  */
    1141                 :      54798 :       else if (stdarg_p (TREE_TYPE (alias->decl)))
    1142                 :            :         {
    1143                 :       1031 :           if (dump_enabled_p ())
    1144                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1145                 :            :                          "cannot create wrapper of stdarg function.\n");
    1146                 :            :         }
    1147                 :      53767 :       else if (ipa_fn_summaries
    1148                 :      53767 :                && ipa_size_summaries->get (alias) != NULL
    1149                 :      53760 :                && ipa_size_summaries->get (alias)->self_size <= 2)
    1150                 :            :         {
    1151                 :          8 :           if (dump_enabled_p ())
    1152                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION, "Wrapper creation is not "
    1153                 :            :                          "profitable (function is too small).\n");
    1154                 :            :         }
    1155                 :            :       /* If user paid attention to mark function noinline, assume it is
    1156                 :            :          somewhat special and do not try to turn it into a wrapper that
    1157                 :            :          cannot be undone by inliner.  */
    1158                 :      53759 :       else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
    1159                 :            :         {
    1160                 :      35300 :           if (dump_enabled_p ())
    1161                 :         26 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1162                 :            :                          "Wrappers are not created for noinline.\n");
    1163                 :            :         }
    1164                 :            :       else
    1165                 :            :         create_wrapper = true;
    1166                 :            : 
    1167                 :            :       /* We can redirect local calls in the case both alias and original
    1168                 :            :          are not interposable.  */
    1169                 :      55373 :       redirect_callers
    1170                 :      55373 :         = alias->get_availability () > AVAIL_INTERPOSABLE
    1171                 :      55373 :           && original->get_availability () > AVAIL_INTERPOSABLE;
    1172                 :            :       /* TODO: We can redirect, but we need to produce alias of ORIGINAL
    1173                 :            :          with proper properties.  */
    1174                 :      55373 :       if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
    1175                 :      55373 :                                                            alias->address_taken))
    1176                 :         15 :         redirect_callers = false;
    1177                 :            : 
    1178                 :      55373 :       if (!redirect_callers && !create_wrapper)
    1179                 :            :         {
    1180                 :         30 :           if (dump_enabled_p ())
    1181                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1182                 :            :                          "Not unifying; cannot redirect callers nor "
    1183                 :            :                          "produce wrapper\n");
    1184                 :         30 :           return false;
    1185                 :            :         }
    1186                 :            : 
    1187                 :            :       /* Work out the symbol the wrapper should call.
    1188                 :            :          If ORIGINAL is interposable, we need to call a local alias.
    1189                 :            :          Also produce local alias (if possible) as an optimization.
    1190                 :            : 
    1191                 :            :          Local aliases cannot be created inside comdat groups because that
    1192                 :            :          prevents inlining.  */
    1193                 :      55343 :       if (!original_discardable && !original->get_comdat_group ())
    1194                 :            :         {
    1195                 :      55343 :           local_original
    1196                 :      55343 :             = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
    1197                 :          0 :           if (!local_original
    1198                 :          0 :               && original->get_availability () > AVAIL_INTERPOSABLE)
    1199                 :            :             local_original = original;
    1200                 :            :         }
    1201                 :            :       /* If we cannot use local alias, fallback to the original
    1202                 :            :          when possible.  */
    1203                 :          0 :       else if (original->get_availability () > AVAIL_INTERPOSABLE)
    1204                 :          0 :         local_original = original;
    1205                 :            : 
    1206                 :            :       /* If original is COMDAT local, we cannot really redirect calls outside
    1207                 :            :          of its comdat group to it.  */
    1208                 :      55343 :       if (original->comdat_local_p ())
    1209                 :            :         redirect_callers = false;
    1210                 :      55343 :       if (!local_original)
    1211                 :            :         {
    1212                 :          0 :           if (dump_enabled_p ())
    1213                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1214                 :            :                          "Not unifying; cannot produce local alias.\n");
    1215                 :          0 :           return false;
    1216                 :            :         }
    1217                 :            : 
    1218                 :      55343 :       if (!redirect_callers && !create_wrapper)
    1219                 :            :         {
    1220                 :          0 :           if (dump_enabled_p ())
    1221                 :          0 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1222                 :            :                          "Not unifying; "
    1223                 :            :                          "cannot redirect callers nor produce a wrapper\n");
    1224                 :          0 :           return false;
    1225                 :            :         }
    1226                 :      55343 :       if (!create_wrapper
    1227                 :      36884 :           && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
    1228                 :            :                                                   NULL, true)
    1229                 :      92227 :           && !alias->can_remove_if_no_direct_calls_p ())
    1230                 :            :         {
    1231                 :      36884 :           if (dump_enabled_p ())
    1232                 :         26 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    1233                 :            :                          "Not unifying; cannot make wrapper and "
    1234                 :            :                          "function has other uses than direct calls\n");
    1235                 :      36884 :           return false;
    1236                 :            :         }
    1237                 :            :     }
    1238                 :            :   else
    1239                 :            :     create_alias = true;
    1240                 :            : 
    1241                 :      29831 :   if (redirect_callers)
    1242                 :            :     {
    1243                 :      16649 :       int nredirected = redirect_all_callers (alias, local_original);
    1244                 :            : 
    1245                 :      16649 :       if (nredirected)
    1246                 :            :         {
    1247                 :        246 :           alias->icf_merged = true;
    1248                 :        246 :           local_original->icf_merged = true;
    1249                 :            : 
    1250                 :        246 :           if (dump_enabled_p ())
    1251                 :          3 :             dump_printf (MSG_NOTE,
    1252                 :            :                          "%i local calls have been "
    1253                 :            :                          "redirected.\n", nredirected);
    1254                 :            :         }
    1255                 :            : 
    1256                 :            :       /* If all callers was redirected, do not produce wrapper.  */
    1257                 :      16649 :       if (alias->can_remove_if_no_direct_calls_p ()
    1258                 :          0 :           && !DECL_VIRTUAL_P (alias->decl)
    1259                 :      16649 :           && !alias->has_aliases_p ())
    1260                 :            :         {
    1261                 :            :           create_wrapper = false;
    1262                 :            :           remove = true;
    1263                 :            :         }
    1264                 :      16649 :       gcc_assert (!create_alias);
    1265                 :            :     }
    1266                 :      13182 :   else if (create_alias)
    1267                 :            :     {
    1268                 :      11372 :       alias->icf_merged = true;
    1269                 :            : 
    1270                 :            :       /* Remove the function's body.  */
    1271                 :      11372 :       ipa_merge_profiles (original, alias);
    1272                 :      11372 :       symtab->call_cgraph_removal_hooks (alias);
    1273                 :      11372 :       alias->release_body (true);
    1274                 :      11372 :       alias->reset ();
    1275                 :            :       /* Notice global symbol possibly produced RTL.  */
    1276                 :      11372 :       ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
    1277                 :            :                                                            NULL, true);
    1278                 :            : 
    1279                 :            :       /* Create the alias.  */
    1280                 :      11372 :       cgraph_node::create_alias (alias_func->decl, decl);
    1281                 :      11372 :       alias->resolve_alias (original);
    1282                 :            : 
    1283                 :      11372 :       original->call_for_symbol_thunks_and_aliases
    1284                 :      11372 :          (set_local, (void *)(size_t) original->local_p (), true);
    1285                 :            : 
    1286                 :      11372 :       if (dump_enabled_p ())
    1287                 :         23 :         dump_printf (MSG_OPTIMIZED_LOCATIONS,
    1288                 :            :                      "Unified; Function alias has been created.\n");
    1289                 :            :     }
    1290                 :      29831 :   if (create_wrapper)
    1291                 :            :     {
    1292                 :      18459 :       gcc_assert (!create_alias);
    1293                 :      18459 :       alias->icf_merged = true;
    1294                 :      18459 :       symtab->call_cgraph_removal_hooks (alias);
    1295                 :      18459 :       local_original->icf_merged = true;
    1296                 :            : 
    1297                 :            :       /* FIXME update local_original counts.  */
    1298                 :      18459 :       ipa_merge_profiles (original, alias, true);
    1299                 :      18459 :       alias->create_wrapper (local_original);
    1300                 :      18459 :       symtab->call_cgraph_insertion_hooks (alias);
    1301                 :            : 
    1302                 :      18459 :       if (dump_enabled_p ())
    1303                 :         20 :         dump_printf (MSG_OPTIMIZED_LOCATIONS,
    1304                 :            :                      "Unified; Wrapper has been created.\n");
    1305                 :            :     }
    1306                 :            : 
    1307                 :            :   /* It's possible that redirection can hit thunks that block
    1308                 :            :      redirection opportunities.  */
    1309                 :      29831 :   gcc_assert (alias->icf_merged || remove || redirect_callers);
    1310                 :      29831 :   original->icf_merged = true;
    1311                 :            : 
    1312                 :            :   /* We use merged flag to track cases where COMDAT function is known to be
    1313                 :            :      compatible its callers.  If we merged in non-COMDAT, we need to give up
    1314                 :            :      on this optimization.  */
    1315                 :      29831 :   if (original->merged_comdat && !alias->merged_comdat)
    1316                 :            :     {
    1317                 :          0 :       if (dump_enabled_p ())
    1318                 :          0 :         dump_printf (MSG_NOTE, "Dropping merged_comdat flag.\n");
    1319                 :          0 :       if (local_original)
    1320                 :          0 :         local_original->merged_comdat = false;
    1321                 :          0 :       original->merged_comdat = false;
    1322                 :            :     }
    1323                 :            : 
    1324                 :      29831 :   if (remove)
    1325                 :            :     {
    1326                 :          0 :       ipa_merge_profiles (original, alias);
    1327                 :          0 :       alias->release_body ();
    1328                 :          0 :       alias->reset ();
    1329                 :          0 :       alias->body_removed = true;
    1330                 :          0 :       alias->icf_merged = true;
    1331                 :          0 :       if (dump_enabled_p ())
    1332                 :          0 :         dump_printf (MSG_OPTIMIZED_LOCATIONS,
    1333                 :            :                      "Unified; Function body was removed.\n");
    1334                 :            :     }
    1335                 :            : 
    1336                 :            :   return true;
    1337                 :            : }
    1338                 :            : 
    1339                 :            : /* Semantic item initialization function.  */
    1340                 :            : 
    1341                 :            : void
    1342                 :     932085 : sem_function::init (ipa_icf_gimple::func_checker *checker)
    1343                 :            : {
    1344                 :     932085 :   m_checker = checker;
    1345                 :     932085 :   if (in_lto_p)
    1346                 :      65218 :     get_node ()->get_untransformed_body ();
    1347                 :            : 
    1348                 :     932085 :   tree fndecl = node->decl;
    1349                 :     932085 :   function *func = DECL_STRUCT_FUNCTION (fndecl);
    1350                 :            : 
    1351                 :     932085 :   gcc_assert (func);
    1352                 :     932085 :   gcc_assert (SSANAMES (func));
    1353                 :            : 
    1354                 :     932085 :   ssa_names_size = SSANAMES (func)->length ();
    1355                 :     932085 :   node = node;
    1356                 :            : 
    1357                 :     932085 :   decl = fndecl;
    1358                 :     932085 :   region_tree = func->eh->region_tree;
    1359                 :            : 
    1360                 :            :   /* iterating all function arguments.  */
    1361                 :     932085 :   arg_count = count_formal_params (fndecl);
    1362                 :            : 
    1363                 :     932085 :   edge_count = n_edges_for_fn (func);
    1364                 :     932085 :   cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
    1365                 :     932085 :   if (!cnode->thunk.thunk_p)
    1366                 :            :     {
    1367                 :     932085 :       cfg_checksum = coverage_compute_cfg_checksum (func);
    1368                 :            : 
    1369                 :     932085 :       inchash::hash hstate;
    1370                 :            : 
    1371                 :     932085 :       basic_block bb;
    1372                 :    7177940 :       FOR_EACH_BB_FN (bb, func)
    1373                 :            :       {
    1374                 :    6245850 :         unsigned nondbg_stmt_count = 0;
    1375                 :            : 
    1376                 :    6245850 :         edge e;
    1377                 :   14818900 :         for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
    1378                 :    8573030 :              ei_next (&ei))
    1379                 :    8573030 :           cfg_checksum = iterative_hash_host_wide_int (e->flags,
    1380                 :            :                          cfg_checksum);
    1381                 :            : 
    1382                 :   49622200 :         for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    1383                 :   37130500 :              gsi_next (&gsi))
    1384                 :            :           {
    1385                 :   37130500 :             gimple *stmt = gsi_stmt (gsi);
    1386                 :            : 
    1387                 :   37130500 :             if (gimple_code (stmt) != GIMPLE_DEBUG
    1388                 :   37130500 :                 && gimple_code (stmt) != GIMPLE_PREDICT)
    1389                 :            :               {
    1390                 :   19838700 :                 hash_stmt (stmt, hstate);
    1391                 :   19838700 :                 nondbg_stmt_count++;
    1392                 :            :               }
    1393                 :            :           }
    1394                 :            : 
    1395                 :    6245850 :         hstate.commit_flag ();
    1396                 :    6245850 :         gcode_hash = hstate.end ();
    1397                 :    6245850 :         bb_sizes.safe_push (nondbg_stmt_count);
    1398                 :            : 
    1399                 :            :         /* Inserting basic block to hash table.  */
    1400                 :    6245850 :         sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
    1401                 :    6245850 :                                           EDGE_COUNT (bb->preds)
    1402                 :   12489400 :                                           + EDGE_COUNT (bb->succs));
    1403                 :            : 
    1404                 :    6245850 :         bb_sorted.safe_push (semantic_bb);
    1405                 :            :       }
    1406                 :            :     }
    1407                 :            :   else
    1408                 :            :     {
    1409                 :          0 :       cfg_checksum = 0;
    1410                 :          0 :       inchash::hash hstate;
    1411                 :          0 :       hstate.add_hwi (cnode->thunk.fixed_offset);
    1412                 :          0 :       hstate.add_hwi (cnode->thunk.virtual_value);
    1413                 :          0 :       hstate.add_flag (cnode->thunk.this_adjusting);
    1414                 :          0 :       hstate.add_flag (cnode->thunk.virtual_offset_p);
    1415                 :          0 :       gcode_hash = hstate.end ();
    1416                 :            :     }
    1417                 :            : 
    1418                 :     932085 :   m_checker = NULL;
    1419                 :     932085 : }
    1420                 :            : 
    1421                 :            : /* Improve accumulated hash for HSTATE based on a gimple statement STMT.  */
    1422                 :            : 
    1423                 :            : void
    1424                 :   19838700 : sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
    1425                 :            : {
    1426                 :   19838700 :   enum gimple_code code = gimple_code (stmt);
    1427                 :            : 
    1428                 :   19838700 :   hstate.add_int (code);
    1429                 :            : 
    1430                 :   19838700 :   switch (code)
    1431                 :            :     {
    1432                 :      16529 :     case GIMPLE_SWITCH:
    1433                 :      16529 :       m_checker->hash_operand (gimple_switch_index (as_a <gswitch *> (stmt)),
    1434                 :      16529 :                              hstate, 0);
    1435                 :      16529 :       break;
    1436                 :   12629200 :     case GIMPLE_ASSIGN:
    1437                 :   12629200 :       hstate.add_int (gimple_assign_rhs_code (stmt));
    1438                 :   12629200 :       if (commutative_tree_code (gimple_assign_rhs_code (stmt))
    1439                 :   12629200 :           || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
    1440                 :            :         {
    1441                 :    1678710 :           m_checker->hash_operand (gimple_assign_rhs1 (stmt), hstate, 0);
    1442                 :    1678710 :           m_checker->hash_operand (gimple_assign_rhs2 (stmt), hstate, 0);
    1443                 :    1678710 :           if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
    1444                 :          0 :             m_checker->hash_operand (gimple_assign_rhs3 (stmt), hstate, 0);
    1445                 :    1678710 :           m_checker->hash_operand (gimple_assign_lhs (stmt), hstate, 0);
    1446                 :            :         }
    1447                 :            :       /* fall through */
    1448                 :            :     case GIMPLE_CALL:
    1449                 :            :     case GIMPLE_ASM:
    1450                 :            :     case GIMPLE_COND:
    1451                 :            :     case GIMPLE_GOTO:
    1452                 :            :     case GIMPLE_RETURN:
    1453                 :            :       /* All these statements are equivalent if their operands are.  */
    1454                 :   75486700 :       for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
    1455                 :   56063300 :         m_checker->hash_operand (gimple_op (stmt, i), hstate, 0);
    1456                 :            :       /* Consider nocf_check attribute in hash as it affects code
    1457                 :            :          generation.  */
    1458                 :   19423300 :       if (code == GIMPLE_CALL
    1459                 :    3535630 :           && flag_cf_protection & CF_BRANCH)
    1460                 :     999568 :         hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
    1461                 :            :     default:
    1462                 :            :       break;
    1463                 :            :     }
    1464                 :   19838700 : }
    1465                 :            : 
    1466                 :            : 
    1467                 :            : /* Return true if polymorphic comparison must be processed.  */
    1468                 :            : 
    1469                 :            : bool
    1470                 :      64802 : sem_function::compare_polymorphic_p (void)
    1471                 :            : {
    1472                 :      64802 :   struct cgraph_edge *e;
    1473                 :            : 
    1474                 :     129604 :   if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
    1475                 :            :     return false;
    1476                 :     129604 :   if (get_node ()->indirect_calls != NULL)
    1477                 :            :     return true;
    1478                 :            :   /* TODO: We can do simple propagation determining what calls may lead to
    1479                 :            :      a polymorphic call.  */
    1480                 :     146522 :   for (e = get_node ()->callees; e; e = e->next_callee)
    1481                 :      68414 :     if (e->callee->definition
    1482                 :      68414 :         && opt_for_fn (e->callee->decl, flag_devirtualize))
    1483                 :            :       return true;
    1484                 :            :   return false;
    1485                 :            : }
    1486                 :            : 
    1487                 :            : /* For a given call graph NODE, the function constructs new
    1488                 :            :    semantic function item.  */
    1489                 :            : 
    1490                 :            : sem_function *
    1491                 :     836070 : sem_function::parse (cgraph_node *node, bitmap_obstack *stack,
    1492                 :            :                      func_checker *checker)
    1493                 :            : {
    1494                 :     836070 :   tree fndecl = node->decl;
    1495                 :     836070 :   function *func = DECL_STRUCT_FUNCTION (fndecl);
    1496                 :            : 
    1497                 :     871043 :   if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
    1498                 :            :     return NULL;
    1499                 :            : 
    1500                 :     796541 :   if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
    1501                 :            :     return NULL;
    1502                 :            : 
    1503                 :     781661 :   if (lookup_attribute_by_prefix ("oacc ",
    1504                 :     781661 :                                   DECL_ATTRIBUTES (node->decl)) != NULL)
    1505                 :            :     return NULL;
    1506                 :            : 
    1507                 :            :   /* PR ipa/70306.  */
    1508                 :     781661 :   if (DECL_STATIC_CONSTRUCTOR (node->decl)
    1509                 :     781661 :       || DECL_STATIC_DESTRUCTOR (node->decl))
    1510                 :            :     return NULL;
    1511                 :            : 
    1512                 :     774172 :   sem_function *f = new sem_function (node, stack);
    1513                 :     774172 :   f->init (checker);
    1514                 :            : 
    1515                 :     774172 :   return f;
    1516                 :            : }
    1517                 :            : 
    1518                 :            : /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
    1519                 :            :    return true if phi nodes are semantically equivalent in these blocks .  */
    1520                 :            : 
    1521                 :            : bool
    1522                 :     308532 : sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
    1523                 :            : {
    1524                 :     308532 :   gphi_iterator si1, si2;
    1525                 :     308532 :   gphi *phi1, *phi2;
    1526                 :     308532 :   unsigned size1, size2, i;
    1527                 :     308532 :   tree t1, t2;
    1528                 :     308532 :   edge e1, e2;
    1529                 :            : 
    1530                 :     308532 :   gcc_assert (bb1 != NULL);
    1531                 :     308532 :   gcc_assert (bb2 != NULL);
    1532                 :            : 
    1533                 :     308532 :   si2 = gsi_start_nonvirtual_phis (bb2);
    1534                 :     320432 :   for (si1 = gsi_start_nonvirtual_phis (bb1); !gsi_end_p (si1);
    1535                 :      11900 :        gsi_next_nonvirtual_phi (&si1))
    1536                 :            :     {
    1537                 :      13503 :       if (gsi_end_p (si1) && gsi_end_p (si2))
    1538                 :            :         break;
    1539                 :            : 
    1540                 :      13503 :       if (gsi_end_p (si1) || gsi_end_p (si2))
    1541                 :          0 :         return return_false();
    1542                 :            : 
    1543                 :      13503 :       phi1 = si1.phi ();
    1544                 :      13503 :       phi2 = si2.phi ();
    1545                 :            : 
    1546                 :      13503 :       tree phi_result1 = gimple_phi_result (phi1);
    1547                 :      13503 :       tree phi_result2 = gimple_phi_result (phi2);
    1548                 :            : 
    1549                 :      13503 :       if (!m_checker->compare_operand (phi_result1, phi_result2))
    1550                 :          1 :         return return_false_with_msg ("PHI results are different");
    1551                 :            : 
    1552                 :      13502 :       size1 = gimple_phi_num_args (phi1);
    1553                 :      13502 :       size2 = gimple_phi_num_args (phi2);
    1554                 :            : 
    1555                 :      13502 :       if (size1 != size2)
    1556                 :          0 :         return return_false ();
    1557                 :            : 
    1558                 :      38766 :       for (i = 0; i < size1; ++i)
    1559                 :            :         {
    1560                 :      26866 :           t1 = gimple_phi_arg (phi1, i)->def;
    1561                 :      26866 :           t2 = gimple_phi_arg (phi2, i)->def;
    1562                 :            : 
    1563                 :      26866 :           if (!m_checker->compare_operand (t1, t2))
    1564                 :       1602 :             return return_false ();
    1565                 :            : 
    1566                 :      25264 :           e1 = gimple_phi_arg_edge (phi1, i);
    1567                 :      25264 :           e2 = gimple_phi_arg_edge (phi2, i);
    1568                 :            : 
    1569                 :      25264 :           if (!m_checker->compare_edge (e1, e2))
    1570                 :          0 :             return return_false ();
    1571                 :            :         }
    1572                 :            : 
    1573                 :      11900 :       gsi_next_nonvirtual_phi (&si2);
    1574                 :            :     }
    1575                 :            : 
    1576                 :            :   return true;
    1577                 :            : }
    1578                 :            : 
    1579                 :            : /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
    1580                 :            :    corresponds to TARGET.  */
    1581                 :            : 
    1582                 :            : bool
    1583                 :     806944 : sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
    1584                 :            : {
    1585                 :     806944 :   source++;
    1586                 :     806944 :   target++;
    1587                 :            : 
    1588                 :    1537230 :   if (bb_dict->length () <= (unsigned)source)
    1589                 :     260025 :     bb_dict->safe_grow_cleared (source + 1);
    1590                 :            : 
    1591                 :     806944 :   if ((*bb_dict)[source] == 0)
    1592                 :            :     {
    1593                 :     266805 :       (*bb_dict)[source] = target;
    1594                 :     266805 :       return true;
    1595                 :            :     }
    1596                 :            :   else
    1597                 :     540139 :     return (*bb_dict)[source] == target;
    1598                 :            : }
    1599                 :            : 
    1600                 :          0 : sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
    1601                 :            : {
    1602                 :          0 : }
    1603                 :            : 
    1604                 :    1900170 : sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
    1605                 :    1900170 : : sem_item (VAR, node, stack)
    1606                 :            : {
    1607                 :    1900170 :   gcc_checking_assert (node);
    1608                 :    1900170 :   gcc_checking_assert (get_node ());
    1609                 :    1900170 : }
    1610                 :            : 
    1611                 :            : /* Fast equality function based on knowledge known in WPA.  */
    1612                 :            : 
    1613                 :            : bool
    1614                 :     371007 : sem_variable::equals_wpa (sem_item *item,
    1615                 :            :                           hash_map <symtab_node *, sem_item *> &ignored_nodes)
    1616                 :            : {
    1617                 :     371007 :   gcc_assert (item->type == VAR);
    1618                 :            : 
    1619                 :     526303 :   if (node->num_references () != item->node->num_references ())
    1620                 :          0 :     return return_false_with_msg ("different number of references");
    1621                 :            : 
    1622                 :     371007 :   if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
    1623                 :          0 :     return return_false_with_msg ("TLS model");
    1624                 :            : 
    1625                 :            :   /* DECL_ALIGN is safe to merge, because we will always chose the largest
    1626                 :            :      alignment out of all aliases.  */
    1627                 :            : 
    1628                 :     371007 :   if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
    1629                 :          0 :     return return_false_with_msg ("Virtual flag mismatch");
    1630                 :            : 
    1631                 :     371007 :   if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
    1632                 :     371007 :       && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
    1633                 :      13168 :           || !operand_equal_p (DECL_SIZE (decl),
    1634                 :      13168 :                                DECL_SIZE (item->decl), OEP_ONLY_CONST)))
    1635                 :      13168 :     return return_false_with_msg ("size mismatch");
    1636                 :            : 
    1637                 :            :   /* Do not attempt to mix data from different user sections;
    1638                 :            :      we do not know what user intends with those.  */
    1639                 :     705832 :   if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
    1640                 :     357838 :        || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
    1641                 :     357840 :       && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
    1642                 :          1 :     return return_false_with_msg ("user section mismatch");
    1643                 :            : 
    1644                 :     357838 :   if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
    1645                 :          0 :     return return_false_with_msg ("text section");
    1646                 :            : 
    1647                 :     459891 :   ipa_ref *ref = NULL, *ref2 = NULL;
    1648                 :     459891 :   for (unsigned i = 0; node->iterate_reference (i, ref); i++)
    1649                 :            :     {
    1650                 :     102134 :       item->node->iterate_reference (i, ref2);
    1651                 :            : 
    1652                 :     102134 :       if (ref->use != ref2->use)
    1653                 :          0 :         return return_false_with_msg ("reference use mismatch");
    1654                 :            : 
    1655                 :     102134 :       if (!compare_symbol_references (ignored_nodes,
    1656                 :            :                                       ref->referred, ref2->referred,
    1657                 :     102134 :                                       ref->address_matters_p ()))
    1658                 :            :         return false;
    1659                 :            :     }
    1660                 :            : 
    1661                 :            :   return true;
    1662                 :            : }
    1663                 :            : 
    1664                 :            : /* Returns true if the item equals to ITEM given as argument.  */
    1665                 :            : 
    1666                 :            : bool
    1667                 :     390178 : sem_variable::equals (sem_item *item,
    1668                 :            :                       hash_map <symtab_node *, sem_item *> &)
    1669                 :            : {
    1670                 :     390178 :   gcc_assert (item->type == VAR);
    1671                 :     390178 :   bool ret;
    1672                 :            : 
    1673                 :     390178 :   if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
    1674                 :        100 :     dyn_cast <varpool_node *>(node)->get_constructor ();
    1675                 :     390178 :   if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
    1676                 :        100 :     dyn_cast <varpool_node *>(item->node)->get_constructor ();
    1677                 :            : 
    1678                 :            :   /* As seen in PR ipa/65303 we have to compare variables types.  */
    1679                 :     390178 :   if (!func_checker::compatible_types_p (TREE_TYPE (decl),
    1680                 :     390178 :                                          TREE_TYPE (item->decl)))
    1681                 :      37104 :     return return_false_with_msg ("variables types are different");
    1682                 :            : 
    1683                 :     353074 :   ret = sem_variable::equals (DECL_INITIAL (decl),
    1684                 :     353074 :                               DECL_INITIAL (item->node->decl));
    1685                 :     353074 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1686                 :          6 :     fprintf (dump_file,
    1687                 :            :              "Equals called for vars: %s:%s with result: %s\n\n",
    1688                 :          3 :              node->dump_name (), item->node->dump_name (),
    1689                 :            :              ret ? "true" : "false");
    1690                 :            : 
    1691                 :            :   return ret;
    1692                 :            : }
    1693                 :            : 
    1694                 :            : /* Compares trees T1 and T2 for semantic equality.  */
    1695                 :            : 
    1696                 :            : bool
    1697                 :    1782270 : sem_variable::equals (tree t1, tree t2)
    1698                 :            : {
    1699                 :    1782270 :   if (!t1 || !t2)
    1700                 :        698 :     return return_with_debug (t1 == t2);
    1701                 :    1781570 :   if (t1 == t2)
    1702                 :            :     return true;
    1703                 :     883587 :   tree_code tc1 = TREE_CODE (t1);
    1704                 :     883587 :   tree_code tc2 = TREE_CODE (t2);
    1705                 :            : 
    1706                 :     883587 :   if (tc1 != tc2)
    1707                 :          0 :     return return_false_with_msg ("TREE_CODE mismatch");
    1708                 :            : 
    1709                 :     883587 :   switch (tc1)
    1710                 :            :     {
    1711                 :     346140 :     case CONSTRUCTOR:
    1712                 :     346140 :       {
    1713                 :     346140 :         vec<constructor_elt, va_gc> *v1, *v2;
    1714                 :     346140 :         unsigned HOST_WIDE_INT idx;
    1715                 :            : 
    1716                 :     346140 :         enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
    1717                 :     346140 :         if (typecode != TREE_CODE (TREE_TYPE (t2)))
    1718                 :          0 :           return return_false_with_msg ("constructor type mismatch");
    1719                 :            : 
    1720                 :     346140 :         if (typecode == ARRAY_TYPE)
    1721                 :            :           {
    1722                 :     135979 :             HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
    1723                 :            :             /* For arrays, check that the sizes all match.  */
    1724                 :     271958 :             if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
    1725                 :     135979 :                 || size_1 == -1
    1726                 :     271958 :                 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
    1727                 :          0 :               return return_false_with_msg ("constructor array size mismatch");
    1728                 :            :           }
    1729                 :     210161 :         else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
    1730                 :     210161 :                                                     TREE_TYPE (t2)))
    1731                 :          0 :           return return_false_with_msg ("constructor type incompatible");
    1732                 :            : 
    1733                 :     346140 :         v1 = CONSTRUCTOR_ELTS (t1);
    1734                 :     346140 :         v2 = CONSTRUCTOR_ELTS (t2);
    1735                 :     931256 :         if (vec_safe_length (v1) != vec_safe_length (v2))
    1736                 :          0 :           return return_false_with_msg ("constructor number of elts mismatch");
    1737                 :            : 
    1738                 :    1737630 :         for (idx = 0; idx < vec_safe_length (v1); ++idx)
    1739                 :            :           {
    1740                 :     549588 :             constructor_elt *c1 = &(*v1)[idx];
    1741                 :     549588 :             constructor_elt *c2 = &(*v2)[idx];
    1742                 :            : 
    1743                 :            :             /* Check that each value is the same...  */
    1744                 :     549588 :             if (!sem_variable::equals (c1->value, c2->value))
    1745                 :            :               return false;
    1746                 :            :             /* ... and that they apply to the same fields!  */
    1747                 :     549588 :             if (!sem_variable::equals (c1->index, c2->index))
    1748                 :            :               return false;
    1749                 :            :           }
    1750                 :            :         return true;
    1751                 :            :       }
    1752                 :          0 :     case MEM_REF:
    1753                 :          0 :       {
    1754                 :          0 :         tree x1 = TREE_OPERAND (t1, 0);
    1755                 :          0 :         tree x2 = TREE_OPERAND (t2, 0);
    1756                 :          0 :         tree y1 = TREE_OPERAND (t1, 1);
    1757                 :          0 :         tree y2 = TREE_OPERAND (t2, 1);
    1758                 :            : 
    1759                 :          0 :         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
    1760                 :          0 :           return return_false ();
    1761                 :            : 
    1762                 :            :         /* Type of the offset on MEM_REF does not matter.  */
    1763                 :          0 :         return return_with_debug (sem_variable::equals (x1, x2)
    1764                 :            :                                   && known_eq (wi::to_poly_offset (y1),
    1765                 :            :                                                wi::to_poly_offset (y2)));
    1766                 :            :       }
    1767                 :     313041 :     case ADDR_EXPR:
    1768                 :     313041 :     case FDESC_EXPR:
    1769                 :     313041 :       {
    1770                 :     313041 :         tree op1 = TREE_OPERAND (t1, 0);
    1771                 :     313041 :         tree op2 = TREE_OPERAND (t2, 0);
    1772                 :     313041 :         return sem_variable::equals (op1, op2);
    1773                 :            :       }
    1774                 :            :     /* References to other vars/decls are compared using ipa-ref.  */
    1775                 :          4 :     case FUNCTION_DECL:
    1776                 :          4 :     case VAR_DECL:
    1777                 :          4 :       if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
    1778                 :            :         return true;
    1779                 :          0 :       return return_false_with_msg ("Declaration mismatch");
    1780                 :         12 :     case CONST_DECL:
    1781                 :            :       /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
    1782                 :            :          need to process its VAR/FUNCTION references without relying on ipa-ref
    1783                 :            :          compare.  */
    1784                 :         12 :     case FIELD_DECL:
    1785                 :         12 :     case LABEL_DECL:
    1786                 :         12 :       return return_false_with_msg ("Declaration mismatch");
    1787                 :        511 :     case INTEGER_CST:
    1788                 :            :       /* Integer constants are the same only if the same width of type.  */
    1789                 :        511 :       if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
    1790                 :          0 :         return return_false_with_msg ("INTEGER_CST precision mismatch");
    1791                 :       1022 :       if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
    1792                 :          0 :         return return_false_with_msg ("INTEGER_CST mode mismatch");
    1793                 :        511 :       return return_with_debug (tree_int_cst_equal (t1, t2));
    1794                 :     213973 :     case STRING_CST:
    1795                 :     427946 :       if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
    1796                 :          0 :         return return_false_with_msg ("STRING_CST mode mismatch");
    1797                 :     213973 :       if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
    1798                 :          0 :         return return_false_with_msg ("STRING_CST length mismatch");
    1799                 :     213973 :       if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
    1800                 :     213973 :                     TREE_STRING_LENGTH (t1)))
    1801                 :          0 :         return return_false_with_msg ("STRING_CST mismatch");
    1802                 :            :       return true;
    1803                 :          0 :     case FIXED_CST:
    1804                 :            :       /* Fixed constants are the same only if the same width of type.  */
    1805                 :          0 :       if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
    1806                 :          0 :         return return_false_with_msg ("FIXED_CST precision mismatch");
    1807                 :            : 
    1808                 :          0 :       return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
    1809                 :            :                                                         TREE_FIXED_CST (t2)));
    1810                 :        390 :     case COMPLEX_CST:
    1811                 :        390 :       return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
    1812                 :        780 :               && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
    1813                 :       5182 :     case REAL_CST:
    1814                 :            :       /* Real constants are the same only if the same width of type.  */
    1815                 :       5182 :       if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
    1816                 :          0 :         return return_false_with_msg ("REAL_CST precision mismatch");
    1817                 :       5182 :       return return_with_debug (real_identical (&TREE_REAL_CST (t1),
    1818                 :            :                                                 &TREE_REAL_CST (t2)));
    1819                 :          0 :     case VECTOR_CST:
    1820                 :          0 :       {
    1821                 :          0 :         if (maybe_ne (VECTOR_CST_NELTS (t1), VECTOR_CST_NELTS (t2)))
    1822                 :          0 :           return return_false_with_msg ("VECTOR_CST nelts mismatch");
    1823                 :            : 
    1824                 :          0 :         unsigned int count
    1825                 :          0 :           = tree_vector_builder::binary_encoded_nelts (t1, t2);
    1826                 :          0 :         for (unsigned int i = 0; i < count; ++i)
    1827                 :          0 :           if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1, i),
    1828                 :          0 :                                      VECTOR_CST_ENCODED_ELT (t2, i)))
    1829                 :            :             return false;
    1830                 :            : 
    1831                 :            :         return true;
    1832                 :            :       }
    1833                 :       3951 :     case ARRAY_REF:
    1834                 :       3951 :     case ARRAY_RANGE_REF:
    1835                 :       3951 :       {
    1836                 :       3951 :         tree x1 = TREE_OPERAND (t1, 0);
    1837                 :       3951 :         tree x2 = TREE_OPERAND (t2, 0);
    1838                 :       3951 :         tree y1 = TREE_OPERAND (t1, 1);
    1839                 :       3951 :         tree y2 = TREE_OPERAND (t2, 1);
    1840                 :            : 
    1841                 :       3951 :         if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
    1842                 :          0 :           return false;
    1843                 :       3951 :         if (!sem_variable::equals (array_ref_low_bound (t1),
    1844                 :            :                                    array_ref_low_bound (t2)))
    1845                 :            :           return false;
    1846                 :       3951 :         if (!sem_variable::equals (array_ref_element_size (t1),
    1847                 :            :                                    array_ref_element_size (t2)))
    1848                 :          0 :           return false;
    1849                 :            :         return true;
    1850                 :            :       }
    1851                 :            :      
    1852                 :         13 :     case COMPONENT_REF:
    1853                 :         13 :     case POINTER_PLUS_EXPR:
    1854                 :         13 :     case PLUS_EXPR:
    1855                 :         13 :     case MINUS_EXPR:
    1856                 :         13 :     case RANGE_EXPR:
    1857                 :         13 :       {
    1858                 :         13 :         tree x1 = TREE_OPERAND (t1, 0);
    1859                 :         13 :         tree x2 = TREE_OPERAND (t2, 0);
    1860                 :         13 :         tree y1 = TREE_OPERAND (t1, 1);
    1861                 :         13 :         tree y2 = TREE_OPERAND (t2, 1);
    1862                 :            : 
    1863                 :         13 :         return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
    1864                 :            :       }
    1865                 :            : 
    1866                 :        370 :     CASE_CONVERT:
    1867                 :        370 :     case VIEW_CONVERT_EXPR:
    1868                 :        370 :       if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
    1869                 :          0 :           return return_false ();
    1870                 :        370 :       return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
    1871                 :          0 :     case ERROR_MARK:
    1872                 :          0 :       return return_false_with_msg ("ERROR_MARK");
    1873                 :          0 :     default:
    1874                 :          0 :       return return_false_with_msg ("Unknown TREE code reached");
    1875                 :            :     }
    1876                 :            : }
    1877                 :            : 
    1878                 :            : /* Parser function that visits a varpool NODE.  */
    1879                 :            : 
    1880                 :            : sem_variable *
    1881                 :    1942890 : sem_variable::parse (varpool_node *node, bitmap_obstack *stack,
    1882                 :            :                      func_checker *checker)
    1883                 :            : {
    1884                 :    1886110 :   if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
    1885                 :    3828970 :       || node->alias)
    1886                 :            :     return NULL;
    1887                 :            : 
    1888                 :    1886010 :   sem_variable *v = new sem_variable (node, stack);
    1889                 :    1886010 :   v->init (checker);
    1890                 :            : 
    1891                 :    1886010 :   return v;
    1892                 :            : }
    1893                 :            : 
    1894                 :            : /* Semantic variable initialization function.  */
    1895                 :            : 
    1896                 :            : void
    1897                 :    2311640 : sem_variable::init (ipa_icf_gimple::func_checker *checker)
    1898                 :            : {
    1899                 :    2311640 :   decl = get_node ()->decl;
    1900                 :            : 
    1901                 :            :   /* All WPA streamed in symbols should have their hashes computed at compile
    1902                 :            :      time.  At this point, the constructor may not be in memory at all.
    1903                 :            :      DECL_INITIAL (decl) would be error_mark_node in that case.  */
    1904                 :    2311640 :   if (!m_hash_set)
    1905                 :            :     {
    1906                 :    1886010 :       gcc_assert (!node->lto_file_data);
    1907                 :    1886010 :       inchash::hash hstate;
    1908                 :    1886010 :       hstate.add_int (456346417);
    1909                 :    1886010 :       checker->hash_operand (DECL_INITIAL (decl), hstate, 0);
    1910                 :    1886010 :       set_hash (hstate.end ());
    1911                 :            :     }
    1912                 :    2311640 : }
    1913                 :            : 
    1914                 :            : /* References independent hash function.  */
    1915                 :            : 
    1916                 :            : hashval_t
    1917                 :    7379350 : sem_variable::get_hash (void)
    1918                 :            : {
    1919                 :    7379350 :   gcc_checking_assert (m_hash_set);
    1920                 :    7379350 :   return m_hash;
    1921                 :            : }
    1922                 :            : 
    1923                 :            : /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
    1924                 :            :    be applied.  */
    1925                 :            : 
    1926                 :            : bool
    1927                 :     352949 : sem_variable::merge (sem_item *alias_item)
    1928                 :            : {
    1929                 :     352949 :   gcc_assert (alias_item->type == VAR);
    1930                 :            : 
    1931                 :     352949 :   AUTO_DUMP_SCOPE ("merge",
    1932                 :            :                    dump_user_location_t::from_function_decl (decl));
    1933                 :     352949 :   if (!sem_item::target_supports_symbol_aliases_p ())
    1934                 :            :     {
    1935                 :          0 :       if (dump_enabled_p ())
    1936                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION, "Not unifying; "
    1937                 :            :                      "Symbol aliases are not supported by target\n");
    1938                 :          0 :       return false;
    1939                 :            :     }
    1940                 :            : 
    1941                 :     352949 :   if (DECL_EXTERNAL (alias_item->decl))
    1942                 :            :     {
    1943                 :          0 :       if (dump_enabled_p ())
    1944                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1945                 :            :                      "Not unifying; alias is external.\n");
    1946                 :          0 :       return false;
    1947                 :            :     }
    1948                 :            : 
    1949                 :     352949 :   sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
    1950                 :            : 
    1951                 :     352949 :   varpool_node *original = get_node ();
    1952                 :     352949 :   varpool_node *alias = alias_var->get_node ();
    1953                 :     352949 :   bool original_discardable = false;
    1954                 :            : 
    1955                 :     352949 :   bool alias_address_matters = alias->address_matters_p ();
    1956                 :            : 
    1957                 :            :   /* See if original is in a section that can be discarded if the main
    1958                 :            :      symbol is not used.
    1959                 :            :      Also consider case where we have resolution info and we know that
    1960                 :            :      original's definition is not going to be used.  In this case we cannot
    1961                 :            :      create alias to original.  */
    1962                 :     352949 :   if (original->can_be_discarded_p ()
    1963                 :     352949 :       || (node->resolution != LDPR_UNKNOWN
    1964                 :     351738 :           && !decl_binds_to_current_def_p (node->decl)))
    1965                 :            :     original_discardable = true;
    1966                 :            : 
    1967                 :     352949 :   gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
    1968                 :            : 
    1969                 :            :   /* Constant pool machinery is not quite ready for aliases.
    1970                 :            :      TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
    1971                 :            :      For LTO merging does not happen that is an important missing feature.
    1972                 :            :      We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
    1973                 :            :      flag is dropped and non-local symbol name is assigned.  */
    1974                 :     352949 :   if (DECL_IN_CONSTANT_POOL (alias->decl)
    1975                 :     352949 :       || DECL_IN_CONSTANT_POOL (original->decl))
    1976                 :            :     {
    1977                 :          3 :       if (dump_enabled_p ())
    1978                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1979                 :            :                      "Not unifying; constant pool variables.\n");
    1980                 :          3 :       return false;
    1981                 :            :     }
    1982                 :            : 
    1983                 :            :   /* Do not attempt to mix functions from different user sections;
    1984                 :            :      we do not know what user intends with those.  */
    1985                 :     697949 :   if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
    1986                 :     352946 :        || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
    1987                 :     352946 :       && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
    1988                 :            :     {
    1989                 :          0 :       if (dump_enabled_p ())
    1990                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    1991                 :            :                      "Not unifying; "
    1992                 :            :                      "original and alias are in different sections.\n");
    1993                 :          0 :       return false;
    1994                 :            :     }
    1995                 :            : 
    1996                 :            :   /* We cannot merge if address comparison matters.  */
    1997                 :     352946 :   if (alias_address_matters && flag_merge_constants < 2)
    1998                 :            :     {
    1999                 :     347266 :       if (dump_enabled_p ())
    2000                 :          1 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    2001                 :            :                      "Not unifying; address of original may be compared.\n");
    2002                 :     347266 :       return false;
    2003                 :            :     }
    2004                 :            : 
    2005                 :       5680 :   if (DECL_ALIGN (original->decl) < DECL_ALIGN (alias->decl))
    2006                 :            :     {
    2007                 :          0 :       if (dump_enabled_p ())
    2008                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    2009                 :            :                      "Not unifying; "
    2010                 :            :                      "original and alias have incompatible alignments\n");
    2011                 :            : 
    2012                 :          0 :       return false;
    2013                 :            :     }
    2014                 :            : 
    2015                 :       5680 :   if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
    2016                 :            :     {
    2017                 :         28 :       if (dump_enabled_p ())
    2018                 :          0 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    2019                 :            :                      "Not unifying; alias cannot be created; "
    2020                 :            :                      "across comdat group boundary\n");
    2021                 :            : 
    2022                 :         28 :       return false;
    2023                 :            :     }
    2024                 :            : 
    2025                 :       5652 :   if (original_discardable)
    2026                 :            :     {
    2027                 :          5 :       if (dump_enabled_p ())
    2028                 :          1 :         dump_printf (MSG_MISSED_OPTIMIZATION,
    2029                 :            :                      "Not unifying; alias cannot be created; "
    2030                 :            :                      "target is discardable\n");
    2031                 :            : 
    2032                 :          5 :       return false;
    2033                 :            :     }
    2034                 :            :   else
    2035                 :            :     {
    2036                 :       5647 :       gcc_assert (!original->alias);
    2037                 :       5647 :       gcc_assert (!alias->alias);
    2038                 :            : 
    2039                 :       5647 :       alias->analyzed = false;
    2040                 :            : 
    2041                 :       5647 :       DECL_INITIAL (alias->decl) = NULL;
    2042                 :       5647 :       ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
    2043                 :            :                                                            NULL, true);
    2044                 :       5647 :       alias->remove_all_references ();
    2045                 :       5647 :       if (TREE_ADDRESSABLE (alias->decl))
    2046                 :         11 :         original->call_for_symbol_and_aliases (set_addressable, NULL, true);
    2047                 :            : 
    2048                 :       5647 :       varpool_node::create_alias (alias_var->decl, decl);
    2049                 :       5647 :       alias->resolve_alias (original);
    2050                 :            : 
    2051                 :       5647 :       if (dump_enabled_p ())
    2052                 :         18 :         dump_printf (MSG_OPTIMIZED_LOCATIONS,
    2053                 :            :                      "Unified; Variable alias has been created.\n");
    2054                 :            : 
    2055                 :       5647 :       return true;
    2056                 :            :     }
    2057                 :            : }
    2058                 :            : 
    2059                 :            : /* Dump symbol to FILE.  */
    2060                 :            : 
    2061                 :            : void
    2062                 :          6 : sem_variable::dump_to_file (FILE *file)
    2063                 :            : {
    2064                 :          6 :   gcc_assert (file);
    2065                 :            : 
    2066                 :          6 :   print_node (file, "", decl, 0);
    2067                 :          6 :   fprintf (file, "\n\n");
    2068                 :          6 : }
    2069                 :            : 
    2070                 :            : unsigned int sem_item_optimizer::class_id = 0;
    2071                 :            : 
    2072                 :     100326 : sem_item_optimizer::sem_item_optimizer ()
    2073                 :            : : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
    2074                 :     100326 :   m_varpool_node_hooks (NULL), m_merged_variables (), m_references ()
    2075                 :            : {
    2076                 :     100326 :   m_items.create (0);
    2077                 :     100326 :   bitmap_obstack_initialize (&m_bmstack);
    2078                 :     100326 : }
    2079                 :            : 
    2080                 :      93278 : sem_item_optimizer::~sem_item_optimizer ()
    2081                 :            : {
    2082                 :    4235200 :   for (unsigned int i = 0; i < m_items.length (); i++)
    2083                 :    2026120 :     delete m_items[i];
    2084                 :            : 
    2085                 :            : 
    2086                 :    1570010 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    2087                 :    1570010 :        it != m_classes.end (); ++it)
    2088                 :            :     {
    2089                 :    6150860 :       for (unsigned int i = 0; i < (*it)->classes.length (); i++)
    2090                 :    3197390 :         delete (*it)->classes[i];
    2091                 :            : 
    2092                 :    1476730 :       (*it)->classes.release ();
    2093                 :    1476730 :       free (*it);
    2094                 :            :     }
    2095                 :            : 
    2096                 :      93278 :   m_items.release ();
    2097                 :            : 
    2098                 :      93278 :   bitmap_obstack_release (&m_bmstack);
    2099                 :      94503 :   m_merged_variables.release ();
    2100                 :      93278 : }
    2101                 :            : 
    2102                 :            : /* Write IPA ICF summary for symbols.  */
    2103                 :            : 
    2104                 :            : void
    2105                 :      14680 : sem_item_optimizer::write_summary (void)
    2106                 :            : {
    2107                 :      14680 :   unsigned int count = 0;
    2108                 :            : 
    2109                 :      14680 :   output_block *ob = create_output_block (LTO_section_ipa_icf);
    2110                 :      14680 :   lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
    2111                 :      14680 :   ob->symbol = NULL;
    2112                 :            : 
    2113                 :            :   /* Calculate number of symbols to be serialized.  */
    2114                 :     334618 :   for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
    2115                 :     669074 :        !lsei_end_p (lsei);
    2116                 :     319938 :        lsei_next_in_partition (&lsei))
    2117                 :            :     {
    2118                 :     319938 :       symtab_node *node = lsei_node (lsei);
    2119                 :            : 
    2120                 :     639876 :       if (m_symtab_node_map.get (node))
    2121                 :     298546 :         count++;
    2122                 :            :     }
    2123                 :            : 
    2124                 :      14680 :   streamer_write_uhwi (ob, count);
    2125                 :            : 
    2126                 :            :   /* Process all of the symbols.  */
    2127                 :     334618 :   for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
    2128                 :     669074 :        !lsei_end_p (lsei);
    2129                 :     319938 :        lsei_next_in_partition (&lsei))
    2130                 :            :     {
    2131                 :     319938 :       symtab_node *node = lsei_node (lsei);
    2132                 :            : 
    2133                 :     639876 :       sem_item **item = m_symtab_node_map.get (node);
    2134                 :            : 
    2135                 :     298546 :       if (item && *item)
    2136                 :            :         {
    2137                 :     298546 :           int node_ref = lto_symtab_encoder_encode (encoder, node);
    2138                 :     298546 :           streamer_write_uhwi_stream (ob->main_stream, node_ref);
    2139                 :            : 
    2140                 :     298546 :           streamer_write_uhwi (ob, (*item)->get_hash ());
    2141                 :            :         }
    2142                 :            :     }
    2143                 :            : 
    2144                 :      14680 :   streamer_write_char_stream (ob->main_stream, 0);
    2145                 :      14680 :   produce_asm (ob, NULL);
    2146                 :      14680 :   destroy_output_block (ob);
    2147                 :      14680 : }
    2148                 :            : 
    2149                 :            : /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
    2150                 :            :    contains LEN bytes.  */
    2151                 :            : 
    2152                 :            : void
    2153                 :       8260 : sem_item_optimizer::read_section (lto_file_decl_data *file_data,
    2154                 :            :                                   const char *data, size_t len)
    2155                 :            : {
    2156                 :       8260 :   const lto_function_header *header
    2157                 :            :     = (const lto_function_header *) data;
    2158                 :       8260 :   const int cfg_offset = sizeof (lto_function_header);
    2159                 :       8260 :   const int main_offset = cfg_offset + header->cfg_size;
    2160                 :       8260 :   const int string_offset = main_offset + header->main_size;
    2161                 :       8260 :   data_in *data_in;
    2162                 :       8260 :   unsigned int i;
    2163                 :       8260 :   unsigned int count;
    2164                 :            : 
    2165                 :       8260 :   lto_input_block ib_main ((const char *) data + main_offset, 0,
    2166                 :       8260 :                            header->main_size, file_data->mode_table);
    2167                 :            : 
    2168                 :       8260 :   data_in
    2169                 :      16520 :     = lto_data_in_create (file_data, (const char *) data + string_offset,
    2170                 :       8260 :                           header->string_size, vNULL);
    2171                 :            : 
    2172                 :       8260 :   count = streamer_read_uhwi (&ib_main);
    2173                 :            : 
    2174                 :      86890 :   for (i = 0; i < count; i++)
    2175                 :            :     {
    2176                 :      78630 :       unsigned int index;
    2177                 :      78630 :       symtab_node *node;
    2178                 :      78630 :       lto_symtab_encoder_t encoder;
    2179                 :            : 
    2180                 :      78630 :       index = streamer_read_uhwi (&ib_main);
    2181                 :      78630 :       encoder = file_data->symtab_node_encoder;
    2182                 :      78630 :       node = lto_symtab_encoder_deref (encoder, index);
    2183                 :            : 
    2184                 :      78630 :       hashval_t hash = streamer_read_uhwi (&ib_main);
    2185                 :      78630 :       gcc_assert (node->definition);
    2186                 :            : 
    2187                 :      78630 :       if (is_a<cgraph_node *> (node))
    2188                 :            :         {
    2189                 :      64471 :           cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
    2190                 :            : 
    2191                 :      64471 :           sem_function *fn = new sem_function (cnode, &m_bmstack);
    2192                 :      64471 :           fn->set_hash (hash);
    2193                 :      64471 :           m_items.safe_push (fn);
    2194                 :            :         }
    2195                 :            :       else
    2196                 :            :         {
    2197                 :      14159 :           varpool_node *vnode = dyn_cast <varpool_node *> (node);
    2198                 :            : 
    2199                 :      14159 :           sem_variable *var = new sem_variable (vnode, &m_bmstack);
    2200                 :      14159 :           var->set_hash (hash);
    2201                 :      14159 :           m_items.safe_push (var);
    2202                 :            :         }
    2203                 :            :     }
    2204                 :            : 
    2205                 :       8260 :   lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
    2206                 :            :                          len);
    2207                 :       8260 :   lto_data_in_delete (data_in);
    2208                 :       8260 : }
    2209                 :            : 
    2210                 :            : /* Read IPA ICF summary for symbols.  */
    2211                 :            : 
    2212                 :            : void
    2213                 :       8381 : sem_item_optimizer::read_summary (void)
    2214                 :            : {
    2215                 :       8381 :   lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
    2216                 :       8381 :   lto_file_decl_data *file_data;
    2217                 :       8381 :   unsigned int j = 0;
    2218                 :            : 
    2219                 :      17731 :   while ((file_data = file_data_vec[j++]))
    2220                 :            :     {
    2221                 :       9350 :       size_t len;
    2222                 :       9350 :       const char *data
    2223                 :       9350 :         = lto_get_summary_section_data (file_data, LTO_section_ipa_icf, &len);
    2224                 :       9350 :       if (data)
    2225                 :       8260 :         read_section (file_data, data, len);
    2226                 :            :     }
    2227                 :       8381 : }
    2228                 :            : 
    2229                 :            : /* Register callgraph and varpool hooks.  */
    2230                 :            : 
    2231                 :            : void
    2232                 :     100326 : sem_item_optimizer::register_hooks (void)
    2233                 :            : {
    2234                 :     100326 :   if (!m_cgraph_node_hooks)
    2235                 :     100326 :     m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
    2236                 :     100326 :                           (&sem_item_optimizer::cgraph_removal_hook, this);
    2237                 :            : 
    2238                 :     100326 :   if (!m_varpool_node_hooks)
    2239                 :     100326 :     m_varpool_node_hooks = symtab->add_varpool_removal_hook
    2240                 :     100326 :                            (&sem_item_optimizer::varpool_removal_hook, this);
    2241                 :     100326 : }
    2242                 :            : 
    2243                 :            : /* Unregister callgraph and varpool hooks.  */
    2244                 :            : 
    2245                 :            : void
    2246                 :      93278 : sem_item_optimizer::unregister_hooks (void)
    2247                 :            : {
    2248                 :      93278 :   if (m_cgraph_node_hooks)
    2249                 :      93278 :     symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
    2250                 :            : 
    2251                 :      93278 :   if (m_varpool_node_hooks)
    2252                 :      93278 :     symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
    2253                 :      93278 : }
    2254                 :            : 
    2255                 :            : /* Adds a CLS to hashtable associated by hash value.  */
    2256                 :            : 
    2257                 :            : void
    2258                 :      28750 : sem_item_optimizer::add_class (congruence_class *cls)
    2259                 :            : {
    2260                 :      28750 :   gcc_assert (cls->members.length ());
    2261                 :            : 
    2262                 :      28750 :   congruence_class_group *group
    2263                 :      28750 :     = get_group_by_hash (cls->members[0]->get_hash (),
    2264                 :      28750 :                          cls->members[0]->type);
    2265                 :      28750 :   group->classes.safe_push (cls);
    2266                 :      28750 : }
    2267                 :            : 
    2268                 :            : /* Gets a congruence class group based on given HASH value and TYPE.  */
    2269                 :            : 
    2270                 :            : congruence_class_group *
    2271                 :    2054870 : sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
    2272                 :            : {
    2273                 :    2054870 :   congruence_class_group *item = XNEW (congruence_class_group);
    2274                 :    2054870 :   item->hash = hash;
    2275                 :    2054870 :   item->type = type;
    2276                 :            : 
    2277                 :    2054870 :   congruence_class_group **slot = m_classes.find_slot (item, INSERT);
    2278                 :            : 
    2279                 :    2054870 :   if (*slot)
    2280                 :     578141 :     free (item);
    2281                 :            :   else
    2282                 :            :     {
    2283                 :    1476730 :       item->classes.create (1);
    2284                 :    1476730 :       *slot = item;
    2285                 :            :     }
    2286                 :            : 
    2287                 :    2054870 :   return *slot;
    2288                 :            : }
    2289                 :            : 
    2290                 :            : /* Callgraph removal hook called for a NODE with a custom DATA.  */
    2291                 :            : 
    2292                 :            : void
    2293                 :       7967 : sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
    2294                 :            : {
    2295                 :       7967 :   sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
    2296                 :       7967 :   optimizer->remove_symtab_node (node);
    2297                 :       7967 : }
    2298                 :            : 
    2299                 :            : /* Varpool removal hook called for a NODE with a custom DATA.  */
    2300                 :            : 
    2301                 :            : void
    2302                 :       2178 : sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
    2303                 :            : {
    2304                 :       2178 :   sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
    2305                 :       2178 :   optimizer->remove_symtab_node (node);
    2306                 :       2178 : }
    2307                 :            : 
    2308                 :            : /* Remove symtab NODE triggered by symtab removal hooks.  */
    2309                 :            : 
    2310                 :            : void
    2311                 :      10145 : sem_item_optimizer::remove_symtab_node (symtab_node *node)
    2312                 :            : {
    2313                 :      10145 :   gcc_assert (m_classes.is_empty ());
    2314                 :            : 
    2315                 :      10145 :   m_removed_items_set.add (node);
    2316                 :      10145 : }
    2317                 :            : 
    2318                 :            : void
    2319                 :     565382 : sem_item_optimizer::remove_item (sem_item *item)
    2320                 :            : {
    2321                 :     565382 :   if (m_symtab_node_map.get (item->node))
    2322                 :     549899 :     m_symtab_node_map.remove (item->node);
    2323                 :     565382 :   delete item;
    2324                 :     565382 : }
    2325                 :            : 
    2326                 :            : /* Removes all callgraph and varpool nodes that are marked by symtab
    2327                 :            :    as deleted.  */
    2328                 :            : 
    2329                 :            : void
    2330                 :      93278 : sem_item_optimizer::filter_removed_items (void)
    2331                 :            : {
    2332                 :      93278 :   auto_vec <sem_item *> filtered;
    2333                 :            : 
    2334                 :    5366690 :   for (unsigned int i = 0; i < m_items.length(); i++)
    2335                 :            :     {
    2336                 :    2591500 :       sem_item *item = m_items[i];
    2337                 :            : 
    2338                 :    2591500 :       if (m_removed_items_set.contains (item->node))
    2339                 :            :         {
    2340                 :       5280 :           remove_item (item);
    2341                 :       5280 :           continue;
    2342                 :            :         }
    2343                 :            : 
    2344                 :    2586220 :       if (item->type == FUNC)
    2345                 :            :         {
    2346                 :     798113 :           cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
    2347                 :            : 
    2348                 :     798113 :           if (in_lto_p && (cnode->alias || cnode->body_removed))
    2349                 :          4 :             remove_item (item);
    2350                 :            :           else
    2351                 :     798109 :             filtered.safe_push (item);
    2352                 :            :         }
    2353                 :            :       else /* VAR.  */
    2354                 :            :         {
    2355                 :    1788110 :           if (!flag_ipa_icf_variables)
    2356                 :          1 :             remove_item (item);
    2357                 :            :           else
    2358                 :            :             {
    2359                 :            :               /* Filter out non-readonly variables.  */
    2360                 :    1788110 :               tree decl = item->decl;
    2361                 :    1788110 :               if (TREE_READONLY (decl))
    2362                 :    1228010 :                 filtered.safe_push (item);
    2363                 :            :               else
    2364                 :     560097 :                 remove_item (item);
    2365                 :            :             }
    2366                 :            :         }
    2367                 :            :     }
    2368                 :            : 
    2369                 :            :   /* Clean-up of released semantic items.  */
    2370                 :            : 
    2371                 :      93278 :   m_items.release ();
    2372                 :    4235200 :   for (unsigned int i = 0; i < filtered.length(); i++)
    2373                 :    2026120 :     m_items.safe_push (filtered[i]);
    2374                 :      93278 : }
    2375                 :            : 
    2376                 :            : /* Optimizer entry point which returns true in case it processes
    2377                 :            :    a merge operation. True is returned if there's a merge operation
    2378                 :            :    processed.  */
    2379                 :            : 
    2380                 :            : bool
    2381                 :      93278 : sem_item_optimizer::execute (void)
    2382                 :            : {
    2383                 :      93278 :   filter_removed_items ();
    2384                 :      93278 :   unregister_hooks ();
    2385                 :            : 
    2386                 :      93278 :   build_graph ();
    2387                 :      93278 :   update_hash_by_addr_refs ();
    2388                 :      93278 :   build_hash_based_classes ();
    2389                 :            : 
    2390                 :      93278 :   if (dump_file)
    2391                 :        173 :     fprintf (dump_file, "Dump after hash based groups\n");
    2392                 :      93278 :   dump_cong_classes ();
    2393                 :            : 
    2394                 :      93278 :   subdivide_classes_by_equality (true);
    2395                 :            : 
    2396                 :      93278 :   if (dump_file)
    2397                 :        173 :     fprintf (dump_file, "Dump after WPA based types groups\n");
    2398                 :            : 
    2399                 :      93278 :   dump_cong_classes ();
    2400                 :            : 
    2401                 :      93278 :   process_cong_reduction ();
    2402                 :      93278 :   checking_verify_classes ();
    2403                 :            : 
    2404                 :      93278 :   if (dump_file)
    2405                 :        173 :     fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
    2406                 :            : 
    2407                 :      93278 :   dump_cong_classes ();
    2408                 :            : 
    2409                 :      93278 :   unsigned int loaded_symbols = parse_nonsingleton_classes ();
    2410                 :      93278 :   subdivide_classes_by_equality ();
    2411                 :            : 
    2412                 :      93278 :   if (dump_file)
    2413                 :        173 :     fprintf (dump_file, "Dump after full equality comparison of groups\n");
    2414                 :            : 
    2415                 :      93278 :   dump_cong_classes ();
    2416                 :            : 
    2417                 :      93278 :   unsigned int prev_class_count = m_classes_count;
    2418                 :            : 
    2419                 :      93278 :   process_cong_reduction ();
    2420                 :      93278 :   dump_cong_classes ();
    2421                 :      93278 :   checking_verify_classes ();
    2422                 :      93278 :   bool merged_p = merge_classes (prev_class_count, loaded_symbols);
    2423                 :            : 
    2424                 :      93278 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2425                 :         20 :     symtab->dump (dump_file);
    2426                 :            : 
    2427                 :      93278 :   return merged_p;
    2428                 :            : }
    2429                 :            : 
    2430                 :            : /* Function responsible for visiting all potential functions and
    2431                 :            :    read-only variables that can be merged.  */
    2432                 :            : 
    2433                 :            : void
    2434                 :      91945 : sem_item_optimizer::parse_funcs_and_vars (void)
    2435                 :            : {
    2436                 :      91945 :   cgraph_node *cnode;
    2437                 :            : 
    2438                 :            :   /* Create dummy func_checker for hashing purpose.  */
    2439                 :     183890 :   func_checker checker;
    2440                 :            : 
    2441                 :      91945 :   if (flag_ipa_icf_functions)
    2442                 :    1856020 :     FOR_EACH_DEFINED_FUNCTION (cnode)
    2443                 :            :     {
    2444                 :     836070 :       sem_function *f = sem_function::parse (cnode, &m_bmstack, &checker);
    2445                 :     836070 :       if (f)
    2446                 :            :         {
    2447                 :     774172 :           m_items.safe_push (f);
    2448                 :     774172 :           m_symtab_node_map.put (cnode, f);
    2449                 :            :         }
    2450                 :            :     }
    2451                 :            : 
    2452                 :      91945 :   varpool_node *vnode;
    2453                 :            : 
    2454                 :      91945 :   if (flag_ipa_icf_variables)
    2455                 :    4069660 :     FOR_EACH_DEFINED_VARIABLE (vnode)
    2456                 :            :     {
    2457                 :    1942890 :       sem_variable *v = sem_variable::parse (vnode, &m_bmstack, &checker);
    2458                 :            : 
    2459                 :    1942890 :       if (v)
    2460                 :            :         {
    2461                 :    1886010 :           m_items.safe_push (v);
    2462                 :    1886010 :           m_symtab_node_map.put (vnode, v);
    2463                 :            :         }
    2464                 :            :     }
    2465                 :      91945 : }
    2466                 :            : 
    2467                 :            : /* Makes pairing between a congruence class CLS and semantic ITEM.  */
    2468                 :            : 
    2469                 :            : void
    2470                 :    3417630 : sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
    2471                 :            : {
    2472                 :    3417630 :   item->index_in_class = cls->members.length ();
    2473                 :    3417630 :   cls->members.safe_push (item);
    2474                 :    3417630 :   cls->referenced_by_count += item->referenced_by_count;
    2475                 :    3417630 :   item->cls = cls;
    2476                 :    3417630 : }
    2477                 :            : 
    2478                 :            : /* For each semantic item, append hash values of references.  */
    2479                 :            : 
    2480                 :            : void
    2481                 :      93278 : sem_item_optimizer::update_hash_by_addr_refs ()
    2482                 :            : {
    2483                 :            :   /* First, append to hash sensitive references and class type if it need to
    2484                 :            :      be matched for ODR.  */
    2485                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2486                 :            :     {
    2487                 :    2026120 :       m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
    2488                 :    2026120 :       if (m_items[i]->type == FUNC)
    2489                 :            :         {
    2490                 :     798109 :           if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
    2491                 :     174162 :               && contains_polymorphic_type_p
    2492                 :     174162 :                    (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
    2493                 :     853355 :               && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
    2494                 :      46190 :                   || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
    2495                 :      74174 :                       && static_cast<sem_function *> (m_items[i])
    2496                 :      92333 :                            ->compare_polymorphic_p ())))
    2497                 :            :              {
    2498                 :      32813 :                 tree class_type
    2499                 :      32813 :                   = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
    2500                 :      32813 :                 inchash::hash hstate (m_items[i]->get_hash ());
    2501                 :            : 
    2502                 :      32813 :                 if (TYPE_NAME (class_type)
    2503                 :      32813 :                      && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
    2504                 :        268 :                   hstate.add_hwi
    2505                 :        268 :                     (IDENTIFIER_HASH_VALUE
    2506                 :            :                        (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
    2507                 :            : 
    2508                 :      32813 :                 m_items[i]->set_hash (hstate.end ());
    2509                 :            :              }
    2510                 :            :         }
    2511                 :            :     }
    2512                 :            : 
    2513                 :            :   /* Once all symbols have enhanced hash value, we can append
    2514                 :            :      hash values of symbols that are seen by IPA ICF and are
    2515                 :            :      references by a semantic item. Newly computed values
    2516                 :            :      are saved to global_hash member variable.  */
    2517                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2518                 :    2026120 :     m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
    2519                 :            : 
    2520                 :            :   /* Global hash value replace current hash values.  */
    2521                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2522                 :    2026120 :     m_items[i]->set_hash (m_items[i]->global_hash);
    2523                 :      93278 : }
    2524                 :            : 
    2525                 :            : /* Congruence classes are built by hash value.  */
    2526                 :            : 
    2527                 :            : void
    2528                 :      93278 : sem_item_optimizer::build_hash_based_classes (void)
    2529                 :            : {
    2530                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2531                 :            :     {
    2532                 :    2026120 :       sem_item *item = m_items[i];
    2533                 :            : 
    2534                 :    2026120 :       congruence_class_group *group
    2535                 :    2026120 :         = get_group_by_hash (item->get_hash (), item->type);
    2536                 :            : 
    2537                 :    2026120 :       if (!group->classes.length ())
    2538                 :            :         {
    2539                 :    1476730 :           m_classes_count++;
    2540                 :    1476730 :           group->classes.safe_push (new congruence_class (class_id++));
    2541                 :            :         }
    2542                 :            : 
    2543                 :    2026120 :       add_item_to_class (group->classes[0], item);
    2544                 :            :     }
    2545                 :      93278 : }
    2546                 :            : 
    2547                 :            : /* Build references according to call graph.  */
    2548                 :            : 
    2549                 :            : void
    2550                 :      93278 : sem_item_optimizer::build_graph (void)
    2551                 :            : {
    2552                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2553                 :            :     {
    2554                 :    2026120 :       sem_item *item = m_items[i];
    2555                 :    2026120 :       m_symtab_node_map.put (item->node, item);
    2556                 :            : 
    2557                 :            :       /* Initialize hash values if we are not in LTO mode.  */
    2558                 :    2026120 :       if (!in_lto_p)
    2559                 :    1963080 :         item->get_hash ();
    2560                 :            :     }
    2561                 :            : 
    2562                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2563                 :            :     {
    2564                 :    2026120 :       sem_item *item = m_items[i];
    2565                 :            : 
    2566                 :    2026120 :       if (item->type == FUNC)
    2567                 :            :         {
    2568                 :     798109 :           cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
    2569                 :            : 
    2570                 :     798109 :           cgraph_edge *e = cnode->callees;
    2571                 :    3979280 :           while (e)
    2572                 :            :             {
    2573                 :    3181170 :               sem_item **slot = m_symtab_node_map.get
    2574                 :    3181170 :                 (e->callee->ultimate_alias_target ());
    2575                 :    2129980 :               if (slot)
    2576                 :    1051200 :                 item->add_reference (&m_references, *slot);
    2577                 :            : 
    2578                 :    3181170 :               e = e->next_callee;
    2579                 :            :             }
    2580                 :            :         }
    2581                 :            : 
    2582                 :    6208050 :       ipa_ref *ref = NULL;
    2583                 :    7013440 :       for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
    2584                 :            :         {
    2585                 :    4181930 :           sem_item **slot = m_symtab_node_map.get
    2586                 :    4191780 :             (ref->referred->ultimate_alias_target ());
    2587                 :    1552600 :           if (slot)
    2588                 :    2629320 :             item->add_reference (&m_references, *slot);
    2589                 :            :         }
    2590                 :            :     }
    2591                 :      93278 : }
    2592                 :            : 
    2593                 :            : /* Semantic items in classes having more than one element and initialized.
    2594                 :            :    In case of WPA, we load function body.  */
    2595                 :            : 
    2596                 :            : unsigned int
    2597                 :      93278 : sem_item_optimizer::parse_nonsingleton_classes (void)
    2598                 :            : {
    2599                 :      93278 :   unsigned int counter = 0;
    2600                 :            : 
    2601                 :            :   /* Create dummy func_checker for hashing purpose.  */
    2602                 :     186556 :   func_checker checker;
    2603                 :            : 
    2604                 :    4235200 :   for (unsigned i = 0; i < m_items.length (); i++)
    2605                 :    2026120 :     if (m_items[i]->cls->members.length () > 1)
    2606                 :            :       {
    2607                 :     583550 :         m_items[i]->init (&checker);
    2608                 :     583550 :         ++counter;
    2609                 :            :       }
    2610                 :            : 
    2611                 :      93278 :   if (dump_file)
    2612                 :            :     {
    2613                 :        173 :       float f = m_items.length () ? 100.0f * counter / m_items.length () : 0.0f;
    2614                 :        173 :       fprintf (dump_file, "Init called for %u items (%.2f%%).\n", counter, f);
    2615                 :            :     }
    2616                 :            : 
    2617                 :      93278 :   return counter;
    2618                 :            : }
    2619                 :            : 
    2620                 :            : /* Equality function for semantic items is used to subdivide existing
    2621                 :            :    classes. If IN_WPA, fast equality function is invoked.  */
    2622                 :            : 
    2623                 :            : void
    2624                 :     186556 : sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
    2625                 :            : {
    2626                 :    3140020 :   for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
    2627                 :    3140020 :        it != m_classes.end (); ++it)
    2628                 :            :     {
    2629                 :    2953460 :       unsigned int class_count = (*it)->classes.length ();
    2630                 :            : 
    2631                 :    5987240 :       for (unsigned i = 0; i < class_count; i++)
    2632                 :            :         {
    2633                 :    3033770 :           congruence_class *c = (*it)->classes[i];
    2634                 :            : 
    2635                 :    3033770 :           if (c->members.length() > 1)
    2636                 :            :             {
    2637                 :     490074 :               auto_vec <sem_item *> new_vector;
    2638                 :            : 
    2639                 :     245037 :               sem_item *first = c->members[0];
    2640                 :     245037 :               new_vector.safe_push (first);
    2641                 :            : 
    2642                 :     245037 :               unsigned class_split_first = (*it)->classes.length ();
    2643                 :            : 
    2644                 :    2527020 :               for (unsigned j = 1; j < c->members.length (); j++)
    2645                 :            :                 {
    2646                 :    1018470 :                   sem_item *item = c->members[j];
    2647                 :            : 
    2648                 :    1018470 :                   bool equals
    2649                 :    1018470 :                     = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
    2650                 :     469083 :                              : first->equals (item, m_symtab_node_map);
    2651                 :            : 
    2652                 :    1018470 :                   if (equals)
    2653                 :     825385 :                     new_vector.safe_push (item);
    2654                 :            :                   else
    2655                 :            :                     {
    2656                 :    1483570 :                       bool integrated = false;
    2657                 :            : 
    2658                 :    1290480 :                       for (unsigned k = class_split_first;
    2659                 :    2967150 :                            k < (*it)->classes.length (); k++)
    2660                 :            :                         {
    2661                 :    1375980 :                           sem_item *x = (*it)->classes[k]->members[0];
    2662                 :    1375980 :                           bool equals
    2663                 :    1375980 :                             = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
    2664                 :     191556 :                                      : x->equals (item, m_symtab_node_map);
    2665                 :            : 
    2666                 :    1375980 :                           if (equals)
    2667                 :            :                             {
    2668                 :      85499 :                               integrated = true;
    2669                 :      85499 :                               add_item_to_class ((*it)->classes[k], item);
    2670                 :            : 
    2671                 :      85499 :                               break;
    2672                 :            :                             }
    2673                 :            :                         }
    2674                 :            : 
    2675                 :      85499 :                       if (!integrated)
    2676                 :            :                         {
    2677                 :     107590 :                           congruence_class *c
    2678                 :     107590 :                             = new congruence_class (class_id++);
    2679                 :     107590 :                           m_classes_count++;
    2680                 :     107590 :                           add_item_to_class (c, item);
    2681                 :            : 
    2682                 :     107590 :                           (*it)->classes.safe_push (c);
    2683                 :            :                         }
    2684                 :            :                     }
    2685                 :            :                 }
    2686                 :            : 
    2687                 :            :               // We replace newly created new_vector for the class we've just
    2688                 :            :               // splitted.
    2689                 :     245037 :               c->members.release ();
    2690                 :     245037 :               c->members.create (new_vector.length ());
    2691                 :            : 
    2692                 :    2630920 :               for (unsigned int j = 0; j < new_vector.length (); j++)
    2693                 :    1070420 :                 add_item_to_class (c, new_vector[j]);
    2694                 :            :             }
    2695                 :            :         }
    2696                 :            :     }
    2697                 :            : 
    2698                 :     186556 :   checking_verify_classes ();
    2699                 :     186556 : }
    2700                 :            : 
    2701                 :            : /* Subdivide classes by address references that members of the class
    2702                 :            :    reference. Example can be a pair of functions that have an address
    2703                 :            :    taken from a function. If these addresses are different the class
    2704                 :            :    is split.  */
    2705                 :            : 
    2706                 :            : unsigned
    2707                 :     186556 : sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
    2708                 :            : {
    2709                 :     186556 :   typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
    2710                 :            : 
    2711                 :     186556 :   unsigned newly_created_classes = 0;
    2712                 :            : 
    2713                 :     186556 :   for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
    2714                 :    3140020 :        it != m_classes.end (); ++it)
    2715                 :            :     {
    2716                 :    2953460 :       unsigned int class_count = (*it)->classes.length ();
    2717                 :    5906930 :       auto_vec<congruence_class *> new_classes;
    2718                 :            : 
    2719                 :    6109200 :       for (unsigned i = 0; i < class_count; i++)
    2720                 :            :         {
    2721                 :    3155740 :           congruence_class *c = (*it)->classes[i];
    2722                 :            : 
    2723                 :    3155740 :           if (c->members.length() > 1)
    2724                 :            :             {
    2725                 :     444490 :               subdivide_hash_map split_map;
    2726                 :            : 
    2727                 :    2682000 :               for (unsigned j = 0; j < c->members.length (); j++)
    2728                 :            :                 {
    2729                 :    1118750 :                   sem_item *source_node = c->members[j];
    2730                 :            : 
    2731                 :    1118750 :                   symbol_compare_collection *collection
    2732                 :    1118750 :                     = new symbol_compare_collection (source_node->node);
    2733                 :            : 
    2734                 :    1118750 :                   bool existed;
    2735                 :    1118750 :                   vec <sem_item *> *slot
    2736                 :    1118750 :                     = &split_map.get_or_insert (collection, &existed);
    2737                 :    1118750 :                   gcc_checking_assert (slot);
    2738                 :            : 
    2739                 :    1118750 :                   slot->safe_push (source_node);
    2740                 :            : 
    2741                 :    1118750 :                   if (existed)
    2742                 :     896509 :                     delete collection;
    2743                 :            :                 }
    2744                 :            : 
    2745                 :            :                /* If the map contains more than one key, we have to split
    2746                 :            :                   the map appropriately.  */
    2747                 :     222245 :               if (split_map.elements () != 1)
    2748                 :            :                 {
    2749                 :          0 :                   bool first_class = true;
    2750                 :            : 
    2751                 :          0 :                   for (subdivide_hash_map::iterator it2 = split_map.begin ();
    2752                 :          0 :                        it2 != split_map.end (); ++it2)
    2753                 :            :                     {
    2754                 :          0 :                       congruence_class *new_cls;
    2755                 :          0 :                       new_cls = new congruence_class (class_id++);
    2756                 :            : 
    2757                 :          0 :                       for (unsigned k = 0; k < (*it2).second.length (); k++)
    2758                 :          0 :                         add_item_to_class (new_cls, (*it2).second[k]);
    2759                 :            : 
    2760                 :          0 :                       worklist_push (new_cls);
    2761                 :          0 :                       newly_created_classes++;
    2762                 :            : 
    2763                 :          0 :                       if (first_class)
    2764                 :            :                         {
    2765                 :          0 :                           (*it)->classes[i] = new_cls;
    2766                 :          0 :                           first_class = false;
    2767                 :            :                         }
    2768                 :            :                       else
    2769                 :            :                         {
    2770                 :          0 :                           new_classes.safe_push (new_cls);
    2771                 :          0 :                           m_classes_count++;
    2772                 :            :                         }
    2773                 :            :                     }
    2774                 :            :                 }
    2775                 :            : 
    2776                 :            :               /* Release memory.  */
    2777                 :     666735 :               for (subdivide_hash_map::iterator it2 = split_map.begin ();
    2778                 :     666735 :                    it2 != split_map.end (); ++it2)
    2779                 :            :                 {
    2780                 :     222245 :                   delete (*it2).first;
    2781                 :     444490 :                   (*it2).second.release ();
    2782                 :            :                 }
    2783                 :            :             }
    2784                 :            :           }
    2785                 :            : 
    2786                 :    2953460 :         for (unsigned i = 0; i < new_classes.length (); i++)
    2787                 :          0 :           (*it)->classes.safe_push (new_classes[i]);
    2788                 :            :     }
    2789                 :            : 
    2790                 :     186556 :   return newly_created_classes;
    2791                 :            : }
    2792                 :            : 
    2793                 :            : /* Verify congruence classes, if checking is enabled.  */
    2794                 :            : 
    2795                 :            : void
    2796                 :     373112 : sem_item_optimizer::checking_verify_classes (void)
    2797                 :            : {
    2798                 :     373112 :   if (flag_checking)
    2799                 :     373092 :     verify_classes ();
    2800                 :     373112 : }
    2801                 :            : 
    2802                 :            : /* Verify congruence classes.  */
    2803                 :            : 
    2804                 :            : void
    2805                 :     373092 : sem_item_optimizer::verify_classes (void)
    2806                 :            : {
    2807                 :    6280000 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    2808                 :    6280000 :        it != m_classes.end (); ++it)
    2809                 :            :     {
    2810                 :   24408000 :       for (unsigned int i = 0; i < (*it)->classes.length (); i++)
    2811                 :            :         {
    2812                 :    6297080 :           congruence_class *cls = (*it)->classes[i];
    2813                 :            : 
    2814                 :    6297080 :           gcc_assert (cls);
    2815                 :    6297080 :           gcc_assert (cls->members.length () > 0);
    2816                 :            : 
    2817                 :   14401600 :           for (unsigned int j = 0; j < cls->members.length (); j++)
    2818                 :            :             {
    2819                 :    8104470 :               sem_item *item = cls->members[j];
    2820                 :            : 
    2821                 :    8104470 :               gcc_assert (item);
    2822                 :    8104470 :               gcc_assert (item->cls == cls);
    2823                 :            :             }
    2824                 :            :         }
    2825                 :            :     }
    2826                 :     373092 : }
    2827                 :            : 
    2828                 :            : /* Disposes split map traverse function. CLS_PTR is pointer to congruence
    2829                 :            :    class, BSLOT is bitmap slot we want to release. DATA is mandatory,
    2830                 :            :    but unused argument.  */
    2831                 :            : 
    2832                 :            : bool
    2833                 :     138069 : sem_item_optimizer::release_split_map (congruence_class * const &,
    2834                 :            :                                        bitmap const &b, traverse_split_pair *)
    2835                 :            : {
    2836                 :     138069 :   bitmap bmp = b;
    2837                 :            : 
    2838                 :     138069 :   BITMAP_FREE (bmp);
    2839                 :            : 
    2840                 :     138069 :   return true;
    2841                 :            : }
    2842                 :            : 
    2843                 :            : /* Process split operation for a class given as pointer CLS_PTR,
    2844                 :            :    where bitmap B splits congruence class members. DATA is used
    2845                 :            :    as argument of split pair.  */
    2846                 :            : 
    2847                 :            : bool
    2848                 :     138069 : sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
    2849                 :            :                                                bitmap const &b,
    2850                 :            :                                                traverse_split_pair *pair)
    2851                 :            : {
    2852                 :     138069 :   sem_item_optimizer *optimizer = pair->optimizer;
    2853                 :     138069 :   const congruence_class *splitter_cls = pair->cls;
    2854                 :            : 
    2855                 :            :   /* If counted bits are greater than zero and less than the number of members
    2856                 :            :      a group will be splitted.  */
    2857                 :     138069 :   unsigned popcount = bitmap_count_bits (b);
    2858                 :            : 
    2859                 :     276138 :   if (popcount > 0 && popcount < cls->members.length ())
    2860                 :            :     {
    2861                 :      28750 :       auto_vec <congruence_class *, 2> newclasses;
    2862                 :      14375 :       newclasses.quick_push (new congruence_class (class_id++));
    2863                 :      14375 :       newclasses.quick_push (new congruence_class (class_id++));
    2864                 :            : 
    2865                 :     284744 :       for (unsigned int i = 0; i < cls->members.length (); i++)
    2866                 :            :         {
    2867                 :     127997 :           int target = bitmap_bit_p (b, i);
    2868                 :     127997 :           congruence_class *tc = newclasses[target];
    2869                 :            : 
    2870                 :     127997 :           add_item_to_class (tc, cls->members[i]);
    2871                 :            :         }
    2872                 :            : 
    2873                 :      14375 :       if (flag_checking)
    2874                 :            :         {
    2875                 :      43125 :           for (unsigned int i = 0; i < 2; i++)
    2876                 :      28750 :             gcc_assert (newclasses[i]->members.length ());
    2877                 :            :         }
    2878                 :            : 
    2879                 :      14375 :       if (splitter_cls == cls)
    2880                 :         35 :         optimizer->splitter_class_removed = true;
    2881                 :            : 
    2882                 :            :       /* Remove old class from worklist if presented.  */
    2883                 :      14375 :       bool in_worklist = cls->in_worklist;
    2884                 :            : 
    2885                 :      14375 :       if (in_worklist)
    2886                 :      10288 :         cls->in_worklist = false;
    2887                 :            : 
    2888                 :      14375 :       congruence_class_group g;
    2889                 :      14375 :       g.hash = cls->members[0]->get_hash ();
    2890                 :      14375 :       g.type = cls->members[0]->type;
    2891                 :            : 
    2892                 :      14375 :       congruence_class_group *slot = optimizer->m_classes.find (&g);
    2893                 :            : 
    2894                 :     203024 :       for (unsigned int i = 0; i < slot->classes.length (); i++)
    2895                 :     101512 :         if (slot->classes[i] == cls)
    2896                 :            :           {
    2897                 :      14375 :             slot->classes.ordered_remove (i);
    2898                 :            :             break;
    2899                 :            :           }
    2900                 :            : 
    2901                 :            :       /* New class will be inserted and integrated to work list.  */
    2902                 :      43125 :       for (unsigned int i = 0; i < 2; i++)
    2903                 :      28750 :         optimizer->add_class (newclasses[i]);
    2904                 :            : 
    2905                 :            :       /* Two classes replace one, so that increment just by one.  */
    2906                 :      14375 :       optimizer->m_classes_count++;
    2907                 :            : 
    2908                 :            :       /* If OLD class was presented in the worklist, we remove the class
    2909                 :            :          and replace it will both newly created classes.  */
    2910                 :      14375 :       if (in_worklist)
    2911                 :      30864 :         for (unsigned int i = 0; i < 2; i++)
    2912                 :      20576 :           optimizer->worklist_push (newclasses[i]);
    2913                 :            :       else /* Just smaller class is inserted.  */
    2914                 :            :         {
    2915                 :       4087 :           unsigned int smaller_index
    2916                 :       4087 :             = (newclasses[0]->members.length ()
    2917                 :       4087 :                < newclasses[1]->members.length ()
    2918                 :       4087 :                ? 0 : 1);
    2919                 :       4087 :           optimizer->worklist_push (newclasses[smaller_index]);
    2920                 :            :         }
    2921                 :            : 
    2922                 :      14375 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2923                 :            :         {
    2924                 :          1 :           fprintf (dump_file, "  congruence class splitted:\n");
    2925                 :          1 :           cls->dump (dump_file, 4);
    2926                 :            : 
    2927                 :          1 :           fprintf (dump_file, "  newly created groups:\n");
    2928                 :          3 :           for (unsigned int i = 0; i < 2; i++)
    2929                 :          2 :             newclasses[i]->dump (dump_file, 4);
    2930                 :            :         }
    2931                 :            : 
    2932                 :            :       /* Release class if not presented in work list.  */
    2933                 :      14375 :       if (!in_worklist)
    2934                 :       8174 :         delete cls;
    2935                 :            : 
    2936                 :      14375 :       return true;
    2937                 :            :     }
    2938                 :            : 
    2939                 :            :   return false;
    2940                 :            : }
    2941                 :            : 
    2942                 :            : /* Compare function for sorting pairs in do_congruence_step_f.  */
    2943                 :            : 
    2944                 :            : int
    2945                 :    1301010 : sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_)
    2946                 :            : {
    2947                 :    1301010 :   const std::pair<congruence_class *, bitmap> *a
    2948                 :            :     = (const std::pair<congruence_class *, bitmap> *)a_;
    2949                 :    1301010 :   const std::pair<congruence_class *, bitmap> *b
    2950                 :            :     = (const std::pair<congruence_class *, bitmap> *)b_;
    2951                 :    1301010 :   if (a->first->id < b->first->id)
    2952                 :            :     return -1;
    2953                 :     613229 :   else if (a->first->id > b->first->id)
    2954                 :     613229 :     return 1;
    2955                 :            :   return 0;
    2956                 :            : }
    2957                 :            : 
    2958                 :            : /* Tests if a class CLS used as INDEXth splits any congruence classes.
    2959                 :            :    Bitmap stack BMSTACK is used for bitmap allocation.  */
    2960                 :            : 
    2961                 :            : bool
    2962                 :    4590070 : sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
    2963                 :            :                                                   unsigned int index)
    2964                 :            : {
    2965                 :    4590070 :   hash_map <congruence_class *, bitmap> split_map;
    2966                 :            : 
    2967                 :   53270400 :   for (unsigned int i = 0; i < cls->members.length (); i++)
    2968                 :            :     {
    2969                 :   22045200 :       sem_item *item = cls->members[i];
    2970                 :   22045200 :       sem_usage_pair needle (item, index);
    2971                 :   22045200 :       vec<sem_item *> *callers = m_references.get (&needle);
    2972                 :   22045200 :       if (callers == NULL)
    2973                 :   16791100 :         continue;
    2974                 :            : 
    2975                 :   25236600 :       for (unsigned int j = 0; j < callers->length (); j++)
    2976                 :            :         {
    2977                 :    7364260 :           sem_item *caller = (*callers)[j];
    2978                 :    7364260 :           if (caller->cls->members.length () < 2)
    2979                 :    6908090 :             continue;
    2980                 :     456165 :           bitmap *slot = split_map.get (caller->cls);
    2981                 :     318096 :           bitmap b;
    2982                 :            : 
    2983                 :     318096 :           if(!slot)
    2984                 :            :             {
    2985                 :     138069 :               b = BITMAP_ALLOC (&m_bmstack);
    2986                 :     138069 :               split_map.put (caller->cls, b);
    2987                 :            :             }
    2988                 :            :           else
    2989                 :     318096 :             b = *slot;
    2990                 :            : 
    2991                 :     456165 :           gcc_checking_assert (caller->cls);
    2992                 :     912330 :           gcc_checking_assert (caller->index_in_class
    2993                 :            :                                < caller->cls->members.length ());
    2994                 :            : 
    2995                 :     456165 :           bitmap_set_bit (b, caller->index_in_class);
    2996                 :            :         }
    2997                 :            :     }
    2998                 :            : 
    2999                 :    9180140 :   auto_vec<std::pair<congruence_class *, bitmap> > to_split;
    3000                 :    4590070 :   to_split.reserve_exact (split_map.elements ());
    3001                 :    9318200 :   for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin ();
    3002                 :    4728140 :        i != split_map.end (); ++i)
    3003                 :     138069 :     to_split.safe_push (*i);
    3004                 :    4590070 :   to_split.qsort (sort_congruence_split);
    3005                 :            : 
    3006                 :    4590070 :   traverse_split_pair pair;
    3007                 :    4590070 :   pair.optimizer = this;
    3008                 :    4590070 :   pair.cls = cls;
    3009                 :            : 
    3010                 :    4590070 :   splitter_class_removed = false;
    3011                 :    4590070 :   bool r = false;
    3012                 :    4943380 :   for (unsigned i = 0; i < to_split.length (); ++i)
    3013                 :     138069 :     r |= traverse_congruence_split (to_split[i].first, to_split[i].second,
    3014                 :            :                                     &pair);
    3015                 :            : 
    3016                 :            :   /* Bitmap clean-up.  */
    3017                 :    4590070 :   split_map.traverse <traverse_split_pair *,
    3018                 :    4590070 :                       sem_item_optimizer::release_split_map> (NULL);
    3019                 :            : 
    3020                 :    4590070 :   return r;
    3021                 :            : }
    3022                 :            : 
    3023                 :            : /* Every usage of a congruence class CLS is a candidate that can split the
    3024                 :            :    collection of classes. Bitmap stack BMSTACK is used for bitmap
    3025                 :            :    allocation.  */
    3026                 :            : 
    3027                 :            : void
    3028                 :    2625700 : sem_item_optimizer::do_congruence_step (congruence_class *cls)
    3029                 :            : {
    3030                 :    2625700 :   bitmap_iterator bi;
    3031                 :    2625700 :   unsigned int i;
    3032                 :            : 
    3033                 :    2625700 :   bitmap usage = BITMAP_ALLOC (&m_bmstack);
    3034                 :            : 
    3035                 :   12226800 :   for (unsigned int i = 0; i < cls->members.length (); i++)
    3036                 :    3487700 :     bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
    3037                 :            : 
    3038                 :    7215740 :   EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
    3039                 :            :   {
    3040                 :    4590070 :     if (dump_file && (dump_flags & TDF_DETAILS))
    3041                 :        188 :       fprintf (dump_file, "  processing congruence step for class: %u "
    3042                 :            :                "(%u items, %u references), index: %u\n", cls->id,
    3043                 :            :                cls->referenced_by_count, cls->members.length (), i);
    3044                 :    4590070 :     do_congruence_step_for_index (cls, i);
    3045                 :            : 
    3046                 :    4590070 :     if (splitter_class_removed)
    3047                 :            :       break;
    3048                 :            :   }
    3049                 :            : 
    3050                 :    2625700 :   BITMAP_FREE (usage);
    3051                 :    2625700 : }
    3052                 :            : 
    3053                 :            : /* Adds a newly created congruence class CLS to worklist.  */
    3054                 :            : 
    3055                 :            : void
    3056                 :    2635990 : sem_item_optimizer::worklist_push (congruence_class *cls)
    3057                 :            : {
    3058                 :            :   /* Return if the class CLS is already presented in work list.  */
    3059                 :    2635990 :   if (cls->in_worklist)
    3060                 :            :     return;
    3061                 :            : 
    3062                 :    2635990 :   cls->in_worklist = true;
    3063                 :    2635990 :   worklist.insert (cls->referenced_by_count, cls);
    3064                 :            : }
    3065                 :            : 
    3066                 :            : /* Pops a class from worklist. */
    3067                 :            : 
    3068                 :            : congruence_class *
    3069                 :    2812260 : sem_item_optimizer::worklist_pop (void)
    3070                 :            : {
    3071                 :    2822550 :   congruence_class *cls;
    3072                 :            : 
    3073                 :    2822550 :   while (!worklist.empty ())
    3074                 :            :     {
    3075                 :    2635990 :       cls = worklist.extract_min ();
    3076                 :    2635990 :       if (cls->in_worklist)
    3077                 :            :         {
    3078                 :    2625700 :           cls->in_worklist = false;
    3079                 :            : 
    3080                 :    2625700 :           return cls;
    3081                 :            :         }
    3082                 :            :       else
    3083                 :            :         {
    3084                 :            :           /* Work list item was already intended to be removed.
    3085                 :            :              The only reason for doing it is to split a class.
    3086                 :            :              Thus, the class CLS is deleted.  */
    3087                 :      20576 :           delete cls;
    3088                 :            :         }
    3089                 :            :     }
    3090                 :            : 
    3091                 :            :   return NULL;
    3092                 :            : }
    3093                 :            : 
    3094                 :            : /* Iterative congruence reduction function.  */
    3095                 :            : 
    3096                 :            : void
    3097                 :     186556 : sem_item_optimizer::process_cong_reduction (void)
    3098                 :            : {
    3099                 :    3140020 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3100                 :    3140020 :        it != m_classes.end (); ++it)
    3101                 :   12189700 :     for (unsigned i = 0; i < (*it)->classes.length (); i++)
    3102                 :    3141360 :       if ((*it)->classes[i]->is_class_used ())
    3103                 :    2611330 :         worklist_push ((*it)->classes[i]);
    3104                 :            : 
    3105                 :     186556 :   if (dump_file)
    3106                 :        346 :     fprintf (dump_file, "Worklist has been filled with: %lu\n",
    3107                 :        346 :              (unsigned long) worklist.nodes ());
    3108                 :            : 
    3109                 :     186556 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3110                 :         40 :     fprintf (dump_file, "Congruence class reduction\n");
    3111                 :            : 
    3112                 :    2812260 :   congruence_class *cls;
    3113                 :            : 
    3114                 :            :   /* Process complete congruence reduction.  */
    3115                 :    2812260 :   while ((cls = worklist_pop ()) != NULL)
    3116                 :    2625700 :     do_congruence_step (cls);
    3117                 :            : 
    3118                 :            :   /* Subdivide newly created classes according to references.  */
    3119                 :     186556 :   unsigned new_classes = subdivide_classes_by_sensitive_refs ();
    3120                 :            : 
    3121                 :     186556 :   if (dump_file)
    3122                 :        346 :     fprintf (dump_file, "Address reference subdivision created: %u "
    3123                 :            :              "new classes.\n", new_classes);
    3124                 :     186556 : }
    3125                 :            : 
    3126                 :            : /* Debug function prints all informations about congruence classes.  */
    3127                 :            : 
    3128                 :            : void
    3129                 :     466390 : sem_item_optimizer::dump_cong_classes (void)
    3130                 :            : {
    3131                 :     466390 :   if (!dump_file)
    3132                 :            :     return;
    3133                 :            : 
    3134                 :            :   /* Histogram calculation.  */
    3135                 :        865 :   unsigned int max_index = 0;
    3136                 :        865 :   unsigned int single_element_classes = 0;
    3137                 :       1725 :   unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
    3138                 :            : 
    3139                 :       3305 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3140                 :       3305 :        it != m_classes.end (); ++it)
    3141                 :      10066 :     for (unsigned i = 0; i < (*it)->classes.length (); i++)
    3142                 :            :       {
    3143                 :       2593 :         unsigned int c = (*it)->classes[i]->members.length ();
    3144                 :       2593 :         histogram[c]++;
    3145                 :            : 
    3146                 :       2593 :         if (c > max_index)
    3147                 :            :           max_index = c;
    3148                 :            : 
    3149                 :       2593 :         if (c == 1)
    3150                 :       2138 :           ++single_element_classes;
    3151                 :            :       }
    3152                 :            : 
    3153                 :        865 :   fprintf (dump_file,
    3154                 :            :            "Congruence classes: %lu with total: %u items (in a non-singular "
    3155                 :        865 :            "class: %u)\n", (unsigned long) m_classes.elements (),
    3156                 :        865 :            m_items.length (), m_items.length () - single_element_classes);
    3157                 :        865 :   fprintf (dump_file,
    3158                 :            :            "Class size histogram [number of members]: number of classes\n");
    3159                 :       2998 :   for (unsigned int i = 0; i <= max_index; i++)
    3160                 :       2133 :     if (histogram[i])
    3161                 :       1172 :       fprintf (dump_file, "%6u: %6u\n", i, histogram[i]);
    3162                 :            : 
    3163                 :        865 :   if (dump_flags & TDF_DETAILS)
    3164                 :        370 :     for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3165                 :        370 :          it != m_classes.end (); ++it)
    3166                 :            :       {
    3167                 :        540 :         fprintf (dump_file, "  group: with %u classes:\n",
    3168                 :        270 :                  (*it)->classes.length ());
    3169                 :            : 
    3170                 :       1190 :         for (unsigned i = 0; i < (*it)->classes.length (); i++)
    3171                 :            :           {
    3172                 :        325 :             (*it)->classes[i]->dump (dump_file, 4);
    3173                 :            : 
    3174                 :        650 :             if (i < (*it)->classes.length () - 1)
    3175                 :         55 :               fprintf (dump_file, " ");
    3176                 :            :           }
    3177                 :            :       }
    3178                 :            : 
    3179                 :        865 :   free (histogram);
    3180                 :            : }
    3181                 :            : 
    3182                 :            : /* Sort pair of sem_items A and B by DECL_UID.  */
    3183                 :            : 
    3184                 :            : static int
    3185                 :    9434590 : sort_sem_items_by_decl_uid (const void *a, const void *b)
    3186                 :            : {
    3187                 :    9434590 :   const sem_item *i1 = *(const sem_item * const *)a;
    3188                 :    9434590 :   const sem_item *i2 = *(const sem_item * const *)b;
    3189                 :            : 
    3190                 :    9434590 :   int uid1 = DECL_UID (i1->decl);
    3191                 :    9434590 :   int uid2 = DECL_UID (i2->decl);
    3192                 :    9434590 :   return uid1 - uid2;
    3193                 :            : }
    3194                 :            : 
    3195                 :            : /* Sort pair of congruence_classes A and B by DECL_UID of the first member.  */
    3196                 :            : 
    3197                 :            : static int
    3198                 :    1707320 : sort_congruence_classes_by_decl_uid (const void *a, const void *b)
    3199                 :            : {
    3200                 :    1707320 :   const congruence_class *c1 = *(const congruence_class * const *)a;
    3201                 :    1707320 :   const congruence_class *c2 = *(const congruence_class * const *)b;
    3202                 :            : 
    3203                 :    1707320 :   int uid1 = DECL_UID (c1->members[0]->decl);
    3204                 :    1707320 :   int uid2 = DECL_UID (c2->members[0]->decl);
    3205                 :    1707320 :   return uid1 - uid2;
    3206                 :            : }
    3207                 :            : 
    3208                 :            : /* Sort pair of congruence_class_groups A and B by
    3209                 :            :    DECL_UID of the first member of a first group.  */
    3210                 :            : 
    3211                 :            : static int
    3212                 :   59784500 : sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
    3213                 :            : {
    3214                 :   59784500 :   const std::pair<congruence_class_group *, int> *g1
    3215                 :            :     = (const std::pair<congruence_class_group *, int> *) a;
    3216                 :   59784500 :   const std::pair<congruence_class_group *, int> *g2
    3217                 :            :     = (const std::pair<congruence_class_group *, int> *) b;
    3218                 :   59784500 :   return g1->second - g2->second;
    3219                 :            : }
    3220                 :            : 
    3221                 :            : /* After reduction is done, we can declare all items in a group
    3222                 :            :    to be equal. PREV_CLASS_COUNT is start number of classes
    3223                 :            :    before reduction. True is returned if there's a merge operation
    3224                 :            :    processed.  LOADED_SYMBOLS is number of symbols that were loaded
    3225                 :            :    in WPA.  */
    3226                 :            : 
    3227                 :            : bool
    3228                 :      93278 : sem_item_optimizer::merge_classes (unsigned int prev_class_count,
    3229                 :            :                                    unsigned int loaded_symbols)
    3230                 :            : {
    3231                 :      93278 :   unsigned int item_count = m_items.length ();
    3232                 :      93278 :   unsigned int class_count = m_classes_count;
    3233                 :      93278 :   unsigned int equal_items = item_count - class_count;
    3234                 :            : 
    3235                 :      93278 :   unsigned int non_singular_classes_count = 0;
    3236                 :      93278 :   unsigned int non_singular_classes_sum = 0;
    3237                 :            : 
    3238                 :      93278 :   bool merged_p = false;
    3239                 :            : 
    3240                 :            :   /* PR lto/78211
    3241                 :            :      Sort functions in congruence classes by DECL_UID and do the same
    3242                 :            :      for the classes to not to break -fcompare-debug.  */
    3243                 :            : 
    3244                 :      93278 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3245                 :    1570010 :        it != m_classes.end (); ++it)
    3246                 :            :     {
    3247                 :    6150860 :       for (unsigned int i = 0; i < (*it)->classes.length (); i++)
    3248                 :            :         {
    3249                 :    1598700 :           congruence_class *c = (*it)->classes[i];
    3250                 :    3197390 :           c->members.qsort (sort_sem_items_by_decl_uid);
    3251                 :            :         }
    3252                 :            : 
    3253                 :    2953460 :       (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
    3254                 :            :     }
    3255                 :            : 
    3256                 :    1570010 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3257                 :    1570010 :        it != m_classes.end (); ++it)
    3258                 :    6150860 :     for (unsigned int i = 0; i < (*it)->classes.length (); i++)
    3259                 :            :       {
    3260                 :    1598700 :         congruence_class *c = (*it)->classes[i];
    3261                 :    1598700 :         if (c->members.length () > 1)
    3262                 :            :           {
    3263                 :     107778 :             non_singular_classes_count++;
    3264                 :     107778 :             non_singular_classes_sum += c->members.length ();
    3265                 :            :           }
    3266                 :            :       }
    3267                 :            : 
    3268                 :      93278 :   auto_vec<std::pair<congruence_class_group *, int> > classes (
    3269                 :      93278 :     m_classes.elements ());
    3270                 :      93278 :   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
    3271                 :    1570010 :        it != m_classes.end (); ++it)
    3272                 :            :     {
    3273                 :    1476730 :       int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
    3274                 :    1476730 :       classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
    3275                 :            :     }
    3276                 :            : 
    3277                 :      93278 :   classes.qsort (sort_congruence_class_groups_by_decl_uid);
    3278                 :            : 
    3279                 :      93278 :   if (dump_file)
    3280                 :            :     {
    3281                 :        173 :       fprintf (dump_file, "\nItem count: %u\n", item_count);
    3282                 :        173 :       fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
    3283                 :            :                prev_class_count, class_count);
    3284                 :        517 :       fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
    3285                 :        172 :                prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
    3286                 :        172 :                class_count ? 1.0f * item_count / class_count : 0.0f);
    3287                 :        228 :       fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
    3288                 :         55 :                non_singular_classes_count ? 1.0f * non_singular_classes_sum /
    3289                 :            :                non_singular_classes_count : 0.0f,
    3290                 :            :                non_singular_classes_count);
    3291                 :        173 :       fprintf (dump_file, "Equal symbols: %u\n", equal_items);
    3292                 :        173 :       unsigned total = equal_items + non_singular_classes_count;
    3293                 :        235 :       fprintf (dump_file, "Totally needed symbols: %u"
    3294                 :            :                ", fraction of loaded symbols: %.2f%%\n\n", total,
    3295                 :         62 :                loaded_symbols ? 100.0f * total / loaded_symbols: 0.0f);
    3296                 :            :     }
    3297                 :            : 
    3298                 :            :   unsigned int l;
    3299                 :            :   std::pair<congruence_class_group *, int> *it;
    3300                 :    3046740 :   FOR_EACH_VEC_ELT (classes, l, it)
    3301                 :    6150860 :     for (unsigned int i = 0; i < it->first->classes.length (); i++)
    3302                 :            :       {
    3303                 :    1598700 :         congruence_class *c = it->first->classes[i];
    3304                 :            : 
    3305                 :    1598700 :         if (c->members.length () == 1)
    3306                 :    1490920 :           continue;
    3307                 :            : 
    3308                 :     107778 :         sem_item *source = c->members[0];
    3309                 :            : 
    3310                 :     107778 :         if (DECL_NAME (source->decl)
    3311                 :     107778 :             && MAIN_NAME_P (DECL_NAME (source->decl)))
    3312                 :            :           /* If merge via wrappers, picking main as the target can be
    3313                 :            :              problematic.  */
    3314                 :          0 :           source = c->members[1];
    3315                 :            : 
    3316                 :    1285960 :         for (unsigned int j = 0; j < c->members.length (); j++)
    3317                 :            :           {
    3318                 :     535204 :             sem_item *alias = c->members[j];
    3319                 :            : 
    3320                 :     535204 :             if (alias == source)
    3321                 :     108075 :               continue;
    3322                 :            : 
    3323                 :     427426 :             dump_user_location_t loc
    3324                 :     427426 :               = dump_user_location_t::from_function_decl (source->decl);
    3325                 :     427426 :             if (dump_enabled_p ())
    3326                 :            :               {
    3327                 :         98 :                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
    3328                 :            :                                  "Semantic equality hit:%s->%s\n",
    3329                 :         98 :                                  source->node->dump_name (),
    3330                 :         98 :                                  alias->node->dump_name ());
    3331                 :         98 :                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
    3332                 :            :                                  "Assembler symbol names:%s->%s\n",
    3333                 :         98 :                                  source->node->dump_asm_name (),
    3334                 :         98 :                                  alias->node->dump_asm_name ());
    3335                 :            :               }
    3336                 :            : 
    3337                 :     427426 :             if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
    3338                 :            :               {
    3339                 :        297 :                 if (dump_enabled_p ())
    3340                 :          1 :                   dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
    3341                 :            :                                    "Merge operation is skipped due to no_icf "
    3342                 :            :                                    "attribute.\n");
    3343                 :        297 :                 continue;
    3344                 :            :               }
    3345                 :            : 
    3346                 :     427129 :             if (dump_file && (dump_flags & TDF_DETAILS))
    3347                 :            :               {
    3348                 :         14 :                 source->dump_to_file (dump_file);
    3349                 :         14 :                 alias->dump_to_file (dump_file);
    3350                 :            :               }
    3351                 :            : 
    3352                 :     427129 :             if (dbg_cnt (merged_ipa_icf))
    3353                 :            :               {
    3354                 :     427125 :                 bool merged = source->merge (alias);
    3355                 :     427125 :                 merged_p |= merged;
    3356                 :            : 
    3357                 :     427125 :                 if (merged && alias->type == VAR)
    3358                 :            :                   {
    3359                 :       5647 :                     symtab_pair p = symtab_pair (source->node, alias->node);
    3360                 :       5647 :                     m_merged_variables.safe_push (p);
    3361                 :            :                   }
    3362                 :            :               }
    3363                 :            :           }
    3364                 :            :       }
    3365                 :            : 
    3366                 :      93278 :   if (!m_merged_variables.is_empty ())
    3367                 :       1225 :     fixup_points_to_sets ();
    3368                 :            : 
    3369                 :      93278 :   return merged_p;
    3370                 :            : }
    3371                 :            : 
    3372                 :            : /* Fixup points to set PT.  */
    3373                 :            : 
    3374                 :            : void
    3375                 :     587019 : sem_item_optimizer::fixup_pt_set (struct pt_solution *pt)
    3376                 :            : {
    3377                 :     587019 :   if (pt->vars == NULL)
    3378                 :     587019 :     return;
    3379                 :            : 
    3380                 :            :   unsigned i;
    3381                 :            :   symtab_pair *item;
    3382                 :    2919080 :   FOR_EACH_VEC_ELT (m_merged_variables, i, item)
    3383                 :    2350110 :     if (bitmap_bit_p (pt->vars, DECL_UID (item->second->decl)))
    3384                 :         15 :       bitmap_set_bit (pt->vars, DECL_UID (item->first->decl));
    3385                 :            : }
    3386                 :            : 
    3387                 :            : /* Set all points-to UIDs of aliases pointing to node N as UID.  */
    3388                 :            : 
    3389                 :            : static void
    3390                 :      45218 : set_alias_uids (symtab_node *n, int uid)
    3391                 :            : {
    3392                 :      45218 :   ipa_ref *ref;
    3393                 :     124370 :   FOR_EACH_ALIAS (n, ref)
    3394                 :            :     {
    3395                 :      39571 :       if (dump_file)
    3396                 :         20 :         fprintf (dump_file, "  Setting points-to UID of [%s] as %d\n",
    3397                 :         20 :                  ref->referring->dump_asm_name (), uid);
    3398                 :            : 
    3399                 :      39571 :       SET_DECL_PT_UID (ref->referring->decl, uid);
    3400                 :      39571 :       set_alias_uids (ref->referring, uid);
    3401                 :            :     }
    3402                 :      45218 : }
    3403                 :            : 
    3404                 :            : /* Fixup points to analysis info.  */
    3405                 :            : 
    3406                 :            : void
    3407                 :       1225 : sem_item_optimizer::fixup_points_to_sets (void)
    3408                 :            : {
    3409                 :            :   /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes.  */
    3410                 :       1225 :   cgraph_node *cnode;
    3411                 :            : 
    3412                 :      62544 :   FOR_EACH_DEFINED_FUNCTION (cnode)
    3413                 :            :     {
    3414                 :      30047 :       tree name;
    3415                 :      30047 :       unsigned i;
    3416                 :      30047 :       function *fn = DECL_STRUCT_FUNCTION (cnode->decl);
    3417                 :      30047 :       if (!gimple_in_ssa_p (fn))
    3418                 :       1118 :         continue;
    3419                 :            : 
    3420                 :    1212860 :       FOR_EACH_SSA_NAME (i, name, fn)
    3421                 :    2196260 :         if (POINTER_TYPE_P (TREE_TYPE (name))
    3422                 :    1186920 :             && SSA_NAME_PTR_INFO (name))
    3423                 :     167056 :           fixup_pt_set (&SSA_NAME_PTR_INFO (name)->pt);
    3424                 :      28929 :       fixup_pt_set (&fn->gimple_df->escaped);
    3425                 :            : 
    3426                 :            :        /* The above gets us to 99% I guess, at least catching the
    3427                 :            :           address compares.  Below also gets us aliasing correct
    3428                 :            :           but as said we're giving leeway to the situation with
    3429                 :            :           readonly vars anyway, so ... */
    3430                 :      28929 :        basic_block bb;
    3431                 :     347052 :        FOR_EACH_BB_FN (bb, fn)
    3432                 :    1914550 :         for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    3433                 :    1278300 :              gsi_next (&gsi))
    3434                 :            :           {
    3435                 :    1473820 :             gcall *call = dyn_cast<gcall *> (gsi_stmt (gsi));
    3436                 :     195517 :             if (call)
    3437                 :            :               {
    3438                 :     195517 :                 fixup_pt_set (gimple_call_use_set (call));
    3439                 :     195517 :                 fixup_pt_set (gimple_call_clobber_set (call));
    3440                 :            :               }
    3441                 :            :           }
    3442                 :            :     }
    3443                 :            : 
    3444                 :            :   unsigned i;
    3445                 :            :   symtab_pair *item;
    3446                 :       6872 :   FOR_EACH_VEC_ELT (m_merged_variables, i, item)
    3447                 :       5647 :     set_alias_uids (item->first, DECL_UID (item->first->decl));
    3448                 :       1225 : }
    3449                 :            : 
    3450                 :            : /* Dump function prints all class members to a FILE with an INDENT.  */
    3451                 :            : 
    3452                 :            : void
    3453                 :        328 : congruence_class::dump (FILE *file, unsigned int indent) const
    3454                 :            : {
    3455                 :        656 :   FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
    3456                 :        328 :                   id, members[0]->get_hash (), members.length ());
    3457                 :            : 
    3458                 :        328 :   FPUTS_SPACES (file, indent + 2, "");
    3459                 :       1508 :   for (unsigned i = 0; i < members.length (); i++)
    3460                 :        426 :     fprintf (file, "%s ", members[i]->node->dump_asm_name ());
    3461                 :            : 
    3462                 :        328 :   fprintf (file, "\n");
    3463                 :        328 : }
    3464                 :            : 
    3465                 :            : /* Returns true if there's a member that is used from another group.  */
    3466                 :            : 
    3467                 :            : bool
    3468                 :    3141360 : congruence_class::is_class_used (void)
    3469                 :            : {
    3470                 :    7421530 :   for (unsigned int i = 0; i < members.length (); i++)
    3471                 :    3180730 :     if (members[i]->referenced_by_count)
    3472                 :            :       return true;
    3473                 :            : 
    3474                 :            :   return false;
    3475                 :            : }
    3476                 :            : 
    3477                 :            : /* Generate pass summary for IPA ICF pass.  */
    3478                 :            : 
    3479                 :            : static void
    3480                 :      91945 : ipa_icf_generate_summary (void)
    3481                 :            : {
    3482                 :      91945 :   if (!optimizer)
    3483                 :      91945 :     optimizer = new sem_item_optimizer ();
    3484                 :            : 
    3485                 :      91945 :   optimizer->register_hooks ();
    3486                 :      91945 :   optimizer->parse_funcs_and_vars ();
    3487                 :      91945 : }
    3488                 :            : 
    3489                 :            : /* Write pass summary for IPA ICF pass.  */
    3490                 :            : 
    3491                 :            : static void
    3492                 :      14680 : ipa_icf_write_summary (void)
    3493                 :            : {
    3494                 :      14680 :   gcc_assert (optimizer);
    3495                 :            : 
    3496                 :      14680 :   optimizer->write_summary ();
    3497                 :      14680 : }
    3498                 :            : 
    3499                 :            : /* Read pass summary for IPA ICF pass.  */
    3500                 :            : 
    3501                 :            : static void
    3502                 :       8381 : ipa_icf_read_summary (void)
    3503                 :            : {
    3504                 :       8381 :   if (!optimizer)
    3505                 :       8381 :     optimizer = new sem_item_optimizer ();
    3506                 :            : 
    3507                 :       8381 :   optimizer->read_summary ();
    3508                 :       8381 :   optimizer->register_hooks ();
    3509                 :       8381 : }
    3510                 :            : 
    3511                 :            : /* Semantic equality execution function.  */
    3512                 :            : 
    3513                 :            : static unsigned int
    3514                 :      93278 : ipa_icf_driver (void)
    3515                 :            : {
    3516                 :      93278 :   gcc_assert (optimizer);
    3517                 :            : 
    3518                 :      93278 :   bool merged_p = optimizer->execute ();
    3519                 :            : 
    3520                 :      93278 :   delete optimizer;
    3521                 :      93278 :   optimizer = NULL;
    3522                 :            : 
    3523                 :      93278 :   return merged_p ? TODO_remove_functions : 0;
    3524                 :            : }
    3525                 :            : 
    3526                 :            : const pass_data pass_data_ipa_icf =
    3527                 :            : {
    3528                 :            :   IPA_PASS,                 /* type */
    3529                 :            :   "icf",                  /* name */
    3530                 :            :   OPTGROUP_IPA,             /* optinfo_flags */
    3531                 :            :   TV_IPA_ICF,               /* tv_id */
    3532                 :            :   0,                        /* properties_required */
    3533                 :            :   0,                        /* properties_provided */
    3534                 :            :   0,                        /* properties_destroyed */
    3535                 :            :   0,                        /* todo_flags_start */
    3536                 :            :   0,                        /* todo_flags_finish */
    3537                 :            : };
    3538                 :            : 
    3539                 :            : class pass_ipa_icf : public ipa_opt_pass_d
    3540                 :            : {
    3541                 :            : public:
    3542                 :     201440 :   pass_ipa_icf (gcc::context *ctxt)
    3543                 :            :     : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
    3544                 :            :                       ipa_icf_generate_summary, /* generate_summary */
    3545                 :            :                       ipa_icf_write_summary, /* write_summary */
    3546                 :            :                       ipa_icf_read_summary, /* read_summary */
    3547                 :            :                       NULL, /*
    3548                 :            :                       write_optimization_summary */
    3549                 :            :                       NULL, /*
    3550                 :            :                       read_optimization_summary */
    3551                 :            :                       NULL, /* stmt_fixup */
    3552                 :            :                       0, /* function_transform_todo_flags_start */
    3553                 :            :                       NULL, /* function_transform */
    3554                 :     402880 :                       NULL) /* variable_transform */
    3555                 :            :   {}
    3556                 :            : 
    3557                 :            :   /* opt_pass methods: */
    3558                 :     431507 :   virtual bool gate (function *)
    3559                 :            :   {
    3560                 :     431507 :     return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
    3561                 :            :   }
    3562                 :            : 
    3563                 :      93278 :   virtual unsigned int execute (function *)
    3564                 :            :   {
    3565                 :      93278 :     return ipa_icf_driver();
    3566                 :            :   }
    3567                 :            : }; // class pass_ipa_icf
    3568                 :            : 
    3569                 :            : } // ipa_icf namespace
    3570                 :            : 
    3571                 :            : ipa_opt_pass_d *
    3572                 :     201440 : make_pass_ipa_icf (gcc::context *ctxt)
    3573                 :            : {
    3574                 :     201440 :   return new ipa_icf::pass_ipa_icf (ctxt);
    3575                 :            : }

Generated by: LCOV version 1.0

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