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 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1393 gimple
*stmt
= gsi_stmt (gsi
);
1395 if (gimple_code (stmt
) != GIMPLE_DEBUG
1396 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1398 hash_stmt (stmt
, hstate
);
1399 nondbg_stmt_count
++;
1403 hstate
.commit_flag ();
1404 gcode_hash
= hstate
.end ();
1405 bb_sizes
.safe_push (nondbg_stmt_count
);
1407 /* Inserting basic block to hash table. */
1408 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1409 EDGE_COUNT (bb
->preds
)
1410 + EDGE_COUNT (bb
->succs
));
1412 bb_sorted
.safe_push (semantic_bb
);
1418 gcode_hash
= thunk_info::get (cnode
)->hash ();
1424 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1427 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1429 enum gimple_code code
= gimple_code (stmt
);
1431 hstate
.add_int (code
);
1436 m_checker
->hash_operand (gimple_switch_index (as_a
<gswitch
*> (stmt
)),
1437 hstate
, 0, func_checker::OP_NORMAL
);
1440 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1448 func_checker::operand_access_type_map
map (5);
1449 func_checker::classify_operands (stmt
, &map
);
1451 /* All these statements are equivalent if their operands are. */
1452 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1454 func_checker::operand_access_type
1455 access_type
= func_checker::get_operand_access_type
1456 (&map
, gimple_op (stmt
, i
));
1457 m_checker
->hash_operand (gimple_op (stmt
, i
), hstate
, 0,
1459 /* For memory accesses when hasing for LTO stremaing record
1460 base and ref alias ptr types so we can compare them at WPA
1461 time without having to read actual function body. */
1462 if (access_type
== func_checker::OP_MEMORY
1463 && lto_streaming_expected_p ()
1464 && flag_strict_aliasing
)
1468 ao_ref_init (&ref
, gimple_op (stmt
, i
));
1469 tree t
= ao_ref_alias_ptr_type (&ref
);
1470 if (!variably_modified_type_p (t
, NULL_TREE
))
1471 memory_access_types
.safe_push (t
);
1472 t
= ao_ref_base_alias_ptr_type (&ref
);
1473 if (!variably_modified_type_p (t
, NULL_TREE
))
1474 memory_access_types
.safe_push (t
);
1477 /* Consider nocf_check attribute in hash as it affects code
1479 if (code
== GIMPLE_CALL
1480 && flag_cf_protection
& CF_BRANCH
)
1481 hstate
.add_flag (gimple_call_nocf_check_p (as_a
<gcall
*> (stmt
)));
1490 /* Return true if polymorphic comparison must be processed. */
1493 sem_function::compare_polymorphic_p (void)
1495 struct cgraph_edge
*e
;
1497 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1499 if (get_node ()->indirect_calls
!= NULL
)
1501 /* TODO: We can do simple propagation determining what calls may lead to
1502 a polymorphic call. */
1503 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1504 if (e
->callee
->definition
1505 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1510 /* For a given call graph NODE, the function constructs new
1511 semantic function item. */
1514 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
,
1515 func_checker
*checker
)
1517 tree fndecl
= node
->decl
;
1518 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1520 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
))
1523 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1526 if (lookup_attribute_by_prefix ("oacc ",
1527 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1531 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1532 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1535 sem_function
*f
= new sem_function (node
, stack
);
1541 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1542 return true if phi nodes are semantically equivalent in these blocks . */
1545 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1547 gphi_iterator si1
, si2
;
1549 unsigned size1
, size2
, i
;
1553 gcc_assert (bb1
!= NULL
);
1554 gcc_assert (bb2
!= NULL
);
1556 si2
= gsi_start_nonvirtual_phis (bb2
);
1557 for (si1
= gsi_start_nonvirtual_phis (bb1
); !gsi_end_p (si1
);
1558 gsi_next_nonvirtual_phi (&si1
))
1560 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1563 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1564 return return_false();
1569 tree phi_result1
= gimple_phi_result (phi1
);
1570 tree phi_result2
= gimple_phi_result (phi2
);
1572 if (!m_checker
->compare_operand (phi_result1
, phi_result2
,
1573 func_checker::OP_NORMAL
))
1574 return return_false_with_msg ("PHI results are different");
1576 size1
= gimple_phi_num_args (phi1
);
1577 size2
= gimple_phi_num_args (phi2
);
1580 return return_false ();
1582 for (i
= 0; i
< size1
; ++i
)
1584 t1
= gimple_phi_arg (phi1
, i
)->def
;
1585 t2
= gimple_phi_arg (phi2
, i
)->def
;
1587 if (!m_checker
->compare_operand (t1
, t2
, func_checker::OP_NORMAL
))
1588 return return_false ();
1590 e1
= gimple_phi_arg_edge (phi1
, i
);
1591 e2
= gimple_phi_arg_edge (phi2
, i
);
1593 if (!m_checker
->compare_edge (e1
, e2
))
1594 return return_false ();
1597 gsi_next_nonvirtual_phi (&si2
);
1603 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1604 corresponds to TARGET. */
1607 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1612 if (bb_dict
->length () <= (unsigned)source
)
1613 bb_dict
->safe_grow_cleared (source
+ 1, true);
1615 if ((*bb_dict
)[source
] == 0)
1617 (*bb_dict
)[source
] = target
;
1621 return (*bb_dict
)[source
] == target
;
1624 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1628 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1629 : sem_item (VAR
, node
, stack
)
1631 gcc_checking_assert (node
);
1632 gcc_checking_assert (get_node ());
1635 /* Fast equality function based on knowledge known in WPA. */
1638 sem_variable::equals_wpa (sem_item
*item
,
1639 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1641 gcc_assert (item
->type
== VAR
);
1643 if (node
->num_references () != item
->node
->num_references ())
1644 return return_false_with_msg ("different number of references");
1646 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1647 return return_false_with_msg ("TLS model");
1649 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1650 alignment out of all aliases. */
1652 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1653 return return_false_with_msg ("Virtual flag mismatch");
1655 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1656 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1657 || !operand_equal_p (DECL_SIZE (decl
),
1658 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1659 return return_false_with_msg ("size mismatch");
1661 /* Do not attempt to mix data from different user sections;
1662 we do not know what user intends with those. */
1663 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1664 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1665 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1666 return return_false_with_msg ("user section mismatch");
1668 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1669 return return_false_with_msg ("text section");
1671 if (TYPE_ADDR_SPACE (TREE_TYPE (decl
))
1672 != TYPE_ADDR_SPACE (TREE_TYPE (item
->decl
)))
1673 return return_false_with_msg ("address-space");
1675 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1676 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1678 item
->node
->iterate_reference (i
, ref2
);
1680 if (ref
->use
!= ref2
->use
)
1681 return return_false_with_msg ("reference use mismatch");
1683 if (!compare_symbol_references (ignored_nodes
,
1684 ref
->referred
, ref2
->referred
,
1685 ref
->address_matters_p ()))
1692 /* Returns true if the item equals to ITEM given as argument. */
1695 sem_variable::equals (sem_item
*item
,
1696 hash_map
<symtab_node
*, sem_item
*> &)
1698 gcc_assert (item
->type
== VAR
);
1701 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1702 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1703 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1704 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1706 /* As seen in PR ipa/65303 we have to compare variables types. */
1707 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1708 TREE_TYPE (item
->decl
)))
1709 return return_false_with_msg ("variables types are different");
1711 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1712 DECL_INITIAL (item
->node
->decl
));
1713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1715 "Equals called for vars: %s:%s with result: %s\n\n",
1716 node
->dump_name (), item
->node
->dump_name (),
1717 ret
? "true" : "false");
1722 /* Compares trees T1 and T2 for semantic equality. */
1725 sem_variable::equals (tree t1
, tree t2
)
1728 return return_with_debug (t1
== t2
);
1731 tree_code tc1
= TREE_CODE (t1
);
1732 tree_code tc2
= TREE_CODE (t2
);
1735 return return_false_with_msg ("TREE_CODE mismatch");
1741 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1742 unsigned HOST_WIDE_INT idx
;
1744 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1745 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1746 return return_false_with_msg ("constructor type mismatch");
1748 if (typecode
== ARRAY_TYPE
)
1750 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1751 /* For arrays, check that the sizes all match. */
1752 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1754 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1755 return return_false_with_msg ("constructor array size mismatch");
1757 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1759 return return_false_with_msg ("constructor type incompatible");
1761 v1
= CONSTRUCTOR_ELTS (t1
);
1762 v2
= CONSTRUCTOR_ELTS (t2
);
1763 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1764 return return_false_with_msg ("constructor number of elts mismatch");
1766 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1768 constructor_elt
*c1
= &(*v1
)[idx
];
1769 constructor_elt
*c2
= &(*v2
)[idx
];
1771 /* Check that each value is the same... */
1772 if (!sem_variable::equals (c1
->value
, c2
->value
))
1774 /* ... and that they apply to the same fields! */
1775 if (!sem_variable::equals (c1
->index
, c2
->index
))
1782 tree x1
= TREE_OPERAND (t1
, 0);
1783 tree x2
= TREE_OPERAND (t2
, 0);
1784 tree y1
= TREE_OPERAND (t1
, 1);
1785 tree y2
= TREE_OPERAND (t2
, 1);
1787 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1788 return return_false ();
1790 /* Type of the offset on MEM_REF does not matter. */
1791 return return_with_debug (sem_variable::equals (x1
, x2
)
1792 && known_eq (wi::to_poly_offset (y1
),
1793 wi::to_poly_offset (y2
)));
1798 tree op1
= TREE_OPERAND (t1
, 0);
1799 tree op2
= TREE_OPERAND (t2
, 0);
1800 return sem_variable::equals (op1
, op2
);
1802 /* References to other vars/decls are compared using ipa-ref. */
1805 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1807 return return_false_with_msg ("Declaration mismatch");
1809 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1810 need to process its VAR/FUNCTION references without relying on ipa-ref
1814 return return_false_with_msg ("Declaration mismatch");
1816 /* Integer constants are the same only if the same width of type. */
1817 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1818 return return_false_with_msg ("INTEGER_CST precision mismatch");
1819 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1820 return return_false_with_msg ("INTEGER_CST mode mismatch");
1821 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1823 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1824 return return_false_with_msg ("STRING_CST mode mismatch");
1825 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1826 return return_false_with_msg ("STRING_CST length mismatch");
1827 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1828 TREE_STRING_LENGTH (t1
)))
1829 return return_false_with_msg ("STRING_CST mismatch");
1832 /* Fixed constants are the same only if the same width of type. */
1833 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1834 return return_false_with_msg ("FIXED_CST precision mismatch");
1836 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1837 TREE_FIXED_CST (t2
)));
1839 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1840 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1842 /* Real constants are the same only if the same width of type. */
1843 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1844 return return_false_with_msg ("REAL_CST precision mismatch");
1845 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
1846 &TREE_REAL_CST (t2
)));
1849 if (maybe_ne (VECTOR_CST_NELTS (t1
), VECTOR_CST_NELTS (t2
)))
1850 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1853 = tree_vector_builder::binary_encoded_nelts (t1
, t2
);
1854 for (unsigned int i
= 0; i
< count
; ++i
)
1855 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1
, i
),
1856 VECTOR_CST_ENCODED_ELT (t2
, i
)))
1862 case ARRAY_RANGE_REF
:
1864 tree x1
= TREE_OPERAND (t1
, 0);
1865 tree x2
= TREE_OPERAND (t2
, 0);
1866 tree y1
= TREE_OPERAND (t1
, 1);
1867 tree y2
= TREE_OPERAND (t2
, 1);
1869 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1871 if (!sem_variable::equals (array_ref_low_bound (t1
),
1872 array_ref_low_bound (t2
)))
1874 if (!sem_variable::equals (array_ref_element_size (t1
),
1875 array_ref_element_size (t2
)))
1881 case POINTER_PLUS_EXPR
:
1886 tree x1
= TREE_OPERAND (t1
, 0);
1887 tree x2
= TREE_OPERAND (t2
, 0);
1888 tree y1
= TREE_OPERAND (t1
, 1);
1889 tree y2
= TREE_OPERAND (t2
, 1);
1891 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1895 case VIEW_CONVERT_EXPR
:
1896 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1897 return return_false ();
1898 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1900 return return_false_with_msg ("ERROR_MARK");
1902 return return_false_with_msg ("Unknown TREE code reached");
1906 /* Parser function that visits a varpool NODE. */
1909 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
,
1910 func_checker
*checker
)
1912 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1916 sem_variable
*v
= new sem_variable (node
, stack
);
1922 /* Semantic variable initialization function. */
1925 sem_variable::init (ipa_icf_gimple::func_checker
*checker
)
1927 decl
= get_node ()->decl
;
1929 /* All WPA streamed in symbols should have their hashes computed at compile
1930 time. At this point, the constructor may not be in memory at all.
1931 DECL_INITIAL (decl) would be error_mark_node in that case. */
1934 gcc_assert (!node
->lto_file_data
);
1935 inchash::hash hstate
;
1936 hstate
.add_int (456346417);
1937 checker
->hash_operand (DECL_INITIAL (decl
), hstate
, 0);
1938 set_hash (hstate
.end ());
1942 /* References independent hash function. */
1945 sem_variable::get_hash (void)
1947 gcc_checking_assert (m_hash_set
);
1951 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1955 sem_variable::merge (sem_item
*alias_item
)
1957 gcc_assert (alias_item
->type
== VAR
);
1959 AUTO_DUMP_SCOPE ("merge",
1960 dump_user_location_t::from_function_decl (decl
));
1961 if (!sem_item::target_supports_symbol_aliases_p ())
1963 if (dump_enabled_p ())
1964 dump_printf (MSG_MISSED_OPTIMIZATION
, "Not unifying; "
1965 "Symbol aliases are not supported by target\n");
1969 if (DECL_EXTERNAL (alias_item
->decl
))
1971 if (dump_enabled_p ())
1972 dump_printf (MSG_MISSED_OPTIMIZATION
,
1973 "Not unifying; alias is external.\n");
1977 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1979 varpool_node
*original
= get_node ();
1980 varpool_node
*alias
= alias_var
->get_node ();
1981 bool original_discardable
= false;
1983 bool alias_address_matters
= alias
->address_matters_p ();
1985 /* See if original is in a section that can be discarded if the main
1987 Also consider case where we have resolution info and we know that
1988 original's definition is not going to be used. In this case we cannot
1989 create alias to original. */
1990 if (original
->can_be_discarded_p ()
1991 || (node
->resolution
!= LDPR_UNKNOWN
1992 && !decl_binds_to_current_def_p (node
->decl
)))
1993 original_discardable
= true;
1995 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1997 /* Constant pool machinery is not quite ready for aliases.
1998 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1999 For LTO merging does not happen that is an important missing feature.
2000 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2001 flag is dropped and non-local symbol name is assigned. */
2002 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2003 || DECL_IN_CONSTANT_POOL (original
->decl
))
2005 if (dump_enabled_p ())
2006 dump_printf (MSG_MISSED_OPTIMIZATION
,
2007 "Not unifying; constant pool variables.\n");
2011 /* Do not attempt to mix functions from different user sections;
2012 we do not know what user intends with those. */
2013 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2014 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2015 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2017 if (dump_enabled_p ())
2018 dump_printf (MSG_MISSED_OPTIMIZATION
,
2020 "original and alias are in different sections.\n");
2024 /* We cannot merge if address comparison matters. */
2025 if (alias_address_matters
&& flag_merge_constants
< 2)
2027 if (dump_enabled_p ())
2028 dump_printf (MSG_MISSED_OPTIMIZATION
,
2029 "Not unifying; address of original may be compared.\n");
2033 if (DECL_ALIGN (original
->decl
) != DECL_ALIGN (alias
->decl
)
2034 && (sanitize_flags_p (SANITIZE_ADDRESS
, original
->decl
)
2035 || sanitize_flags_p (SANITIZE_ADDRESS
, alias
->decl
)))
2037 if (dump_enabled_p ())
2038 dump_printf (MSG_MISSED_OPTIMIZATION
,
2040 "ASAN requires equal alignments for original and alias\n");
2045 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2047 if (dump_enabled_p ())
2048 dump_printf (MSG_MISSED_OPTIMIZATION
,
2050 "original and alias have incompatible alignments\n");
2055 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2057 if (dump_enabled_p ())
2058 dump_printf (MSG_MISSED_OPTIMIZATION
,
2059 "Not unifying; alias cannot be created; "
2060 "across comdat group boundary\n");
2065 if (original_discardable
)
2067 if (dump_enabled_p ())
2068 dump_printf (MSG_MISSED_OPTIMIZATION
,
2069 "Not unifying; alias cannot be created; "
2070 "target is discardable\n");
2076 gcc_assert (!original
->alias
);
2077 gcc_assert (!alias
->alias
);
2079 alias
->analyzed
= false;
2081 DECL_INITIAL (alias
->decl
) = NULL
;
2082 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2084 alias
->remove_all_references ();
2085 if (TREE_ADDRESSABLE (alias
->decl
))
2086 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2088 varpool_node::create_alias (alias_var
->decl
, decl
);
2089 alias
->resolve_alias (original
);
2091 if (dump_enabled_p ())
2092 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
2093 "Unified; Variable alias has been created.\n");
2099 /* Dump symbol to FILE. */
2102 sem_variable::dump_to_file (FILE *file
)
2106 print_node (file
, "", decl
, 0);
2107 fprintf (file
, "\n\n");
2110 unsigned int sem_item_optimizer::class_id
= 0;
2112 sem_item_optimizer::sem_item_optimizer ()
2113 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2114 m_varpool_node_hooks (NULL
), m_merged_variables (), m_references ()
2117 bitmap_obstack_initialize (&m_bmstack
);
2120 sem_item_optimizer::~sem_item_optimizer ()
2122 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2126 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2127 it
!= m_classes
.end (); ++it
)
2129 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2130 delete (*it
)->classes
[i
];
2132 (*it
)->classes
.release ();
2138 bitmap_obstack_release (&m_bmstack
);
2139 m_merged_variables
.release ();
2142 /* Write IPA ICF summary for symbols. */
2145 sem_item_optimizer::write_summary (void)
2147 unsigned int count
= 0;
2149 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2150 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2153 /* Calculate number of symbols to be serialized. */
2154 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2156 lsei_next_in_partition (&lsei
))
2158 symtab_node
*node
= lsei_node (lsei
);
2160 if (m_symtab_node_map
.get (node
))
2164 streamer_write_uhwi (ob
, count
);
2166 /* Process all of the symbols. */
2167 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2169 lsei_next_in_partition (&lsei
))
2171 symtab_node
*node
= lsei_node (lsei
);
2173 sem_item
**item
= m_symtab_node_map
.get (node
);
2177 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2178 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2180 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2182 if ((*item
)->type
== FUNC
)
2184 sem_function
*fn
= static_cast<sem_function
*> (*item
);
2185 streamer_write_uhwi (ob
, fn
->memory_access_types
.length ());
2186 for (unsigned i
= 0; i
< fn
->memory_access_types
.length (); i
++)
2187 stream_write_tree (ob
, fn
->memory_access_types
[i
], true);
2192 streamer_write_char_stream (ob
->main_stream
, 0);
2193 produce_asm (ob
, NULL
);
2194 destroy_output_block (ob
);
2197 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2198 contains LEN bytes. */
2201 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2202 const char *data
, size_t len
)
2204 const lto_function_header
*header
2205 = (const lto_function_header
*) data
;
2206 const int cfg_offset
= sizeof (lto_function_header
);
2207 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2208 const int string_offset
= main_offset
+ header
->main_size
;
2213 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2214 header
->main_size
, file_data
);
2217 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2218 header
->string_size
, vNULL
);
2220 count
= streamer_read_uhwi (&ib_main
);
2222 for (i
= 0; i
< count
; i
++)
2226 lto_symtab_encoder_t encoder
;
2228 index
= streamer_read_uhwi (&ib_main
);
2229 encoder
= file_data
->symtab_node_encoder
;
2230 node
= lto_symtab_encoder_deref (encoder
, index
);
2232 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2233 gcc_assert (node
->definition
);
2235 if (is_a
<cgraph_node
*> (node
))
2237 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2239 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2240 unsigned count
= streamer_read_uhwi (&ib_main
);
2241 inchash::hash
hstate (0);
2242 if (flag_incremental_link
== INCREMENTAL_LINK_LTO
)
2243 fn
->memory_access_types
.reserve_exact (count
);
2244 for (unsigned i
= 0; i
< count
; i
++)
2246 tree type
= stream_read_tree (&ib_main
, data_in
);
2247 hstate
.add_int (get_deref_alias_set (type
));
2248 if (flag_incremental_link
== INCREMENTAL_LINK_LTO
)
2249 fn
->memory_access_types
.quick_push (type
);
2251 fn
->m_alias_sets_hash
= hstate
.end ();
2252 fn
->set_hash (hash
);
2253 m_items
.safe_push (fn
);
2257 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2259 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2260 var
->set_hash (hash
);
2261 m_items
.safe_push (var
);
2265 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2267 lto_data_in_delete (data_in
);
2270 /* Read IPA ICF summary for symbols. */
2273 sem_item_optimizer::read_summary (void)
2275 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2276 lto_file_decl_data
*file_data
;
2279 while ((file_data
= file_data_vec
[j
++]))
2283 = lto_get_summary_section_data (file_data
, LTO_section_ipa_icf
, &len
);
2285 read_section (file_data
, data
, len
);
2289 /* Register callgraph and varpool hooks. */
2292 sem_item_optimizer::register_hooks (void)
2294 if (!m_cgraph_node_hooks
)
2295 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2296 (&sem_item_optimizer::cgraph_removal_hook
, this);
2298 if (!m_varpool_node_hooks
)
2299 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2300 (&sem_item_optimizer::varpool_removal_hook
, this);
2303 /* Unregister callgraph and varpool hooks. */
2306 sem_item_optimizer::unregister_hooks (void)
2308 if (m_cgraph_node_hooks
)
2309 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2311 if (m_varpool_node_hooks
)
2312 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2315 /* Adds a CLS to hashtable associated by hash value. */
2318 sem_item_optimizer::add_class (congruence_class
*cls
)
2320 gcc_assert (cls
->members
.length ());
2322 congruence_class_group
*group
2323 = get_group_by_hash (cls
->members
[0]->get_hash (),
2324 cls
->members
[0]->type
);
2325 group
->classes
.safe_push (cls
);
2328 /* Gets a congruence class group based on given HASH value and TYPE. */
2330 congruence_class_group
*
2331 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2333 congruence_class_group
*item
= XNEW (congruence_class_group
);
2337 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2343 item
->classes
.create (1);
2350 /* Callgraph removal hook called for a NODE with a custom DATA. */
2353 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2355 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2356 optimizer
->remove_symtab_node (node
);
2359 /* Varpool removal hook called for a NODE with a custom DATA. */
2362 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2364 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2365 optimizer
->remove_symtab_node (node
);
2368 /* Remove symtab NODE triggered by symtab removal hooks. */
2371 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2373 gcc_assert (m_classes
.is_empty ());
2375 m_removed_items_set
.add (node
);
2379 sem_item_optimizer::remove_item (sem_item
*item
)
2381 if (m_symtab_node_map
.get (item
->node
))
2382 m_symtab_node_map
.remove (item
->node
);
2386 /* Removes all callgraph and varpool nodes that are marked by symtab
2390 sem_item_optimizer::filter_removed_items (void)
2392 auto_vec
<sem_item
*> filtered
;
2394 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2396 sem_item
*item
= m_items
[i
];
2398 if (m_removed_items_set
.contains (item
->node
))
2404 if (item
->type
== FUNC
)
2406 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2408 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2411 filtered
.safe_push (item
);
2415 if (!flag_ipa_icf_variables
)
2419 /* Filter out non-readonly variables. */
2420 tree decl
= item
->decl
;
2421 varpool_node
*vnode
= static_cast <sem_variable
*>(item
)->get_node ();
2422 if (!TREE_READONLY (decl
) || vnode
->body_removed
)
2425 filtered
.safe_push (item
);
2430 /* Clean-up of released semantic items. */
2433 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2434 m_items
.safe_push (filtered
[i
]);
2437 /* Optimizer entry point which returns true in case it processes
2438 a merge operation. True is returned if there's a merge operation
2442 sem_item_optimizer::execute (void)
2444 filter_removed_items ();
2445 unregister_hooks ();
2448 update_hash_by_addr_refs ();
2449 update_hash_by_memory_access_type ();
2450 build_hash_based_classes ();
2453 fprintf (dump_file
, "Dump after hash based groups\n");
2454 dump_cong_classes ();
2456 subdivide_classes_by_equality (true);
2459 fprintf (dump_file
, "Dump after WPA based types groups\n");
2461 dump_cong_classes ();
2463 process_cong_reduction ();
2464 checking_verify_classes ();
2467 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2469 dump_cong_classes ();
2471 unsigned int loaded_symbols
= parse_nonsingleton_classes ();
2472 subdivide_classes_by_equality ();
2475 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2477 dump_cong_classes ();
2479 unsigned int prev_class_count
= m_classes_count
;
2481 process_cong_reduction ();
2482 dump_cong_classes ();
2483 checking_verify_classes ();
2484 bool merged_p
= merge_classes (prev_class_count
, loaded_symbols
);
2486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2487 symtab
->dump (dump_file
);
2492 /* Function responsible for visiting all potential functions and
2493 read-only variables that can be merged. */
2496 sem_item_optimizer::parse_funcs_and_vars (void)
2500 /* Create dummy func_checker for hashing purpose. */
2501 func_checker checker
;
2503 if (flag_ipa_icf_functions
)
2504 FOR_EACH_DEFINED_FUNCTION (cnode
)
2506 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
, &checker
);
2509 m_items
.safe_push (f
);
2510 m_symtab_node_map
.put (cnode
, f
);
2514 varpool_node
*vnode
;
2516 if (flag_ipa_icf_variables
)
2517 FOR_EACH_DEFINED_VARIABLE (vnode
)
2519 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
, &checker
);
2523 m_items
.safe_push (v
);
2524 m_symtab_node_map
.put (vnode
, v
);
2529 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2532 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2534 item
->index_in_class
= cls
->members
.length ();
2535 cls
->members
.safe_push (item
);
2536 cls
->referenced_by_count
+= item
->referenced_by_count
;
2540 /* For each semantic item, append hash values of references. */
2543 sem_item_optimizer::update_hash_by_addr_refs ()
2545 /* First, append to hash sensitive references and class type if it need to
2546 be matched for ODR. */
2547 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2549 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2550 if (m_items
[i
]->type
== FUNC
)
2552 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2553 && contains_polymorphic_type_p
2554 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2555 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2556 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2557 && static_cast<sem_function
*> (m_items
[i
])
2558 ->compare_polymorphic_p ())))
2561 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2562 inchash::hash
hstate (m_items
[i
]->get_hash ());
2564 /* Hash ODR types by mangled name if it is defined.
2565 If not we know that type is anonymous of free_lang_data
2566 was not run and in that case type main variants are
2568 if (TYPE_NAME (class_type
)
2569 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
))
2570 && !type_in_anonymous_namespace_p
2573 (IDENTIFIER_HASH_VALUE
2574 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2579 || type_in_anonymous_namespace_p (class_type
));
2580 hstate
.add_hwi (TYPE_UID (TYPE_MAIN_VARIANT (class_type
)));
2583 m_items
[i
]->set_hash (hstate
.end ());
2588 /* Once all symbols have enhanced hash value, we can append
2589 hash values of symbols that are seen by IPA ICF and are
2590 references by a semantic item. Newly computed values
2591 are saved to global_hash member variable. */
2592 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2593 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2595 /* Global hash value replace current hash values. */
2596 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2597 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2601 sem_item_optimizer::update_hash_by_memory_access_type ()
2603 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2605 if (m_items
[i
]->type
== FUNC
)
2607 sem_function
*fn
= static_cast<sem_function
*> (m_items
[i
]);
2608 inchash::hash
hstate (fn
->get_hash ());
2609 hstate
.add_int (fn
->m_alias_sets_hash
);
2610 fn
->set_hash (hstate
.end ());
2615 /* Congruence classes are built by hash value. */
2618 sem_item_optimizer::build_hash_based_classes (void)
2620 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2622 sem_item
*item
= m_items
[i
];
2624 congruence_class_group
*group
2625 = get_group_by_hash (item
->get_hash (), item
->type
);
2627 if (!group
->classes
.length ())
2630 group
->classes
.safe_push (new congruence_class (class_id
++));
2633 add_item_to_class (group
->classes
[0], item
);
2637 /* Build references according to call graph. */
2640 sem_item_optimizer::build_graph (void)
2642 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2644 sem_item
*item
= m_items
[i
];
2645 m_symtab_node_map
.put (item
->node
, item
);
2647 /* Initialize hash values if we are not in LTO mode. */
2652 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2654 sem_item
*item
= m_items
[i
];
2656 if (item
->type
== FUNC
)
2658 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2660 cgraph_edge
*e
= cnode
->callees
;
2663 sem_item
**slot
= m_symtab_node_map
.get
2664 (e
->callee
->ultimate_alias_target ());
2666 item
->add_reference (&m_references
, *slot
);
2672 ipa_ref
*ref
= NULL
;
2673 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2675 sem_item
**slot
= m_symtab_node_map
.get
2676 (ref
->referred
->ultimate_alias_target ());
2678 item
->add_reference (&m_references
, *slot
);
2683 /* Semantic items in classes having more than one element and initialized.
2684 In case of WPA, we load function body. */
2687 sem_item_optimizer::parse_nonsingleton_classes (void)
2689 unsigned int counter
= 0;
2691 /* Create dummy func_checker for hashing purpose. */
2692 func_checker checker
;
2694 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2695 if (m_items
[i
]->cls
->members
.length () > 1)
2697 m_items
[i
]->init (&checker
);
2703 float f
= m_items
.length () ? 100.0f
* counter
/ m_items
.length () : 0.0f
;
2704 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", counter
, f
);
2710 /* Equality function for semantic items is used to subdivide existing
2711 classes. If IN_WPA, fast equality function is invoked. */
2714 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2716 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2717 it
!= m_classes
.end (); ++it
)
2719 unsigned int class_count
= (*it
)->classes
.length ();
2721 for (unsigned i
= 0; i
< class_count
; i
++)
2723 congruence_class
*c
= (*it
)->classes
[i
];
2725 if (c
->members
.length() > 1)
2727 auto_vec
<sem_item
*> new_vector
;
2729 sem_item
*first
= c
->members
[0];
2730 new_vector
.safe_push (first
);
2732 unsigned class_split_first
= (*it
)->classes
.length ();
2734 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2736 sem_item
*item
= c
->members
[j
];
2739 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2740 : first
->equals (item
, m_symtab_node_map
);
2743 new_vector
.safe_push (item
);
2746 bool integrated
= false;
2748 for (unsigned k
= class_split_first
;
2749 k
< (*it
)->classes
.length (); k
++)
2751 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2753 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2754 : x
->equals (item
, m_symtab_node_map
);
2759 add_item_to_class ((*it
)->classes
[k
], item
);
2768 = new congruence_class (class_id
++);
2770 add_item_to_class (c
, item
);
2772 (*it
)->classes
.safe_push (c
);
2777 // We replace newly created new_vector for the class we've just
2779 c
->members
.release ();
2780 c
->members
.create (new_vector
.length ());
2782 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2783 add_item_to_class (c
, new_vector
[j
]);
2788 checking_verify_classes ();
2791 /* Subdivide classes by address references that members of the class
2792 reference. Example can be a pair of functions that have an address
2793 taken from a function. If these addresses are different the class
2797 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2799 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2801 unsigned newly_created_classes
= 0;
2803 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2804 it
!= m_classes
.end (); ++it
)
2806 unsigned int class_count
= (*it
)->classes
.length ();
2807 auto_vec
<congruence_class
*> new_classes
;
2809 for (unsigned i
= 0; i
< class_count
; i
++)
2811 congruence_class
*c
= (*it
)->classes
[i
];
2813 if (c
->members
.length() > 1)
2815 subdivide_hash_map split_map
;
2817 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2819 sem_item
*source_node
= c
->members
[j
];
2821 symbol_compare_collection
*collection
2822 = new symbol_compare_collection (source_node
->node
);
2825 vec
<sem_item
*> *slot
2826 = &split_map
.get_or_insert (collection
, &existed
);
2827 gcc_checking_assert (slot
);
2829 slot
->safe_push (source_node
);
2835 /* If the map contains more than one key, we have to split
2836 the map appropriately. */
2837 if (split_map
.elements () != 1)
2839 bool first_class
= true;
2841 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2842 it2
!= split_map
.end (); ++it2
)
2844 congruence_class
*new_cls
;
2845 new_cls
= new congruence_class (class_id
++);
2847 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2848 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2850 worklist_push (new_cls
);
2851 newly_created_classes
++;
2855 (*it
)->classes
[i
] = new_cls
;
2856 first_class
= false;
2860 new_classes
.safe_push (new_cls
);
2866 /* Release memory. */
2867 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2868 it2
!= split_map
.end (); ++it2
)
2870 delete (*it2
).first
;
2871 (*it2
).second
.release ();
2876 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2877 (*it
)->classes
.safe_push (new_classes
[i
]);
2880 return newly_created_classes
;
2883 /* Verify congruence classes, if checking is enabled. */
2886 sem_item_optimizer::checking_verify_classes (void)
2892 /* Verify congruence classes. */
2895 sem_item_optimizer::verify_classes (void)
2897 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2898 it
!= m_classes
.end (); ++it
)
2900 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2902 congruence_class
*cls
= (*it
)->classes
[i
];
2905 gcc_assert (cls
->members
.length () > 0);
2907 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2909 sem_item
*item
= cls
->members
[j
];
2912 gcc_assert (item
->cls
== cls
);
2918 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2919 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2920 but unused argument. */
2923 sem_item_optimizer::release_split_map (congruence_class
* const &,
2924 bitmap
const &b
, traverse_split_pair
*)
2933 /* Process split operation for a class given as pointer CLS_PTR,
2934 where bitmap B splits congruence class members. DATA is used
2935 as argument of split pair. */
2938 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2940 traverse_split_pair
*pair
)
2942 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2943 const congruence_class
*splitter_cls
= pair
->cls
;
2945 /* If counted bits are greater than zero and less than the number of members
2946 a group will be splitted. */
2947 unsigned popcount
= bitmap_count_bits (b
);
2949 if (popcount
> 0 && popcount
< cls
->members
.length ())
2951 auto_vec
<congruence_class
*, 2> newclasses
;
2952 newclasses
.quick_push (new congruence_class (class_id
++));
2953 newclasses
.quick_push (new congruence_class (class_id
++));
2955 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2957 int target
= bitmap_bit_p (b
, i
);
2958 congruence_class
*tc
= newclasses
[target
];
2960 add_item_to_class (tc
, cls
->members
[i
]);
2965 for (unsigned int i
= 0; i
< 2; i
++)
2966 gcc_assert (newclasses
[i
]->members
.length ());
2969 if (splitter_cls
== cls
)
2970 optimizer
->splitter_class_removed
= true;
2972 /* Remove old class from worklist if presented. */
2973 bool in_worklist
= cls
->in_worklist
;
2976 cls
->in_worklist
= false;
2978 congruence_class_group g
;
2979 g
.hash
= cls
->members
[0]->get_hash ();
2980 g
.type
= cls
->members
[0]->type
;
2982 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
2984 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2985 if (slot
->classes
[i
] == cls
)
2987 slot
->classes
.ordered_remove (i
);
2991 /* New class will be inserted and integrated to work list. */
2992 for (unsigned int i
= 0; i
< 2; i
++)
2993 optimizer
->add_class (newclasses
[i
]);
2995 /* Two classes replace one, so that increment just by one. */
2996 optimizer
->m_classes_count
++;
2998 /* If OLD class was presented in the worklist, we remove the class
2999 and replace it will both newly created classes. */
3001 for (unsigned int i
= 0; i
< 2; i
++)
3002 optimizer
->worklist_push (newclasses
[i
]);
3003 else /* Just smaller class is inserted. */
3005 unsigned int smaller_index
3006 = (newclasses
[0]->members
.length ()
3007 < newclasses
[1]->members
.length ()
3009 optimizer
->worklist_push (newclasses
[smaller_index
]);
3012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3014 fprintf (dump_file
, " congruence class splitted:\n");
3015 cls
->dump (dump_file
, 4);
3017 fprintf (dump_file
, " newly created groups:\n");
3018 for (unsigned int i
= 0; i
< 2; i
++)
3019 newclasses
[i
]->dump (dump_file
, 4);
3022 /* Release class if not presented in work list. */
3032 /* Compare function for sorting pairs in do_congruence_step_f. */
3035 sem_item_optimizer::sort_congruence_split (const void *a_
, const void *b_
)
3037 const std::pair
<congruence_class
*, bitmap
> *a
3038 = (const std::pair
<congruence_class
*, bitmap
> *)a_
;
3039 const std::pair
<congruence_class
*, bitmap
> *b
3040 = (const std::pair
<congruence_class
*, bitmap
> *)b_
;
3041 if (a
->first
->id
< b
->first
->id
)
3043 else if (a
->first
->id
> b
->first
->id
)
3048 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3049 Bitmap stack BMSTACK is used for bitmap allocation. */
3052 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3055 hash_map
<congruence_class
*, bitmap
> split_map
;
3057 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3059 sem_item
*item
= cls
->members
[i
];
3060 sem_usage_pair
needle (item
, index
);
3061 vec
<sem_item
*> *callers
= m_references
.get (&needle
);
3062 if (callers
== NULL
)
3065 for (unsigned int j
= 0; j
< callers
->length (); j
++)
3067 sem_item
*caller
= (*callers
)[j
];
3068 if (caller
->cls
->members
.length () < 2)
3070 bitmap
*slot
= split_map
.get (caller
->cls
);
3075 b
= BITMAP_ALLOC (&m_bmstack
);
3076 split_map
.put (caller
->cls
, b
);
3081 gcc_checking_assert (caller
->cls
);
3082 gcc_checking_assert (caller
->index_in_class
3083 < caller
->cls
->members
.length ());
3085 bitmap_set_bit (b
, caller
->index_in_class
);
3089 auto_vec
<std::pair
<congruence_class
*, bitmap
> > to_split
;
3090 to_split
.reserve_exact (split_map
.elements ());
3091 for (hash_map
<congruence_class
*, bitmap
>::iterator i
= split_map
.begin ();
3092 i
!= split_map
.end (); ++i
)
3093 to_split
.safe_push (*i
);
3094 to_split
.qsort (sort_congruence_split
);
3096 traverse_split_pair pair
;
3097 pair
.optimizer
= this;
3100 splitter_class_removed
= false;
3102 for (unsigned i
= 0; i
< to_split
.length (); ++i
)
3103 r
|= traverse_congruence_split (to_split
[i
].first
, to_split
[i
].second
,
3106 /* Bitmap clean-up. */
3107 split_map
.traverse
<traverse_split_pair
*,
3108 sem_item_optimizer::release_split_map
> (NULL
);
3113 /* Every usage of a congruence class CLS is a candidate that can split the
3114 collection of classes. Bitmap stack BMSTACK is used for bitmap
3118 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3123 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3125 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3126 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3128 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3131 fprintf (dump_file
, " processing congruence step for class: %u "
3132 "(%u items, %u references), index: %u\n", cls
->id
,
3133 cls
->referenced_by_count
, cls
->members
.length (), i
);
3134 do_congruence_step_for_index (cls
, i
);
3136 if (splitter_class_removed
)
3140 BITMAP_FREE (usage
);
3143 /* Adds a newly created congruence class CLS to worklist. */
3146 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3148 /* Return if the class CLS is already presented in work list. */
3149 if (cls
->in_worklist
)
3152 cls
->in_worklist
= true;
3153 worklist
.insert (cls
->referenced_by_count
, cls
);
3156 /* Pops a class from worklist. */
3159 sem_item_optimizer::worklist_pop (void)
3161 congruence_class
*cls
;
3163 while (!worklist
.empty ())
3165 cls
= worklist
.extract_min ();
3166 if (cls
->in_worklist
)
3168 cls
->in_worklist
= false;
3174 /* Work list item was already intended to be removed.
3175 The only reason for doing it is to split a class.
3176 Thus, the class CLS is deleted. */
3184 /* Iterative congruence reduction function. */
3187 sem_item_optimizer::process_cong_reduction (void)
3189 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3190 it
!= m_classes
.end (); ++it
)
3191 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3192 if ((*it
)->classes
[i
]->is_class_used ())
3193 worklist_push ((*it
)->classes
[i
]);
3196 fprintf (dump_file
, "Worklist has been filled with: "
3197 HOST_SIZE_T_PRINT_UNSIGNED
"\n",
3198 (fmt_size_t
) worklist
.nodes ());
3200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3201 fprintf (dump_file
, "Congruence class reduction\n");
3203 congruence_class
*cls
;
3205 /* Process complete congruence reduction. */
3206 while ((cls
= worklist_pop ()) != NULL
)
3207 do_congruence_step (cls
);
3209 /* Subdivide newly created classes according to references. */
3210 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3213 fprintf (dump_file
, "Address reference subdivision created: %u "
3214 "new classes.\n", new_classes
);
3217 /* Debug function prints all informations about congruence classes. */
3220 sem_item_optimizer::dump_cong_classes (void)
3225 /* Histogram calculation. */
3226 unsigned int max_index
= 0;
3227 unsigned int single_element_classes
= 0;
3228 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3230 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3231 it
!= m_classes
.end (); ++it
)
3232 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3234 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3241 ++single_element_classes
;
3245 "Congruence classes: " HOST_SIZE_T_PRINT_UNSIGNED
" with total: "
3246 "%u items (in a non-singular class: %u)\n",
3247 (fmt_size_t
) m_classes
.elements (),
3248 m_items
.length (), m_items
.length () - single_element_classes
);
3250 "Class size histogram [number of members]: number of classes\n");
3251 for (unsigned int i
= 0; i
<= max_index
; i
++)
3253 fprintf (dump_file
, "%6u: %6u\n", i
, histogram
[i
]);
3255 if (dump_flags
& TDF_DETAILS
)
3256 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3257 it
!= m_classes
.end (); ++it
)
3259 fprintf (dump_file
, " group: with %u classes:\n",
3260 (*it
)->classes
.length ());
3262 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3264 (*it
)->classes
[i
]->dump (dump_file
, 4);
3266 if (i
< (*it
)->classes
.length () - 1)
3267 fprintf (dump_file
, " ");
3274 /* Sort pair of sem_items A and B by DECL_UID. */
3277 sort_sem_items_by_decl_uid (const void *a
, const void *b
)
3279 const sem_item
*i1
= *(const sem_item
* const *)a
;
3280 const sem_item
*i2
= *(const sem_item
* const *)b
;
3282 int uid1
= DECL_UID (i1
->decl
);
3283 int uid2
= DECL_UID (i2
->decl
);
3287 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3290 sort_congruence_classes_by_decl_uid (const void *a
, const void *b
)
3292 const congruence_class
*c1
= *(const congruence_class
* const *)a
;
3293 const congruence_class
*c2
= *(const congruence_class
* const *)b
;
3295 int uid1
= DECL_UID (c1
->members
[0]->decl
);
3296 int uid2
= DECL_UID (c2
->members
[0]->decl
);
3300 /* Sort pair of congruence_class_groups A and B by
3301 DECL_UID of the first member of a first group. */
3304 sort_congruence_class_groups_by_decl_uid (const void *a
, const void *b
)
3306 const std::pair
<congruence_class_group
*, int> *g1
3307 = (const std::pair
<congruence_class_group
*, int> *) a
;
3308 const std::pair
<congruence_class_group
*, int> *g2
3309 = (const std::pair
<congruence_class_group
*, int> *) b
;
3310 return g1
->second
- g2
->second
;
3313 /* After reduction is done, we can declare all items in a group
3314 to be equal. PREV_CLASS_COUNT is start number of classes
3315 before reduction. True is returned if there's a merge operation
3316 processed. LOADED_SYMBOLS is number of symbols that were loaded
3320 sem_item_optimizer::merge_classes (unsigned int prev_class_count
,
3321 unsigned int loaded_symbols
)
3323 unsigned int item_count
= m_items
.length ();
3324 unsigned int class_count
= m_classes_count
;
3325 unsigned int equal_items
= item_count
- class_count
;
3327 unsigned int non_singular_classes_count
= 0;
3328 unsigned int non_singular_classes_sum
= 0;
3330 bool merged_p
= false;
3333 Sort functions in congruence classes by DECL_UID and do the same
3334 for the classes to not to break -fcompare-debug. */
3336 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3337 it
!= m_classes
.end (); ++it
)
3339 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3341 congruence_class
*c
= (*it
)->classes
[i
];
3342 c
->members
.qsort (sort_sem_items_by_decl_uid
);
3345 (*it
)->classes
.qsort (sort_congruence_classes_by_decl_uid
);
3348 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3349 it
!= m_classes
.end (); ++it
)
3350 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3352 congruence_class
*c
= (*it
)->classes
[i
];
3353 if (c
->members
.length () > 1)
3355 non_singular_classes_count
++;
3356 non_singular_classes_sum
+= c
->members
.length ();
3360 auto_vec
<std::pair
<congruence_class_group
*, int> > classes (
3361 m_classes
.elements ());
3362 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3363 it
!= m_classes
.end (); ++it
)
3365 int uid
= DECL_UID ((*it
)->classes
[0]->members
[0]->decl
);
3366 classes
.quick_push (std::pair
<congruence_class_group
*, int> (*it
, uid
));
3369 classes
.qsort (sort_congruence_class_groups_by_decl_uid
);
3373 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3374 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3375 prev_class_count
, class_count
);
3376 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3377 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3378 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3379 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3380 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3381 non_singular_classes_count
: 0.0f
,
3382 non_singular_classes_count
);
3383 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3384 unsigned total
= equal_items
+ non_singular_classes_count
;
3385 fprintf (dump_file
, "Totally needed symbols: %u"
3386 ", fraction of loaded symbols: %.2f%%\n\n", total
,
3387 loaded_symbols
? 100.0f
* total
/ loaded_symbols
: 0.0f
);
3391 std::pair
<congruence_class_group
*, int> *it
;
3392 FOR_EACH_VEC_ELT (classes
, l
, it
)
3393 for (unsigned int i
= 0; i
< it
->first
->classes
.length (); i
++)
3395 congruence_class
*c
= it
->first
->classes
[i
];
3397 if (c
->members
.length () == 1)
3400 sem_item
*source
= c
->members
[0];
3402 if (DECL_NAME (source
->decl
)
3403 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3404 /* If merge via wrappers, picking main as the target can be
3406 source
= c
->members
[1];
3408 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3410 sem_item
*alias
= c
->members
[j
];
3412 if (alias
== source
)
3415 dump_user_location_t loc
3416 = dump_user_location_t::from_function_decl (source
->decl
);
3417 if (dump_enabled_p ())
3419 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3420 "Semantic equality hit:%s->%s\n",
3421 source
->node
->dump_name (),
3422 alias
->node
->dump_name ());
3423 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3424 "Assembler symbol names:%s->%s\n",
3425 source
->node
->dump_asm_name (),
3426 alias
->node
->dump_asm_name ());
3429 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
))
3430 || lookup_attribute ("no_icf", DECL_ATTRIBUTES (source
->decl
)))
3432 if (dump_enabled_p ())
3433 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3434 "Merge operation is skipped due to no_icf "
3439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3441 source
->dump_to_file (dump_file
);
3442 alias
->dump_to_file (dump_file
);
3445 if (dbg_cnt (merged_ipa_icf
))
3447 bool merged
= source
->merge (alias
);
3450 if (merged
&& alias
->type
== VAR
)
3452 symtab_pair p
= symtab_pair (source
->node
, alias
->node
);
3453 m_merged_variables
.safe_push (p
);
3459 if (!m_merged_variables
.is_empty ())
3460 fixup_points_to_sets ();
3465 /* Fixup points to set PT. */
3468 sem_item_optimizer::fixup_pt_set (struct pt_solution
*pt
)
3470 if (pt
->vars
== NULL
)
3475 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3476 if (bitmap_bit_p (pt
->vars
, DECL_UID (item
->second
->decl
)))
3477 bitmap_set_bit (pt
->vars
, DECL_UID (item
->first
->decl
));
3480 /* Set all points-to UIDs of aliases pointing to node N as UID. */
3483 set_alias_uids (symtab_node
*n
, int uid
)
3486 FOR_EACH_ALIAS (n
, ref
)
3489 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
3490 ref
->referring
->dump_asm_name (), uid
);
3492 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
3493 set_alias_uids (ref
->referring
, uid
);
3497 /* Fixup points to analysis info. */
3500 sem_item_optimizer::fixup_points_to_sets (void)
3502 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3505 FOR_EACH_DEFINED_FUNCTION (cnode
)
3509 function
*fn
= DECL_STRUCT_FUNCTION (cnode
->decl
);
3510 if (!gimple_in_ssa_p (fn
))
3513 FOR_EACH_SSA_NAME (i
, name
, fn
)
3514 if (POINTER_TYPE_P (TREE_TYPE (name
))
3515 && SSA_NAME_PTR_INFO (name
))
3516 fixup_pt_set (&SSA_NAME_PTR_INFO (name
)->pt
);
3517 fixup_pt_set (&fn
->gimple_df
->escaped
);
3518 fixup_pt_set (&fn
->gimple_df
->escaped_return
);
3520 /* The above gets us to 99% I guess, at least catching the
3521 address compares. Below also gets us aliasing correct
3522 but as said we're giving leeway to the situation with
3523 readonly vars anyway, so ... */
3525 FOR_EACH_BB_FN (bb
, fn
)
3526 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
3529 gcall
*call
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
3532 fixup_pt_set (gimple_call_use_set (call
));
3533 fixup_pt_set (gimple_call_clobber_set (call
));
3540 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3541 set_alias_uids (item
->first
, DECL_UID (item
->first
->decl
));
3544 /* Dump function prints all class members to a FILE with an INDENT. */
3547 congruence_class::dump (FILE *file
, unsigned int indent
) const
3549 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3550 id
, members
[0]->get_hash (), members
.length ());
3552 FPUTS_SPACES (file
, indent
+ 2, "");
3553 for (unsigned i
= 0; i
< members
.length (); i
++)
3554 fprintf (file
, "%s ", members
[i
]->node
->dump_asm_name ());
3556 fprintf (file
, "\n");
3559 /* Returns true if there's a member that is used from another group. */
3562 congruence_class::is_class_used (void)
3564 for (unsigned int i
= 0; i
< members
.length (); i
++)
3565 if (members
[i
]->referenced_by_count
)
3571 /* Generate pass summary for IPA ICF pass. */
3574 ipa_icf_generate_summary (void)
3577 optimizer
= new sem_item_optimizer ();
3579 optimizer
->register_hooks ();
3580 optimizer
->parse_funcs_and_vars ();
3583 /* Write pass summary for IPA ICF pass. */
3586 ipa_icf_write_summary (void)
3588 gcc_assert (optimizer
);
3590 optimizer
->write_summary ();
3593 /* Read pass summary for IPA ICF pass. */
3596 ipa_icf_read_summary (void)
3599 optimizer
= new sem_item_optimizer ();
3601 optimizer
->read_summary ();
3602 optimizer
->register_hooks ();
3605 /* Semantic equality execution function. */
3608 ipa_icf_driver (void)
3610 gcc_assert (optimizer
);
3612 bool merged_p
= optimizer
->execute ();
3617 return merged_p
? TODO_remove_functions
: 0;
3620 const pass_data pass_data_ipa_icf
=
3622 IPA_PASS
, /* type */
3624 OPTGROUP_IPA
, /* optinfo_flags */
3625 TV_IPA_ICF
, /* tv_id */
3626 0, /* properties_required */
3627 0, /* properties_provided */
3628 0, /* properties_destroyed */
3629 0, /* todo_flags_start */
3630 0, /* todo_flags_finish */
3633 class pass_ipa_icf
: public ipa_opt_pass_d
3636 pass_ipa_icf (gcc::context
*ctxt
)
3637 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3638 ipa_icf_generate_summary
, /* generate_summary */
3639 ipa_icf_write_summary
, /* write_summary */
3640 ipa_icf_read_summary
, /* read_summary */
3642 write_optimization_summary */
3644 read_optimization_summary */
3645 NULL
, /* stmt_fixup */
3646 0, /* function_transform_todo_flags_start */
3647 NULL
, /* function_transform */
3648 NULL
) /* variable_transform */
3651 /* opt_pass methods: */
3652 bool gate (function
*) final override
3654 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3657 unsigned int execute (function
*) final override
3659 return ipa_icf_driver();
3661 }; // class pass_ipa_icf
3663 } // ipa_icf namespace
3666 make_pass_ipa_icf (gcc::context
*ctxt
)
3668 return new ipa_icf::pass_ipa_icf (ctxt
);
3671 /* Reset all state within ipa-icf.cc so that we can rerun the compiler
3672 within the same process. For use by toplev::finalize. */
3675 ipa_icf_cc_finalize (void)
3677 ipa_icf::optimizer
= NULL
;