1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2024 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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
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
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/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
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
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
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.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
67 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
69 #include "tree-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
79 #include "ipa-fnsummary.h"
82 #include "print-tree.h"
83 #include "ipa-utils.h"
84 #include "tree-ssa-alias-compare.h"
85 #include "ipa-icf-gimple.h"
86 #include "fibonacci_heap.h"
88 #include "stor-layout.h"
90 #include "tree-vector-builder.h"
91 #include "symtab-thunks.h"
95 using namespace ipa_icf_gimple
;
99 /* Initialization and computation of symtab node hash, there data
100 are propagated later on. */
102 static sem_item_optimizer
*optimizer
= NULL
;
106 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
108 m_references
.create (0);
109 m_interposables
.create (0);
113 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
116 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
118 if (ref
->address_matters_p ())
119 m_references
.safe_push (ref
->referred
);
121 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
123 if (ref
->address_matters_p ())
124 m_references
.safe_push (ref
->referred
);
126 m_interposables
.safe_push (ref
->referred
);
130 if (is_a
<cgraph_node
*> (node
))
132 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
134 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
135 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
136 m_interposables
.safe_push (e
->callee
);
140 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
142 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
143 : item (_item
), index (_index
)
147 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
148 : type (_type
), referenced_by_count (0), m_hash (-1), m_hash_set (false)
153 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
154 bitmap_obstack
*stack
)
155 : type (_type
), node (_node
), referenced_by_count (0), m_hash (-1),
162 /* Add reference to a semantic TARGET. */
165 sem_item::add_reference (ref_map
*refs
,
168 unsigned index
= reference_count
++;
171 sem_usage_pair
*pair
= new sem_usage_pair (target
, index
);
172 vec
<sem_item
*> &v
= refs
->get_or_insert (pair
, &existed
);
177 bitmap_set_bit (target
->usage_index_bitmap
, index
);
178 refs_set
.add (target
->node
);
179 ++target
->referenced_by_count
;
182 /* Initialize internal data structures. Bitmap STACK is used for
183 bitmap memory allocation process. */
186 sem_item::setup (bitmap_obstack
*stack
)
188 gcc_checking_assert (node
);
191 tree_refs
.create (0);
192 usage_index_bitmap
= BITMAP_ALLOC (stack
);
195 sem_item::~sem_item ()
197 tree_refs
.release ();
199 BITMAP_FREE (usage_index_bitmap
);
202 /* Dump function for debugging purpose. */
205 sem_item::dump (void)
209 fprintf (dump_file
, "[%s] %s (tree:%p)\n", type
== FUNC
? "func" : "var",
210 node
->dump_name (), (void *) node
->decl
);
211 fprintf (dump_file
, " hash: %u\n", get_hash ());
215 /* Return true if target supports alias symbols. */
218 sem_item::target_supports_symbol_aliases_p (void)
220 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
223 gcc_checking_assert (TARGET_SUPPORTS_ALIASES
);
228 void sem_item::set_hash (hashval_t hash
)
234 hash_map
<const_tree
, hashval_t
> sem_item::m_type_hash_cache
;
236 /* Semantic function constructor that uses STACK as bitmap memory stack. */
238 sem_function::sem_function (bitmap_obstack
*stack
)
239 : sem_item (FUNC
, stack
), memory_access_types (), m_alias_sets_hash (0),
240 m_checker (NULL
), m_compared_func (NULL
)
243 bb_sorted
.create (0);
246 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
247 : sem_item (FUNC
, node
, stack
), memory_access_types (),
248 m_alias_sets_hash (0), m_checker (NULL
), m_compared_func (NULL
)
251 bb_sorted
.create (0);
254 sem_function::~sem_function ()
256 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
257 delete (bb_sorted
[i
]);
260 bb_sorted
.release ();
263 /* Calculates hash value based on a BASIC_BLOCK. */
266 sem_function::get_bb_hash (const sem_bb
*basic_block
)
268 inchash::hash hstate
;
270 hstate
.add_int (basic_block
->nondbg_stmt_count
);
271 hstate
.add_int (basic_block
->edge_count
);
273 return hstate
.end ();
276 /* References independent hash function. */
279 sem_function::get_hash (void)
283 inchash::hash hstate
;
284 hstate
.add_int (177454); /* Random number for function type. */
286 hstate
.add_int (arg_count
);
287 hstate
.add_int (cfg_checksum
);
288 hstate
.add_int (gcode_hash
);
290 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
291 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
293 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
294 hstate
.add_int (bb_sizes
[i
]);
296 /* Add common features of declaration itself. */
297 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
299 (cl_target_option_hash
300 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
301 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
303 (cl_optimization_hash
304 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
305 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
306 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
308 set_hash (hstate
.end ());
314 /* Compare properties of symbols N1 and N2 that does not affect semantics of
315 symbol itself but affects semantics of its references from USED_BY (which
316 may be NULL if it is unknown). If comparison is false, symbols
317 can still be merged but any symbols referring them can't.
319 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
321 TODO: We can also split attributes to those that determine codegen of
322 a function body/variable constructor itself and those that are used when
326 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
331 if (is_a
<cgraph_node
*> (n1
))
333 /* Inline properties matters: we do now want to merge uses of inline
334 function to uses of normal function because inline hint would be lost.
335 We however can merge inline function to noinline because the alias
336 will keep its DECL_DECLARED_INLINE flag.
338 Also ignore inline flag when optimizing for size or when function
339 is known to not be inlinable.
341 TODO: the optimize_size checks can also be assumed to be true if
342 unit has no !optimize_size functions. */
344 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
345 || !opt_for_fn (used_by
->decl
, optimize_size
))
346 && !opt_for_fn (n1
->decl
, optimize_size
)
347 && n1
->get_availability () > AVAIL_INTERPOSABLE
348 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
350 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
351 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
352 return return_false_with_msg
353 ("DECL_DISREGARD_INLINE_LIMITS are different");
355 if (DECL_DECLARED_INLINE_P (n1
->decl
)
356 != DECL_DECLARED_INLINE_P (n2
->decl
))
357 return return_false_with_msg ("inline attributes are different");
360 if (DECL_IS_OPERATOR_NEW_P (n1
->decl
)
361 != DECL_IS_OPERATOR_NEW_P (n2
->decl
))
362 return return_false_with_msg ("operator new flags are different");
364 if (DECL_IS_REPLACEABLE_OPERATOR (n1
->decl
)
365 != DECL_IS_REPLACEABLE_OPERATOR (n2
->decl
))
366 return return_false_with_msg ("replaceable operator flags are different");
369 /* Merging two definitions with a reference to equivalent vtables, but
370 belonging to a different type may result in ipa-polymorphic-call analysis
371 giving a wrong answer about the dynamic type of instance. */
372 if (is_a
<varpool_node
*> (n1
))
374 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
375 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
376 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
377 DECL_CONTEXT (n2
->decl
)))
378 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
379 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
380 return return_false_with_msg
381 ("references to virtual tables cannot be merged");
383 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
384 return return_false_with_msg ("alignment mismatch");
386 /* For functions we compare attributes in equals_wpa, because we do
387 not know what attributes may cause codegen differences, but for
388 variables just compare attributes for references - the codegen
389 for constructors is affected only by those attributes that we lower
390 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
391 if (!attribute_list_equal (DECL_ATTRIBUTES (n1
->decl
),
392 DECL_ATTRIBUTES (n2
->decl
)))
393 return return_false_with_msg ("different var decl attributes");
394 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
395 TREE_TYPE (n2
->decl
)) != 1)
396 return return_false_with_msg ("different var type attributes");
399 /* When matching virtual tables, be sure to also match information
400 relevant for polymorphic call analysis. */
401 if (used_by
&& is_a
<varpool_node
*> (used_by
)
402 && DECL_VIRTUAL_P (used_by
->decl
))
404 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
405 return return_false_with_msg ("virtual flag mismatch");
406 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
407 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
408 return return_false_with_msg ("final flag mismatch");
413 /* Hash properties that are compared by compare_referenced_symbol_properties. */
416 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
417 inchash::hash
&hstate
,
420 if (is_a
<cgraph_node
*> (ref
))
422 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
423 && !opt_for_fn (ref
->decl
, optimize_size
)
424 && !DECL_UNINLINABLE (ref
->decl
))
426 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
427 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
429 hstate
.add_flag (DECL_IS_OPERATOR_NEW_P (ref
->decl
));
431 else if (is_a
<varpool_node
*> (ref
))
433 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
435 hstate
.add_int (DECL_ALIGN (ref
->decl
));
440 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
441 point to a same function. Comparison can be skipped if IGNORED_NODES
442 contains these nodes. ADDRESS indicate if address is taken. */
445 sem_item::compare_symbol_references (
446 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
447 symtab_node
*n1
, symtab_node
*n2
, bool address
)
449 enum availability avail1
, avail2
;
454 /* Never match variable and function. */
455 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
458 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
460 if (address
&& n1
->equal_address_to (n2
) == 1)
462 if (!address
&& n1
->semantically_equivalent_p (n2
))
465 n1
= n1
->ultimate_alias_target (&avail1
);
466 n2
= n2
->ultimate_alias_target (&avail2
);
468 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
469 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
472 return return_false_with_msg ("different references");
475 /* If cgraph edges E1 and E2 are indirect calls, verify that
476 ECF flags are the same. */
478 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
480 if (e1
->indirect_info
&& e2
->indirect_info
)
482 int e1_flags
= e1
->indirect_info
->ecf_flags
;
483 int e2_flags
= e2
->indirect_info
->ecf_flags
;
485 if (e1_flags
!= e2_flags
)
486 return return_false_with_msg ("ICF flags are different");
488 else if (e1
->indirect_info
|| e2
->indirect_info
)
494 /* Return true if parameter I may be used. */
497 sem_function::param_used_p (unsigned int i
)
499 if (ipa_node_params_sum
== NULL
)
502 ipa_node_params
*parms_info
= ipa_node_params_sum
->get (get_node ());
504 if (!parms_info
|| vec_safe_length (parms_info
->descriptors
) <= i
)
507 return ipa_is_param_used (parms_info
, i
);
510 /* Perform additional check needed to match types function parameters that are
511 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
512 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
515 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
517 /* Be sure that parameters are TBAA compatible. */
518 if (!func_checker::compatible_types_p (parm1
, parm2
))
519 return return_false_with_msg ("parameter type is not compatible");
521 if (POINTER_TYPE_P (parm1
)
522 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
523 return return_false_with_msg ("argument restrict flag mismatch");
525 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
526 if (POINTER_TYPE_P (parm1
)
527 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
528 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
529 return return_false_with_msg ("pointer wrt reference mismatch");
534 /* Fast equality function based on knowledge known in WPA. */
537 sem_function::equals_wpa (sem_item
*item
,
538 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
540 gcc_assert (item
->type
== FUNC
);
541 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
542 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
544 m_compared_func
= static_cast<sem_function
*> (item
);
546 if (cnode
->thunk
!= cnode2
->thunk
)
547 return return_false_with_msg ("thunk mismatch");
548 if (cnode
->former_thunk_p () != cnode2
->former_thunk_p ())
549 return return_false_with_msg ("former_thunk_p mismatch");
551 if ((cnode
->thunk
|| cnode
->former_thunk_p ())
552 && thunk_info::get (cnode
) != thunk_info::get (cnode2
))
553 return return_false_with_msg ("thunk_info mismatch");
555 /* Compare special function DECL attributes. */
556 if (DECL_FUNCTION_PERSONALITY (decl
)
557 != DECL_FUNCTION_PERSONALITY (item
->decl
))
558 return return_false_with_msg ("function personalities are different");
560 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
561 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
562 return return_false_with_msg ("instrument function entry exit "
563 "attributes are different");
565 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
566 return return_false_with_msg ("no stack limit attributes are different");
568 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
569 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
571 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
572 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
574 /* TODO: pure/const flags mostly matters only for references, except for
575 the fact that codegen takes LOOPING flag as a hint that loops are
576 finite. We may arrange the code to always pick leader that has least
577 specified flags and then this can go into comparing symbol properties. */
578 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
579 return return_false_with_msg ("decl_or_type flags are different");
581 /* Do not match polymorphic constructors of different types. They calls
582 type memory location for ipa-polymorphic-call and we do not want
583 it to get confused by wrong type. */
584 if (DECL_CXX_CONSTRUCTOR_P (decl
)
585 && opt_for_fn (decl
, flag_devirtualize
)
586 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
588 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
589 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
590 else if (!func_checker::compatible_polymorphic_types_p
591 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
592 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
593 return return_false_with_msg ("ctor polymorphic type mismatch");
596 /* Checking function TARGET and OPTIMIZATION flags. */
597 cl_target_option
*tar1
= target_opts_for_fn (decl
);
598 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
600 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
604 fprintf (dump_file
, "target flags difference");
605 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
608 return return_false_with_msg ("Target flags are different");
611 cl_optimization
*opt1
= opts_for_fn (decl
);
612 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
614 if (opt1
!= opt2
&& !cl_optimization_option_eq (opt1
, opt2
))
616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
618 fprintf (dump_file
, "optimization flags difference");
619 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
622 return return_false_with_msg ("optimization flags are different");
625 /* Result type checking. */
626 if (!func_checker::compatible_types_p
627 (TREE_TYPE (TREE_TYPE (decl
)),
628 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
629 return return_false_with_msg ("result types are different");
631 /* Checking types of arguments. */
632 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
633 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
634 for (unsigned i
= 0; list1
&& list2
;
635 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
637 tree parm1
= TREE_VALUE (list1
);
638 tree parm2
= TREE_VALUE (list2
);
640 /* This guard is here for function pointer with attributes (pr59927.c). */
641 if (!parm1
|| !parm2
)
642 return return_false_with_msg ("NULL argument type");
644 /* Verify that types are compatible to ensure that both functions
645 have same calling conventions. */
646 if (!types_compatible_p (parm1
, parm2
))
647 return return_false_with_msg ("parameter types are not compatible");
649 if (!param_used_p (i
))
652 /* Perform additional checks for used parameters. */
653 if (!compatible_parm_types_p (parm1
, parm2
))
658 return return_false_with_msg ("Mismatched number of parameters");
660 if (node
->num_references () != item
->node
->num_references ())
661 return return_false_with_msg ("different number of references");
663 /* Checking function attributes.
664 This is quadratic in number of attributes */
665 if (comp_type_attributes (TREE_TYPE (decl
),
666 TREE_TYPE (item
->decl
)) != 1)
667 return return_false_with_msg ("different type attributes");
668 if (!attribute_list_equal (DECL_ATTRIBUTES (decl
),
669 DECL_ATTRIBUTES (item
->decl
)))
670 return return_false_with_msg ("different decl attributes");
672 /* The type of THIS pointer type memory location for
673 ipa-polymorphic-call-analysis. */
674 if (opt_for_fn (decl
, flag_devirtualize
)
675 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
676 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
678 && compare_polymorphic_p ())
680 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
681 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
682 if (!func_checker::compatible_polymorphic_types_p
683 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
684 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
685 return return_false_with_msg ("THIS pointer ODR type mismatch");
688 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
689 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
691 item
->node
->iterate_reference (i
, ref2
);
693 if (ref
->use
!= ref2
->use
)
694 return return_false_with_msg ("reference use mismatch");
696 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
698 ref
->address_matters_p ()))
702 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
703 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
707 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
710 if (!compare_edge_flags (e1
, e2
))
713 e1
= e1
->next_callee
;
714 e2
= e2
->next_callee
;
718 return return_false_with_msg ("different number of calls");
720 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
721 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
725 if (!compare_edge_flags (e1
, e2
))
728 e1
= e1
->next_callee
;
729 e2
= e2
->next_callee
;
733 return return_false_with_msg ("different number of indirect calls");
738 /* Update hash by address sensitive references. We iterate over all
739 sensitive references (address_matters_p) and we hash ultimate alias
740 target of these nodes, which can improve a semantic item hash.
742 Also hash in referenced symbols properties. This can be done at any time
743 (as the properties should not change), but it is convenient to do it here
744 while we walk the references anyway. */
747 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
748 sem_item
*> &m_symtab_node_map
)
751 inchash::hash
hstate (get_hash ());
753 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
755 hstate
.add_int (ref
->use
);
756 hash_referenced_symbol_properties (ref
->referred
, hstate
,
757 ref
->use
== IPA_REF_ADDR
);
758 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
759 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
762 if (is_a
<cgraph_node
*> (node
))
764 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
767 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
768 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
770 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
774 set_hash (hstate
.end ());
777 /* Update hash by computed local hash values taken from different
779 TODO: stronger SCC based hashing would be desirable here. */
782 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
783 sem_item
*> &m_symtab_node_map
)
786 inchash::hash
state (get_hash ());
788 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
790 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
792 state
.merge_hash ((*result
)->get_hash ());
797 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
800 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
802 state
.merge_hash ((*result
)->get_hash ());
806 global_hash
= state
.end ();
809 /* Returns true if the item equals to ITEM given as argument. */
812 sem_function::equals (sem_item
*item
,
813 hash_map
<symtab_node
*, sem_item
*> &)
815 gcc_assert (item
->type
== FUNC
);
816 bool eq
= equals_private (item
);
818 if (m_checker
!= NULL
)
824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
826 "Equals called for: %s:%s with result: %s\n\n",
828 item
->node
->dump_name (),
829 eq
? "true" : "false");
834 /* Processes function equality comparison. */
837 sem_function::equals_private (sem_item
*item
)
839 if (item
->type
!= FUNC
)
842 basic_block bb1
, bb2
;
844 edge_iterator ei1
, ei2
;
848 m_compared_func
= static_cast<sem_function
*> (item
);
850 gcc_assert (decl
!= item
->decl
);
852 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
853 || edge_count
!= m_compared_func
->edge_count
854 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
855 return return_false ();
857 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
859 opt_for_fn (m_compared_func
->decl
,
860 flag_strict_aliasing
),
862 &m_compared_func
->refs_set
);
863 arg1
= DECL_ARGUMENTS (decl
);
864 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
866 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
868 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
869 return return_false_with_msg ("argument types are not compatible");
870 if (!param_used_p (i
))
872 /* Perform additional checks for used parameters. */
873 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
875 if (!m_checker
->compare_decl (arg1
, arg2
))
876 return return_false ();
879 return return_false_with_msg ("Mismatched number of arguments");
881 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
884 /* Fill-up label dictionary. */
885 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
887 m_checker
->parse_labels (bb_sorted
[i
]);
888 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
891 /* Checking all basic blocks. */
892 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
893 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
894 return return_false ();
896 auto_vec
<int> bb_dict
;
898 /* Basic block edges check. */
899 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
901 bb1
= bb_sorted
[i
]->bb
;
902 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
904 ei2
= ei_start (bb2
->preds
);
906 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
910 if (e1
->flags
!= e2
->flags
)
911 return return_false_with_msg ("flags comparison returns false");
913 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
914 return return_false_with_msg ("edge comparison returns false");
916 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
917 return return_false_with_msg ("BB comparison returns false");
919 if (!m_checker
->compare_edge (e1
, e2
))
920 return return_false_with_msg ("edge comparison returns false");
926 /* Basic block PHI nodes comparison. */
927 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
928 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
929 return return_false_with_msg ("PHI node comparison returns false");
934 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
935 Helper for call_for_symbol_thunks_and_aliases. */
938 set_local (cgraph_node
*node
, void *data
)
940 node
->local
= data
!= NULL
;
944 /* TREE_ADDRESSABLE of NODE to true.
945 Helper for call_for_symbol_thunks_and_aliases. */
948 set_addressable (varpool_node
*node
, void *)
950 TREE_ADDRESSABLE (node
->decl
) = 1;
954 /* Clear DECL_RTL of NODE.
955 Helper for call_for_symbol_thunks_and_aliases. */
958 clear_decl_rtl (symtab_node
*node
, void *)
960 SET_DECL_RTL (node
->decl
, NULL
);
964 /* Redirect all callers of N and its aliases to TO. Remove aliases if
965 possible. Return number of redirections made. */
968 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
972 cgraph_edge
*e
= n
->callers
;
976 /* Redirecting thunks to interposable symbols or symbols in other sections
977 may not be supported by target output code. Play safe for now and
978 punt on redirection. */
979 if (!e
->caller
->thunk
)
981 struct cgraph_edge
*nexte
= e
->next_caller
;
982 e
->redirect_callee (to
);
989 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
991 bool removed
= false;
992 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
994 if ((DECL_COMDAT_GROUP (n
->decl
)
995 && (DECL_COMDAT_GROUP (n
->decl
)
996 == DECL_COMDAT_GROUP (n_alias
->decl
)))
997 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
998 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1000 nredirected
+= redirect_all_callers (n_alias
, to
);
1001 if (n_alias
->can_remove_if_no_direct_calls_p ()
1002 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1004 && !n_alias
->has_aliases_p ())
1013 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1017 sem_function::merge (sem_item
*alias_item
)
1019 gcc_assert (alias_item
->type
== FUNC
);
1021 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1023 cgraph_node
*original
= get_node ();
1024 cgraph_node
*local_original
= NULL
;
1025 cgraph_node
*alias
= alias_func
->get_node ();
1027 bool create_wrapper
= false;
1028 bool create_alias
= false;
1029 bool redirect_callers
= false;
1030 bool remove
= false;
1032 bool original_discardable
= false;
1033 bool original_discarded
= false;
1035 bool original_address_matters
= original
->address_matters_p ();
1036 bool alias_address_matters
= alias
->address_matters_p ();
1038 AUTO_DUMP_SCOPE ("merge",
1039 dump_user_location_t::from_function_decl (decl
));
1041 if (DECL_EXTERNAL (alias
->decl
))
1043 if (dump_enabled_p ())
1044 dump_printf (MSG_MISSED_OPTIMIZATION
,
1045 "Not unifying; alias is external.\n");
1049 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1050 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1052 if (dump_enabled_p ())
1053 dump_printf (MSG_MISSED_OPTIMIZATION
,
1054 "Not unifying; DECL_NO_INLINE_WARNING mismatch.\n");
1058 /* Do not attempt to mix functions from different user sections;
1059 we do not know what user intends with those. */
1060 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1061 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1062 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1064 if (dump_enabled_p ())
1065 dump_printf (MSG_MISSED_OPTIMIZATION
,
1067 "original and alias are in different sections.\n");
1071 if (!original
->in_same_comdat_group_p (alias
)
1072 || original
->comdat_local_p ())
1074 if (dump_enabled_p ())
1075 dump_printf (MSG_MISSED_OPTIMIZATION
,
1076 "Not unifying; alias nor wrapper cannot be created; "
1077 "across comdat group boundary\n");
1081 /* See if original is in a section that can be discarded if the main
1082 symbol is not used. */
1084 if (original
->can_be_discarded_p ())
1085 original_discardable
= true;
1086 /* Also consider case where we have resolution info and we know that
1087 original's definition is not going to be used. In this case we cannot
1088 create alias to original. */
1089 if (node
->resolution
!= LDPR_UNKNOWN
1090 && !decl_binds_to_current_def_p (node
->decl
))
1091 original_discardable
= original_discarded
= true;
1093 /* Creating a symtab alias is the optimal way to merge.
1094 It however cannot be used in the following cases:
1096 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1097 2) if ORIGINAL is in a section that may be discarded by linker or if
1098 it is an external functions where we cannot create an alias
1099 (ORIGINAL_DISCARDABLE)
1100 3) if target do not support symbol aliases.
1101 4) original and alias lie in different comdat groups.
1103 If we cannot produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1104 and/or redirect all callers from ALIAS to ORIGINAL. */
1105 if ((original_address_matters
&& alias_address_matters
)
1106 || (original_discardable
1107 && (!DECL_COMDAT_GROUP (alias
->decl
)
1108 || (DECL_COMDAT_GROUP (alias
->decl
)
1109 != DECL_COMDAT_GROUP (original
->decl
))))
1110 || original_discarded
1111 || !sem_item::target_supports_symbol_aliases_p ()
1112 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1114 /* First see if we can produce wrapper. */
1116 /* Symbol properties that matter for references must be preserved.
1117 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1118 with proper properties. */
1119 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1120 alias
->address_taken
))
1122 if (dump_enabled_p ())
1123 dump_printf (MSG_MISSED_OPTIMIZATION
,
1124 "Wrapper cannot be created because referenced symbol "
1125 "properties mismatch\n");
1127 /* Do not turn function in one comdat group into wrapper to another
1128 comdat group. Other compiler producing the body of the
1129 another comdat group may make opposite decision and with unfortunate
1130 linker choices this may close a loop. */
1131 else if (DECL_COMDAT_GROUP (original
->decl
)
1132 && DECL_COMDAT_GROUP (alias
->decl
)
1133 && (DECL_COMDAT_GROUP (alias
->decl
)
1134 != DECL_COMDAT_GROUP (original
->decl
)))
1136 if (dump_enabled_p ())
1137 dump_printf (MSG_MISSED_OPTIMIZATION
,
1138 "Wrapper cannot be created because of COMDAT\n");
1140 else if (DECL_STATIC_CHAIN (alias
->decl
)
1141 || DECL_STATIC_CHAIN (original
->decl
))
1143 if (dump_enabled_p ())
1144 dump_printf (MSG_MISSED_OPTIMIZATION
,
1145 "Cannot create wrapper of nested function.\n");
1147 /* TODO: We can also deal with variadic functions never calling
1149 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1151 if (dump_enabled_p ())
1152 dump_printf (MSG_MISSED_OPTIMIZATION
,
1153 "cannot create wrapper of stdarg function.\n");
1155 else if (ipa_fn_summaries
1156 && ipa_size_summaries
->get (alias
) != NULL
1157 && ipa_size_summaries
->get (alias
)->self_size
<= 2)
1159 if (dump_enabled_p ())
1160 dump_printf (MSG_MISSED_OPTIMIZATION
, "Wrapper creation is not "
1161 "profitable (function is too small).\n");
1163 /* If user paid attention to mark function noinline, assume it is
1164 somewhat special and do not try to turn it into a wrapper that
1165 cannot be undone by inliner. */
1166 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1168 if (dump_enabled_p ())
1169 dump_printf (MSG_MISSED_OPTIMIZATION
,
1170 "Wrappers are not created for noinline.\n");
1173 create_wrapper
= true;
1175 /* We can redirect local calls in the case both alias and original
1176 are not interposable. */
1178 = alias
->get_availability () > AVAIL_INTERPOSABLE
1179 && original
->get_availability () > AVAIL_INTERPOSABLE
;
1180 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1181 with proper properties. */
1182 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1183 alias
->address_taken
))
1184 redirect_callers
= false;
1186 if (!redirect_callers
&& !create_wrapper
)
1188 if (dump_enabled_p ())
1189 dump_printf (MSG_MISSED_OPTIMIZATION
,
1190 "Not unifying; cannot redirect callers nor "
1191 "produce wrapper\n");
1195 /* Work out the symbol the wrapper should call.
1196 If ORIGINAL is interposable, we need to call a local alias.
1197 Also produce local alias (if possible) as an optimization.
1199 Local aliases cannot be created inside comdat groups because that
1200 prevents inlining. */
1201 if (!original_discardable
&& !original
->get_comdat_group ())
1204 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1206 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1207 local_original
= original
;
1209 /* If we cannot use local alias, fallback to the original
1211 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1212 local_original
= original
;
1214 /* If original is COMDAT local, we cannot really redirect calls outside
1215 of its comdat group to it. */
1216 if (original
->comdat_local_p ())
1217 redirect_callers
= false;
1218 if (!local_original
)
1220 if (dump_enabled_p ())
1221 dump_printf (MSG_MISSED_OPTIMIZATION
,
1222 "Not unifying; cannot produce local alias.\n");
1226 if (!redirect_callers
&& !create_wrapper
)
1228 if (dump_enabled_p ())
1229 dump_printf (MSG_MISSED_OPTIMIZATION
,
1231 "cannot redirect callers nor produce a wrapper\n");
1235 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1237 && !alias
->can_remove_if_no_direct_calls_p ())
1239 if (dump_enabled_p ())
1240 dump_printf (MSG_MISSED_OPTIMIZATION
,
1241 "Not unifying; cannot make wrapper and "
1242 "function has other uses than direct calls\n");
1247 create_alias
= true;
1249 if (redirect_callers
)
1251 int nredirected
= redirect_all_callers (alias
, local_original
);
1255 alias
->icf_merged
= true;
1256 local_original
->icf_merged
= true;
1258 if (dump_enabled_p ())
1259 dump_printf (MSG_NOTE
,
1260 "%i local calls have been "
1261 "redirected.\n", nredirected
);
1264 /* If all callers was redirected, do not produce wrapper. */
1265 if (alias
->can_remove_if_no_direct_calls_p ()
1266 && !DECL_VIRTUAL_P (alias
->decl
)
1267 && !alias
->has_aliases_p ())
1269 create_wrapper
= false;
1272 gcc_assert (!create_alias
);
1274 else if (create_alias
)
1276 alias
->icf_merged
= true;
1278 /* Remove the function's body. */
1279 ipa_merge_profiles (original
, alias
);
1280 symtab
->call_cgraph_removal_hooks (alias
);
1281 alias
->release_body (true);
1283 /* Notice global symbol possibly produced RTL. */
1284 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1287 /* Create the alias. */
1288 cgraph_node::create_alias (alias_func
->decl
, decl
);
1289 alias
->resolve_alias (original
);
1291 original
->call_for_symbol_thunks_and_aliases
1292 (set_local
, (void *)(size_t) original
->local_p (), true);
1294 if (dump_enabled_p ())
1295 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1296 "Unified; Function alias has been created.\n");
1300 gcc_assert (!create_alias
);
1301 alias
->icf_merged
= true;
1302 symtab
->call_cgraph_removal_hooks (alias
);
1303 local_original
->icf_merged
= true;
1305 /* FIXME update local_original counts. */
1306 ipa_merge_profiles (original
, alias
, true);
1307 alias
->create_wrapper (local_original
);
1308 symtab
->call_cgraph_insertion_hooks (alias
);
1310 if (dump_enabled_p ())
1311 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1312 "Unified; Wrapper has been created.\n");
1315 /* It's possible that redirection can hit thunks that block
1316 redirection opportunities. */
1317 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1318 original
->icf_merged
= true;
1320 /* We use merged flag to track cases where COMDAT function is known to be
1321 compatible its callers. If we merged in non-COMDAT, we need to give up
1322 on this optimization. */
1323 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1325 if (dump_enabled_p ())
1326 dump_printf (MSG_NOTE
, "Dropping merged_comdat flag.\n");
1328 local_original
->merged_comdat
= false;
1329 original
->merged_comdat
= false;
1334 ipa_merge_profiles (original
, alias
);
1335 alias
->release_body ();
1337 alias
->body_removed
= true;
1338 alias
->icf_merged
= true;
1339 if (dump_enabled_p ())
1340 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1341 "Unified; Function body was removed.\n");
1347 /* Semantic item initialization function. */
1350 sem_function::init (ipa_icf_gimple::func_checker
*checker
)
1352 m_checker
= checker
;
1354 get_node ()->get_untransformed_body ();
1356 tree fndecl
= node
->decl
;
1357 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1360 gcc_assert (SSANAMES (func
));
1362 ssa_names_size
= SSANAMES (func
)->length ();
1366 region_tree
= func
->eh
->region_tree
;
1368 /* iterating all function arguments. */
1369 arg_count
= count_formal_params (fndecl
);
1371 edge_count
= n_edges_for_fn (func
);
1372 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1375 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1377 inchash::hash hstate
;
1380 FOR_EACH_BB_FN (bb
, func
)
1382 unsigned nondbg_stmt_count
= 0;
1385 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1387 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1390 /* TODO: We should be able to match PHIs with different order of
1391 parameters. This needs to be also updated in
1392 sem_function::compare_phi_node. */
1394 for (si
= gsi_start_nonvirtual_phis (bb
); !gsi_end_p (si
);
1395 gsi_next_nonvirtual_phi (&si
))
1397 hstate
.add_int (GIMPLE_PHI
);
1398 gphi
*phi
= si
.phi ();
1399 m_checker
->hash_operand (gimple_phi_result (phi
), hstate
, 0,
1400 func_checker::OP_NORMAL
);
1401 hstate
.add_int (gimple_phi_num_args (phi
));
1402 for (unsigned int i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1403 m_checker
->hash_operand (gimple_phi_arg_def (phi
, i
),
1404 hstate
, 0, func_checker::OP_NORMAL
);
1407 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1410 gimple
*stmt
= gsi_stmt (gsi
);
1412 if (gimple_code (stmt
) != GIMPLE_DEBUG
1413 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1415 hash_stmt (stmt
, hstate
);
1416 nondbg_stmt_count
++;
1420 hstate
.commit_flag ();
1421 gcode_hash
= hstate
.end ();
1422 bb_sizes
.safe_push (nondbg_stmt_count
);
1424 /* Inserting basic block to hash table. */
1425 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1426 EDGE_COUNT (bb
->preds
)
1427 + EDGE_COUNT (bb
->succs
));
1429 bb_sorted
.safe_push (semantic_bb
);
1435 gcode_hash
= thunk_info::get (cnode
)->hash ();
1441 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1444 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1446 enum gimple_code code
= gimple_code (stmt
);
1448 hstate
.add_int (code
);
1453 m_checker
->hash_operand (gimple_switch_index (as_a
<gswitch
*> (stmt
)),
1454 hstate
, 0, func_checker::OP_NORMAL
);
1457 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1465 func_checker::operand_access_type_map
map (5);
1466 func_checker::classify_operands (stmt
, &map
);
1468 /* All these statements are equivalent if their operands are. */
1469 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1471 func_checker::operand_access_type
1472 access_type
= func_checker::get_operand_access_type
1473 (&map
, gimple_op (stmt
, i
));
1474 m_checker
->hash_operand (gimple_op (stmt
, i
), hstate
, 0,
1476 /* For memory accesses when hasing for LTO stremaing record
1477 base and ref alias ptr types so we can compare them at WPA
1478 time without having to read actual function body. */
1479 if (access_type
== func_checker::OP_MEMORY
1480 && lto_streaming_expected_p ()
1481 && flag_strict_aliasing
)
1485 ao_ref_init (&ref
, gimple_op (stmt
, i
));
1486 tree t
= ao_ref_alias_ptr_type (&ref
);
1487 if (!variably_modified_type_p (t
, NULL_TREE
))
1488 memory_access_types
.safe_push (t
);
1489 t
= ao_ref_base_alias_ptr_type (&ref
);
1490 if (!variably_modified_type_p (t
, NULL_TREE
))
1491 memory_access_types
.safe_push (t
);
1494 /* Consider nocf_check attribute in hash as it affects code
1496 if (code
== GIMPLE_CALL
1497 && flag_cf_protection
& CF_BRANCH
)
1498 hstate
.add_flag (gimple_call_nocf_check_p (as_a
<gcall
*> (stmt
)));
1507 /* Return true if polymorphic comparison must be processed. */
1510 sem_function::compare_polymorphic_p (void)
1512 struct cgraph_edge
*e
;
1514 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1516 if (get_node ()->indirect_calls
!= NULL
)
1518 /* TODO: We can do simple propagation determining what calls may lead to
1519 a polymorphic call. */
1520 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1521 if (e
->callee
->definition
1522 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1527 /* For a given call graph NODE, the function constructs new
1528 semantic function item. */
1531 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
,
1532 func_checker
*checker
)
1534 tree fndecl
= node
->decl
;
1535 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1537 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
))
1540 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1543 if (lookup_attribute_by_prefix ("oacc ",
1544 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1548 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1549 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1552 sem_function
*f
= new sem_function (node
, stack
);
1558 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1559 return true if phi nodes are semantically equivalent in these blocks . */
1562 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1564 gphi_iterator si1
, si2
;
1566 unsigned size1
, size2
, i
;
1570 gcc_assert (bb1
!= NULL
);
1571 gcc_assert (bb2
!= NULL
);
1573 si2
= gsi_start_nonvirtual_phis (bb2
);
1574 for (si1
= gsi_start_nonvirtual_phis (bb1
); !gsi_end_p (si1
);
1575 gsi_next_nonvirtual_phi (&si1
))
1577 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1580 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1581 return return_false();
1586 tree phi_result1
= gimple_phi_result (phi1
);
1587 tree phi_result2
= gimple_phi_result (phi2
);
1589 if (!m_checker
->compare_operand (phi_result1
, phi_result2
,
1590 func_checker::OP_NORMAL
))
1591 return return_false_with_msg ("PHI results are different");
1593 size1
= gimple_phi_num_args (phi1
);
1594 size2
= gimple_phi_num_args (phi2
);
1597 return return_false ();
1599 /* TODO: We should be able to match PHIs with different order of
1600 parameters. This needs to be also updated in sem_function::init. */
1601 for (i
= 0; i
< size1
; ++i
)
1603 t1
= gimple_phi_arg (phi1
, i
)->def
;
1604 t2
= gimple_phi_arg (phi2
, i
)->def
;
1606 if (!m_checker
->compare_operand (t1
, t2
, func_checker::OP_NORMAL
))
1607 return return_false ();
1609 e1
= gimple_phi_arg_edge (phi1
, i
);
1610 e2
= gimple_phi_arg_edge (phi2
, i
);
1612 if (!m_checker
->compare_edge (e1
, e2
))
1613 return return_false ();
1616 gsi_next_nonvirtual_phi (&si2
);
1622 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1623 corresponds to TARGET. */
1626 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1631 if (bb_dict
->length () <= (unsigned)source
)
1632 bb_dict
->safe_grow_cleared (source
+ 1, true);
1634 if ((*bb_dict
)[source
] == 0)
1636 (*bb_dict
)[source
] = target
;
1640 return (*bb_dict
)[source
] == target
;
1643 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1647 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1648 : sem_item (VAR
, node
, stack
)
1650 gcc_checking_assert (node
);
1651 gcc_checking_assert (get_node ());
1654 /* Fast equality function based on knowledge known in WPA. */
1657 sem_variable::equals_wpa (sem_item
*item
,
1658 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1660 gcc_assert (item
->type
== VAR
);
1662 if (node
->num_references () != item
->node
->num_references ())
1663 return return_false_with_msg ("different number of references");
1665 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1666 return return_false_with_msg ("TLS model");
1668 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1669 alignment out of all aliases. */
1671 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1672 return return_false_with_msg ("Virtual flag mismatch");
1674 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1675 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1676 || !operand_equal_p (DECL_SIZE (decl
),
1677 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1678 return return_false_with_msg ("size mismatch");
1680 /* Do not attempt to mix data from different user sections;
1681 we do not know what user intends with those. */
1682 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1683 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1684 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1685 return return_false_with_msg ("user section mismatch");
1687 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1688 return return_false_with_msg ("text section");
1690 if (TYPE_ADDR_SPACE (TREE_TYPE (decl
))
1691 != TYPE_ADDR_SPACE (TREE_TYPE (item
->decl
)))
1692 return return_false_with_msg ("address-space");
1694 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1695 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1697 item
->node
->iterate_reference (i
, ref2
);
1699 if (ref
->use
!= ref2
->use
)
1700 return return_false_with_msg ("reference use mismatch");
1702 if (!compare_symbol_references (ignored_nodes
,
1703 ref
->referred
, ref2
->referred
,
1704 ref
->address_matters_p ()))
1711 /* Returns true if the item equals to ITEM given as argument. */
1714 sem_variable::equals (sem_item
*item
,
1715 hash_map
<symtab_node
*, sem_item
*> &)
1717 gcc_assert (item
->type
== VAR
);
1720 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1721 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1722 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1723 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1725 /* As seen in PR ipa/65303 we have to compare variables types. */
1726 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1727 TREE_TYPE (item
->decl
)))
1728 return return_false_with_msg ("variables types are different");
1730 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1731 DECL_INITIAL (item
->node
->decl
));
1732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1734 "Equals called for vars: %s:%s with result: %s\n\n",
1735 node
->dump_name (), item
->node
->dump_name (),
1736 ret
? "true" : "false");
1741 /* Compares trees T1 and T2 for semantic equality. */
1744 sem_variable::equals (tree t1
, tree t2
)
1747 return return_with_debug (t1
== t2
);
1750 tree_code tc1
= TREE_CODE (t1
);
1751 tree_code tc2
= TREE_CODE (t2
);
1754 return return_false_with_msg ("TREE_CODE mismatch");
1760 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1761 unsigned HOST_WIDE_INT idx
;
1763 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1764 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1765 return return_false_with_msg ("constructor type mismatch");
1767 if (typecode
== ARRAY_TYPE
)
1769 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1770 /* For arrays, check that the sizes all match. */
1771 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1773 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1774 return return_false_with_msg ("constructor array size mismatch");
1776 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1778 return return_false_with_msg ("constructor type incompatible");
1780 v1
= CONSTRUCTOR_ELTS (t1
);
1781 v2
= CONSTRUCTOR_ELTS (t2
);
1782 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1783 return return_false_with_msg ("constructor number of elts mismatch");
1785 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1787 constructor_elt
*c1
= &(*v1
)[idx
];
1788 constructor_elt
*c2
= &(*v2
)[idx
];
1790 /* Check that each value is the same... */
1791 if (!sem_variable::equals (c1
->value
, c2
->value
))
1793 /* ... and that they apply to the same fields! */
1794 if (!sem_variable::equals (c1
->index
, c2
->index
))
1801 tree x1
= TREE_OPERAND (t1
, 0);
1802 tree x2
= TREE_OPERAND (t2
, 0);
1803 tree y1
= TREE_OPERAND (t1
, 1);
1804 tree y2
= TREE_OPERAND (t2
, 1);
1806 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1807 return return_false ();
1809 /* Type of the offset on MEM_REF does not matter. */
1810 return return_with_debug (sem_variable::equals (x1
, x2
)
1811 && known_eq (wi::to_poly_offset (y1
),
1812 wi::to_poly_offset (y2
)));
1817 tree op1
= TREE_OPERAND (t1
, 0);
1818 tree op2
= TREE_OPERAND (t2
, 0);
1819 return sem_variable::equals (op1
, op2
);
1821 /* References to other vars/decls are compared using ipa-ref. */
1824 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1826 return return_false_with_msg ("Declaration mismatch");
1828 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1829 need to process its VAR/FUNCTION references without relying on ipa-ref
1833 return return_false_with_msg ("Declaration mismatch");
1835 /* Integer constants are the same only if the same width of type. */
1836 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1837 return return_false_with_msg ("INTEGER_CST precision mismatch");
1838 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1839 return return_false_with_msg ("INTEGER_CST mode mismatch");
1840 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1842 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1843 return return_false_with_msg ("STRING_CST mode mismatch");
1844 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1845 return return_false_with_msg ("STRING_CST length mismatch");
1846 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1847 TREE_STRING_LENGTH (t1
)))
1848 return return_false_with_msg ("STRING_CST mismatch");
1851 /* Fixed constants are the same only if the same width of type. */
1852 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1853 return return_false_with_msg ("FIXED_CST precision mismatch");
1855 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1856 TREE_FIXED_CST (t2
)));
1858 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1859 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1861 /* Real constants are the same only if the same width of type. */
1862 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1863 return return_false_with_msg ("REAL_CST precision mismatch");
1864 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
1865 &TREE_REAL_CST (t2
)));
1868 if (maybe_ne (VECTOR_CST_NELTS (t1
), VECTOR_CST_NELTS (t2
)))
1869 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1872 = tree_vector_builder::binary_encoded_nelts (t1
, t2
);
1873 for (unsigned int i
= 0; i
< count
; ++i
)
1874 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1
, i
),
1875 VECTOR_CST_ENCODED_ELT (t2
, i
)))
1881 case ARRAY_RANGE_REF
:
1883 tree x1
= TREE_OPERAND (t1
, 0);
1884 tree x2
= TREE_OPERAND (t2
, 0);
1885 tree y1
= TREE_OPERAND (t1
, 1);
1886 tree y2
= TREE_OPERAND (t2
, 1);
1888 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1890 if (!sem_variable::equals (array_ref_low_bound (t1
),
1891 array_ref_low_bound (t2
)))
1893 if (!sem_variable::equals (array_ref_element_size (t1
),
1894 array_ref_element_size (t2
)))
1900 case POINTER_PLUS_EXPR
:
1905 tree x1
= TREE_OPERAND (t1
, 0);
1906 tree x2
= TREE_OPERAND (t2
, 0);
1907 tree y1
= TREE_OPERAND (t1
, 1);
1908 tree y2
= TREE_OPERAND (t2
, 1);
1910 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1914 case VIEW_CONVERT_EXPR
:
1915 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1916 return return_false ();
1917 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1919 return return_false_with_msg ("ERROR_MARK");
1921 return return_false_with_msg ("Unknown TREE code reached");
1925 /* Parser function that visits a varpool NODE. */
1928 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
,
1929 func_checker
*checker
)
1931 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1935 sem_variable
*v
= new sem_variable (node
, stack
);
1941 /* Semantic variable initialization function. */
1944 sem_variable::init (ipa_icf_gimple::func_checker
*checker
)
1946 decl
= get_node ()->decl
;
1948 /* All WPA streamed in symbols should have their hashes computed at compile
1949 time. At this point, the constructor may not be in memory at all.
1950 DECL_INITIAL (decl) would be error_mark_node in that case. */
1953 gcc_assert (!node
->lto_file_data
);
1954 inchash::hash hstate
;
1955 hstate
.add_int (456346417);
1956 checker
->hash_operand (DECL_INITIAL (decl
), hstate
, 0);
1957 set_hash (hstate
.end ());
1961 /* References independent hash function. */
1964 sem_variable::get_hash (void)
1966 gcc_checking_assert (m_hash_set
);
1970 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1974 sem_variable::merge (sem_item
*alias_item
)
1976 gcc_assert (alias_item
->type
== VAR
);
1978 AUTO_DUMP_SCOPE ("merge",
1979 dump_user_location_t::from_function_decl (decl
));
1980 if (!sem_item::target_supports_symbol_aliases_p ())
1982 if (dump_enabled_p ())
1983 dump_printf (MSG_MISSED_OPTIMIZATION
, "Not unifying; "
1984 "Symbol aliases are not supported by target\n");
1988 if (DECL_EXTERNAL (alias_item
->decl
))
1990 if (dump_enabled_p ())
1991 dump_printf (MSG_MISSED_OPTIMIZATION
,
1992 "Not unifying; alias is external.\n");
1996 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1998 varpool_node
*original
= get_node ();
1999 varpool_node
*alias
= alias_var
->get_node ();
2000 bool original_discardable
= false;
2002 bool alias_address_matters
= alias
->address_matters_p ();
2004 /* See if original is in a section that can be discarded if the main
2006 Also consider case where we have resolution info and we know that
2007 original's definition is not going to be used. In this case we cannot
2008 create alias to original. */
2009 if (original
->can_be_discarded_p ()
2010 || (node
->resolution
!= LDPR_UNKNOWN
2011 && !decl_binds_to_current_def_p (node
->decl
)))
2012 original_discardable
= true;
2014 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2016 /* Constant pool machinery is not quite ready for aliases.
2017 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2018 For LTO merging does not happen that is an important missing feature.
2019 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2020 flag is dropped and non-local symbol name is assigned. */
2021 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2022 || DECL_IN_CONSTANT_POOL (original
->decl
))
2024 if (dump_enabled_p ())
2025 dump_printf (MSG_MISSED_OPTIMIZATION
,
2026 "Not unifying; constant pool variables.\n");
2030 /* Do not attempt to mix functions from different user sections;
2031 we do not know what user intends with those. */
2032 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2033 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2034 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2036 if (dump_enabled_p ())
2037 dump_printf (MSG_MISSED_OPTIMIZATION
,
2039 "original and alias are in different sections.\n");
2043 /* We cannot merge if address comparison matters. */
2044 if (alias_address_matters
&& flag_merge_constants
< 2)
2046 if (dump_enabled_p ())
2047 dump_printf (MSG_MISSED_OPTIMIZATION
,
2048 "Not unifying; address of original may be compared.\n");
2052 if (DECL_ALIGN (original
->decl
) != DECL_ALIGN (alias
->decl
)
2053 && (sanitize_flags_p (SANITIZE_ADDRESS
, original
->decl
)
2054 || sanitize_flags_p (SANITIZE_ADDRESS
, alias
->decl
)))
2056 if (dump_enabled_p ())
2057 dump_printf (MSG_MISSED_OPTIMIZATION
,
2059 "ASAN requires equal alignments for original and alias\n");
2064 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2066 if (dump_enabled_p ())
2067 dump_printf (MSG_MISSED_OPTIMIZATION
,
2069 "original and alias have incompatible alignments\n");
2074 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2076 if (dump_enabled_p ())
2077 dump_printf (MSG_MISSED_OPTIMIZATION
,
2078 "Not unifying; alias cannot be created; "
2079 "across comdat group boundary\n");
2084 if (original_discardable
)
2086 if (dump_enabled_p ())
2087 dump_printf (MSG_MISSED_OPTIMIZATION
,
2088 "Not unifying; alias cannot be created; "
2089 "target is discardable\n");
2095 gcc_assert (!original
->alias
);
2096 gcc_assert (!alias
->alias
);
2098 alias
->analyzed
= false;
2100 DECL_INITIAL (alias
->decl
) = NULL
;
2101 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2103 alias
->remove_all_references ();
2104 if (TREE_ADDRESSABLE (alias
->decl
))
2105 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2107 varpool_node::create_alias (alias_var
->decl
, decl
);
2108 alias
->resolve_alias (original
);
2110 if (dump_enabled_p ())
2111 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
2112 "Unified; Variable alias has been created.\n");
2118 /* Dump symbol to FILE. */
2121 sem_variable::dump_to_file (FILE *file
)
2125 print_node (file
, "", decl
, 0);
2126 fprintf (file
, "\n\n");
2129 unsigned int sem_item_optimizer::class_id
= 0;
2131 sem_item_optimizer::sem_item_optimizer ()
2132 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2133 m_varpool_node_hooks (NULL
), m_merged_variables (), m_references ()
2136 bitmap_obstack_initialize (&m_bmstack
);
2139 sem_item_optimizer::~sem_item_optimizer ()
2141 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2145 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2146 it
!= m_classes
.end (); ++it
)
2148 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2149 delete (*it
)->classes
[i
];
2151 (*it
)->classes
.release ();
2157 bitmap_obstack_release (&m_bmstack
);
2158 m_merged_variables
.release ();
2161 /* Write IPA ICF summary for symbols. */
2164 sem_item_optimizer::write_summary (void)
2166 unsigned int count
= 0;
2168 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2169 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2172 /* Calculate number of symbols to be serialized. */
2173 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2175 lsei_next_in_partition (&lsei
))
2177 symtab_node
*node
= lsei_node (lsei
);
2179 if (m_symtab_node_map
.get (node
))
2183 streamer_write_uhwi (ob
, count
);
2185 /* Process all of the symbols. */
2186 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2188 lsei_next_in_partition (&lsei
))
2190 symtab_node
*node
= lsei_node (lsei
);
2192 sem_item
**item
= m_symtab_node_map
.get (node
);
2196 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2197 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2199 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2201 if ((*item
)->type
== FUNC
)
2203 sem_function
*fn
= static_cast<sem_function
*> (*item
);
2204 streamer_write_uhwi (ob
, fn
->memory_access_types
.length ());
2205 for (unsigned i
= 0; i
< fn
->memory_access_types
.length (); i
++)
2206 stream_write_tree (ob
, fn
->memory_access_types
[i
], true);
2211 streamer_write_char_stream (ob
->main_stream
, 0);
2212 produce_asm (ob
, NULL
);
2213 destroy_output_block (ob
);
2216 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2217 contains LEN bytes. */
2220 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2221 const char *data
, size_t len
)
2223 const lto_function_header
*header
2224 = (const lto_function_header
*) data
;
2225 const int cfg_offset
= sizeof (lto_function_header
);
2226 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2227 const int string_offset
= main_offset
+ header
->main_size
;
2232 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2233 header
->main_size
, file_data
);
2236 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2237 header
->string_size
, vNULL
);
2239 count
= streamer_read_uhwi (&ib_main
);
2241 for (i
= 0; i
< count
; i
++)
2245 lto_symtab_encoder_t encoder
;
2247 index
= streamer_read_uhwi (&ib_main
);
2248 encoder
= file_data
->symtab_node_encoder
;
2249 node
= lto_symtab_encoder_deref (encoder
, index
);
2251 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2252 gcc_assert (node
->definition
);
2254 if (is_a
<cgraph_node
*> (node
))
2256 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2258 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2259 unsigned count
= streamer_read_uhwi (&ib_main
);
2260 inchash::hash
hstate (0);
2261 if (flag_incremental_link
== INCREMENTAL_LINK_LTO
)
2262 fn
->memory_access_types
.reserve_exact (count
);
2263 for (unsigned i
= 0; i
< count
; i
++)
2265 tree type
= stream_read_tree (&ib_main
, data_in
);
2266 hstate
.add_int (get_deref_alias_set (type
));
2267 if (flag_incremental_link
== INCREMENTAL_LINK_LTO
)
2268 fn
->memory_access_types
.quick_push (type
);
2270 fn
->m_alias_sets_hash
= hstate
.end ();
2271 fn
->set_hash (hash
);
2272 m_items
.safe_push (fn
);
2276 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2278 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2279 var
->set_hash (hash
);
2280 m_items
.safe_push (var
);
2284 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2286 lto_data_in_delete (data_in
);
2289 /* Read IPA ICF summary for symbols. */
2292 sem_item_optimizer::read_summary (void)
2294 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2295 lto_file_decl_data
*file_data
;
2298 while ((file_data
= file_data_vec
[j
++]))
2302 = lto_get_summary_section_data (file_data
, LTO_section_ipa_icf
, &len
);
2304 read_section (file_data
, data
, len
);
2308 /* Register callgraph and varpool hooks. */
2311 sem_item_optimizer::register_hooks (void)
2313 if (!m_cgraph_node_hooks
)
2314 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2315 (&sem_item_optimizer::cgraph_removal_hook
, this);
2317 if (!m_varpool_node_hooks
)
2318 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2319 (&sem_item_optimizer::varpool_removal_hook
, this);
2322 /* Unregister callgraph and varpool hooks. */
2325 sem_item_optimizer::unregister_hooks (void)
2327 if (m_cgraph_node_hooks
)
2328 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2330 if (m_varpool_node_hooks
)
2331 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2334 /* Adds a CLS to hashtable associated by hash value. */
2337 sem_item_optimizer::add_class (congruence_class
*cls
)
2339 gcc_assert (cls
->members
.length ());
2341 congruence_class_group
*group
2342 = get_group_by_hash (cls
->members
[0]->get_hash (),
2343 cls
->members
[0]->type
);
2344 group
->classes
.safe_push (cls
);
2347 /* Gets a congruence class group based on given HASH value and TYPE. */
2349 congruence_class_group
*
2350 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2352 congruence_class_group
*item
= XNEW (congruence_class_group
);
2356 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2362 item
->classes
.create (1);
2369 /* Callgraph removal hook called for a NODE with a custom DATA. */
2372 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2374 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2375 optimizer
->remove_symtab_node (node
);
2378 /* Varpool removal hook called for a NODE with a custom DATA. */
2381 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2383 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2384 optimizer
->remove_symtab_node (node
);
2387 /* Remove symtab NODE triggered by symtab removal hooks. */
2390 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2392 gcc_assert (m_classes
.is_empty ());
2394 m_removed_items_set
.add (node
);
2398 sem_item_optimizer::remove_item (sem_item
*item
)
2400 if (m_symtab_node_map
.get (item
->node
))
2401 m_symtab_node_map
.remove (item
->node
);
2405 /* Removes all callgraph and varpool nodes that are marked by symtab
2409 sem_item_optimizer::filter_removed_items (void)
2411 auto_vec
<sem_item
*> filtered
;
2413 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2415 sem_item
*item
= m_items
[i
];
2417 if (m_removed_items_set
.contains (item
->node
))
2423 if (item
->type
== FUNC
)
2425 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2427 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2430 filtered
.safe_push (item
);
2434 if (!flag_ipa_icf_variables
)
2438 /* Filter out non-readonly variables. */
2439 tree decl
= item
->decl
;
2440 varpool_node
*vnode
= static_cast <sem_variable
*>(item
)->get_node ();
2441 if (!TREE_READONLY (decl
) || vnode
->body_removed
)
2444 filtered
.safe_push (item
);
2449 /* Clean-up of released semantic items. */
2452 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2453 m_items
.safe_push (filtered
[i
]);
2456 /* Optimizer entry point which returns true in case it processes
2457 a merge operation. True is returned if there's a merge operation
2461 sem_item_optimizer::execute (void)
2463 filter_removed_items ();
2464 unregister_hooks ();
2467 update_hash_by_addr_refs ();
2468 update_hash_by_memory_access_type ();
2469 build_hash_based_classes ();
2472 fprintf (dump_file
, "Dump after hash based groups\n");
2473 dump_cong_classes ();
2475 subdivide_classes_by_equality (true);
2478 fprintf (dump_file
, "Dump after WPA based types groups\n");
2480 dump_cong_classes ();
2482 process_cong_reduction ();
2483 checking_verify_classes ();
2486 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2488 dump_cong_classes ();
2490 unsigned int loaded_symbols
= parse_nonsingleton_classes ();
2491 subdivide_classes_by_equality ();
2494 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2496 dump_cong_classes ();
2498 unsigned int prev_class_count
= m_classes_count
;
2500 process_cong_reduction ();
2501 dump_cong_classes ();
2502 checking_verify_classes ();
2503 bool merged_p
= merge_classes (prev_class_count
, loaded_symbols
);
2505 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2506 symtab
->dump (dump_file
);
2511 /* Function responsible for visiting all potential functions and
2512 read-only variables that can be merged. */
2515 sem_item_optimizer::parse_funcs_and_vars (void)
2519 /* Create dummy func_checker for hashing purpose. */
2520 func_checker checker
;
2522 if (flag_ipa_icf_functions
)
2523 FOR_EACH_DEFINED_FUNCTION (cnode
)
2525 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
, &checker
);
2528 m_items
.safe_push (f
);
2529 m_symtab_node_map
.put (cnode
, f
);
2533 varpool_node
*vnode
;
2535 if (flag_ipa_icf_variables
)
2536 FOR_EACH_DEFINED_VARIABLE (vnode
)
2538 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
, &checker
);
2542 m_items
.safe_push (v
);
2543 m_symtab_node_map
.put (vnode
, v
);
2548 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2551 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2553 item
->index_in_class
= cls
->members
.length ();
2554 cls
->members
.safe_push (item
);
2555 cls
->referenced_by_count
+= item
->referenced_by_count
;
2559 /* For each semantic item, append hash values of references. */
2562 sem_item_optimizer::update_hash_by_addr_refs ()
2564 /* First, append to hash sensitive references and class type if it need to
2565 be matched for ODR. */
2566 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2568 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2569 if (m_items
[i
]->type
== FUNC
)
2571 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2572 && contains_polymorphic_type_p
2573 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2574 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2575 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2576 && static_cast<sem_function
*> (m_items
[i
])
2577 ->compare_polymorphic_p ())))
2580 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2581 inchash::hash
hstate (m_items
[i
]->get_hash ());
2583 /* Hash ODR types by mangled name if it is defined.
2584 If not we know that type is anonymous of free_lang_data
2585 was not run and in that case type main variants are
2587 if (TYPE_NAME (class_type
)
2588 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
))
2589 && !type_in_anonymous_namespace_p
2592 (IDENTIFIER_HASH_VALUE
2593 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2598 || type_in_anonymous_namespace_p (class_type
));
2599 hstate
.add_hwi (TYPE_UID (TYPE_MAIN_VARIANT (class_type
)));
2602 m_items
[i
]->set_hash (hstate
.end ());
2607 /* Once all symbols have enhanced hash value, we can append
2608 hash values of symbols that are seen by IPA ICF and are
2609 references by a semantic item. Newly computed values
2610 are saved to global_hash member variable. */
2611 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2612 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2614 /* Global hash value replace current hash values. */
2615 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2616 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2620 sem_item_optimizer::update_hash_by_memory_access_type ()
2622 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2624 if (m_items
[i
]->type
== FUNC
)
2626 sem_function
*fn
= static_cast<sem_function
*> (m_items
[i
]);
2627 inchash::hash
hstate (fn
->get_hash ());
2628 hstate
.add_int (fn
->m_alias_sets_hash
);
2629 fn
->set_hash (hstate
.end ());
2634 /* Congruence classes are built by hash value. */
2637 sem_item_optimizer::build_hash_based_classes (void)
2639 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2641 sem_item
*item
= m_items
[i
];
2643 congruence_class_group
*group
2644 = get_group_by_hash (item
->get_hash (), item
->type
);
2646 if (!group
->classes
.length ())
2649 group
->classes
.safe_push (new congruence_class (class_id
++));
2652 add_item_to_class (group
->classes
[0], item
);
2656 /* Build references according to call graph. */
2659 sem_item_optimizer::build_graph (void)
2661 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2663 sem_item
*item
= m_items
[i
];
2664 m_symtab_node_map
.put (item
->node
, item
);
2666 /* Initialize hash values if we are not in LTO mode. */
2671 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2673 sem_item
*item
= m_items
[i
];
2675 if (item
->type
== FUNC
)
2677 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2679 cgraph_edge
*e
= cnode
->callees
;
2682 sem_item
**slot
= m_symtab_node_map
.get
2683 (e
->callee
->ultimate_alias_target ());
2685 item
->add_reference (&m_references
, *slot
);
2691 ipa_ref
*ref
= NULL
;
2692 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2694 sem_item
**slot
= m_symtab_node_map
.get
2695 (ref
->referred
->ultimate_alias_target ());
2697 item
->add_reference (&m_references
, *slot
);
2702 /* Semantic items in classes having more than one element and initialized.
2703 In case of WPA, we load function body. */
2706 sem_item_optimizer::parse_nonsingleton_classes (void)
2708 unsigned int counter
= 0;
2710 /* Create dummy func_checker for hashing purpose. */
2711 func_checker checker
;
2713 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2714 if (m_items
[i
]->cls
->members
.length () > 1)
2716 m_items
[i
]->init (&checker
);
2722 float f
= m_items
.length () ? 100.0f
* counter
/ m_items
.length () : 0.0f
;
2723 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", counter
, f
);
2729 /* Equality function for semantic items is used to subdivide existing
2730 classes. If IN_WPA, fast equality function is invoked. */
2733 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2735 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2736 it
!= m_classes
.end (); ++it
)
2738 unsigned int class_count
= (*it
)->classes
.length ();
2740 for (unsigned i
= 0; i
< class_count
; i
++)
2742 congruence_class
*c
= (*it
)->classes
[i
];
2744 if (c
->members
.length() > 1)
2746 auto_vec
<sem_item
*> new_vector
;
2748 sem_item
*first
= c
->members
[0];
2749 new_vector
.safe_push (first
);
2751 unsigned class_split_first
= (*it
)->classes
.length ();
2753 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2755 sem_item
*item
= c
->members
[j
];
2758 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2759 : first
->equals (item
, m_symtab_node_map
);
2762 new_vector
.safe_push (item
);
2765 bool integrated
= false;
2767 for (unsigned k
= class_split_first
;
2768 k
< (*it
)->classes
.length (); k
++)
2770 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2772 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2773 : x
->equals (item
, m_symtab_node_map
);
2778 add_item_to_class ((*it
)->classes
[k
], item
);
2787 = new congruence_class (class_id
++);
2789 add_item_to_class (c
, item
);
2791 (*it
)->classes
.safe_push (c
);
2796 // We replace newly created new_vector for the class we've just
2798 c
->members
.release ();
2799 c
->members
.create (new_vector
.length ());
2801 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2802 add_item_to_class (c
, new_vector
[j
]);
2807 checking_verify_classes ();
2810 /* Subdivide classes by address references that members of the class
2811 reference. Example can be a pair of functions that have an address
2812 taken from a function. If these addresses are different the class
2816 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2818 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2820 unsigned newly_created_classes
= 0;
2822 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2823 it
!= m_classes
.end (); ++it
)
2825 unsigned int class_count
= (*it
)->classes
.length ();
2826 auto_vec
<congruence_class
*> new_classes
;
2828 for (unsigned i
= 0; i
< class_count
; i
++)
2830 congruence_class
*c
= (*it
)->classes
[i
];
2832 if (c
->members
.length() > 1)
2834 subdivide_hash_map split_map
;
2836 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2838 sem_item
*source_node
= c
->members
[j
];
2840 symbol_compare_collection
*collection
2841 = new symbol_compare_collection (source_node
->node
);
2844 vec
<sem_item
*> *slot
2845 = &split_map
.get_or_insert (collection
, &existed
);
2846 gcc_checking_assert (slot
);
2848 slot
->safe_push (source_node
);
2854 /* If the map contains more than one key, we have to split
2855 the map appropriately. */
2856 if (split_map
.elements () != 1)
2858 bool first_class
= true;
2860 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2861 it2
!= split_map
.end (); ++it2
)
2863 congruence_class
*new_cls
;
2864 new_cls
= new congruence_class (class_id
++);
2866 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2867 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2869 worklist_push (new_cls
);
2870 newly_created_classes
++;
2874 (*it
)->classes
[i
] = new_cls
;
2875 first_class
= false;
2879 new_classes
.safe_push (new_cls
);
2885 /* Release memory. */
2886 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2887 it2
!= split_map
.end (); ++it2
)
2889 delete (*it2
).first
;
2890 (*it2
).second
.release ();
2895 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2896 (*it
)->classes
.safe_push (new_classes
[i
]);
2899 return newly_created_classes
;
2902 /* Verify congruence classes, if checking is enabled. */
2905 sem_item_optimizer::checking_verify_classes (void)
2911 /* Verify congruence classes. */
2914 sem_item_optimizer::verify_classes (void)
2916 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2917 it
!= m_classes
.end (); ++it
)
2919 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2921 congruence_class
*cls
= (*it
)->classes
[i
];
2924 gcc_assert (cls
->members
.length () > 0);
2926 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2928 sem_item
*item
= cls
->members
[j
];
2931 gcc_assert (item
->cls
== cls
);
2937 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2938 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2939 but unused argument. */
2942 sem_item_optimizer::release_split_map (congruence_class
* const &,
2943 bitmap
const &b
, traverse_split_pair
*)
2952 /* Process split operation for a class given as pointer CLS_PTR,
2953 where bitmap B splits congruence class members. DATA is used
2954 as argument of split pair. */
2957 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2959 traverse_split_pair
*pair
)
2961 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2962 const congruence_class
*splitter_cls
= pair
->cls
;
2964 /* If counted bits are greater than zero and less than the number of members
2965 a group will be splitted. */
2966 unsigned popcount
= bitmap_count_bits (b
);
2968 if (popcount
> 0 && popcount
< cls
->members
.length ())
2970 auto_vec
<congruence_class
*, 2> newclasses
;
2971 newclasses
.quick_push (new congruence_class (class_id
++));
2972 newclasses
.quick_push (new congruence_class (class_id
++));
2974 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2976 int target
= bitmap_bit_p (b
, i
);
2977 congruence_class
*tc
= newclasses
[target
];
2979 add_item_to_class (tc
, cls
->members
[i
]);
2984 for (unsigned int i
= 0; i
< 2; i
++)
2985 gcc_assert (newclasses
[i
]->members
.length ());
2988 if (splitter_cls
== cls
)
2989 optimizer
->splitter_class_removed
= true;
2991 /* Remove old class from worklist if presented. */
2992 bool in_worklist
= cls
->in_worklist
;
2995 cls
->in_worklist
= false;
2997 congruence_class_group g
;
2998 g
.hash
= cls
->members
[0]->get_hash ();
2999 g
.type
= cls
->members
[0]->type
;
3001 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
3003 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3004 if (slot
->classes
[i
] == cls
)
3006 slot
->classes
.ordered_remove (i
);
3010 /* New class will be inserted and integrated to work list. */
3011 for (unsigned int i
= 0; i
< 2; i
++)
3012 optimizer
->add_class (newclasses
[i
]);
3014 /* Two classes replace one, so that increment just by one. */
3015 optimizer
->m_classes_count
++;
3017 /* If OLD class was presented in the worklist, we remove the class
3018 and replace it will both newly created classes. */
3020 for (unsigned int i
= 0; i
< 2; i
++)
3021 optimizer
->worklist_push (newclasses
[i
]);
3022 else /* Just smaller class is inserted. */
3024 unsigned int smaller_index
3025 = (newclasses
[0]->members
.length ()
3026 < newclasses
[1]->members
.length ()
3028 optimizer
->worklist_push (newclasses
[smaller_index
]);
3031 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3033 fprintf (dump_file
, " congruence class splitted:\n");
3034 cls
->dump (dump_file
, 4);
3036 fprintf (dump_file
, " newly created groups:\n");
3037 for (unsigned int i
= 0; i
< 2; i
++)
3038 newclasses
[i
]->dump (dump_file
, 4);
3041 /* Release class if not presented in work list. */
3051 /* Compare function for sorting pairs in do_congruence_step_f. */
3054 sem_item_optimizer::sort_congruence_split (const void *a_
, const void *b_
)
3056 const std::pair
<congruence_class
*, bitmap
> *a
3057 = (const std::pair
<congruence_class
*, bitmap
> *)a_
;
3058 const std::pair
<congruence_class
*, bitmap
> *b
3059 = (const std::pair
<congruence_class
*, bitmap
> *)b_
;
3060 if (a
->first
->id
< b
->first
->id
)
3062 else if (a
->first
->id
> b
->first
->id
)
3067 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3068 Bitmap stack BMSTACK is used for bitmap allocation. */
3071 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3074 hash_map
<congruence_class
*, bitmap
> split_map
;
3076 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3078 sem_item
*item
= cls
->members
[i
];
3079 sem_usage_pair
needle (item
, index
);
3080 vec
<sem_item
*> *callers
= m_references
.get (&needle
);
3081 if (callers
== NULL
)
3084 for (unsigned int j
= 0; j
< callers
->length (); j
++)
3086 sem_item
*caller
= (*callers
)[j
];
3087 if (caller
->cls
->members
.length () < 2)
3089 bitmap
*slot
= split_map
.get (caller
->cls
);
3094 b
= BITMAP_ALLOC (&m_bmstack
);
3095 split_map
.put (caller
->cls
, b
);
3100 gcc_checking_assert (caller
->cls
);
3101 gcc_checking_assert (caller
->index_in_class
3102 < caller
->cls
->members
.length ());
3104 bitmap_set_bit (b
, caller
->index_in_class
);
3108 auto_vec
<std::pair
<congruence_class
*, bitmap
> > to_split
;
3109 to_split
.reserve_exact (split_map
.elements ());
3110 for (hash_map
<congruence_class
*, bitmap
>::iterator i
= split_map
.begin ();
3111 i
!= split_map
.end (); ++i
)
3112 to_split
.safe_push (*i
);
3113 to_split
.qsort (sort_congruence_split
);
3115 traverse_split_pair pair
;
3116 pair
.optimizer
= this;
3119 splitter_class_removed
= false;
3121 for (unsigned i
= 0; i
< to_split
.length (); ++i
)
3122 r
|= traverse_congruence_split (to_split
[i
].first
, to_split
[i
].second
,
3125 /* Bitmap clean-up. */
3126 split_map
.traverse
<traverse_split_pair
*,
3127 sem_item_optimizer::release_split_map
> (NULL
);
3132 /* Every usage of a congruence class CLS is a candidate that can split the
3133 collection of classes. Bitmap stack BMSTACK is used for bitmap
3137 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3142 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3144 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3145 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3147 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3150 fprintf (dump_file
, " processing congruence step for class: %u "
3151 "(%u items, %u references), index: %u\n", cls
->id
,
3152 cls
->referenced_by_count
, cls
->members
.length (), i
);
3153 do_congruence_step_for_index (cls
, i
);
3155 if (splitter_class_removed
)
3159 BITMAP_FREE (usage
);
3162 /* Adds a newly created congruence class CLS to worklist. */
3165 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3167 /* Return if the class CLS is already presented in work list. */
3168 if (cls
->in_worklist
)
3171 cls
->in_worklist
= true;
3172 worklist
.insert (cls
->referenced_by_count
, cls
);
3175 /* Pops a class from worklist. */
3178 sem_item_optimizer::worklist_pop (void)
3180 congruence_class
*cls
;
3182 while (!worklist
.empty ())
3184 cls
= worklist
.extract_min ();
3185 if (cls
->in_worklist
)
3187 cls
->in_worklist
= false;
3193 /* Work list item was already intended to be removed.
3194 The only reason for doing it is to split a class.
3195 Thus, the class CLS is deleted. */
3203 /* Iterative congruence reduction function. */
3206 sem_item_optimizer::process_cong_reduction (void)
3208 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3209 it
!= m_classes
.end (); ++it
)
3210 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3211 if ((*it
)->classes
[i
]->is_class_used ())
3212 worklist_push ((*it
)->classes
[i
]);
3215 fprintf (dump_file
, "Worklist has been filled with: "
3216 HOST_SIZE_T_PRINT_UNSIGNED
"\n",
3217 (fmt_size_t
) worklist
.nodes ());
3219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3220 fprintf (dump_file
, "Congruence class reduction\n");
3222 congruence_class
*cls
;
3224 /* Process complete congruence reduction. */
3225 while ((cls
= worklist_pop ()) != NULL
)
3226 do_congruence_step (cls
);
3228 /* Subdivide newly created classes according to references. */
3229 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3232 fprintf (dump_file
, "Address reference subdivision created: %u "
3233 "new classes.\n", new_classes
);
3236 /* Debug function prints all informations about congruence classes. */
3239 sem_item_optimizer::dump_cong_classes (void)
3244 /* Histogram calculation. */
3245 unsigned int max_index
= 0;
3246 unsigned int single_element_classes
= 0;
3247 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3249 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3250 it
!= m_classes
.end (); ++it
)
3251 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3253 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3260 ++single_element_classes
;
3264 "Congruence classes: " HOST_SIZE_T_PRINT_UNSIGNED
" with total: "
3265 "%u items (in a non-singular class: %u)\n",
3266 (fmt_size_t
) m_classes
.elements (),
3267 m_items
.length (), m_items
.length () - single_element_classes
);
3269 "Class size histogram [number of members]: number of classes\n");
3270 for (unsigned int i
= 0; i
<= max_index
; i
++)
3272 fprintf (dump_file
, "%6u: %6u\n", i
, histogram
[i
]);
3274 if (dump_flags
& TDF_DETAILS
)
3275 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3276 it
!= m_classes
.end (); ++it
)
3278 fprintf (dump_file
, " group: with %u classes:\n",
3279 (*it
)->classes
.length ());
3281 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3283 (*it
)->classes
[i
]->dump (dump_file
, 4);
3285 if (i
< (*it
)->classes
.length () - 1)
3286 fprintf (dump_file
, " ");
3293 /* Sort pair of sem_items A and B by DECL_UID. */
3296 sort_sem_items_by_decl_uid (const void *a
, const void *b
)
3298 const sem_item
*i1
= *(const sem_item
* const *)a
;
3299 const sem_item
*i2
= *(const sem_item
* const *)b
;
3301 int uid1
= DECL_UID (i1
->decl
);
3302 int uid2
= DECL_UID (i2
->decl
);
3306 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3309 sort_congruence_classes_by_decl_uid (const void *a
, const void *b
)
3311 const congruence_class
*c1
= *(const congruence_class
* const *)a
;
3312 const congruence_class
*c2
= *(const congruence_class
* const *)b
;
3314 int uid1
= DECL_UID (c1
->members
[0]->decl
);
3315 int uid2
= DECL_UID (c2
->members
[0]->decl
);
3319 /* Sort pair of congruence_class_groups A and B by
3320 DECL_UID of the first member of a first group. */
3323 sort_congruence_class_groups_by_decl_uid (const void *a
, const void *b
)
3325 const std::pair
<congruence_class_group
*, int> *g1
3326 = (const std::pair
<congruence_class_group
*, int> *) a
;
3327 const std::pair
<congruence_class_group
*, int> *g2
3328 = (const std::pair
<congruence_class_group
*, int> *) b
;
3329 return g1
->second
- g2
->second
;
3332 /* After reduction is done, we can declare all items in a group
3333 to be equal. PREV_CLASS_COUNT is start number of classes
3334 before reduction. True is returned if there's a merge operation
3335 processed. LOADED_SYMBOLS is number of symbols that were loaded
3339 sem_item_optimizer::merge_classes (unsigned int prev_class_count
,
3340 unsigned int loaded_symbols
)
3342 unsigned int item_count
= m_items
.length ();
3343 unsigned int class_count
= m_classes_count
;
3344 unsigned int equal_items
= item_count
- class_count
;
3346 unsigned int non_singular_classes_count
= 0;
3347 unsigned int non_singular_classes_sum
= 0;
3349 bool merged_p
= false;
3352 Sort functions in congruence classes by DECL_UID and do the same
3353 for the classes to not to break -fcompare-debug. */
3355 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3356 it
!= m_classes
.end (); ++it
)
3358 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3360 congruence_class
*c
= (*it
)->classes
[i
];
3361 c
->members
.qsort (sort_sem_items_by_decl_uid
);
3364 (*it
)->classes
.qsort (sort_congruence_classes_by_decl_uid
);
3367 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3368 it
!= m_classes
.end (); ++it
)
3369 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3371 congruence_class
*c
= (*it
)->classes
[i
];
3372 if (c
->members
.length () > 1)
3374 non_singular_classes_count
++;
3375 non_singular_classes_sum
+= c
->members
.length ();
3379 auto_vec
<std::pair
<congruence_class_group
*, int> > classes (
3380 m_classes
.elements ());
3381 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3382 it
!= m_classes
.end (); ++it
)
3384 int uid
= DECL_UID ((*it
)->classes
[0]->members
[0]->decl
);
3385 classes
.quick_push (std::pair
<congruence_class_group
*, int> (*it
, uid
));
3388 classes
.qsort (sort_congruence_class_groups_by_decl_uid
);
3392 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3393 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3394 prev_class_count
, class_count
);
3395 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3396 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3397 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3398 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3399 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3400 non_singular_classes_count
: 0.0f
,
3401 non_singular_classes_count
);
3402 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3403 unsigned total
= equal_items
+ non_singular_classes_count
;
3404 fprintf (dump_file
, "Totally needed symbols: %u"
3405 ", fraction of loaded symbols: %.2f%%\n\n", total
,
3406 loaded_symbols
? 100.0f
* total
/ loaded_symbols
: 0.0f
);
3410 std::pair
<congruence_class_group
*, int> *it
;
3411 FOR_EACH_VEC_ELT (classes
, l
, it
)
3412 for (unsigned int i
= 0; i
< it
->first
->classes
.length (); i
++)
3414 congruence_class
*c
= it
->first
->classes
[i
];
3416 if (c
->members
.length () == 1)
3419 sem_item
*source
= c
->members
[0];
3420 bool this_merged_p
= false;
3422 if (DECL_NAME (source
->decl
)
3423 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3424 /* If merge via wrappers, picking main as the target can be
3426 source
= c
->members
[1];
3428 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3430 sem_item
*alias
= c
->members
[j
];
3432 if (alias
== source
)
3435 dump_user_location_t loc
3436 = dump_user_location_t::from_function_decl (source
->decl
);
3437 if (dump_enabled_p ())
3439 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3440 "Semantic equality hit:%s->%s\n",
3441 source
->node
->dump_name (),
3442 alias
->node
->dump_name ());
3443 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3444 "Assembler symbol names:%s->%s\n",
3445 source
->node
->dump_asm_name (),
3446 alias
->node
->dump_asm_name ());
3449 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
))
3450 || lookup_attribute ("no_icf", DECL_ATTRIBUTES (source
->decl
)))
3452 if (dump_enabled_p ())
3453 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3454 "Merge operation is skipped due to no_icf "
3459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3461 source
->dump_to_file (dump_file
);
3462 alias
->dump_to_file (dump_file
);
3465 if (dbg_cnt (merged_ipa_icf
))
3467 bool merged
= source
->merge (alias
);
3468 this_merged_p
|= merged
;
3470 if (merged
&& alias
->type
== VAR
)
3472 symtab_pair p
= symtab_pair (source
->node
, alias
->node
);
3473 m_merged_variables
.safe_push (p
);
3478 merged_p
|= this_merged_p
;
3480 && source
->type
== FUNC
3481 && (!flag_wpa
|| flag_checking
))
3485 FOR_EACH_SSA_NAME (i
, name
, DECL_STRUCT_FUNCTION (source
->decl
))
3487 /* We need to either merge or reset SSA_NAME_*_INFO.
3488 For merging we don't preserve the mapping between
3489 original and alias SSA_NAMEs from successful equals
3491 if (POINTER_TYPE_P (TREE_TYPE (name
)))
3493 if (SSA_NAME_PTR_INFO (name
))
3495 gcc_checking_assert (!flag_wpa
);
3496 SSA_NAME_PTR_INFO (name
) = NULL
;
3499 else if (SSA_NAME_RANGE_INFO (name
))
3501 gcc_checking_assert (!flag_wpa
);
3502 SSA_NAME_RANGE_INFO (name
) = NULL
;
3508 if (!m_merged_variables
.is_empty ())
3509 fixup_points_to_sets ();
3514 /* Fixup points to set PT. */
3517 sem_item_optimizer::fixup_pt_set (struct pt_solution
*pt
)
3519 if (pt
->vars
== NULL
)
3524 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3525 if (bitmap_bit_p (pt
->vars
, DECL_UID (item
->second
->decl
)))
3526 bitmap_set_bit (pt
->vars
, DECL_UID (item
->first
->decl
));
3529 /* Set all points-to UIDs of aliases pointing to node N as UID. */
3532 set_alias_uids (symtab_node
*n
, int uid
)
3535 FOR_EACH_ALIAS (n
, ref
)
3538 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
3539 ref
->referring
->dump_asm_name (), uid
);
3541 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
3542 set_alias_uids (ref
->referring
, uid
);
3546 /* Fixup points to analysis info. */
3549 sem_item_optimizer::fixup_points_to_sets (void)
3551 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3554 FOR_EACH_DEFINED_FUNCTION (cnode
)
3558 function
*fn
= DECL_STRUCT_FUNCTION (cnode
->decl
);
3559 if (!gimple_in_ssa_p (fn
))
3562 FOR_EACH_SSA_NAME (i
, name
, fn
)
3563 if (POINTER_TYPE_P (TREE_TYPE (name
))
3564 && SSA_NAME_PTR_INFO (name
))
3565 fixup_pt_set (&SSA_NAME_PTR_INFO (name
)->pt
);
3566 fixup_pt_set (&fn
->gimple_df
->escaped
);
3567 fixup_pt_set (&fn
->gimple_df
->escaped_return
);
3569 /* The above gets us to 99% I guess, at least catching the
3570 address compares. Below also gets us aliasing correct
3571 but as said we're giving leeway to the situation with
3572 readonly vars anyway, so ... */
3574 FOR_EACH_BB_FN (bb
, fn
)
3575 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
3578 gcall
*call
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
3581 fixup_pt_set (gimple_call_use_set (call
));
3582 fixup_pt_set (gimple_call_clobber_set (call
));
3589 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3590 set_alias_uids (item
->first
, DECL_UID (item
->first
->decl
));
3593 /* Dump function prints all class members to a FILE with an INDENT. */
3596 congruence_class::dump (FILE *file
, unsigned int indent
) const
3598 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3599 id
, members
[0]->get_hash (), members
.length ());
3601 FPUTS_SPACES (file
, indent
+ 2, "");
3602 for (unsigned i
= 0; i
< members
.length (); i
++)
3603 fprintf (file
, "%s ", members
[i
]->node
->dump_asm_name ());
3605 fprintf (file
, "\n");
3608 /* Returns true if there's a member that is used from another group. */
3611 congruence_class::is_class_used (void)
3613 for (unsigned int i
= 0; i
< members
.length (); i
++)
3614 if (members
[i
]->referenced_by_count
)
3620 /* Generate pass summary for IPA ICF pass. */
3623 ipa_icf_generate_summary (void)
3626 optimizer
= new sem_item_optimizer ();
3628 optimizer
->register_hooks ();
3629 optimizer
->parse_funcs_and_vars ();
3632 /* Write pass summary for IPA ICF pass. */
3635 ipa_icf_write_summary (void)
3637 gcc_assert (optimizer
);
3639 optimizer
->write_summary ();
3642 /* Read pass summary for IPA ICF pass. */
3645 ipa_icf_read_summary (void)
3648 optimizer
= new sem_item_optimizer ();
3650 optimizer
->read_summary ();
3651 optimizer
->register_hooks ();
3654 /* Semantic equality execution function. */
3657 ipa_icf_driver (void)
3659 gcc_assert (optimizer
);
3661 bool merged_p
= optimizer
->execute ();
3666 return merged_p
? TODO_remove_functions
: 0;
3669 const pass_data pass_data_ipa_icf
=
3671 IPA_PASS
, /* type */
3673 OPTGROUP_IPA
, /* optinfo_flags */
3674 TV_IPA_ICF
, /* tv_id */
3675 0, /* properties_required */
3676 0, /* properties_provided */
3677 0, /* properties_destroyed */
3678 0, /* todo_flags_start */
3679 0, /* todo_flags_finish */
3682 class pass_ipa_icf
: public ipa_opt_pass_d
3685 pass_ipa_icf (gcc::context
*ctxt
)
3686 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3687 ipa_icf_generate_summary
, /* generate_summary */
3688 ipa_icf_write_summary
, /* write_summary */
3689 ipa_icf_read_summary
, /* read_summary */
3691 write_optimization_summary */
3693 read_optimization_summary */
3694 NULL
, /* stmt_fixup */
3695 0, /* function_transform_todo_flags_start */
3696 NULL
, /* function_transform */
3697 NULL
) /* variable_transform */
3700 /* opt_pass methods: */
3701 bool gate (function
*) final override
3703 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3706 unsigned int execute (function
*) final override
3708 return ipa_icf_driver();
3710 }; // class pass_ipa_icf
3712 } // ipa_icf namespace
3715 make_pass_ipa_icf (gcc::context
*ctxt
)
3717 return new ipa_icf::pass_ipa_icf (ctxt
);
3720 /* Reset all state within ipa-icf.cc so that we can rerun the compiler
3721 within the same process. For use by toplev::finalize. */
3724 ipa_icf_cc_finalize (void)
3726 ipa_icf::optimizer
= NULL
;