1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2020 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 "fold-const.h"
72 #include "gimple-iterator.h"
74 #include "symbol-summary.h"
76 #include "ipa-fnsummary.h"
79 #include "print-tree.h"
80 #include "ipa-utils.h"
81 #include "ipa-icf-gimple.h"
82 #include "fibonacci_heap.h"
84 #include "stor-layout.h"
86 #include "tree-vector-builder.h"
88 using namespace ipa_icf_gimple
;
92 /* Initialization and computation of symtab node hash, there data
93 are propagated later on. */
95 static sem_item_optimizer
*optimizer
= NULL
;
99 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
101 m_references
.create (0);
102 m_interposables
.create (0);
106 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
109 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
111 if (ref
->address_matters_p ())
112 m_references
.safe_push (ref
->referred
);
114 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
116 if (ref
->address_matters_p ())
117 m_references
.safe_push (ref
->referred
);
119 m_interposables
.safe_push (ref
->referred
);
123 if (is_a
<cgraph_node
*> (node
))
125 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
127 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
128 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
129 m_interposables
.safe_push (e
->callee
);
133 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
135 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
136 : item (_item
), index (_index
)
140 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
141 : type (_type
), referenced_by_count (0), m_hash (-1), m_hash_set (false)
146 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
147 bitmap_obstack
*stack
)
148 : type (_type
), node (_node
), referenced_by_count (0), m_hash (-1),
155 /* Add reference to a semantic TARGET. */
158 sem_item::add_reference (ref_map
*refs
,
161 unsigned index
= reference_count
++;
165 = refs
->get_or_insert (new sem_usage_pair (target
, index
), &existed
);
167 bitmap_set_bit (target
->usage_index_bitmap
, index
);
168 refs_set
.add (target
->node
);
169 ++target
->referenced_by_count
;
172 /* Initialize internal data structures. Bitmap STACK is used for
173 bitmap memory allocation process. */
176 sem_item::setup (bitmap_obstack
*stack
)
178 gcc_checking_assert (node
);
181 tree_refs
.create (0);
182 usage_index_bitmap
= BITMAP_ALLOC (stack
);
185 sem_item::~sem_item ()
187 tree_refs
.release ();
189 BITMAP_FREE (usage_index_bitmap
);
192 /* Dump function for debugging purpose. */
195 sem_item::dump (void)
199 fprintf (dump_file
, "[%s] %s (tree:%p)\n", type
== FUNC
? "func" : "var",
200 node
->dump_name (), (void *) node
->decl
);
201 fprintf (dump_file
, " hash: %u\n", get_hash ());
205 /* Return true if target supports alias symbols. */
208 sem_item::target_supports_symbol_aliases_p (void)
210 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
217 void sem_item::set_hash (hashval_t hash
)
223 hash_map
<const_tree
, hashval_t
> sem_item::m_type_hash_cache
;
225 /* Semantic function constructor that uses STACK as bitmap memory stack. */
227 sem_function::sem_function (bitmap_obstack
*stack
)
228 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
231 bb_sorted
.create (0);
234 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
235 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
238 bb_sorted
.create (0);
241 sem_function::~sem_function ()
243 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
244 delete (bb_sorted
[i
]);
247 bb_sorted
.release ();
250 /* Calculates hash value based on a BASIC_BLOCK. */
253 sem_function::get_bb_hash (const sem_bb
*basic_block
)
255 inchash::hash hstate
;
257 hstate
.add_int (basic_block
->nondbg_stmt_count
);
258 hstate
.add_int (basic_block
->edge_count
);
260 return hstate
.end ();
263 /* References independent hash function. */
266 sem_function::get_hash (void)
270 inchash::hash hstate
;
271 hstate
.add_int (177454); /* Random number for function type. */
273 hstate
.add_int (arg_count
);
274 hstate
.add_int (cfg_checksum
);
275 hstate
.add_int (gcode_hash
);
277 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
278 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
280 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
281 hstate
.add_int (bb_sizes
[i
]);
283 /* Add common features of declaration itself. */
284 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
286 (cl_target_option_hash
287 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
288 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
290 (cl_optimization_hash
291 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
292 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
293 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
295 set_hash (hstate
.end ());
301 /* Compare properties of symbols N1 and N2 that does not affect semantics of
302 symbol itself but affects semantics of its references from USED_BY (which
303 may be NULL if it is unknown). If comparison is false, symbols
304 can still be merged but any symbols referring them can't.
306 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
308 TODO: We can also split attributes to those that determine codegen of
309 a function body/variable constructor itself and those that are used when
313 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
318 if (is_a
<cgraph_node
*> (n1
))
320 /* Inline properties matters: we do now want to merge uses of inline
321 function to uses of normal function because inline hint would be lost.
322 We however can merge inline function to noinline because the alias
323 will keep its DECL_DECLARED_INLINE flag.
325 Also ignore inline flag when optimizing for size or when function
326 is known to not be inlinable.
328 TODO: the optimize_size checks can also be assumed to be true if
329 unit has no !optimize_size functions. */
331 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
332 || !opt_for_fn (used_by
->decl
, optimize_size
))
333 && !opt_for_fn (n1
->decl
, optimize_size
)
334 && n1
->get_availability () > AVAIL_INTERPOSABLE
335 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
337 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
338 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
339 return return_false_with_msg
340 ("DECL_DISREGARD_INLINE_LIMITS are different");
342 if (DECL_DECLARED_INLINE_P (n1
->decl
)
343 != DECL_DECLARED_INLINE_P (n2
->decl
))
344 return return_false_with_msg ("inline attributes are different");
347 if (DECL_IS_OPERATOR_NEW_P (n1
->decl
)
348 != DECL_IS_OPERATOR_NEW_P (n2
->decl
))
349 return return_false_with_msg ("operator new flags are different");
352 /* Merging two definitions with a reference to equivalent vtables, but
353 belonging to a different type may result in ipa-polymorphic-call analysis
354 giving a wrong answer about the dynamic type of instance. */
355 if (is_a
<varpool_node
*> (n1
))
357 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
358 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
359 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
360 DECL_CONTEXT (n2
->decl
)))
361 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
362 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
363 return return_false_with_msg
364 ("references to virtual tables cannot be merged");
366 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
367 return return_false_with_msg ("alignment mismatch");
369 /* For functions we compare attributes in equals_wpa, because we do
370 not know what attributes may cause codegen differences, but for
371 variables just compare attributes for references - the codegen
372 for constructors is affected only by those attributes that we lower
373 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
374 if (!attribute_list_equal (DECL_ATTRIBUTES (n1
->decl
),
375 DECL_ATTRIBUTES (n2
->decl
)))
376 return return_false_with_msg ("different var decl attributes");
377 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
378 TREE_TYPE (n2
->decl
)) != 1)
379 return return_false_with_msg ("different var type attributes");
382 /* When matching virtual tables, be sure to also match information
383 relevant for polymorphic call analysis. */
384 if (used_by
&& is_a
<varpool_node
*> (used_by
)
385 && DECL_VIRTUAL_P (used_by
->decl
))
387 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
388 return return_false_with_msg ("virtual flag mismatch");
389 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
390 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
391 return return_false_with_msg ("final flag mismatch");
396 /* Hash properties that are compared by compare_referenced_symbol_properties. */
399 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
400 inchash::hash
&hstate
,
403 if (is_a
<cgraph_node
*> (ref
))
405 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
406 && !opt_for_fn (ref
->decl
, optimize_size
)
407 && !DECL_UNINLINABLE (ref
->decl
))
409 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
410 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
412 hstate
.add_flag (DECL_IS_OPERATOR_NEW_P (ref
->decl
));
414 else if (is_a
<varpool_node
*> (ref
))
416 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
418 hstate
.add_int (DECL_ALIGN (ref
->decl
));
423 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
424 point to a same function. Comparison can be skipped if IGNORED_NODES
425 contains these nodes. ADDRESS indicate if address is taken. */
428 sem_item::compare_symbol_references (
429 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
430 symtab_node
*n1
, symtab_node
*n2
, bool address
)
432 enum availability avail1
, avail2
;
437 /* Never match variable and function. */
438 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
441 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
443 if (address
&& n1
->equal_address_to (n2
) == 1)
445 if (!address
&& n1
->semantically_equivalent_p (n2
))
448 n1
= n1
->ultimate_alias_target (&avail1
);
449 n2
= n2
->ultimate_alias_target (&avail2
);
451 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
452 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
455 return return_false_with_msg ("different references");
458 /* If cgraph edges E1 and E2 are indirect calls, verify that
459 ECF flags are the same. */
461 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
463 if (e1
->indirect_info
&& e2
->indirect_info
)
465 int e1_flags
= e1
->indirect_info
->ecf_flags
;
466 int e2_flags
= e2
->indirect_info
->ecf_flags
;
468 if (e1_flags
!= e2_flags
)
469 return return_false_with_msg ("ICF flags are different");
471 else if (e1
->indirect_info
|| e2
->indirect_info
)
477 /* Return true if parameter I may be used. */
480 sem_function::param_used_p (unsigned int i
)
482 if (ipa_node_params_sum
== NULL
)
485 class ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
487 if (!parms_info
|| vec_safe_length (parms_info
->descriptors
) <= i
)
490 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
493 /* Perform additional check needed to match types function parameters that are
494 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
495 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
498 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
500 /* Be sure that parameters are TBAA compatible. */
501 if (!func_checker::compatible_types_p (parm1
, parm2
))
502 return return_false_with_msg ("parameter type is not compatible");
504 if (POINTER_TYPE_P (parm1
)
505 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
506 return return_false_with_msg ("argument restrict flag mismatch");
508 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
509 if (POINTER_TYPE_P (parm1
)
510 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
511 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
512 return return_false_with_msg ("pointer wrt reference mismatch");
517 /* Fast equality function based on knowledge known in WPA. */
520 sem_function::equals_wpa (sem_item
*item
,
521 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
523 gcc_assert (item
->type
== FUNC
);
524 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
525 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
527 m_compared_func
= static_cast<sem_function
*> (item
);
529 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
530 return return_false_with_msg ("thunk_p mismatch");
532 if (cnode
->thunk
.thunk_p
)
534 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
535 return return_false_with_msg ("thunk fixed_offset mismatch");
536 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
537 return return_false_with_msg ("thunk virtual_value mismatch");
538 if (cnode
->thunk
.indirect_offset
!= cnode2
->thunk
.indirect_offset
)
539 return return_false_with_msg ("thunk indirect_offset mismatch");
540 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
541 return return_false_with_msg ("thunk this_adjusting mismatch");
542 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
543 return return_false_with_msg ("thunk virtual_offset_p mismatch");
546 /* Compare special function DECL attributes. */
547 if (DECL_FUNCTION_PERSONALITY (decl
)
548 != DECL_FUNCTION_PERSONALITY (item
->decl
))
549 return return_false_with_msg ("function personalities are different");
551 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
552 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
553 return return_false_with_msg ("instrument function entry exit "
554 "attributes are different");
556 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
557 return return_false_with_msg ("no stack limit attributes are different");
559 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
560 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
562 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
563 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
565 /* TODO: pure/const flags mostly matters only for references, except for
566 the fact that codegen takes LOOPING flag as a hint that loops are
567 finite. We may arrange the code to always pick leader that has least
568 specified flags and then this can go into comparing symbol properties. */
569 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
570 return return_false_with_msg ("decl_or_type flags are different");
572 /* Do not match polymorphic constructors of different types. They calls
573 type memory location for ipa-polymorphic-call and we do not want
574 it to get confused by wrong type. */
575 if (DECL_CXX_CONSTRUCTOR_P (decl
)
576 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
578 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
579 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
580 else if (!func_checker::compatible_polymorphic_types_p
581 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
582 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
583 return return_false_with_msg ("ctor polymorphic type mismatch");
586 /* Checking function TARGET and OPTIMIZATION flags. */
587 cl_target_option
*tar1
= target_opts_for_fn (decl
);
588 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
590 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
592 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
594 fprintf (dump_file
, "target flags difference");
595 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
598 return return_false_with_msg ("Target flags are different");
601 cl_optimization
*opt1
= opts_for_fn (decl
);
602 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
604 if (opt1
!= opt2
&& !cl_optimization_option_eq (opt1
, opt2
))
606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
608 fprintf (dump_file
, "optimization flags difference");
609 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
612 return return_false_with_msg ("optimization flags are different");
615 /* Result type checking. */
616 if (!func_checker::compatible_types_p
617 (TREE_TYPE (TREE_TYPE (decl
)),
618 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
619 return return_false_with_msg ("result types are different");
621 /* Checking types of arguments. */
622 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
623 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
624 for (unsigned i
= 0; list1
&& list2
;
625 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
627 tree parm1
= TREE_VALUE (list1
);
628 tree parm2
= TREE_VALUE (list2
);
630 /* This guard is here for function pointer with attributes (pr59927.c). */
631 if (!parm1
|| !parm2
)
632 return return_false_with_msg ("NULL argument type");
634 /* Verify that types are compatible to ensure that both functions
635 have same calling conventions. */
636 if (!types_compatible_p (parm1
, parm2
))
637 return return_false_with_msg ("parameter types are not compatible");
639 if (!param_used_p (i
))
642 /* Perform additional checks for used parameters. */
643 if (!compatible_parm_types_p (parm1
, parm2
))
648 return return_false_with_msg ("Mismatched number of parameters");
650 if (node
->num_references () != item
->node
->num_references ())
651 return return_false_with_msg ("different number of references");
653 /* Checking function attributes.
654 This is quadratic in number of attributes */
655 if (comp_type_attributes (TREE_TYPE (decl
),
656 TREE_TYPE (item
->decl
)) != 1)
657 return return_false_with_msg ("different type attributes");
658 if (!attribute_list_equal (DECL_ATTRIBUTES (decl
),
659 DECL_ATTRIBUTES (item
->decl
)))
660 return return_false_with_msg ("different decl attributes");
662 /* The type of THIS pointer type memory location for
663 ipa-polymorphic-call-analysis. */
664 if (opt_for_fn (decl
, flag_devirtualize
)
665 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
666 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
668 && compare_polymorphic_p ())
670 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
671 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
672 if (!func_checker::compatible_polymorphic_types_p
673 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
674 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
675 return return_false_with_msg ("THIS pointer ODR type mismatch");
678 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
679 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
681 item
->node
->iterate_reference (i
, ref2
);
683 if (ref
->use
!= ref2
->use
)
684 return return_false_with_msg ("reference use mismatch");
686 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
688 ref
->address_matters_p ()))
692 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
693 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
697 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
700 if (!compare_edge_flags (e1
, e2
))
703 e1
= e1
->next_callee
;
704 e2
= e2
->next_callee
;
708 return return_false_with_msg ("different number of calls");
710 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
711 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
715 if (!compare_edge_flags (e1
, e2
))
718 e1
= e1
->next_callee
;
719 e2
= e2
->next_callee
;
723 return return_false_with_msg ("different number of indirect calls");
728 /* Update hash by address sensitive references. We iterate over all
729 sensitive references (address_matters_p) and we hash ultimate alias
730 target of these nodes, which can improve a semantic item hash.
732 Also hash in referenced symbols properties. This can be done at any time
733 (as the properties should not change), but it is convenient to do it here
734 while we walk the references anyway. */
737 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
738 sem_item
*> &m_symtab_node_map
)
741 inchash::hash
hstate (get_hash ());
743 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
745 hstate
.add_int (ref
->use
);
746 hash_referenced_symbol_properties (ref
->referred
, hstate
,
747 ref
->use
== IPA_REF_ADDR
);
748 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
749 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
752 if (is_a
<cgraph_node
*> (node
))
754 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
757 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
758 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
760 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
764 set_hash (hstate
.end ());
767 /* Update hash by computed local hash values taken from different
769 TODO: stronger SCC based hashing would be desirable here. */
772 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
773 sem_item
*> &m_symtab_node_map
)
776 inchash::hash
state (get_hash ());
778 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
780 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
782 state
.merge_hash ((*result
)->get_hash ());
787 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
790 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
792 state
.merge_hash ((*result
)->get_hash ());
796 global_hash
= state
.end ();
799 /* Returns true if the item equals to ITEM given as argument. */
802 sem_function::equals (sem_item
*item
,
803 hash_map
<symtab_node
*, sem_item
*> &)
805 gcc_assert (item
->type
== FUNC
);
806 bool eq
= equals_private (item
);
808 if (m_checker
!= NULL
)
814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
816 "Equals called for: %s:%s with result: %s\n\n",
818 item
->node
->dump_name (),
819 eq
? "true" : "false");
824 /* Processes function equality comparison. */
827 sem_function::equals_private (sem_item
*item
)
829 if (item
->type
!= FUNC
)
832 basic_block bb1
, bb2
;
834 edge_iterator ei1
, ei2
;
838 m_compared_func
= static_cast<sem_function
*> (item
);
840 gcc_assert (decl
!= item
->decl
);
842 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
843 || edge_count
!= m_compared_func
->edge_count
844 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
845 return return_false ();
847 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
850 &m_compared_func
->refs_set
);
851 arg1
= DECL_ARGUMENTS (decl
);
852 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
854 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
856 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
857 return return_false_with_msg ("argument types are not compatible");
858 if (!param_used_p (i
))
860 /* Perform additional checks for used parameters. */
861 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
863 if (!m_checker
->compare_decl (arg1
, arg2
))
864 return return_false ();
867 return return_false_with_msg ("Mismatched number of arguments");
869 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
872 /* Fill-up label dictionary. */
873 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
875 m_checker
->parse_labels (bb_sorted
[i
]);
876 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
879 /* Checking all basic blocks. */
880 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
881 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
882 return return_false ();
884 auto_vec
<int> bb_dict
;
886 /* Basic block edges check. */
887 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
889 bb1
= bb_sorted
[i
]->bb
;
890 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
892 ei2
= ei_start (bb2
->preds
);
894 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
898 if (e1
->flags
!= e2
->flags
)
899 return return_false_with_msg ("flags comparison returns false");
901 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
902 return return_false_with_msg ("edge comparison returns false");
904 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
905 return return_false_with_msg ("BB comparison returns false");
907 if (!m_checker
->compare_edge (e1
, e2
))
908 return return_false_with_msg ("edge comparison returns false");
914 /* Basic block PHI nodes comparison. */
915 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
916 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
917 return return_false_with_msg ("PHI node comparison returns false");
922 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
923 Helper for call_for_symbol_thunks_and_aliases. */
926 set_local (cgraph_node
*node
, void *data
)
928 node
->local
= data
!= NULL
;
932 /* TREE_ADDRESSABLE of NODE to true.
933 Helper for call_for_symbol_thunks_and_aliases. */
936 set_addressable (varpool_node
*node
, void *)
938 TREE_ADDRESSABLE (node
->decl
) = 1;
942 /* Clear DECL_RTL of NODE.
943 Helper for call_for_symbol_thunks_and_aliases. */
946 clear_decl_rtl (symtab_node
*node
, void *)
948 SET_DECL_RTL (node
->decl
, NULL
);
952 /* Redirect all callers of N and its aliases to TO. Remove aliases if
953 possible. Return number of redirections made. */
956 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
960 cgraph_edge
*e
= n
->callers
;
964 /* Redirecting thunks to interposable symbols or symbols in other sections
965 may not be supported by target output code. Play safe for now and
966 punt on redirection. */
967 if (!e
->caller
->thunk
.thunk_p
)
969 struct cgraph_edge
*nexte
= e
->next_caller
;
970 e
->redirect_callee (to
);
977 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
979 bool removed
= false;
980 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
982 if ((DECL_COMDAT_GROUP (n
->decl
)
983 && (DECL_COMDAT_GROUP (n
->decl
)
984 == DECL_COMDAT_GROUP (n_alias
->decl
)))
985 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
986 && n
->get_availability () > AVAIL_INTERPOSABLE
))
988 nredirected
+= redirect_all_callers (n_alias
, to
);
989 if (n_alias
->can_remove_if_no_direct_calls_p ()
990 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
992 && !n_alias
->has_aliases_p ())
1001 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1005 sem_function::merge (sem_item
*alias_item
)
1007 gcc_assert (alias_item
->type
== FUNC
);
1009 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1011 cgraph_node
*original
= get_node ();
1012 cgraph_node
*local_original
= NULL
;
1013 cgraph_node
*alias
= alias_func
->get_node ();
1015 bool create_wrapper
= false;
1016 bool create_alias
= false;
1017 bool redirect_callers
= false;
1018 bool remove
= false;
1020 bool original_discardable
= false;
1021 bool original_discarded
= false;
1023 bool original_address_matters
= original
->address_matters_p ();
1024 bool alias_address_matters
= alias
->address_matters_p ();
1026 AUTO_DUMP_SCOPE ("merge",
1027 dump_user_location_t::from_function_decl (decl
));
1029 if (DECL_EXTERNAL (alias
->decl
))
1031 if (dump_enabled_p ())
1032 dump_printf (MSG_MISSED_OPTIMIZATION
,
1033 "Not unifying; alias is external.\n");
1037 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1038 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1040 if (dump_enabled_p ())
1041 dump_printf (MSG_MISSED_OPTIMIZATION
,
1042 "Not unifying; DECL_NO_INLINE_WARNING mismatch.\n");
1046 /* Do not attempt to mix functions from different user sections;
1047 we do not know what user intends with those. */
1048 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1049 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1050 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1052 if (dump_enabled_p ())
1053 dump_printf (MSG_MISSED_OPTIMIZATION
,
1055 "original and alias are in different sections.\n");
1059 if (!original
->in_same_comdat_group_p (alias
)
1060 || original
->comdat_local_p ())
1062 if (dump_enabled_p ())
1063 dump_printf (MSG_MISSED_OPTIMIZATION
,
1064 "Not unifying; alias nor wrapper cannot be created; "
1065 "across comdat group boundary\n");
1069 /* See if original is in a section that can be discarded if the main
1070 symbol is not used. */
1072 if (original
->can_be_discarded_p ())
1073 original_discardable
= true;
1074 /* Also consider case where we have resolution info and we know that
1075 original's definition is not going to be used. In this case we cannot
1076 create alias to original. */
1077 if (node
->resolution
!= LDPR_UNKNOWN
1078 && !decl_binds_to_current_def_p (node
->decl
))
1079 original_discardable
= original_discarded
= true;
1081 /* Creating a symtab alias is the optimal way to merge.
1082 It however cannot be used in the following cases:
1084 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1085 2) if ORIGINAL is in a section that may be discarded by linker or if
1086 it is an external functions where we cannot create an alias
1087 (ORIGINAL_DISCARDABLE)
1088 3) if target do not support symbol aliases.
1089 4) original and alias lie in different comdat groups.
1091 If we cannot produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1092 and/or redirect all callers from ALIAS to ORIGINAL. */
1093 if ((original_address_matters
&& alias_address_matters
)
1094 || (original_discardable
1095 && (!DECL_COMDAT_GROUP (alias
->decl
)
1096 || (DECL_COMDAT_GROUP (alias
->decl
)
1097 != DECL_COMDAT_GROUP (original
->decl
))))
1098 || original_discarded
1099 || !sem_item::target_supports_symbol_aliases_p ()
1100 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1102 /* First see if we can produce wrapper. */
1104 /* Symbol properties that matter for references must be preserved.
1105 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1106 with proper properties. */
1107 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1108 alias
->address_taken
))
1110 if (dump_enabled_p ())
1111 dump_printf (MSG_MISSED_OPTIMIZATION
,
1112 "Wrapper cannot be created because referenced symbol "
1113 "properties mismatch\n");
1115 /* Do not turn function in one comdat group into wrapper to another
1116 comdat group. Other compiler producing the body of the
1117 another comdat group may make opposite decision and with unfortunate
1118 linker choices this may close a loop. */
1119 else if (DECL_COMDAT_GROUP (original
->decl
)
1120 && DECL_COMDAT_GROUP (alias
->decl
)
1121 && (DECL_COMDAT_GROUP (alias
->decl
)
1122 != DECL_COMDAT_GROUP (original
->decl
)))
1124 if (dump_enabled_p ())
1125 dump_printf (MSG_MISSED_OPTIMIZATION
,
1126 "Wrapper cannot be created because of COMDAT\n");
1128 else if (DECL_STATIC_CHAIN (alias
->decl
)
1129 || DECL_STATIC_CHAIN (original
->decl
))
1131 if (dump_enabled_p ())
1132 dump_printf (MSG_MISSED_OPTIMIZATION
,
1133 "Cannot create wrapper of nested function.\n");
1135 /* TODO: We can also deal with variadic functions never calling
1137 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1139 if (dump_enabled_p ())
1140 dump_printf (MSG_MISSED_OPTIMIZATION
,
1141 "cannot create wrapper of stdarg function.\n");
1143 else if (ipa_fn_summaries
1144 && ipa_size_summaries
->get (alias
) != NULL
1145 && ipa_size_summaries
->get (alias
)->self_size
<= 2)
1147 if (dump_enabled_p ())
1148 dump_printf (MSG_MISSED_OPTIMIZATION
, "Wrapper creation is not "
1149 "profitable (function is too small).\n");
1151 /* If user paid attention to mark function noinline, assume it is
1152 somewhat special and do not try to turn it into a wrapper that
1153 cannot be undone by inliner. */
1154 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1156 if (dump_enabled_p ())
1157 dump_printf (MSG_MISSED_OPTIMIZATION
,
1158 "Wrappers are not created for noinline.\n");
1161 create_wrapper
= true;
1163 /* We can redirect local calls in the case both alias and original
1164 are not interposable. */
1166 = alias
->get_availability () > AVAIL_INTERPOSABLE
1167 && original
->get_availability () > AVAIL_INTERPOSABLE
;
1168 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1169 with proper properties. */
1170 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1171 alias
->address_taken
))
1172 redirect_callers
= false;
1174 if (!redirect_callers
&& !create_wrapper
)
1176 if (dump_enabled_p ())
1177 dump_printf (MSG_MISSED_OPTIMIZATION
,
1178 "Not unifying; cannot redirect callers nor "
1179 "produce wrapper\n");
1183 /* Work out the symbol the wrapper should call.
1184 If ORIGINAL is interposable, we need to call a local alias.
1185 Also produce local alias (if possible) as an optimization.
1187 Local aliases cannot be created inside comdat groups because that
1188 prevents inlining. */
1189 if (!original_discardable
&& !original
->get_comdat_group ())
1192 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1194 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1195 local_original
= original
;
1197 /* If we cannot use local alias, fallback to the original
1199 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1200 local_original
= original
;
1202 /* If original is COMDAT local, we cannot really redirect calls outside
1203 of its comdat group to it. */
1204 if (original
->comdat_local_p ())
1205 redirect_callers
= false;
1206 if (!local_original
)
1208 if (dump_enabled_p ())
1209 dump_printf (MSG_MISSED_OPTIMIZATION
,
1210 "Not unifying; cannot produce local alias.\n");
1214 if (!redirect_callers
&& !create_wrapper
)
1216 if (dump_enabled_p ())
1217 dump_printf (MSG_MISSED_OPTIMIZATION
,
1219 "cannot redirect callers nor produce a wrapper\n");
1223 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1225 && !alias
->can_remove_if_no_direct_calls_p ())
1227 if (dump_enabled_p ())
1228 dump_printf (MSG_MISSED_OPTIMIZATION
,
1229 "Not unifying; cannot make wrapper and "
1230 "function has other uses than direct calls\n");
1235 create_alias
= true;
1237 if (redirect_callers
)
1239 int nredirected
= redirect_all_callers (alias
, local_original
);
1243 alias
->icf_merged
= true;
1244 local_original
->icf_merged
= true;
1246 if (dump_enabled_p ())
1247 dump_printf (MSG_NOTE
,
1248 "%i local calls have been "
1249 "redirected.\n", nredirected
);
1252 /* If all callers was redirected, do not produce wrapper. */
1253 if (alias
->can_remove_if_no_direct_calls_p ()
1254 && !DECL_VIRTUAL_P (alias
->decl
)
1255 && !alias
->has_aliases_p ())
1257 create_wrapper
= false;
1260 gcc_assert (!create_alias
);
1262 else if (create_alias
)
1264 alias
->icf_merged
= true;
1266 /* Remove the function's body. */
1267 ipa_merge_profiles (original
, alias
);
1268 symtab
->call_cgraph_removal_hooks (alias
);
1269 alias
->release_body (true);
1271 /* Notice global symbol possibly produced RTL. */
1272 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1275 /* Create the alias. */
1276 cgraph_node::create_alias (alias_func
->decl
, decl
);
1277 alias
->resolve_alias (original
);
1279 original
->call_for_symbol_thunks_and_aliases
1280 (set_local
, (void *)(size_t) original
->local_p (), true);
1282 if (dump_enabled_p ())
1283 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1284 "Unified; Function alias has been created.\n");
1288 gcc_assert (!create_alias
);
1289 alias
->icf_merged
= true;
1290 symtab
->call_cgraph_removal_hooks (alias
);
1291 local_original
->icf_merged
= true;
1293 /* FIXME update local_original counts. */
1294 ipa_merge_profiles (original
, alias
, true);
1295 alias
->create_wrapper (local_original
);
1296 symtab
->call_cgraph_insertion_hooks (alias
);
1298 if (dump_enabled_p ())
1299 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1300 "Unified; Wrapper has been created.\n");
1303 /* It's possible that redirection can hit thunks that block
1304 redirection opportunities. */
1305 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1306 original
->icf_merged
= true;
1308 /* We use merged flag to track cases where COMDAT function is known to be
1309 compatible its callers. If we merged in non-COMDAT, we need to give up
1310 on this optimization. */
1311 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1313 if (dump_enabled_p ())
1314 dump_printf (MSG_NOTE
, "Dropping merged_comdat flag.\n");
1316 local_original
->merged_comdat
= false;
1317 original
->merged_comdat
= false;
1322 ipa_merge_profiles (original
, alias
);
1323 alias
->release_body ();
1325 alias
->body_removed
= true;
1326 alias
->icf_merged
= true;
1327 if (dump_enabled_p ())
1328 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
1329 "Unified; Function body was removed.\n");
1335 /* Semantic item initialization function. */
1338 sem_function::init (ipa_icf_gimple::func_checker
*checker
)
1340 m_checker
= checker
;
1342 get_node ()->get_untransformed_body ();
1344 tree fndecl
= node
->decl
;
1345 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1348 gcc_assert (SSANAMES (func
));
1350 ssa_names_size
= SSANAMES (func
)->length ();
1354 region_tree
= func
->eh
->region_tree
;
1356 /* iterating all function arguments. */
1357 arg_count
= count_formal_params (fndecl
);
1359 edge_count
= n_edges_for_fn (func
);
1360 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1361 if (!cnode
->thunk
.thunk_p
)
1363 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1365 inchash::hash hstate
;
1368 FOR_EACH_BB_FN (bb
, func
)
1370 unsigned nondbg_stmt_count
= 0;
1373 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1375 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1378 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1381 gimple
*stmt
= gsi_stmt (gsi
);
1383 if (gimple_code (stmt
) != GIMPLE_DEBUG
1384 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1386 hash_stmt (stmt
, hstate
);
1387 nondbg_stmt_count
++;
1391 hstate
.commit_flag ();
1392 gcode_hash
= hstate
.end ();
1393 bb_sizes
.safe_push (nondbg_stmt_count
);
1395 /* Inserting basic block to hash table. */
1396 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1397 EDGE_COUNT (bb
->preds
)
1398 + EDGE_COUNT (bb
->succs
));
1400 bb_sorted
.safe_push (semantic_bb
);
1406 inchash::hash hstate
;
1407 hstate
.add_hwi (cnode
->thunk
.fixed_offset
);
1408 hstate
.add_hwi (cnode
->thunk
.virtual_value
);
1409 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1410 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1411 gcode_hash
= hstate
.end ();
1417 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1420 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1422 enum gimple_code code
= gimple_code (stmt
);
1424 hstate
.add_int (code
);
1429 m_checker
->hash_operand (gimple_switch_index (as_a
<gswitch
*> (stmt
)),
1433 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1434 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1435 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1437 m_checker
->hash_operand (gimple_assign_rhs1 (stmt
), hstate
, 0);
1438 m_checker
->hash_operand (gimple_assign_rhs2 (stmt
), hstate
, 0);
1439 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1440 m_checker
->hash_operand (gimple_assign_rhs3 (stmt
), hstate
, 0);
1441 m_checker
->hash_operand (gimple_assign_lhs (stmt
), hstate
, 0);
1449 /* All these statements are equivalent if their operands are. */
1450 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1451 m_checker
->hash_operand (gimple_op (stmt
, i
), hstate
, 0);
1452 /* Consider nocf_check attribute in hash as it affects code
1454 if (code
== GIMPLE_CALL
1455 && flag_cf_protection
& CF_BRANCH
)
1456 hstate
.add_flag (gimple_call_nocf_check_p (as_a
<gcall
*> (stmt
)));
1463 /* Return true if polymorphic comparison must be processed. */
1466 sem_function::compare_polymorphic_p (void)
1468 struct cgraph_edge
*e
;
1470 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1472 if (get_node ()->indirect_calls
!= NULL
)
1474 /* TODO: We can do simple propagation determining what calls may lead to
1475 a polymorphic call. */
1476 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1477 if (e
->callee
->definition
1478 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1483 /* For a given call graph NODE, the function constructs new
1484 semantic function item. */
1487 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
,
1488 func_checker
*checker
)
1490 tree fndecl
= node
->decl
;
1491 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1493 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1496 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1499 if (lookup_attribute_by_prefix ("oacc ",
1500 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1504 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1505 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1508 sem_function
*f
= new sem_function (node
, stack
);
1514 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1515 return true if phi nodes are semantically equivalent in these blocks . */
1518 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1520 gphi_iterator si1
, si2
;
1522 unsigned size1
, size2
, i
;
1526 gcc_assert (bb1
!= NULL
);
1527 gcc_assert (bb2
!= NULL
);
1529 si2
= gsi_start_nonvirtual_phis (bb2
);
1530 for (si1
= gsi_start_nonvirtual_phis (bb1
); !gsi_end_p (si1
);
1531 gsi_next_nonvirtual_phi (&si1
))
1533 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1536 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1537 return return_false();
1542 tree phi_result1
= gimple_phi_result (phi1
);
1543 tree phi_result2
= gimple_phi_result (phi2
);
1545 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1546 return return_false_with_msg ("PHI results are different");
1548 size1
= gimple_phi_num_args (phi1
);
1549 size2
= gimple_phi_num_args (phi2
);
1552 return return_false ();
1554 for (i
= 0; i
< size1
; ++i
)
1556 t1
= gimple_phi_arg (phi1
, i
)->def
;
1557 t2
= gimple_phi_arg (phi2
, i
)->def
;
1559 if (!m_checker
->compare_operand (t1
, t2
))
1560 return return_false ();
1562 e1
= gimple_phi_arg_edge (phi1
, i
);
1563 e2
= gimple_phi_arg_edge (phi2
, i
);
1565 if (!m_checker
->compare_edge (e1
, e2
))
1566 return return_false ();
1569 gsi_next_nonvirtual_phi (&si2
);
1575 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1576 corresponds to TARGET. */
1579 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1584 if (bb_dict
->length () <= (unsigned)source
)
1585 bb_dict
->safe_grow_cleared (source
+ 1);
1587 if ((*bb_dict
)[source
] == 0)
1589 (*bb_dict
)[source
] = target
;
1593 return (*bb_dict
)[source
] == target
;
1596 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1600 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1601 : sem_item (VAR
, node
, stack
)
1603 gcc_checking_assert (node
);
1604 gcc_checking_assert (get_node ());
1607 /* Fast equality function based on knowledge known in WPA. */
1610 sem_variable::equals_wpa (sem_item
*item
,
1611 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1613 gcc_assert (item
->type
== VAR
);
1615 if (node
->num_references () != item
->node
->num_references ())
1616 return return_false_with_msg ("different number of references");
1618 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1619 return return_false_with_msg ("TLS model");
1621 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1622 alignment out of all aliases. */
1624 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1625 return return_false_with_msg ("Virtual flag mismatch");
1627 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1628 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1629 || !operand_equal_p (DECL_SIZE (decl
),
1630 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1631 return return_false_with_msg ("size mismatch");
1633 /* Do not attempt to mix data from different user sections;
1634 we do not know what user intends with those. */
1635 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1636 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1637 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1638 return return_false_with_msg ("user section mismatch");
1640 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1641 return return_false_with_msg ("text section");
1643 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1644 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1646 item
->node
->iterate_reference (i
, ref2
);
1648 if (ref
->use
!= ref2
->use
)
1649 return return_false_with_msg ("reference use mismatch");
1651 if (!compare_symbol_references (ignored_nodes
,
1652 ref
->referred
, ref2
->referred
,
1653 ref
->address_matters_p ()))
1660 /* Returns true if the item equals to ITEM given as argument. */
1663 sem_variable::equals (sem_item
*item
,
1664 hash_map
<symtab_node
*, sem_item
*> &)
1666 gcc_assert (item
->type
== VAR
);
1669 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1670 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1671 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1672 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1674 /* As seen in PR ipa/65303 we have to compare variables types. */
1675 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1676 TREE_TYPE (item
->decl
)))
1677 return return_false_with_msg ("variables types are different");
1679 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1680 DECL_INITIAL (item
->node
->decl
));
1681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1683 "Equals called for vars: %s:%s with result: %s\n\n",
1684 node
->dump_name (), item
->node
->dump_name (),
1685 ret
? "true" : "false");
1690 /* Compares trees T1 and T2 for semantic equality. */
1693 sem_variable::equals (tree t1
, tree t2
)
1696 return return_with_debug (t1
== t2
);
1699 tree_code tc1
= TREE_CODE (t1
);
1700 tree_code tc2
= TREE_CODE (t2
);
1703 return return_false_with_msg ("TREE_CODE mismatch");
1709 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1710 unsigned HOST_WIDE_INT idx
;
1712 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1713 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1714 return return_false_with_msg ("constructor type mismatch");
1716 if (typecode
== ARRAY_TYPE
)
1718 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1719 /* For arrays, check that the sizes all match. */
1720 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1722 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1723 return return_false_with_msg ("constructor array size mismatch");
1725 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1727 return return_false_with_msg ("constructor type incompatible");
1729 v1
= CONSTRUCTOR_ELTS (t1
);
1730 v2
= CONSTRUCTOR_ELTS (t2
);
1731 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1732 return return_false_with_msg ("constructor number of elts mismatch");
1734 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1736 constructor_elt
*c1
= &(*v1
)[idx
];
1737 constructor_elt
*c2
= &(*v2
)[idx
];
1739 /* Check that each value is the same... */
1740 if (!sem_variable::equals (c1
->value
, c2
->value
))
1742 /* ... and that they apply to the same fields! */
1743 if (!sem_variable::equals (c1
->index
, c2
->index
))
1750 tree x1
= TREE_OPERAND (t1
, 0);
1751 tree x2
= TREE_OPERAND (t2
, 0);
1752 tree y1
= TREE_OPERAND (t1
, 1);
1753 tree y2
= TREE_OPERAND (t2
, 1);
1755 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1756 return return_false ();
1758 /* Type of the offset on MEM_REF does not matter. */
1759 return return_with_debug (sem_variable::equals (x1
, x2
)
1760 && known_eq (wi::to_poly_offset (y1
),
1761 wi::to_poly_offset (y2
)));
1766 tree op1
= TREE_OPERAND (t1
, 0);
1767 tree op2
= TREE_OPERAND (t2
, 0);
1768 return sem_variable::equals (op1
, op2
);
1770 /* References to other vars/decls are compared using ipa-ref. */
1773 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1775 return return_false_with_msg ("Declaration mismatch");
1777 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1778 need to process its VAR/FUNCTION references without relying on ipa-ref
1782 return return_false_with_msg ("Declaration mismatch");
1784 /* Integer constants are the same only if the same width of type. */
1785 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1786 return return_false_with_msg ("INTEGER_CST precision mismatch");
1787 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1788 return return_false_with_msg ("INTEGER_CST mode mismatch");
1789 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1791 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1792 return return_false_with_msg ("STRING_CST mode mismatch");
1793 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1794 return return_false_with_msg ("STRING_CST length mismatch");
1795 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1796 TREE_STRING_LENGTH (t1
)))
1797 return return_false_with_msg ("STRING_CST mismatch");
1800 /* Fixed constants are the same only if the same width of type. */
1801 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1802 return return_false_with_msg ("FIXED_CST precision mismatch");
1804 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1805 TREE_FIXED_CST (t2
)));
1807 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1808 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1810 /* Real constants are the same only if the same width of type. */
1811 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1812 return return_false_with_msg ("REAL_CST precision mismatch");
1813 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
1814 &TREE_REAL_CST (t2
)));
1817 if (maybe_ne (VECTOR_CST_NELTS (t1
), VECTOR_CST_NELTS (t2
)))
1818 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1821 = tree_vector_builder::binary_encoded_nelts (t1
, t2
);
1822 for (unsigned int i
= 0; i
< count
; ++i
)
1823 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1
, i
),
1824 VECTOR_CST_ENCODED_ELT (t2
, i
)))
1830 case ARRAY_RANGE_REF
:
1832 tree x1
= TREE_OPERAND (t1
, 0);
1833 tree x2
= TREE_OPERAND (t2
, 0);
1834 tree y1
= TREE_OPERAND (t1
, 1);
1835 tree y2
= TREE_OPERAND (t2
, 1);
1837 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1839 if (!sem_variable::equals (array_ref_low_bound (t1
),
1840 array_ref_low_bound (t2
)))
1842 if (!sem_variable::equals (array_ref_element_size (t1
),
1843 array_ref_element_size (t2
)))
1849 case POINTER_PLUS_EXPR
:
1854 tree x1
= TREE_OPERAND (t1
, 0);
1855 tree x2
= TREE_OPERAND (t2
, 0);
1856 tree y1
= TREE_OPERAND (t1
, 1);
1857 tree y2
= TREE_OPERAND (t2
, 1);
1859 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1863 case VIEW_CONVERT_EXPR
:
1864 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1865 return return_false ();
1866 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1868 return return_false_with_msg ("ERROR_MARK");
1870 return return_false_with_msg ("Unknown TREE code reached");
1874 /* Parser function that visits a varpool NODE. */
1877 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
,
1878 func_checker
*checker
)
1880 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1884 sem_variable
*v
= new sem_variable (node
, stack
);
1890 /* Semantic variable initialization function. */
1893 sem_variable::init (ipa_icf_gimple::func_checker
*checker
)
1895 decl
= get_node ()->decl
;
1897 /* All WPA streamed in symbols should have their hashes computed at compile
1898 time. At this point, the constructor may not be in memory at all.
1899 DECL_INITIAL (decl) would be error_mark_node in that case. */
1902 gcc_assert (!node
->lto_file_data
);
1903 inchash::hash hstate
;
1904 hstate
.add_int (456346417);
1905 checker
->hash_operand (DECL_INITIAL (decl
), hstate
, 0);
1906 set_hash (hstate
.end ());
1910 /* References independent hash function. */
1913 sem_variable::get_hash (void)
1915 gcc_checking_assert (m_hash_set
);
1919 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1923 sem_variable::merge (sem_item
*alias_item
)
1925 gcc_assert (alias_item
->type
== VAR
);
1927 AUTO_DUMP_SCOPE ("merge",
1928 dump_user_location_t::from_function_decl (decl
));
1929 if (!sem_item::target_supports_symbol_aliases_p ())
1931 if (dump_enabled_p ())
1932 dump_printf (MSG_MISSED_OPTIMIZATION
, "Not unifying; "
1933 "Symbol aliases are not supported by target\n");
1937 if (DECL_EXTERNAL (alias_item
->decl
))
1939 if (dump_enabled_p ())
1940 dump_printf (MSG_MISSED_OPTIMIZATION
,
1941 "Not unifying; alias is external.\n");
1945 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1947 varpool_node
*original
= get_node ();
1948 varpool_node
*alias
= alias_var
->get_node ();
1949 bool original_discardable
= false;
1951 bool alias_address_matters
= alias
->address_matters_p ();
1953 /* See if original is in a section that can be discarded if the main
1955 Also consider case where we have resolution info and we know that
1956 original's definition is not going to be used. In this case we cannot
1957 create alias to original. */
1958 if (original
->can_be_discarded_p ()
1959 || (node
->resolution
!= LDPR_UNKNOWN
1960 && !decl_binds_to_current_def_p (node
->decl
)))
1961 original_discardable
= true;
1963 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1965 /* Constant pool machinery is not quite ready for aliases.
1966 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1967 For LTO merging does not happen that is an important missing feature.
1968 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1969 flag is dropped and non-local symbol name is assigned. */
1970 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1971 || DECL_IN_CONSTANT_POOL (original
->decl
))
1973 if (dump_enabled_p ())
1974 dump_printf (MSG_MISSED_OPTIMIZATION
,
1975 "Not unifying; constant pool variables.\n");
1979 /* Do not attempt to mix functions from different user sections;
1980 we do not know what user intends with those. */
1981 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1982 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1983 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1985 if (dump_enabled_p ())
1986 dump_printf (MSG_MISSED_OPTIMIZATION
,
1988 "original and alias are in different sections.\n");
1992 /* We cannot merge if address comparison matters. */
1993 if (alias_address_matters
&& flag_merge_constants
< 2)
1995 if (dump_enabled_p ())
1996 dump_printf (MSG_MISSED_OPTIMIZATION
,
1997 "Not unifying; address of original may be compared.\n");
2001 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2003 if (dump_enabled_p ())
2004 dump_printf (MSG_MISSED_OPTIMIZATION
,
2006 "original and alias have incompatible alignments\n");
2011 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2013 if (dump_enabled_p ())
2014 dump_printf (MSG_MISSED_OPTIMIZATION
,
2015 "Not unifying; alias cannot be created; "
2016 "across comdat group boundary\n");
2021 if (original_discardable
)
2023 if (dump_enabled_p ())
2024 dump_printf (MSG_MISSED_OPTIMIZATION
,
2025 "Not unifying; alias cannot be created; "
2026 "target is discardable\n");
2032 gcc_assert (!original
->alias
);
2033 gcc_assert (!alias
->alias
);
2035 alias
->analyzed
= false;
2037 DECL_INITIAL (alias
->decl
) = NULL
;
2038 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2040 alias
->remove_all_references ();
2041 if (TREE_ADDRESSABLE (alias
->decl
))
2042 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2044 varpool_node::create_alias (alias_var
->decl
, decl
);
2045 alias
->resolve_alias (original
);
2047 if (dump_enabled_p ())
2048 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
2049 "Unified; Variable alias has been created.\n");
2055 /* Dump symbol to FILE. */
2058 sem_variable::dump_to_file (FILE *file
)
2062 print_node (file
, "", decl
, 0);
2063 fprintf (file
, "\n\n");
2066 unsigned int sem_item_optimizer::class_id
= 0;
2068 sem_item_optimizer::sem_item_optimizer ()
2069 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2070 m_varpool_node_hooks (NULL
), m_merged_variables (), m_references ()
2073 bitmap_obstack_initialize (&m_bmstack
);
2076 sem_item_optimizer::~sem_item_optimizer ()
2078 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2082 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2083 it
!= m_classes
.end (); ++it
)
2085 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2086 delete (*it
)->classes
[i
];
2088 (*it
)->classes
.release ();
2094 bitmap_obstack_release (&m_bmstack
);
2095 m_merged_variables
.release ();
2098 /* Write IPA ICF summary for symbols. */
2101 sem_item_optimizer::write_summary (void)
2103 unsigned int count
= 0;
2105 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2106 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2109 /* Calculate number of symbols to be serialized. */
2110 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2112 lsei_next_in_partition (&lsei
))
2114 symtab_node
*node
= lsei_node (lsei
);
2116 if (m_symtab_node_map
.get (node
))
2120 streamer_write_uhwi (ob
, count
);
2122 /* Process all of the symbols. */
2123 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2125 lsei_next_in_partition (&lsei
))
2127 symtab_node
*node
= lsei_node (lsei
);
2129 sem_item
**item
= m_symtab_node_map
.get (node
);
2133 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2134 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2136 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2140 streamer_write_char_stream (ob
->main_stream
, 0);
2141 produce_asm (ob
, NULL
);
2142 destroy_output_block (ob
);
2145 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2146 contains LEN bytes. */
2149 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2150 const char *data
, size_t len
)
2152 const lto_function_header
*header
2153 = (const lto_function_header
*) data
;
2154 const int cfg_offset
= sizeof (lto_function_header
);
2155 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2156 const int string_offset
= main_offset
+ header
->main_size
;
2161 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2162 header
->main_size
, file_data
->mode_table
);
2165 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2166 header
->string_size
, vNULL
);
2168 count
= streamer_read_uhwi (&ib_main
);
2170 for (i
= 0; i
< count
; i
++)
2174 lto_symtab_encoder_t encoder
;
2176 index
= streamer_read_uhwi (&ib_main
);
2177 encoder
= file_data
->symtab_node_encoder
;
2178 node
= lto_symtab_encoder_deref (encoder
, index
);
2180 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2181 gcc_assert (node
->definition
);
2183 if (is_a
<cgraph_node
*> (node
))
2185 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2187 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2188 fn
->set_hash (hash
);
2189 m_items
.safe_push (fn
);
2193 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2195 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2196 var
->set_hash (hash
);
2197 m_items
.safe_push (var
);
2201 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2203 lto_data_in_delete (data_in
);
2206 /* Read IPA ICF summary for symbols. */
2209 sem_item_optimizer::read_summary (void)
2211 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2212 lto_file_decl_data
*file_data
;
2215 while ((file_data
= file_data_vec
[j
++]))
2219 = lto_get_summary_section_data (file_data
, LTO_section_ipa_icf
, &len
);
2221 read_section (file_data
, data
, len
);
2225 /* Register callgraph and varpool hooks. */
2228 sem_item_optimizer::register_hooks (void)
2230 if (!m_cgraph_node_hooks
)
2231 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2232 (&sem_item_optimizer::cgraph_removal_hook
, this);
2234 if (!m_varpool_node_hooks
)
2235 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2236 (&sem_item_optimizer::varpool_removal_hook
, this);
2239 /* Unregister callgraph and varpool hooks. */
2242 sem_item_optimizer::unregister_hooks (void)
2244 if (m_cgraph_node_hooks
)
2245 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2247 if (m_varpool_node_hooks
)
2248 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2251 /* Adds a CLS to hashtable associated by hash value. */
2254 sem_item_optimizer::add_class (congruence_class
*cls
)
2256 gcc_assert (cls
->members
.length ());
2258 congruence_class_group
*group
2259 = get_group_by_hash (cls
->members
[0]->get_hash (),
2260 cls
->members
[0]->type
);
2261 group
->classes
.safe_push (cls
);
2264 /* Gets a congruence class group based on given HASH value and TYPE. */
2266 congruence_class_group
*
2267 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2269 congruence_class_group
*item
= XNEW (congruence_class_group
);
2273 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2279 item
->classes
.create (1);
2286 /* Callgraph removal hook called for a NODE with a custom DATA. */
2289 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2291 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2292 optimizer
->remove_symtab_node (node
);
2295 /* Varpool removal hook called for a NODE with a custom DATA. */
2298 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2300 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2301 optimizer
->remove_symtab_node (node
);
2304 /* Remove symtab NODE triggered by symtab removal hooks. */
2307 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2309 gcc_assert (m_classes
.is_empty ());
2311 m_removed_items_set
.add (node
);
2315 sem_item_optimizer::remove_item (sem_item
*item
)
2317 if (m_symtab_node_map
.get (item
->node
))
2318 m_symtab_node_map
.remove (item
->node
);
2322 /* Removes all callgraph and varpool nodes that are marked by symtab
2326 sem_item_optimizer::filter_removed_items (void)
2328 auto_vec
<sem_item
*> filtered
;
2330 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2332 sem_item
*item
= m_items
[i
];
2334 if (m_removed_items_set
.contains (item
->node
))
2340 if (item
->type
== FUNC
)
2342 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2344 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2347 filtered
.safe_push (item
);
2351 if (!flag_ipa_icf_variables
)
2355 /* Filter out non-readonly variables. */
2356 tree decl
= item
->decl
;
2357 if (TREE_READONLY (decl
))
2358 filtered
.safe_push (item
);
2365 /* Clean-up of released semantic items. */
2368 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2369 m_items
.safe_push (filtered
[i
]);
2372 /* Optimizer entry point which returns true in case it processes
2373 a merge operation. True is returned if there's a merge operation
2377 sem_item_optimizer::execute (void)
2379 filter_removed_items ();
2380 unregister_hooks ();
2383 update_hash_by_addr_refs ();
2384 build_hash_based_classes ();
2387 fprintf (dump_file
, "Dump after hash based groups\n");
2388 dump_cong_classes ();
2390 subdivide_classes_by_equality (true);
2393 fprintf (dump_file
, "Dump after WPA based types groups\n");
2395 dump_cong_classes ();
2397 process_cong_reduction ();
2398 checking_verify_classes ();
2401 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2403 dump_cong_classes ();
2405 unsigned int loaded_symbols
= parse_nonsingleton_classes ();
2406 subdivide_classes_by_equality ();
2409 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2411 dump_cong_classes ();
2413 unsigned int prev_class_count
= m_classes_count
;
2415 process_cong_reduction ();
2416 dump_cong_classes ();
2417 checking_verify_classes ();
2418 bool merged_p
= merge_classes (prev_class_count
, loaded_symbols
);
2420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2421 symtab
->dump (dump_file
);
2426 /* Function responsible for visiting all potential functions and
2427 read-only variables that can be merged. */
2430 sem_item_optimizer::parse_funcs_and_vars (void)
2434 /* Create dummy func_checker for hashing purpose. */
2435 func_checker checker
;
2437 if (flag_ipa_icf_functions
)
2438 FOR_EACH_DEFINED_FUNCTION (cnode
)
2440 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
, &checker
);
2443 m_items
.safe_push (f
);
2444 m_symtab_node_map
.put (cnode
, f
);
2448 varpool_node
*vnode
;
2450 if (flag_ipa_icf_variables
)
2451 FOR_EACH_DEFINED_VARIABLE (vnode
)
2453 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
, &checker
);
2457 m_items
.safe_push (v
);
2458 m_symtab_node_map
.put (vnode
, v
);
2463 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2466 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2468 item
->index_in_class
= cls
->members
.length ();
2469 cls
->members
.safe_push (item
);
2470 cls
->referenced_by_count
+= item
->referenced_by_count
;
2474 /* For each semantic item, append hash values of references. */
2477 sem_item_optimizer::update_hash_by_addr_refs ()
2479 /* First, append to hash sensitive references and class type if it need to
2480 be matched for ODR. */
2481 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2483 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2484 if (m_items
[i
]->type
== FUNC
)
2486 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2487 && contains_polymorphic_type_p
2488 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2489 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2490 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2491 && static_cast<sem_function
*> (m_items
[i
])
2492 ->compare_polymorphic_p ())))
2495 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2496 inchash::hash
hstate (m_items
[i
]->get_hash ());
2498 if (TYPE_NAME (class_type
)
2499 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2501 (IDENTIFIER_HASH_VALUE
2502 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2504 m_items
[i
]->set_hash (hstate
.end ());
2509 /* Once all symbols have enhanced hash value, we can append
2510 hash values of symbols that are seen by IPA ICF and are
2511 references by a semantic item. Newly computed values
2512 are saved to global_hash member variable. */
2513 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2514 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2516 /* Global hash value replace current hash values. */
2517 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2518 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2521 /* Congruence classes are built by hash value. */
2524 sem_item_optimizer::build_hash_based_classes (void)
2526 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2528 sem_item
*item
= m_items
[i
];
2530 congruence_class_group
*group
2531 = get_group_by_hash (item
->get_hash (), item
->type
);
2533 if (!group
->classes
.length ())
2536 group
->classes
.safe_push (new congruence_class (class_id
++));
2539 add_item_to_class (group
->classes
[0], item
);
2543 /* Build references according to call graph. */
2546 sem_item_optimizer::build_graph (void)
2548 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2550 sem_item
*item
= m_items
[i
];
2551 m_symtab_node_map
.put (item
->node
, item
);
2553 /* Initialize hash values if we are not in LTO mode. */
2558 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2560 sem_item
*item
= m_items
[i
];
2562 if (item
->type
== FUNC
)
2564 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2566 cgraph_edge
*e
= cnode
->callees
;
2569 sem_item
**slot
= m_symtab_node_map
.get
2570 (e
->callee
->ultimate_alias_target ());
2572 item
->add_reference (&m_references
, *slot
);
2578 ipa_ref
*ref
= NULL
;
2579 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2581 sem_item
**slot
= m_symtab_node_map
.get
2582 (ref
->referred
->ultimate_alias_target ());
2584 item
->add_reference (&m_references
, *slot
);
2589 /* Semantic items in classes having more than one element and initialized.
2590 In case of WPA, we load function body. */
2593 sem_item_optimizer::parse_nonsingleton_classes (void)
2595 unsigned int counter
= 0;
2597 /* Create dummy func_checker for hashing purpose. */
2598 func_checker checker
;
2600 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2601 if (m_items
[i
]->cls
->members
.length () > 1)
2603 m_items
[i
]->init (&checker
);
2609 float f
= m_items
.length () ? 100.0f
* counter
/ m_items
.length () : 0.0f
;
2610 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", counter
, f
);
2616 /* Equality function for semantic items is used to subdivide existing
2617 classes. If IN_WPA, fast equality function is invoked. */
2620 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2622 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2623 it
!= m_classes
.end (); ++it
)
2625 unsigned int class_count
= (*it
)->classes
.length ();
2627 for (unsigned i
= 0; i
< class_count
; i
++)
2629 congruence_class
*c
= (*it
)->classes
[i
];
2631 if (c
->members
.length() > 1)
2633 auto_vec
<sem_item
*> new_vector
;
2635 sem_item
*first
= c
->members
[0];
2636 new_vector
.safe_push (first
);
2638 unsigned class_split_first
= (*it
)->classes
.length ();
2640 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2642 sem_item
*item
= c
->members
[j
];
2645 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2646 : first
->equals (item
, m_symtab_node_map
);
2649 new_vector
.safe_push (item
);
2652 bool integrated
= false;
2654 for (unsigned k
= class_split_first
;
2655 k
< (*it
)->classes
.length (); k
++)
2657 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2659 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2660 : x
->equals (item
, m_symtab_node_map
);
2665 add_item_to_class ((*it
)->classes
[k
], item
);
2674 = new congruence_class (class_id
++);
2676 add_item_to_class (c
, item
);
2678 (*it
)->classes
.safe_push (c
);
2683 // We replace newly created new_vector for the class we've just
2685 c
->members
.release ();
2686 c
->members
.create (new_vector
.length ());
2688 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2689 add_item_to_class (c
, new_vector
[j
]);
2694 checking_verify_classes ();
2697 /* Subdivide classes by address references that members of the class
2698 reference. Example can be a pair of functions that have an address
2699 taken from a function. If these addresses are different the class
2703 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2705 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2707 unsigned newly_created_classes
= 0;
2709 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2710 it
!= m_classes
.end (); ++it
)
2712 unsigned int class_count
= (*it
)->classes
.length ();
2713 auto_vec
<congruence_class
*> new_classes
;
2715 for (unsigned i
= 0; i
< class_count
; i
++)
2717 congruence_class
*c
= (*it
)->classes
[i
];
2719 if (c
->members
.length() > 1)
2721 subdivide_hash_map split_map
;
2723 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2725 sem_item
*source_node
= c
->members
[j
];
2727 symbol_compare_collection
*collection
2728 = new symbol_compare_collection (source_node
->node
);
2731 vec
<sem_item
*> *slot
2732 = &split_map
.get_or_insert (collection
, &existed
);
2733 gcc_checking_assert (slot
);
2735 slot
->safe_push (source_node
);
2741 /* If the map contains more than one key, we have to split
2742 the map appropriately. */
2743 if (split_map
.elements () != 1)
2745 bool first_class
= true;
2747 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2748 it2
!= split_map
.end (); ++it2
)
2750 congruence_class
*new_cls
;
2751 new_cls
= new congruence_class (class_id
++);
2753 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2754 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2756 worklist_push (new_cls
);
2757 newly_created_classes
++;
2761 (*it
)->classes
[i
] = new_cls
;
2762 first_class
= false;
2766 new_classes
.safe_push (new_cls
);
2772 /* Release memory. */
2773 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2774 it2
!= split_map
.end (); ++it2
)
2776 delete (*it2
).first
;
2777 (*it2
).second
.release ();
2782 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2783 (*it
)->classes
.safe_push (new_classes
[i
]);
2786 return newly_created_classes
;
2789 /* Verify congruence classes, if checking is enabled. */
2792 sem_item_optimizer::checking_verify_classes (void)
2798 /* Verify congruence classes. */
2801 sem_item_optimizer::verify_classes (void)
2803 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2804 it
!= m_classes
.end (); ++it
)
2806 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2808 congruence_class
*cls
= (*it
)->classes
[i
];
2811 gcc_assert (cls
->members
.length () > 0);
2813 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2815 sem_item
*item
= cls
->members
[j
];
2818 gcc_assert (item
->cls
== cls
);
2824 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2825 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2826 but unused argument. */
2829 sem_item_optimizer::release_split_map (congruence_class
* const &,
2830 bitmap
const &b
, traverse_split_pair
*)
2839 /* Process split operation for a class given as pointer CLS_PTR,
2840 where bitmap B splits congruence class members. DATA is used
2841 as argument of split pair. */
2844 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2846 traverse_split_pair
*pair
)
2848 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2849 const congruence_class
*splitter_cls
= pair
->cls
;
2851 /* If counted bits are greater than zero and less than the number of members
2852 a group will be splitted. */
2853 unsigned popcount
= bitmap_count_bits (b
);
2855 if (popcount
> 0 && popcount
< cls
->members
.length ())
2857 auto_vec
<congruence_class
*, 2> newclasses
;
2858 newclasses
.quick_push (new congruence_class (class_id
++));
2859 newclasses
.quick_push (new congruence_class (class_id
++));
2861 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2863 int target
= bitmap_bit_p (b
, i
);
2864 congruence_class
*tc
= newclasses
[target
];
2866 add_item_to_class (tc
, cls
->members
[i
]);
2871 for (unsigned int i
= 0; i
< 2; i
++)
2872 gcc_assert (newclasses
[i
]->members
.length ());
2875 if (splitter_cls
== cls
)
2876 optimizer
->splitter_class_removed
= true;
2878 /* Remove old class from worklist if presented. */
2879 bool in_worklist
= cls
->in_worklist
;
2882 cls
->in_worklist
= false;
2884 congruence_class_group g
;
2885 g
.hash
= cls
->members
[0]->get_hash ();
2886 g
.type
= cls
->members
[0]->type
;
2888 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
2890 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2891 if (slot
->classes
[i
] == cls
)
2893 slot
->classes
.ordered_remove (i
);
2897 /* New class will be inserted and integrated to work list. */
2898 for (unsigned int i
= 0; i
< 2; i
++)
2899 optimizer
->add_class (newclasses
[i
]);
2901 /* Two classes replace one, so that increment just by one. */
2902 optimizer
->m_classes_count
++;
2904 /* If OLD class was presented in the worklist, we remove the class
2905 and replace it will both newly created classes. */
2907 for (unsigned int i
= 0; i
< 2; i
++)
2908 optimizer
->worklist_push (newclasses
[i
]);
2909 else /* Just smaller class is inserted. */
2911 unsigned int smaller_index
2912 = (newclasses
[0]->members
.length ()
2913 < newclasses
[1]->members
.length ()
2915 optimizer
->worklist_push (newclasses
[smaller_index
]);
2918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2920 fprintf (dump_file
, " congruence class splitted:\n");
2921 cls
->dump (dump_file
, 4);
2923 fprintf (dump_file
, " newly created groups:\n");
2924 for (unsigned int i
= 0; i
< 2; i
++)
2925 newclasses
[i
]->dump (dump_file
, 4);
2928 /* Release class if not presented in work list. */
2938 /* Compare function for sorting pairs in do_congruence_step_f. */
2941 sem_item_optimizer::sort_congruence_split (const void *a_
, const void *b_
)
2943 const std::pair
<congruence_class
*, bitmap
> *a
2944 = (const std::pair
<congruence_class
*, bitmap
> *)a_
;
2945 const std::pair
<congruence_class
*, bitmap
> *b
2946 = (const std::pair
<congruence_class
*, bitmap
> *)b_
;
2947 if (a
->first
->id
< b
->first
->id
)
2949 else if (a
->first
->id
> b
->first
->id
)
2954 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2955 Bitmap stack BMSTACK is used for bitmap allocation. */
2958 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2961 hash_map
<congruence_class
*, bitmap
> split_map
;
2963 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2965 sem_item
*item
= cls
->members
[i
];
2966 sem_usage_pair
needle (item
, index
);
2967 vec
<sem_item
*> *callers
= m_references
.get (&needle
);
2968 if (callers
== NULL
)
2971 for (unsigned int j
= 0; j
< callers
->length (); j
++)
2973 sem_item
*caller
= (*callers
)[j
];
2974 if (caller
->cls
->members
.length () < 2)
2976 bitmap
*slot
= split_map
.get (caller
->cls
);
2981 b
= BITMAP_ALLOC (&m_bmstack
);
2982 split_map
.put (caller
->cls
, b
);
2987 gcc_checking_assert (caller
->cls
);
2988 gcc_checking_assert (caller
->index_in_class
2989 < caller
->cls
->members
.length ());
2991 bitmap_set_bit (b
, caller
->index_in_class
);
2995 auto_vec
<std::pair
<congruence_class
*, bitmap
> > to_split
;
2996 to_split
.reserve_exact (split_map
.elements ());
2997 for (hash_map
<congruence_class
*, bitmap
>::iterator i
= split_map
.begin ();
2998 i
!= split_map
.end (); ++i
)
2999 to_split
.safe_push (*i
);
3000 to_split
.qsort (sort_congruence_split
);
3002 traverse_split_pair pair
;
3003 pair
.optimizer
= this;
3006 splitter_class_removed
= false;
3008 for (unsigned i
= 0; i
< to_split
.length (); ++i
)
3009 r
|= traverse_congruence_split (to_split
[i
].first
, to_split
[i
].second
,
3012 /* Bitmap clean-up. */
3013 split_map
.traverse
<traverse_split_pair
*,
3014 sem_item_optimizer::release_split_map
> (NULL
);
3019 /* Every usage of a congruence class CLS is a candidate that can split the
3020 collection of classes. Bitmap stack BMSTACK is used for bitmap
3024 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3029 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3031 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3032 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3034 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3037 fprintf (dump_file
, " processing congruence step for class: %u "
3038 "(%u items, %u references), index: %u\n", cls
->id
,
3039 cls
->referenced_by_count
, cls
->members
.length (), i
);
3040 do_congruence_step_for_index (cls
, i
);
3042 if (splitter_class_removed
)
3046 BITMAP_FREE (usage
);
3049 /* Adds a newly created congruence class CLS to worklist. */
3052 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3054 /* Return if the class CLS is already presented in work list. */
3055 if (cls
->in_worklist
)
3058 cls
->in_worklist
= true;
3059 worklist
.insert (cls
->referenced_by_count
, cls
);
3062 /* Pops a class from worklist. */
3065 sem_item_optimizer::worklist_pop (void)
3067 congruence_class
*cls
;
3069 while (!worklist
.empty ())
3071 cls
= worklist
.extract_min ();
3072 if (cls
->in_worklist
)
3074 cls
->in_worklist
= false;
3080 /* Work list item was already intended to be removed.
3081 The only reason for doing it is to split a class.
3082 Thus, the class CLS is deleted. */
3090 /* Iterative congruence reduction function. */
3093 sem_item_optimizer::process_cong_reduction (void)
3095 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3096 it
!= m_classes
.end (); ++it
)
3097 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3098 if ((*it
)->classes
[i
]->is_class_used ())
3099 worklist_push ((*it
)->classes
[i
]);
3102 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3103 (unsigned long) worklist
.nodes ());
3105 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3106 fprintf (dump_file
, "Congruence class reduction\n");
3108 congruence_class
*cls
;
3110 /* Process complete congruence reduction. */
3111 while ((cls
= worklist_pop ()) != NULL
)
3112 do_congruence_step (cls
);
3114 /* Subdivide newly created classes according to references. */
3115 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3118 fprintf (dump_file
, "Address reference subdivision created: %u "
3119 "new classes.\n", new_classes
);
3122 /* Debug function prints all informations about congruence classes. */
3125 sem_item_optimizer::dump_cong_classes (void)
3130 /* Histogram calculation. */
3131 unsigned int max_index
= 0;
3132 unsigned int single_element_classes
= 0;
3133 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3135 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3136 it
!= m_classes
.end (); ++it
)
3137 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3139 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3146 ++single_element_classes
;
3150 "Congruence classes: %lu with total: %u items (in a non-singular "
3151 "class: %u)\n", (unsigned long) m_classes
.elements (),
3152 m_items
.length (), m_items
.length () - single_element_classes
);
3154 "Class size histogram [number of members]: number of classes\n");
3155 for (unsigned int i
= 0; i
<= max_index
; i
++)
3157 fprintf (dump_file
, "%6u: %6u\n", i
, histogram
[i
]);
3159 if (dump_flags
& TDF_DETAILS
)
3160 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3161 it
!= m_classes
.end (); ++it
)
3163 fprintf (dump_file
, " group: with %u classes:\n",
3164 (*it
)->classes
.length ());
3166 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3168 (*it
)->classes
[i
]->dump (dump_file
, 4);
3170 if (i
< (*it
)->classes
.length () - 1)
3171 fprintf (dump_file
, " ");
3178 /* Sort pair of sem_items A and B by DECL_UID. */
3181 sort_sem_items_by_decl_uid (const void *a
, const void *b
)
3183 const sem_item
*i1
= *(const sem_item
* const *)a
;
3184 const sem_item
*i2
= *(const sem_item
* const *)b
;
3186 int uid1
= DECL_UID (i1
->decl
);
3187 int uid2
= DECL_UID (i2
->decl
);
3191 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3194 sort_congruence_classes_by_decl_uid (const void *a
, const void *b
)
3196 const congruence_class
*c1
= *(const congruence_class
* const *)a
;
3197 const congruence_class
*c2
= *(const congruence_class
* const *)b
;
3199 int uid1
= DECL_UID (c1
->members
[0]->decl
);
3200 int uid2
= DECL_UID (c2
->members
[0]->decl
);
3204 /* Sort pair of congruence_class_groups A and B by
3205 DECL_UID of the first member of a first group. */
3208 sort_congruence_class_groups_by_decl_uid (const void *a
, const void *b
)
3210 const std::pair
<congruence_class_group
*, int> *g1
3211 = (const std::pair
<congruence_class_group
*, int> *) a
;
3212 const std::pair
<congruence_class_group
*, int> *g2
3213 = (const std::pair
<congruence_class_group
*, int> *) b
;
3214 return g1
->second
- g2
->second
;
3217 /* After reduction is done, we can declare all items in a group
3218 to be equal. PREV_CLASS_COUNT is start number of classes
3219 before reduction. True is returned if there's a merge operation
3220 processed. LOADED_SYMBOLS is number of symbols that were loaded
3224 sem_item_optimizer::merge_classes (unsigned int prev_class_count
,
3225 unsigned int loaded_symbols
)
3227 unsigned int item_count
= m_items
.length ();
3228 unsigned int class_count
= m_classes_count
;
3229 unsigned int equal_items
= item_count
- class_count
;
3231 unsigned int non_singular_classes_count
= 0;
3232 unsigned int non_singular_classes_sum
= 0;
3234 bool merged_p
= false;
3237 Sort functions in congruence classes by DECL_UID and do the same
3238 for the classes to not to break -fcompare-debug. */
3240 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3241 it
!= m_classes
.end (); ++it
)
3243 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3245 congruence_class
*c
= (*it
)->classes
[i
];
3246 c
->members
.qsort (sort_sem_items_by_decl_uid
);
3249 (*it
)->classes
.qsort (sort_congruence_classes_by_decl_uid
);
3252 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3253 it
!= m_classes
.end (); ++it
)
3254 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3256 congruence_class
*c
= (*it
)->classes
[i
];
3257 if (c
->members
.length () > 1)
3259 non_singular_classes_count
++;
3260 non_singular_classes_sum
+= c
->members
.length ();
3264 auto_vec
<std::pair
<congruence_class_group
*, int> > classes (
3265 m_classes
.elements ());
3266 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3267 it
!= m_classes
.end (); ++it
)
3269 int uid
= DECL_UID ((*it
)->classes
[0]->members
[0]->decl
);
3270 classes
.quick_push (std::pair
<congruence_class_group
*, int> (*it
, uid
));
3273 classes
.qsort (sort_congruence_class_groups_by_decl_uid
);
3277 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3278 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3279 prev_class_count
, class_count
);
3280 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3281 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3282 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3283 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3284 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3285 non_singular_classes_count
: 0.0f
,
3286 non_singular_classes_count
);
3287 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3288 unsigned total
= equal_items
+ non_singular_classes_count
;
3289 fprintf (dump_file
, "Totally needed symbols: %u"
3290 ", fraction of loaded symbols: %.2f%%\n\n", total
,
3291 loaded_symbols
? 100.0f
* total
/ loaded_symbols
: 0.0f
);
3295 std::pair
<congruence_class_group
*, int> *it
;
3296 FOR_EACH_VEC_ELT (classes
, l
, it
)
3297 for (unsigned int i
= 0; i
< it
->first
->classes
.length (); i
++)
3299 congruence_class
*c
= it
->first
->classes
[i
];
3301 if (c
->members
.length () == 1)
3304 sem_item
*source
= c
->members
[0];
3306 if (DECL_NAME (source
->decl
)
3307 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3308 /* If merge via wrappers, picking main as the target can be
3310 source
= c
->members
[1];
3312 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3314 sem_item
*alias
= c
->members
[j
];
3316 if (alias
== source
)
3319 dump_user_location_t loc
3320 = dump_user_location_t::from_function_decl (source
->decl
);
3321 if (dump_enabled_p ())
3323 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3324 "Semantic equality hit:%s->%s\n",
3325 source
->node
->dump_name (),
3326 alias
->node
->dump_name ());
3327 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3328 "Assembler symbol names:%s->%s\n",
3329 source
->node
->dump_asm_name (),
3330 alias
->node
->dump_asm_name ());
3333 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3335 if (dump_enabled_p ())
3336 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, loc
,
3337 "Merge operation is skipped due to no_icf "
3342 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3344 source
->dump_to_file (dump_file
);
3345 alias
->dump_to_file (dump_file
);
3348 if (dbg_cnt (merged_ipa_icf
))
3350 bool merged
= source
->merge (alias
);
3353 if (merged
&& alias
->type
== VAR
)
3355 symtab_pair p
= symtab_pair (source
->node
, alias
->node
);
3356 m_merged_variables
.safe_push (p
);
3362 if (!m_merged_variables
.is_empty ())
3363 fixup_points_to_sets ();
3368 /* Fixup points to set PT. */
3371 sem_item_optimizer::fixup_pt_set (struct pt_solution
*pt
)
3373 if (pt
->vars
== NULL
)
3378 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3379 if (bitmap_bit_p (pt
->vars
, DECL_UID (item
->second
->decl
)))
3380 bitmap_set_bit (pt
->vars
, DECL_UID (item
->first
->decl
));
3383 /* Set all points-to UIDs of aliases pointing to node N as UID. */
3386 set_alias_uids (symtab_node
*n
, int uid
)
3389 FOR_EACH_ALIAS (n
, ref
)
3392 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
3393 ref
->referring
->dump_asm_name (), uid
);
3395 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
3396 set_alias_uids (ref
->referring
, uid
);
3400 /* Fixup points to analysis info. */
3403 sem_item_optimizer::fixup_points_to_sets (void)
3405 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3408 FOR_EACH_DEFINED_FUNCTION (cnode
)
3412 function
*fn
= DECL_STRUCT_FUNCTION (cnode
->decl
);
3413 if (!gimple_in_ssa_p (fn
))
3416 FOR_EACH_SSA_NAME (i
, name
, fn
)
3417 if (POINTER_TYPE_P (TREE_TYPE (name
))
3418 && SSA_NAME_PTR_INFO (name
))
3419 fixup_pt_set (&SSA_NAME_PTR_INFO (name
)->pt
);
3420 fixup_pt_set (&fn
->gimple_df
->escaped
);
3422 /* The above gets us to 99% I guess, at least catching the
3423 address compares. Below also gets us aliasing correct
3424 but as said we're giving leeway to the situation with
3425 readonly vars anyway, so ... */
3427 FOR_EACH_BB_FN (bb
, fn
)
3428 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
3431 gcall
*call
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
3434 fixup_pt_set (gimple_call_use_set (call
));
3435 fixup_pt_set (gimple_call_clobber_set (call
));
3442 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3443 set_alias_uids (item
->first
, DECL_UID (item
->first
->decl
));
3446 /* Dump function prints all class members to a FILE with an INDENT. */
3449 congruence_class::dump (FILE *file
, unsigned int indent
) const
3451 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3452 id
, members
[0]->get_hash (), members
.length ());
3454 FPUTS_SPACES (file
, indent
+ 2, "");
3455 for (unsigned i
= 0; i
< members
.length (); i
++)
3456 fprintf (file
, "%s ", members
[i
]->node
->dump_asm_name ());
3458 fprintf (file
, "\n");
3461 /* Returns true if there's a member that is used from another group. */
3464 congruence_class::is_class_used (void)
3466 for (unsigned int i
= 0; i
< members
.length (); i
++)
3467 if (members
[i
]->referenced_by_count
)
3473 /* Generate pass summary for IPA ICF pass. */
3476 ipa_icf_generate_summary (void)
3479 optimizer
= new sem_item_optimizer ();
3481 optimizer
->register_hooks ();
3482 optimizer
->parse_funcs_and_vars ();
3485 /* Write pass summary for IPA ICF pass. */
3488 ipa_icf_write_summary (void)
3490 gcc_assert (optimizer
);
3492 optimizer
->write_summary ();
3495 /* Read pass summary for IPA ICF pass. */
3498 ipa_icf_read_summary (void)
3501 optimizer
= new sem_item_optimizer ();
3503 optimizer
->read_summary ();
3504 optimizer
->register_hooks ();
3507 /* Semantic equality execution function. */
3510 ipa_icf_driver (void)
3512 gcc_assert (optimizer
);
3514 bool merged_p
= optimizer
->execute ();
3519 return merged_p
? TODO_remove_functions
: 0;
3522 const pass_data pass_data_ipa_icf
=
3524 IPA_PASS
, /* type */
3526 OPTGROUP_IPA
, /* optinfo_flags */
3527 TV_IPA_ICF
, /* tv_id */
3528 0, /* properties_required */
3529 0, /* properties_provided */
3530 0, /* properties_destroyed */
3531 0, /* todo_flags_start */
3532 0, /* todo_flags_finish */
3535 class pass_ipa_icf
: public ipa_opt_pass_d
3538 pass_ipa_icf (gcc::context
*ctxt
)
3539 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3540 ipa_icf_generate_summary
, /* generate_summary */
3541 ipa_icf_write_summary
, /* write_summary */
3542 ipa_icf_read_summary
, /* read_summary */
3544 write_optimization_summary */
3546 read_optimization_summary */
3547 NULL
, /* stmt_fixup */
3548 0, /* function_transform_todo_flags_start */
3549 NULL
, /* function_transform */
3550 NULL
) /* variable_transform */
3553 /* opt_pass methods: */
3554 virtual bool gate (function
*)
3556 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3559 virtual unsigned int execute (function
*)
3561 return ipa_icf_driver();
3563 }; // class pass_ipa_icf
3565 } // ipa_icf namespace
3568 make_pass_ipa_icf (gcc::context
*ctxt
)
3570 return new ipa_icf::pass_ipa_icf (ctxt
);