1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2018 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.
57 #include "coretypes.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-fnsummary.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.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
), 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
), m_hash (-1), m_hash_set (false)
154 /* Add reference to a semantic TARGET. */
157 sem_item::add_reference (sem_item
*target
)
159 refs
.safe_push (target
);
160 unsigned index
= refs
.length ();
161 target
->usages
.safe_push (new sem_usage_pair(this, index
));
162 bitmap_set_bit (target
->usage_index_bitmap
, index
);
163 refs_set
.add (target
->node
);
166 /* Initialize internal data structures. Bitmap STACK is used for
167 bitmap memory allocation process. */
170 sem_item::setup (bitmap_obstack
*stack
)
172 gcc_checking_assert (node
);
175 tree_refs
.create (0);
177 usage_index_bitmap
= BITMAP_ALLOC (stack
);
180 sem_item::~sem_item ()
182 for (unsigned i
= 0; i
< usages
.length (); i
++)
186 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 ());
202 fprintf (dump_file
, " references: ");
204 for (unsigned i
= 0; i
< refs
.length (); i
++)
205 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
206 i
< refs
.length() - 1 ? "," : "");
208 fprintf (dump_file
, "\n");
212 /* Return true if target supports alias symbols. */
215 sem_item::target_supports_symbol_aliases_p (void)
217 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
224 void sem_item::set_hash (hashval_t hash
)
230 hash_map
<const_tree
, hashval_t
> sem_item::m_type_hash_cache
;
232 /* Semantic function constructor that uses STACK as bitmap memory stack. */
234 sem_function::sem_function (bitmap_obstack
*stack
)
235 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
238 bb_sorted
.create (0);
241 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
242 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
245 bb_sorted
.create (0);
248 sem_function::~sem_function ()
250 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
251 delete (bb_sorted
[i
]);
254 bb_sorted
.release ();
257 /* Calculates hash value based on a BASIC_BLOCK. */
260 sem_function::get_bb_hash (const sem_bb
*basic_block
)
262 inchash::hash hstate
;
264 hstate
.add_int (basic_block
->nondbg_stmt_count
);
265 hstate
.add_int (basic_block
->edge_count
);
267 return hstate
.end ();
270 /* References independent hash function. */
273 sem_function::get_hash (void)
277 inchash::hash hstate
;
278 hstate
.add_int (177454); /* Random number for function type. */
280 hstate
.add_int (arg_count
);
281 hstate
.add_int (cfg_checksum
);
282 hstate
.add_int (gcode_hash
);
284 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
285 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
287 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
288 hstate
.add_int (bb_sizes
[i
]);
290 /* Add common features of declaration itself. */
291 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
293 (cl_target_option_hash
294 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
295 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
297 (cl_optimization_hash
298 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
299 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
300 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
302 set_hash (hstate
.end ());
308 /* Return ture if A1 and A2 represent equivalent function attribute lists.
309 Based on comp_type_attributes. */
312 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
317 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
319 const struct attribute_spec
*as
;
322 as
= lookup_attribute_spec (get_attribute_name (a
));
323 /* TODO: We can introduce as->affects_decl_identity
324 and as->affects_decl_reference_identity if attribute mismatch
325 gets a common reason to give up on merging. It may not be worth
327 For example returns_nonnull affects only references, while
328 optimize attribute can be ignored because it is already lowered
329 into flags representation and compared separately. */
333 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
334 if (!attr
|| !attribute_value_equal (a
, attr
))
339 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
341 const struct attribute_spec
*as
;
343 as
= lookup_attribute_spec (get_attribute_name (a
));
347 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
349 /* We don't need to compare trees again, as we did this
350 already in first loop. */
355 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
359 /* Compare properties of symbols N1 and N2 that does not affect semantics of
360 symbol itself but affects semantics of its references from USED_BY (which
361 may be NULL if it is unknown). If comparsion is false, symbols
362 can still be merged but any symbols referring them can't.
364 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
366 TODO: We can also split attributes to those that determine codegen of
367 a function body/variable constructor itself and those that are used when
371 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
376 if (is_a
<cgraph_node
*> (n1
))
378 /* Inline properties matters: we do now want to merge uses of inline
379 function to uses of normal function because inline hint would be lost.
380 We however can merge inline function to noinline because the alias
381 will keep its DECL_DECLARED_INLINE flag.
383 Also ignore inline flag when optimizing for size or when function
384 is known to not be inlinable.
386 TODO: the optimize_size checks can also be assumed to be true if
387 unit has no !optimize_size functions. */
389 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
390 || !opt_for_fn (used_by
->decl
, optimize_size
))
391 && !opt_for_fn (n1
->decl
, optimize_size
)
392 && n1
->get_availability () > AVAIL_INTERPOSABLE
393 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
395 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
396 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
397 return return_false_with_msg
398 ("DECL_DISREGARD_INLINE_LIMITS are different");
400 if (DECL_DECLARED_INLINE_P (n1
->decl
)
401 != DECL_DECLARED_INLINE_P (n2
->decl
))
402 return return_false_with_msg ("inline attributes are different");
405 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
406 != DECL_IS_OPERATOR_NEW (n2
->decl
))
407 return return_false_with_msg ("operator new flags are different");
410 /* Merging two definitions with a reference to equivalent vtables, but
411 belonging to a different type may result in ipa-polymorphic-call analysis
412 giving a wrong answer about the dynamic type of instance. */
413 if (is_a
<varpool_node
*> (n1
))
415 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
416 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
417 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
418 DECL_CONTEXT (n2
->decl
)))
419 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
420 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
421 return return_false_with_msg
422 ("references to virtual tables can not be merged");
424 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
425 return return_false_with_msg ("alignment mismatch");
427 /* For functions we compare attributes in equals_wpa, because we do
428 not know what attributes may cause codegen differences, but for
429 variables just compare attributes for references - the codegen
430 for constructors is affected only by those attributes that we lower
431 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
432 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
433 DECL_ATTRIBUTES (n2
->decl
)))
434 return return_false_with_msg ("different var decl attributes");
435 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
436 TREE_TYPE (n2
->decl
)) != 1)
437 return return_false_with_msg ("different var type attributes");
440 /* When matching virtual tables, be sure to also match information
441 relevant for polymorphic call analysis. */
442 if (used_by
&& is_a
<varpool_node
*> (used_by
)
443 && DECL_VIRTUAL_P (used_by
->decl
))
445 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
446 return return_false_with_msg ("virtual flag mismatch");
447 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
448 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
449 return return_false_with_msg ("final flag mismatch");
454 /* Hash properties that are compared by compare_referenced_symbol_properties. */
457 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
458 inchash::hash
&hstate
,
461 if (is_a
<cgraph_node
*> (ref
))
463 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
464 && !opt_for_fn (ref
->decl
, optimize_size
)
465 && !DECL_UNINLINABLE (ref
->decl
))
467 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
468 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
470 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
472 else if (is_a
<varpool_node
*> (ref
))
474 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
476 hstate
.add_int (DECL_ALIGN (ref
->decl
));
481 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
482 point to a same function. Comparison can be skipped if IGNORED_NODES
483 contains these nodes. ADDRESS indicate if address is taken. */
486 sem_item::compare_symbol_references (
487 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
488 symtab_node
*n1
, symtab_node
*n2
, bool address
)
490 enum availability avail1
, avail2
;
495 /* Never match variable and function. */
496 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
499 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
501 if (address
&& n1
->equal_address_to (n2
) == 1)
503 if (!address
&& n1
->semantically_equivalent_p (n2
))
506 n1
= n1
->ultimate_alias_target (&avail1
);
507 n2
= n2
->ultimate_alias_target (&avail2
);
509 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
510 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
513 return return_false_with_msg ("different references");
516 /* If cgraph edges E1 and E2 are indirect calls, verify that
517 ECF flags are the same. */
519 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
521 if (e1
->indirect_info
&& e2
->indirect_info
)
523 int e1_flags
= e1
->indirect_info
->ecf_flags
;
524 int e2_flags
= e2
->indirect_info
->ecf_flags
;
526 if (e1_flags
!= e2_flags
)
527 return return_false_with_msg ("ICF flags are different");
529 else if (e1
->indirect_info
|| e2
->indirect_info
)
535 /* Return true if parameter I may be used. */
538 sem_function::param_used_p (unsigned int i
)
540 if (ipa_node_params_sum
== NULL
)
543 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
545 if (vec_safe_length (parms_info
->descriptors
) <= i
)
548 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
551 /* Perform additional check needed to match types function parameters that are
552 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
553 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
556 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
558 /* Be sure that parameters are TBAA compatible. */
559 if (!func_checker::compatible_types_p (parm1
, parm2
))
560 return return_false_with_msg ("parameter type is not compatible");
562 if (POINTER_TYPE_P (parm1
)
563 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
564 return return_false_with_msg ("argument restrict flag mismatch");
566 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
567 if (POINTER_TYPE_P (parm1
)
568 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
569 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
570 return return_false_with_msg ("pointer wrt reference mismatch");
575 /* Fast equality function based on knowledge known in WPA. */
578 sem_function::equals_wpa (sem_item
*item
,
579 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
581 gcc_assert (item
->type
== FUNC
);
582 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
583 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
585 m_compared_func
= static_cast<sem_function
*> (item
);
587 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
588 return return_false_with_msg ("thunk_p mismatch");
590 if (cnode
->thunk
.thunk_p
)
592 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
593 return return_false_with_msg ("thunk fixed_offset mismatch");
594 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
595 return return_false_with_msg ("thunk virtual_value mismatch");
596 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
597 return return_false_with_msg ("thunk this_adjusting mismatch");
598 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
599 return return_false_with_msg ("thunk virtual_offset_p mismatch");
600 if (cnode
->thunk
.add_pointer_bounds_args
601 != cnode2
->thunk
.add_pointer_bounds_args
)
602 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
605 /* Compare special function DECL attributes. */
606 if (DECL_FUNCTION_PERSONALITY (decl
)
607 != DECL_FUNCTION_PERSONALITY (item
->decl
))
608 return return_false_with_msg ("function personalities are different");
610 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
611 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
612 return return_false_with_msg ("intrument function entry exit "
613 "attributes are different");
615 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
616 return return_false_with_msg ("no stack limit attributes are different");
618 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
619 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
621 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
622 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
624 /* TODO: pure/const flags mostly matters only for references, except for
625 the fact that codegen takes LOOPING flag as a hint that loops are
626 finite. We may arrange the code to always pick leader that has least
627 specified flags and then this can go into comparing symbol properties. */
628 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
629 return return_false_with_msg ("decl_or_type flags are different");
631 /* Do not match polymorphic constructors of different types. They calls
632 type memory location for ipa-polymorphic-call and we do not want
633 it to get confused by wrong type. */
634 if (DECL_CXX_CONSTRUCTOR_P (decl
)
635 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
637 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
638 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
639 else if (!func_checker::compatible_polymorphic_types_p
640 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
641 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
642 return return_false_with_msg ("ctor polymorphic type mismatch");
645 /* Checking function TARGET and OPTIMIZATION flags. */
646 cl_target_option
*tar1
= target_opts_for_fn (decl
);
647 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
649 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
653 fprintf (dump_file
, "target flags difference");
654 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
657 return return_false_with_msg ("Target flags are different");
660 cl_optimization
*opt1
= opts_for_fn (decl
);
661 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
663 if (opt1
!= opt2
&& !cl_optimization_option_eq (opt1
, opt2
))
665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
667 fprintf (dump_file
, "optimization flags difference");
668 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
671 return return_false_with_msg ("optimization flags are different");
674 /* Result type checking. */
675 if (!func_checker::compatible_types_p
676 (TREE_TYPE (TREE_TYPE (decl
)),
677 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
678 return return_false_with_msg ("result types are different");
680 /* Checking types of arguments. */
681 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
682 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
683 for (unsigned i
= 0; list1
&& list2
;
684 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
686 tree parm1
= TREE_VALUE (list1
);
687 tree parm2
= TREE_VALUE (list2
);
689 /* This guard is here for function pointer with attributes (pr59927.c). */
690 if (!parm1
|| !parm2
)
691 return return_false_with_msg ("NULL argument type");
693 /* Verify that types are compatible to ensure that both functions
694 have same calling conventions. */
695 if (!types_compatible_p (parm1
, parm2
))
696 return return_false_with_msg ("parameter types are not compatible");
698 if (!param_used_p (i
))
701 /* Perform additional checks for used parameters. */
702 if (!compatible_parm_types_p (parm1
, parm2
))
707 return return_false_with_msg ("Mismatched number of parameters");
709 if (node
->num_references () != item
->node
->num_references ())
710 return return_false_with_msg ("different number of references");
712 /* Checking function attributes.
713 This is quadratic in number of attributes */
714 if (comp_type_attributes (TREE_TYPE (decl
),
715 TREE_TYPE (item
->decl
)) != 1)
716 return return_false_with_msg ("different type attributes");
717 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
718 DECL_ATTRIBUTES (item
->decl
)))
719 return return_false_with_msg ("different decl attributes");
721 /* The type of THIS pointer type memory location for
722 ipa-polymorphic-call-analysis. */
723 if (opt_for_fn (decl
, flag_devirtualize
)
724 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
725 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
727 && compare_polymorphic_p ())
729 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
730 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
731 if (!func_checker::compatible_polymorphic_types_p
732 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
733 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
734 return return_false_with_msg ("THIS pointer ODR type mismatch");
737 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
738 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
740 item
->node
->iterate_reference (i
, ref2
);
742 if (ref
->use
!= ref2
->use
)
743 return return_false_with_msg ("reference use mismatch");
745 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
747 ref
->address_matters_p ()))
751 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
752 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
756 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
759 if (!compare_edge_flags (e1
, e2
))
762 e1
= e1
->next_callee
;
763 e2
= e2
->next_callee
;
767 return return_false_with_msg ("different number of calls");
769 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
770 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
774 if (!compare_edge_flags (e1
, e2
))
777 e1
= e1
->next_callee
;
778 e2
= e2
->next_callee
;
782 return return_false_with_msg ("different number of indirect calls");
787 /* Update hash by address sensitive references. We iterate over all
788 sensitive references (address_matters_p) and we hash ultime alias
789 target of these nodes, which can improve a semantic item hash.
791 Also hash in referenced symbols properties. This can be done at any time
792 (as the properties should not change), but it is convenient to do it here
793 while we walk the references anyway. */
796 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
797 sem_item
*> &m_symtab_node_map
)
800 inchash::hash
hstate (get_hash ());
802 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
804 hstate
.add_int (ref
->use
);
805 hash_referenced_symbol_properties (ref
->referred
, hstate
,
806 ref
->use
== IPA_REF_ADDR
);
807 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
808 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
811 if (is_a
<cgraph_node
*> (node
))
813 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
816 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
817 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
819 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
823 set_hash (hstate
.end ());
826 /* Update hash by computed local hash values taken from different
828 TODO: stronger SCC based hashing would be desirable here. */
831 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
832 sem_item
*> &m_symtab_node_map
)
835 inchash::hash
state (get_hash ());
837 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
839 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
841 state
.merge_hash ((*result
)->get_hash ());
846 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
849 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
851 state
.merge_hash ((*result
)->get_hash ());
855 global_hash
= state
.end ();
858 /* Returns true if the item equals to ITEM given as argument. */
861 sem_function::equals (sem_item
*item
,
862 hash_map
<symtab_node
*, sem_item
*> &)
864 gcc_assert (item
->type
== FUNC
);
865 bool eq
= equals_private (item
);
867 if (m_checker
!= NULL
)
873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
875 "Equals called for: %s:%s with result: %s\n\n",
877 item
->node
->dump_name (),
878 eq
? "true" : "false");
883 /* Processes function equality comparison. */
886 sem_function::equals_private (sem_item
*item
)
888 if (item
->type
!= FUNC
)
891 basic_block bb1
, bb2
;
893 edge_iterator ei1
, ei2
;
897 m_compared_func
= static_cast<sem_function
*> (item
);
899 gcc_assert (decl
!= item
->decl
);
901 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
902 || edge_count
!= m_compared_func
->edge_count
903 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
904 return return_false ();
906 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
907 compare_polymorphic_p (),
910 &m_compared_func
->refs_set
);
911 arg1
= DECL_ARGUMENTS (decl
);
912 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
914 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
916 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
917 return return_false_with_msg ("argument types are not compatible");
918 if (!param_used_p (i
))
920 /* Perform additional checks for used parameters. */
921 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
923 if (!m_checker
->compare_decl (arg1
, arg2
))
924 return return_false ();
927 return return_false_with_msg ("Mismatched number of arguments");
929 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
932 /* Fill-up label dictionary. */
933 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
935 m_checker
->parse_labels (bb_sorted
[i
]);
936 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
939 /* Checking all basic blocks. */
940 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
941 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
942 return return_false();
944 dump_message ("All BBs are equal\n");
946 auto_vec
<int> bb_dict
;
948 /* Basic block edges check. */
949 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
951 bb1
= bb_sorted
[i
]->bb
;
952 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
954 ei2
= ei_start (bb2
->preds
);
956 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
960 if (e1
->flags
!= e2
->flags
)
961 return return_false_with_msg ("flags comparison returns false");
963 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
964 return return_false_with_msg ("edge comparison returns false");
966 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
967 return return_false_with_msg ("BB comparison returns false");
969 if (!m_checker
->compare_edge (e1
, e2
))
970 return return_false_with_msg ("edge comparison returns false");
976 /* Basic block PHI nodes comparison. */
977 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
978 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
979 return return_false_with_msg ("PHI node comparison returns false");
984 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
985 Helper for call_for_symbol_thunks_and_aliases. */
988 set_local (cgraph_node
*node
, void *data
)
990 node
->local
.local
= data
!= NULL
;
994 /* TREE_ADDRESSABLE of NODE to true.
995 Helper for call_for_symbol_thunks_and_aliases. */
998 set_addressable (varpool_node
*node
, void *)
1000 TREE_ADDRESSABLE (node
->decl
) = 1;
1004 /* Clear DECL_RTL of NODE.
1005 Helper for call_for_symbol_thunks_and_aliases. */
1008 clear_decl_rtl (symtab_node
*node
, void *)
1010 SET_DECL_RTL (node
->decl
, NULL
);
1014 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1015 possible. Return number of redirections made. */
1018 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1020 int nredirected
= 0;
1022 cgraph_edge
*e
= n
->callers
;
1026 /* Redirecting thunks to interposable symbols or symbols in other sections
1027 may not be supported by target output code. Play safe for now and
1028 punt on redirection. */
1029 if (!e
->caller
->thunk
.thunk_p
)
1031 struct cgraph_edge
*nexte
= e
->next_caller
;
1032 e
->redirect_callee (to
);
1039 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1041 bool removed
= false;
1042 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1044 if ((DECL_COMDAT_GROUP (n
->decl
)
1045 && (DECL_COMDAT_GROUP (n
->decl
)
1046 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1047 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1048 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1050 nredirected
+= redirect_all_callers (n_alias
, to
);
1051 if (n_alias
->can_remove_if_no_direct_calls_p ()
1052 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1054 && !n_alias
->has_aliases_p ())
1063 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1067 sem_function::merge (sem_item
*alias_item
)
1069 gcc_assert (alias_item
->type
== FUNC
);
1071 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1073 cgraph_node
*original
= get_node ();
1074 cgraph_node
*local_original
= NULL
;
1075 cgraph_node
*alias
= alias_func
->get_node ();
1077 bool create_wrapper
= false;
1078 bool create_alias
= false;
1079 bool redirect_callers
= false;
1080 bool remove
= false;
1082 bool original_discardable
= false;
1083 bool original_discarded
= false;
1085 bool original_address_matters
= original
->address_matters_p ();
1086 bool alias_address_matters
= alias
->address_matters_p ();
1088 if (DECL_EXTERNAL (alias
->decl
))
1091 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1095 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1096 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1101 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1105 /* Do not attempt to mix functions from different user sections;
1106 we do not know what user intends with those. */
1107 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1108 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1109 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1114 "original and alias are in different sections.\n\n");
1118 if (!original
->in_same_comdat_group_p (alias
)
1119 || original
->comdat_local_p ())
1123 "Not unifying; alias nor wrapper cannot be created; "
1124 "across comdat group boundary\n\n");
1129 /* See if original is in a section that can be discarded if the main
1130 symbol is not used. */
1132 if (original
->can_be_discarded_p ())
1133 original_discardable
= true;
1134 /* Also consider case where we have resolution info and we know that
1135 original's definition is not going to be used. In this case we can not
1136 create alias to original. */
1137 if (node
->resolution
!= LDPR_UNKNOWN
1138 && !decl_binds_to_current_def_p (node
->decl
))
1139 original_discardable
= original_discarded
= true;
1141 /* Creating a symtab alias is the optimal way to merge.
1142 It however can not be used in the following cases:
1144 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1145 2) if ORIGINAL is in a section that may be discarded by linker or if
1146 it is an external functions where we can not create an alias
1147 (ORIGINAL_DISCARDABLE)
1148 3) if target do not support symbol aliases.
1149 4) original and alias lie in different comdat groups.
1151 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1152 and/or redirect all callers from ALIAS to ORIGINAL. */
1153 if ((original_address_matters
&& alias_address_matters
)
1154 || (original_discardable
1155 && (!DECL_COMDAT_GROUP (alias
->decl
)
1156 || (DECL_COMDAT_GROUP (alias
->decl
)
1157 != DECL_COMDAT_GROUP (original
->decl
))))
1158 || original_discarded
1159 || !sem_item::target_supports_symbol_aliases_p ()
1160 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1162 /* First see if we can produce wrapper. */
1164 /* Symbol properties that matter for references must be preserved.
1165 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1166 with proper properties. */
1167 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1168 alias
->address_taken
))
1172 "Wrapper cannot be created because referenced symbol "
1173 "properties mismatch\n");
1175 /* Do not turn function in one comdat group into wrapper to another
1176 comdat group. Other compiler producing the body of the
1177 another comdat group may make opossite decision and with unfortunate
1178 linker choices this may close a loop. */
1179 else if (DECL_COMDAT_GROUP (original
->decl
)
1180 && DECL_COMDAT_GROUP (alias
->decl
)
1181 && (DECL_COMDAT_GROUP (alias
->decl
)
1182 != DECL_COMDAT_GROUP (original
->decl
)))
1186 "Wrapper cannot be created because of COMDAT\n");
1188 else if (DECL_STATIC_CHAIN (alias
->decl
)
1189 || DECL_STATIC_CHAIN (original
->decl
))
1193 "Cannot create wrapper of nested function.\n");
1195 /* TODO: We can also deal with variadic functions never calling
1197 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1201 "can not create wrapper of stdarg function.\n");
1203 else if (ipa_fn_summaries
1204 && ipa_fn_summaries
->get (alias
) != NULL
1205 && ipa_fn_summaries
->get (alias
)->self_size
<= 2)
1208 fprintf (dump_file
, "Wrapper creation is not "
1209 "profitable (function is too small).\n");
1211 /* If user paid attention to mark function noinline, assume it is
1212 somewhat special and do not try to turn it into a wrapper that can
1213 not be undone by inliner. */
1214 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1217 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1220 create_wrapper
= true;
1222 /* We can redirect local calls in the case both alias and orignal
1223 are not interposable. */
1225 = alias
->get_availability () > AVAIL_INTERPOSABLE
1226 && original
->get_availability () > AVAIL_INTERPOSABLE
;
1227 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1228 with proper properties. */
1229 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1230 alias
->address_taken
))
1231 redirect_callers
= false;
1233 if (!redirect_callers
&& !create_wrapper
)
1236 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1237 "produce wrapper\n\n");
1241 /* Work out the symbol the wrapper should call.
1242 If ORIGINAL is interposable, we need to call a local alias.
1243 Also produce local alias (if possible) as an optimization.
1245 Local aliases can not be created inside comdat groups because that
1246 prevents inlining. */
1247 if (!original_discardable
&& !original
->get_comdat_group ())
1250 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1252 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1253 local_original
= original
;
1255 /* If we can not use local alias, fallback to the original
1257 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1258 local_original
= original
;
1260 /* If original is COMDAT local, we can not really redirect calls outside
1261 of its comdat group to it. */
1262 if (original
->comdat_local_p ())
1263 redirect_callers
= false;
1264 if (!local_original
)
1267 fprintf (dump_file
, "Not unifying; "
1268 "can not produce local alias.\n\n");
1272 if (!redirect_callers
&& !create_wrapper
)
1275 fprintf (dump_file
, "Not unifying; "
1276 "can not redirect callers nor produce a wrapper\n\n");
1280 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1282 && !alias
->can_remove_if_no_direct_calls_p ())
1285 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1286 "function has other uses than direct calls\n\n");
1291 create_alias
= true;
1293 if (redirect_callers
)
1295 int nredirected
= redirect_all_callers (alias
, local_original
);
1299 alias
->icf_merged
= true;
1300 local_original
->icf_merged
= true;
1302 if (dump_file
&& nredirected
)
1303 fprintf (dump_file
, "%i local calls have been "
1304 "redirected.\n", nredirected
);
1307 /* If all callers was redirected, do not produce wrapper. */
1308 if (alias
->can_remove_if_no_direct_calls_p ()
1309 && !DECL_VIRTUAL_P (alias
->decl
)
1310 && !alias
->has_aliases_p ())
1312 create_wrapper
= false;
1315 gcc_assert (!create_alias
);
1317 else if (create_alias
)
1319 alias
->icf_merged
= true;
1321 /* Remove the function's body. */
1322 ipa_merge_profiles (original
, alias
);
1323 alias
->release_body (true);
1325 /* Notice global symbol possibly produced RTL. */
1326 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1329 /* Create the alias. */
1330 cgraph_node::create_alias (alias_func
->decl
, decl
);
1331 alias
->resolve_alias (original
);
1333 original
->call_for_symbol_thunks_and_aliases
1334 (set_local
, (void *)(size_t) original
->local_p (), true);
1337 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1341 gcc_assert (!create_alias
);
1342 alias
->icf_merged
= true;
1343 local_original
->icf_merged
= true;
1345 /* FIXME update local_original counts. */
1346 ipa_merge_profiles (original
, alias
, true);
1347 alias
->create_wrapper (local_original
);
1350 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1353 /* It's possible that redirection can hit thunks that block
1354 redirection opportunities. */
1355 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1356 original
->icf_merged
= true;
1358 /* We use merged flag to track cases where COMDAT function is known to be
1359 compatible its callers. If we merged in non-COMDAT, we need to give up
1360 on this optimization. */
1361 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1364 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1366 local_original
->merged_comdat
= false;
1367 original
->merged_comdat
= false;
1372 ipa_merge_profiles (original
, alias
);
1373 alias
->release_body ();
1375 alias
->body_removed
= true;
1376 alias
->icf_merged
= true;
1378 fprintf (dump_file
, "Unified; Function body was removed.\n");
1384 /* Semantic item initialization function. */
1387 sem_function::init (void)
1390 get_node ()->get_untransformed_body ();
1392 tree fndecl
= node
->decl
;
1393 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1396 gcc_assert (SSANAMES (func
));
1398 ssa_names_size
= SSANAMES (func
)->length ();
1402 region_tree
= func
->eh
->region_tree
;
1404 /* iterating all function arguments. */
1405 arg_count
= count_formal_params (fndecl
);
1407 edge_count
= n_edges_for_fn (func
);
1408 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1409 if (!cnode
->thunk
.thunk_p
)
1411 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1413 inchash::hash hstate
;
1416 FOR_EACH_BB_FN (bb
, func
)
1418 unsigned nondbg_stmt_count
= 0;
1421 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1423 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1426 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1429 gimple
*stmt
= gsi_stmt (gsi
);
1431 if (gimple_code (stmt
) != GIMPLE_DEBUG
1432 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1434 hash_stmt (stmt
, hstate
);
1435 nondbg_stmt_count
++;
1439 hstate
.commit_flag ();
1440 gcode_hash
= hstate
.end ();
1441 bb_sizes
.safe_push (nondbg_stmt_count
);
1443 /* Inserting basic block to hash table. */
1444 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1445 EDGE_COUNT (bb
->preds
)
1446 + EDGE_COUNT (bb
->succs
));
1448 bb_sorted
.safe_push (semantic_bb
);
1454 inchash::hash hstate
;
1455 hstate
.add_hwi (cnode
->thunk
.fixed_offset
);
1456 hstate
.add_hwi (cnode
->thunk
.virtual_value
);
1457 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1458 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1459 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1460 gcode_hash
= hstate
.end ();
1464 /* Accumulate to HSTATE a hash of expression EXP.
1465 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1466 and DECL equality classes. */
1469 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1471 if (exp
== NULL_TREE
)
1473 hstate
.merge_hash (0);
1477 /* Handled component can be matched in a cureful way proving equivalence
1478 even if they syntactically differ. Just skip them. */
1480 while (handled_component_p (exp
))
1481 exp
= TREE_OPERAND (exp
, 0);
1483 enum tree_code code
= TREE_CODE (exp
);
1484 hstate
.add_int (code
);
1488 /* Use inchash::add_expr for everything that is LTO stable. */
1496 inchash::add_expr (exp
, hstate
);
1500 unsigned HOST_WIDE_INT idx
;
1503 hstate
.add_hwi (int_size_in_bytes (TREE_TYPE (exp
)));
1505 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1507 add_expr (value
, hstate
);
1512 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1518 hstate
.add_hwi (int_size_in_bytes (TREE_TYPE (exp
)));
1521 case POINTER_PLUS_EXPR
:
1524 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1525 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1529 inchash::hash one
, two
;
1530 add_expr (TREE_OPERAND (exp
, 0), one
);
1531 add_expr (TREE_OPERAND (exp
, 1), two
);
1532 hstate
.add_commutative (one
, two
);
1536 hstate
.add_hwi (int_size_in_bytes (TREE_TYPE (exp
)));
1537 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1543 /* Accumulate to HSTATE a hash of type t.
1544 TYpes that may end up being compatible after LTO type merging needs to have
1548 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1550 if (type
== NULL_TREE
)
1552 hstate
.merge_hash (0);
1556 type
= TYPE_MAIN_VARIANT (type
);
1558 hstate
.add_int (TYPE_MODE (type
));
1560 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1562 hstate
.add_int (COMPLEX_TYPE
);
1563 sem_item::add_type (TREE_TYPE (type
), hstate
);
1565 else if (INTEGRAL_TYPE_P (type
))
1567 hstate
.add_int (INTEGER_TYPE
);
1568 hstate
.add_flag (TYPE_UNSIGNED (type
));
1569 hstate
.add_int (TYPE_PRECISION (type
));
1571 else if (VECTOR_TYPE_P (type
))
1573 hstate
.add_int (VECTOR_TYPE
);
1574 hstate
.add_int (TYPE_PRECISION (type
));
1575 sem_item::add_type (TREE_TYPE (type
), hstate
);
1577 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1579 hstate
.add_int (ARRAY_TYPE
);
1580 /* Do not hash size, so complete and incomplete types can match. */
1581 sem_item::add_type (TREE_TYPE (type
), hstate
);
1583 else if (RECORD_OR_UNION_TYPE_P (type
))
1585 /* Incomplete types must be skipped here. */
1586 if (!COMPLETE_TYPE_P (type
))
1588 hstate
.add_int (RECORD_TYPE
);
1592 hashval_t
*val
= m_type_hash_cache
.get (type
);
1596 inchash::hash hstate2
;
1601 hstate2
.add_int (RECORD_TYPE
);
1602 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1603 if (TREE_CODE (f
) == FIELD_DECL
)
1605 add_type (TREE_TYPE (f
), hstate2
);
1609 hstate2
.add_int (nf
);
1610 hash
= hstate2
.end ();
1611 hstate
.add_hwi (hash
);
1612 m_type_hash_cache
.put (type
, hash
);
1615 hstate
.add_hwi (*val
);
1619 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1622 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1624 enum gimple_code code
= gimple_code (stmt
);
1626 hstate
.add_int (code
);
1631 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1634 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1635 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1636 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1638 inchash::hash one
, two
;
1640 add_expr (gimple_assign_rhs1 (stmt
), one
);
1641 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1642 add_expr (gimple_assign_rhs2 (stmt
), two
);
1643 hstate
.add_commutative (one
, two
);
1644 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1646 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1647 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1649 add_expr (gimple_assign_lhs (stmt
), hstate
);
1650 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1659 /* All these statements are equivalent if their operands are. */
1660 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1662 add_expr (gimple_op (stmt
, i
), hstate
);
1663 if (gimple_op (stmt
, i
))
1664 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1666 /* Consider nocf_check attribute in hash as it affects code
1668 if (code
== GIMPLE_CALL
1669 && flag_cf_protection
& CF_BRANCH
)
1670 hstate
.add_flag (gimple_call_nocf_check_p (as_a
<gcall
*> (stmt
)));
1677 /* Return true if polymorphic comparison must be processed. */
1680 sem_function::compare_polymorphic_p (void)
1682 struct cgraph_edge
*e
;
1684 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1686 if (get_node ()->indirect_calls
!= NULL
)
1688 /* TODO: We can do simple propagation determining what calls may lead to
1689 a polymorphic call. */
1690 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1691 if (e
->callee
->definition
1692 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1697 /* For a given call graph NODE, the function constructs new
1698 semantic function item. */
1701 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1703 tree fndecl
= node
->decl
;
1704 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1706 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1709 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1712 if (lookup_attribute_by_prefix ("oacc ",
1713 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1717 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1718 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1721 sem_function
*f
= new sem_function (node
, stack
);
1728 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1729 return true if phi nodes are semantically equivalent in these blocks . */
1732 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1734 gphi_iterator si1
, si2
;
1736 unsigned size1
, size2
, i
;
1740 gcc_assert (bb1
!= NULL
);
1741 gcc_assert (bb2
!= NULL
);
1743 si2
= gsi_start_phis (bb2
);
1744 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1747 gsi_next_nonvirtual_phi (&si1
);
1748 gsi_next_nonvirtual_phi (&si2
);
1750 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1753 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1754 return return_false();
1759 tree phi_result1
= gimple_phi_result (phi1
);
1760 tree phi_result2
= gimple_phi_result (phi2
);
1762 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1763 return return_false_with_msg ("PHI results are different");
1765 size1
= gimple_phi_num_args (phi1
);
1766 size2
= gimple_phi_num_args (phi2
);
1769 return return_false ();
1771 for (i
= 0; i
< size1
; ++i
)
1773 t1
= gimple_phi_arg (phi1
, i
)->def
;
1774 t2
= gimple_phi_arg (phi2
, i
)->def
;
1776 if (!m_checker
->compare_operand (t1
, t2
))
1777 return return_false ();
1779 e1
= gimple_phi_arg_edge (phi1
, i
);
1780 e2
= gimple_phi_arg_edge (phi2
, i
);
1782 if (!m_checker
->compare_edge (e1
, e2
))
1783 return return_false ();
1792 /* Returns true if tree T can be compared as a handled component. */
1795 sem_function::icf_handled_component_p (tree t
)
1797 tree_code tc
= TREE_CODE (t
);
1799 return (handled_component_p (t
)
1800 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1803 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1804 corresponds to TARGET. */
1807 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1812 if (bb_dict
->length () <= (unsigned)source
)
1813 bb_dict
->safe_grow_cleared (source
+ 1);
1815 if ((*bb_dict
)[source
] == 0)
1817 (*bb_dict
)[source
] = target
;
1821 return (*bb_dict
)[source
] == target
;
1824 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1828 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1829 : sem_item (VAR
, node
, stack
)
1831 gcc_checking_assert (node
);
1832 gcc_checking_assert (get_node ());
1835 /* Fast equality function based on knowledge known in WPA. */
1838 sem_variable::equals_wpa (sem_item
*item
,
1839 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1841 gcc_assert (item
->type
== VAR
);
1843 if (node
->num_references () != item
->node
->num_references ())
1844 return return_false_with_msg ("different number of references");
1846 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1847 return return_false_with_msg ("TLS model");
1849 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1850 alignment out of all aliases. */
1852 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1853 return return_false_with_msg ("Virtual flag mismatch");
1855 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1856 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1857 || !operand_equal_p (DECL_SIZE (decl
),
1858 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1859 return return_false_with_msg ("size mismatch");
1861 /* Do not attempt to mix data from different user sections;
1862 we do not know what user intends with those. */
1863 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1864 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1865 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1866 return return_false_with_msg ("user section mismatch");
1868 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1869 return return_false_with_msg ("text section");
1871 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1872 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1874 item
->node
->iterate_reference (i
, ref2
);
1876 if (ref
->use
!= ref2
->use
)
1877 return return_false_with_msg ("reference use mismatch");
1879 if (!compare_symbol_references (ignored_nodes
,
1880 ref
->referred
, ref2
->referred
,
1881 ref
->address_matters_p ()))
1888 /* Returns true if the item equals to ITEM given as argument. */
1891 sem_variable::equals (sem_item
*item
,
1892 hash_map
<symtab_node
*, sem_item
*> &)
1894 gcc_assert (item
->type
== VAR
);
1897 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1898 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1899 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1900 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1902 /* As seen in PR ipa/65303 we have to compare variables types. */
1903 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1904 TREE_TYPE (item
->decl
)))
1905 return return_false_with_msg ("variables types are different");
1907 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1908 DECL_INITIAL (item
->node
->decl
));
1909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1911 "Equals called for vars: %s:%s with result: %s\n\n",
1912 node
->dump_name (), item
->node
->dump_name (),
1913 ret
? "true" : "false");
1918 /* Compares trees T1 and T2 for semantic equality. */
1921 sem_variable::equals (tree t1
, tree t2
)
1924 return return_with_debug (t1
== t2
);
1927 tree_code tc1
= TREE_CODE (t1
);
1928 tree_code tc2
= TREE_CODE (t2
);
1931 return return_false_with_msg ("TREE_CODE mismatch");
1937 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1938 unsigned HOST_WIDE_INT idx
;
1940 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1941 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1942 return return_false_with_msg ("constructor type mismatch");
1944 if (typecode
== ARRAY_TYPE
)
1946 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1947 /* For arrays, check that the sizes all match. */
1948 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1950 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1951 return return_false_with_msg ("constructor array size mismatch");
1953 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1955 return return_false_with_msg ("constructor type incompatible");
1957 v1
= CONSTRUCTOR_ELTS (t1
);
1958 v2
= CONSTRUCTOR_ELTS (t2
);
1959 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1960 return return_false_with_msg ("constructor number of elts mismatch");
1962 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1964 constructor_elt
*c1
= &(*v1
)[idx
];
1965 constructor_elt
*c2
= &(*v2
)[idx
];
1967 /* Check that each value is the same... */
1968 if (!sem_variable::equals (c1
->value
, c2
->value
))
1970 /* ... and that they apply to the same fields! */
1971 if (!sem_variable::equals (c1
->index
, c2
->index
))
1978 tree x1
= TREE_OPERAND (t1
, 0);
1979 tree x2
= TREE_OPERAND (t2
, 0);
1980 tree y1
= TREE_OPERAND (t1
, 1);
1981 tree y2
= TREE_OPERAND (t2
, 1);
1983 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1984 return return_false ();
1986 /* Type of the offset on MEM_REF does not matter. */
1987 return return_with_debug (sem_variable::equals (x1
, x2
)
1988 && known_eq (wi::to_poly_offset (y1
),
1989 wi::to_poly_offset (y2
)));
1994 tree op1
= TREE_OPERAND (t1
, 0);
1995 tree op2
= TREE_OPERAND (t2
, 0);
1996 return sem_variable::equals (op1
, op2
);
1998 /* References to other vars/decls are compared using ipa-ref. */
2001 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
2003 return return_false_with_msg ("Declaration mismatch");
2005 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2006 need to process its VAR/FUNCTION references without relying on ipa-ref
2010 return return_false_with_msg ("Declaration mismatch");
2012 /* Integer constants are the same only if the same width of type. */
2013 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2014 return return_false_with_msg ("INTEGER_CST precision mismatch");
2015 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2016 return return_false_with_msg ("INTEGER_CST mode mismatch");
2017 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2019 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2020 return return_false_with_msg ("STRING_CST mode mismatch");
2021 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2022 return return_false_with_msg ("STRING_CST length mismatch");
2023 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2024 TREE_STRING_LENGTH (t1
)))
2025 return return_false_with_msg ("STRING_CST mismatch");
2028 /* Fixed constants are the same only if the same width of type. */
2029 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2030 return return_false_with_msg ("FIXED_CST precision mismatch");
2032 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2033 TREE_FIXED_CST (t2
)));
2035 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2036 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2038 /* Real constants are the same only if the same width of type. */
2039 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2040 return return_false_with_msg ("REAL_CST precision mismatch");
2041 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2042 &TREE_REAL_CST (t2
)));
2045 if (maybe_ne (VECTOR_CST_NELTS (t1
), VECTOR_CST_NELTS (t2
)))
2046 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2049 = tree_vector_builder::binary_encoded_nelts (t1
, t2
);
2050 for (unsigned int i
= 0; i
< count
; ++i
)
2051 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1
, i
),
2052 VECTOR_CST_ENCODED_ELT (t2
, i
)))
2058 case ARRAY_RANGE_REF
:
2060 tree x1
= TREE_OPERAND (t1
, 0);
2061 tree x2
= TREE_OPERAND (t2
, 0);
2062 tree y1
= TREE_OPERAND (t1
, 1);
2063 tree y2
= TREE_OPERAND (t2
, 1);
2065 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2067 if (!sem_variable::equals (array_ref_low_bound (t1
),
2068 array_ref_low_bound (t2
)))
2070 if (!sem_variable::equals (array_ref_element_size (t1
),
2071 array_ref_element_size (t2
)))
2077 case POINTER_PLUS_EXPR
:
2082 tree x1
= TREE_OPERAND (t1
, 0);
2083 tree x2
= TREE_OPERAND (t2
, 0);
2084 tree y1
= TREE_OPERAND (t1
, 1);
2085 tree y2
= TREE_OPERAND (t2
, 1);
2087 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2091 case VIEW_CONVERT_EXPR
:
2092 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2093 return return_false ();
2094 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2096 return return_false_with_msg ("ERROR_MARK");
2098 return return_false_with_msg ("Unknown TREE code reached");
2102 /* Parser function that visits a varpool NODE. */
2105 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2107 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2111 sem_variable
*v
= new sem_variable (node
, stack
);
2118 /* References independent hash function. */
2121 sem_variable::get_hash (void)
2126 /* All WPA streamed in symbols should have their hashes computed at compile
2127 time. At this point, the constructor may not be in memory at all.
2128 DECL_INITIAL (decl) would be error_mark_node in that case. */
2129 gcc_assert (!node
->lto_file_data
);
2130 tree ctor
= DECL_INITIAL (decl
);
2131 inchash::hash hstate
;
2133 hstate
.add_int (456346417);
2134 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2135 hstate
.add_hwi (tree_to_shwi (DECL_SIZE (decl
)));
2136 add_expr (ctor
, hstate
);
2137 set_hash (hstate
.end ());
2142 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2146 sem_variable::merge (sem_item
*alias_item
)
2148 gcc_assert (alias_item
->type
== VAR
);
2150 if (!sem_item::target_supports_symbol_aliases_p ())
2153 fprintf (dump_file
, "Not unifying; "
2154 "Symbol aliases are not supported by target\n\n");
2158 if (DECL_EXTERNAL (alias_item
->decl
))
2161 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2165 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2167 varpool_node
*original
= get_node ();
2168 varpool_node
*alias
= alias_var
->get_node ();
2169 bool original_discardable
= false;
2171 bool alias_address_matters
= alias
->address_matters_p ();
2173 /* See if original is in a section that can be discarded if the main
2175 Also consider case where we have resolution info and we know that
2176 original's definition is not going to be used. In this case we can not
2177 create alias to original. */
2178 if (original
->can_be_discarded_p ()
2179 || (node
->resolution
!= LDPR_UNKNOWN
2180 && !decl_binds_to_current_def_p (node
->decl
)))
2181 original_discardable
= true;
2183 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2185 /* Constant pool machinery is not quite ready for aliases.
2186 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2187 For LTO merging does not happen that is an important missing feature.
2188 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2189 flag is dropped and non-local symbol name is assigned. */
2190 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2191 || DECL_IN_CONSTANT_POOL (original
->decl
))
2195 "Not unifying; constant pool variables.\n\n");
2199 /* Do not attempt to mix functions from different user sections;
2200 we do not know what user intends with those. */
2201 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2202 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2203 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2208 "original and alias are in different sections.\n\n");
2212 /* We can not merge if address comparsion metters. */
2213 if (alias_address_matters
&& flag_merge_constants
< 2)
2217 "Not unifying; address of original may be compared.\n\n");
2221 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2224 fprintf (dump_file
, "Not unifying; "
2225 "original and alias have incompatible alignments\n\n");
2230 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2233 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2234 "across comdat group boundary\n\n");
2239 if (original_discardable
)
2242 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2243 "target is discardable\n\n");
2249 gcc_assert (!original
->alias
);
2250 gcc_assert (!alias
->alias
);
2252 alias
->analyzed
= false;
2254 DECL_INITIAL (alias
->decl
) = NULL
;
2255 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2257 alias
->need_bounds_init
= false;
2258 alias
->remove_all_references ();
2259 if (TREE_ADDRESSABLE (alias
->decl
))
2260 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2262 varpool_node::create_alias (alias_var
->decl
, decl
);
2263 alias
->resolve_alias (original
);
2266 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2272 /* Dump symbol to FILE. */
2275 sem_variable::dump_to_file (FILE *file
)
2279 print_node (file
, "", decl
, 0);
2280 fprintf (file
, "\n\n");
2283 unsigned int sem_item_optimizer::class_id
= 0;
2285 sem_item_optimizer::sem_item_optimizer ()
2286 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2287 m_varpool_node_hooks (NULL
), m_merged_variables ()
2290 bitmap_obstack_initialize (&m_bmstack
);
2293 sem_item_optimizer::~sem_item_optimizer ()
2295 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2299 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2300 it
!= m_classes
.end (); ++it
)
2302 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2303 delete (*it
)->classes
[i
];
2305 (*it
)->classes
.release ();
2311 bitmap_obstack_release (&m_bmstack
);
2312 m_merged_variables
.release ();
2315 /* Write IPA ICF summary for symbols. */
2318 sem_item_optimizer::write_summary (void)
2320 unsigned int count
= 0;
2322 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2323 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2326 /* Calculate number of symbols to be serialized. */
2327 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2329 lsei_next_in_partition (&lsei
))
2331 symtab_node
*node
= lsei_node (lsei
);
2333 if (m_symtab_node_map
.get (node
))
2337 streamer_write_uhwi (ob
, count
);
2339 /* Process all of the symbols. */
2340 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2342 lsei_next_in_partition (&lsei
))
2344 symtab_node
*node
= lsei_node (lsei
);
2346 sem_item
**item
= m_symtab_node_map
.get (node
);
2350 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2351 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2353 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2357 streamer_write_char_stream (ob
->main_stream
, 0);
2358 produce_asm (ob
, NULL
);
2359 destroy_output_block (ob
);
2362 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2363 contains LEN bytes. */
2366 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2367 const char *data
, size_t len
)
2369 const lto_function_header
*header
2370 = (const lto_function_header
*) data
;
2371 const int cfg_offset
= sizeof (lto_function_header
);
2372 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2373 const int string_offset
= main_offset
+ header
->main_size
;
2378 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2379 header
->main_size
, file_data
->mode_table
);
2382 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2383 header
->string_size
, vNULL
);
2385 count
= streamer_read_uhwi (&ib_main
);
2387 for (i
= 0; i
< count
; i
++)
2391 lto_symtab_encoder_t encoder
;
2393 index
= streamer_read_uhwi (&ib_main
);
2394 encoder
= file_data
->symtab_node_encoder
;
2395 node
= lto_symtab_encoder_deref (encoder
, index
);
2397 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2399 gcc_assert (node
->definition
);
2402 fprintf (dump_file
, "Symbol added: %s (tree: %p)\n",
2403 node
->dump_asm_name (), (void *) node
->decl
);
2405 if (is_a
<cgraph_node
*> (node
))
2407 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2409 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2410 fn
->set_hash (hash
);
2411 m_items
.safe_push (fn
);
2415 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2417 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2418 var
->set_hash (hash
);
2419 m_items
.safe_push (var
);
2423 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2425 lto_data_in_delete (data_in
);
2428 /* Read IPA ICF summary for symbols. */
2431 sem_item_optimizer::read_summary (void)
2433 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2434 lto_file_decl_data
*file_data
;
2437 while ((file_data
= file_data_vec
[j
++]))
2440 const char *data
= lto_get_section_data (file_data
,
2441 LTO_section_ipa_icf
, NULL
, &len
);
2444 read_section (file_data
, data
, len
);
2448 /* Register callgraph and varpool hooks. */
2451 sem_item_optimizer::register_hooks (void)
2453 if (!m_cgraph_node_hooks
)
2454 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2455 (&sem_item_optimizer::cgraph_removal_hook
, this);
2457 if (!m_varpool_node_hooks
)
2458 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2459 (&sem_item_optimizer::varpool_removal_hook
, this);
2462 /* Unregister callgraph and varpool hooks. */
2465 sem_item_optimizer::unregister_hooks (void)
2467 if (m_cgraph_node_hooks
)
2468 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2470 if (m_varpool_node_hooks
)
2471 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2474 /* Adds a CLS to hashtable associated by hash value. */
2477 sem_item_optimizer::add_class (congruence_class
*cls
)
2479 gcc_assert (cls
->members
.length ());
2481 congruence_class_group
*group
2482 = get_group_by_hash (cls
->members
[0]->get_hash (),
2483 cls
->members
[0]->type
);
2484 group
->classes
.safe_push (cls
);
2487 /* Gets a congruence class group based on given HASH value and TYPE. */
2489 congruence_class_group
*
2490 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2492 congruence_class_group
*item
= XNEW (congruence_class_group
);
2496 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2502 item
->classes
.create (1);
2509 /* Callgraph removal hook called for a NODE with a custom DATA. */
2512 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2514 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2515 optimizer
->remove_symtab_node (node
);
2518 /* Varpool removal hook called for a NODE with a custom DATA. */
2521 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2523 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2524 optimizer
->remove_symtab_node (node
);
2527 /* Remove symtab NODE triggered by symtab removal hooks. */
2530 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2532 gcc_assert (!m_classes
.elements ());
2534 m_removed_items_set
.add (node
);
2538 sem_item_optimizer::remove_item (sem_item
*item
)
2540 if (m_symtab_node_map
.get (item
->node
))
2541 m_symtab_node_map
.remove (item
->node
);
2545 /* Removes all callgraph and varpool nodes that are marked by symtab
2549 sem_item_optimizer::filter_removed_items (void)
2551 auto_vec
<sem_item
*> filtered
;
2553 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2555 sem_item
*item
= m_items
[i
];
2557 if (m_removed_items_set
.contains (item
->node
))
2563 if (item
->type
== FUNC
)
2565 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2567 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2570 filtered
.safe_push (item
);
2574 if (!flag_ipa_icf_variables
)
2578 /* Filter out non-readonly variables. */
2579 tree decl
= item
->decl
;
2580 if (TREE_READONLY (decl
))
2581 filtered
.safe_push (item
);
2588 /* Clean-up of released semantic items. */
2591 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2592 m_items
.safe_push (filtered
[i
]);
2595 /* Optimizer entry point which returns true in case it processes
2596 a merge operation. True is returned if there's a merge operation
2600 sem_item_optimizer::execute (void)
2602 filter_removed_items ();
2603 unregister_hooks ();
2606 update_hash_by_addr_refs ();
2607 build_hash_based_classes ();
2610 fprintf (dump_file
, "Dump after hash based groups\n");
2611 dump_cong_classes ();
2613 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2614 m_items
[i
]->init_wpa ();
2616 subdivide_classes_by_equality (true);
2619 fprintf (dump_file
, "Dump after WPA based types groups\n");
2621 dump_cong_classes ();
2623 process_cong_reduction ();
2624 checking_verify_classes ();
2627 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2629 dump_cong_classes ();
2631 parse_nonsingleton_classes ();
2632 subdivide_classes_by_equality ();
2635 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2637 dump_cong_classes ();
2639 unsigned int prev_class_count
= m_classes_count
;
2641 process_cong_reduction ();
2642 dump_cong_classes ();
2643 checking_verify_classes ();
2644 bool merged_p
= merge_classes (prev_class_count
);
2646 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2647 symtab
->dump (dump_file
);
2652 /* Function responsible for visiting all potential functions and
2653 read-only variables that can be merged. */
2656 sem_item_optimizer::parse_funcs_and_vars (void)
2660 if (flag_ipa_icf_functions
)
2661 FOR_EACH_DEFINED_FUNCTION (cnode
)
2663 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2666 m_items
.safe_push (f
);
2667 m_symtab_node_map
.put (cnode
, f
);
2670 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2673 f
->dump_to_file (dump_file
);
2676 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2679 varpool_node
*vnode
;
2681 if (flag_ipa_icf_variables
)
2682 FOR_EACH_DEFINED_VARIABLE (vnode
)
2684 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2688 m_items
.safe_push (v
);
2689 m_symtab_node_map
.put (vnode
, v
);
2694 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2697 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2699 item
->index_in_class
= cls
->members
.length ();
2700 cls
->members
.safe_push (item
);
2704 /* For each semantic item, append hash values of references. */
2707 sem_item_optimizer::update_hash_by_addr_refs ()
2709 /* First, append to hash sensitive references and class type if it need to
2710 be matched for ODR. */
2711 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2713 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2714 if (m_items
[i
]->type
== FUNC
)
2716 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2717 && contains_polymorphic_type_p
2718 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2719 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2720 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2721 && static_cast<sem_function
*> (m_items
[i
])
2722 ->compare_polymorphic_p ())))
2725 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2726 inchash::hash
hstate (m_items
[i
]->get_hash ());
2728 if (TYPE_NAME (class_type
)
2729 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2731 (IDENTIFIER_HASH_VALUE
2732 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2734 m_items
[i
]->set_hash (hstate
.end ());
2739 /* Once all symbols have enhanced hash value, we can append
2740 hash values of symbols that are seen by IPA ICF and are
2741 references by a semantic item. Newly computed values
2742 are saved to global_hash member variable. */
2743 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2744 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2746 /* Global hash value replace current hash values. */
2747 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2748 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2751 /* Congruence classes are built by hash value. */
2754 sem_item_optimizer::build_hash_based_classes (void)
2756 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2758 sem_item
*item
= m_items
[i
];
2760 congruence_class_group
*group
2761 = get_group_by_hash (item
->get_hash (), item
->type
);
2763 if (!group
->classes
.length ())
2766 group
->classes
.safe_push (new congruence_class (class_id
++));
2769 add_item_to_class (group
->classes
[0], item
);
2773 /* Build references according to call graph. */
2776 sem_item_optimizer::build_graph (void)
2778 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2780 sem_item
*item
= m_items
[i
];
2781 m_symtab_node_map
.put (item
->node
, item
);
2783 /* Initialize hash values if we are not in LTO mode. */
2788 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2790 sem_item
*item
= m_items
[i
];
2792 if (item
->type
== FUNC
)
2794 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2796 cgraph_edge
*e
= cnode
->callees
;
2799 sem_item
**slot
= m_symtab_node_map
.get
2800 (e
->callee
->ultimate_alias_target ());
2802 item
->add_reference (*slot
);
2808 ipa_ref
*ref
= NULL
;
2809 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2811 sem_item
**slot
= m_symtab_node_map
.get
2812 (ref
->referred
->ultimate_alias_target ());
2814 item
->add_reference (*slot
);
2819 /* Semantic items in classes having more than one element and initialized.
2820 In case of WPA, we load function body. */
2823 sem_item_optimizer::parse_nonsingleton_classes (void)
2825 unsigned int init_called_count
= 0;
2827 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2828 if (m_items
[i
]->cls
->members
.length () > 1)
2830 m_items
[i
]->init ();
2831 init_called_count
++;
2835 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n",
2837 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length ()
2841 /* Equality function for semantic items is used to subdivide existing
2842 classes. If IN_WPA, fast equality function is invoked. */
2845 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2847 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2848 it
!= m_classes
.end (); ++it
)
2850 unsigned int class_count
= (*it
)->classes
.length ();
2852 for (unsigned i
= 0; i
< class_count
; i
++)
2854 congruence_class
*c
= (*it
)->classes
[i
];
2856 if (c
->members
.length() > 1)
2858 auto_vec
<sem_item
*> new_vector
;
2860 sem_item
*first
= c
->members
[0];
2861 new_vector
.safe_push (first
);
2863 unsigned class_split_first
= (*it
)->classes
.length ();
2865 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2867 sem_item
*item
= c
->members
[j
];
2870 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2871 : first
->equals (item
, m_symtab_node_map
);
2874 new_vector
.safe_push (item
);
2877 bool integrated
= false;
2879 for (unsigned k
= class_split_first
;
2880 k
< (*it
)->classes
.length (); k
++)
2882 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2884 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2885 : x
->equals (item
, m_symtab_node_map
);
2890 add_item_to_class ((*it
)->classes
[k
], item
);
2899 = new congruence_class (class_id
++);
2901 add_item_to_class (c
, item
);
2903 (*it
)->classes
.safe_push (c
);
2908 // We replace newly created new_vector for the class we've just
2910 c
->members
.release ();
2911 c
->members
.create (new_vector
.length ());
2913 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2914 add_item_to_class (c
, new_vector
[j
]);
2919 checking_verify_classes ();
2922 /* Subdivide classes by address references that members of the class
2923 reference. Example can be a pair of functions that have an address
2924 taken from a function. If these addresses are different the class
2928 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2930 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2932 unsigned newly_created_classes
= 0;
2934 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2935 it
!= m_classes
.end (); ++it
)
2937 unsigned int class_count
= (*it
)->classes
.length ();
2938 auto_vec
<congruence_class
*> new_classes
;
2940 for (unsigned i
= 0; i
< class_count
; i
++)
2942 congruence_class
*c
= (*it
)->classes
[i
];
2944 if (c
->members
.length() > 1)
2946 subdivide_hash_map split_map
;
2948 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2950 sem_item
*source_node
= c
->members
[j
];
2952 symbol_compare_collection
*collection
2953 = new symbol_compare_collection (source_node
->node
);
2956 vec
<sem_item
*> *slot
2957 = &split_map
.get_or_insert (collection
, &existed
);
2958 gcc_checking_assert (slot
);
2960 slot
->safe_push (source_node
);
2966 /* If the map contains more than one key, we have to split
2967 the map appropriately. */
2968 if (split_map
.elements () != 1)
2970 bool first_class
= true;
2972 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2973 it2
!= split_map
.end (); ++it2
)
2975 congruence_class
*new_cls
;
2976 new_cls
= new congruence_class (class_id
++);
2978 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2979 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2981 worklist_push (new_cls
);
2982 newly_created_classes
++;
2986 (*it
)->classes
[i
] = new_cls
;
2987 first_class
= false;
2991 new_classes
.safe_push (new_cls
);
2997 /* Release memory. */
2998 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2999 it2
!= split_map
.end (); ++it2
)
3001 delete (*it2
).first
;
3002 (*it2
).second
.release ();
3007 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
3008 (*it
)->classes
.safe_push (new_classes
[i
]);
3011 return newly_created_classes
;
3014 /* Verify congruence classes, if checking is enabled. */
3017 sem_item_optimizer::checking_verify_classes (void)
3023 /* Verify congruence classes. */
3026 sem_item_optimizer::verify_classes (void)
3028 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3029 it
!= m_classes
.end (); ++it
)
3031 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3033 congruence_class
*cls
= (*it
)->classes
[i
];
3036 gcc_assert (cls
->members
.length () > 0);
3038 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3040 sem_item
*item
= cls
->members
[j
];
3043 gcc_assert (item
->cls
== cls
);
3045 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3047 sem_usage_pair
*usage
= item
->usages
[k
];
3048 gcc_assert (usage
->item
->index_in_class
3049 < usage
->item
->cls
->members
.length ());
3056 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3057 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3058 but unused argument. */
3061 sem_item_optimizer::release_split_map (congruence_class
* const &,
3062 bitmap
const &b
, traverse_split_pair
*)
3071 /* Process split operation for a class given as pointer CLS_PTR,
3072 where bitmap B splits congruence class members. DATA is used
3073 as argument of split pair. */
3076 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3078 traverse_split_pair
*pair
)
3080 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3081 const congruence_class
*splitter_cls
= pair
->cls
;
3083 /* If counted bits are greater than zero and less than the number of members
3084 a group will be splitted. */
3085 unsigned popcount
= bitmap_count_bits (b
);
3087 if (popcount
> 0 && popcount
< cls
->members
.length ())
3089 auto_vec
<congruence_class
*, 2> newclasses
;
3090 newclasses
.quick_push (new congruence_class (class_id
++));
3091 newclasses
.quick_push (new congruence_class (class_id
++));
3093 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3095 int target
= bitmap_bit_p (b
, i
);
3096 congruence_class
*tc
= newclasses
[target
];
3098 add_item_to_class (tc
, cls
->members
[i
]);
3103 for (unsigned int i
= 0; i
< 2; i
++)
3104 gcc_assert (newclasses
[i
]->members
.length ());
3107 if (splitter_cls
== cls
)
3108 optimizer
->splitter_class_removed
= true;
3110 /* Remove old class from worklist if presented. */
3111 bool in_worklist
= cls
->in_worklist
;
3114 cls
->in_worklist
= false;
3116 congruence_class_group g
;
3117 g
.hash
= cls
->members
[0]->get_hash ();
3118 g
.type
= cls
->members
[0]->type
;
3120 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
3122 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3123 if (slot
->classes
[i
] == cls
)
3125 slot
->classes
.ordered_remove (i
);
3129 /* New class will be inserted and integrated to work list. */
3130 for (unsigned int i
= 0; i
< 2; i
++)
3131 optimizer
->add_class (newclasses
[i
]);
3133 /* Two classes replace one, so that increment just by one. */
3134 optimizer
->m_classes_count
++;
3136 /* If OLD class was presented in the worklist, we remove the class
3137 and replace it will both newly created classes. */
3139 for (unsigned int i
= 0; i
< 2; i
++)
3140 optimizer
->worklist_push (newclasses
[i
]);
3141 else /* Just smaller class is inserted. */
3143 unsigned int smaller_index
3144 = (newclasses
[0]->members
.length ()
3145 < newclasses
[1]->members
.length ()
3147 optimizer
->worklist_push (newclasses
[smaller_index
]);
3150 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3152 fprintf (dump_file
, " congruence class splitted:\n");
3153 cls
->dump (dump_file
, 4);
3155 fprintf (dump_file
, " newly created groups:\n");
3156 for (unsigned int i
= 0; i
< 2; i
++)
3157 newclasses
[i
]->dump (dump_file
, 4);
3160 /* Release class if not presented in work list. */
3169 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3170 Bitmap stack BMSTACK is used for bitmap allocation. */
3173 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3176 hash_map
<congruence_class
*, bitmap
> split_map
;
3178 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3180 sem_item
*item
= cls
->members
[i
];
3182 /* Iterate all usages that have INDEX as usage of the item. */
3183 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3185 sem_usage_pair
*usage
= item
->usages
[j
];
3187 if (usage
->index
!= index
)
3190 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3195 b
= BITMAP_ALLOC (&m_bmstack
);
3196 split_map
.put (usage
->item
->cls
, b
);
3201 gcc_checking_assert (usage
->item
->cls
);
3202 gcc_checking_assert (usage
->item
->index_in_class
3203 < usage
->item
->cls
->members
.length ());
3205 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3209 traverse_split_pair pair
;
3210 pair
.optimizer
= this;
3213 splitter_class_removed
= false;
3214 split_map
.traverse
<traverse_split_pair
*,
3215 sem_item_optimizer::traverse_congruence_split
> (&pair
);
3217 /* Bitmap clean-up. */
3218 split_map
.traverse
<traverse_split_pair
*,
3219 sem_item_optimizer::release_split_map
> (NULL
);
3222 /* Every usage of a congruence class CLS is a candidate that can split the
3223 collection of classes. Bitmap stack BMSTACK is used for bitmap
3227 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3232 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3234 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3235 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3237 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3240 fprintf (dump_file
, " processing congruence step for class: %u, "
3241 "index: %u\n", cls
->id
, i
);
3243 do_congruence_step_for_index (cls
, i
);
3245 if (splitter_class_removed
)
3249 BITMAP_FREE (usage
);
3252 /* Adds a newly created congruence class CLS to worklist. */
3255 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3257 /* Return if the class CLS is already presented in work list. */
3258 if (cls
->in_worklist
)
3261 cls
->in_worklist
= true;
3262 worklist
.push_back (cls
);
3265 /* Pops a class from worklist. */
3268 sem_item_optimizer::worklist_pop (void)
3270 congruence_class
*cls
;
3272 while (!worklist
.empty ())
3274 cls
= worklist
.front ();
3275 worklist
.pop_front ();
3276 if (cls
->in_worklist
)
3278 cls
->in_worklist
= false;
3284 /* Work list item was already intended to be removed.
3285 The only reason for doing it is to split a class.
3286 Thus, the class CLS is deleted. */
3294 /* Iterative congruence reduction function. */
3297 sem_item_optimizer::process_cong_reduction (void)
3299 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3300 it
!= m_classes
.end (); ++it
)
3301 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3302 if ((*it
)->classes
[i
]->is_class_used ())
3303 worklist_push ((*it
)->classes
[i
]);
3306 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3307 (unsigned long) worklist
.size ());
3309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3310 fprintf (dump_file
, "Congruence class reduction\n");
3312 congruence_class
*cls
;
3314 /* Process complete congruence reduction. */
3315 while ((cls
= worklist_pop ()) != NULL
)
3316 do_congruence_step (cls
);
3318 /* Subdivide newly created classes according to references. */
3319 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3322 fprintf (dump_file
, "Address reference subdivision created: %u "
3323 "new classes.\n", new_classes
);
3326 /* Debug function prints all informations about congruence classes. */
3329 sem_item_optimizer::dump_cong_classes (void)
3335 "Congruence classes: %u (unique hash values: %lu), with total: "
3336 "%u items\n", m_classes_count
,
3337 (unsigned long) m_classes
.elements (), m_items
.length ());
3339 /* Histogram calculation. */
3340 unsigned int max_index
= 0;
3341 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3343 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3344 it
!= m_classes
.end (); ++it
)
3345 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3347 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3355 "Class size histogram [num of members]: number of classe number "
3358 for (unsigned int i
= 0; i
<= max_index
; i
++)
3360 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3362 fprintf (dump_file
, "\n\n");
3364 if (dump_flags
& TDF_DETAILS
)
3365 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3366 it
!= m_classes
.end (); ++it
)
3368 fprintf (dump_file
, " group: with %u classes:\n",
3369 (*it
)->classes
.length ());
3371 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3373 (*it
)->classes
[i
]->dump (dump_file
, 4);
3375 if (i
< (*it
)->classes
.length () - 1)
3376 fprintf (dump_file
, " ");
3383 /* Sort pair of sem_items A and B by DECL_UID. */
3386 sort_sem_items_by_decl_uid (const void *a
, const void *b
)
3388 const sem_item
*i1
= *(const sem_item
* const *)a
;
3389 const sem_item
*i2
= *(const sem_item
* const *)b
;
3391 int uid1
= DECL_UID (i1
->decl
);
3392 int uid2
= DECL_UID (i2
->decl
);
3396 else if (uid1
> uid2
)
3402 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3405 sort_congruence_classes_by_decl_uid (const void *a
, const void *b
)
3407 const congruence_class
*c1
= *(const congruence_class
* const *)a
;
3408 const congruence_class
*c2
= *(const congruence_class
* const *)b
;
3410 int uid1
= DECL_UID (c1
->members
[0]->decl
);
3411 int uid2
= DECL_UID (c2
->members
[0]->decl
);
3415 else if (uid1
> uid2
)
3421 /* Sort pair of congruence_class_groups A and B by
3422 DECL_UID of the first member of a first group. */
3425 sort_congruence_class_groups_by_decl_uid (const void *a
, const void *b
)
3427 const congruence_class_group
*g1
3428 = *(const congruence_class_group
* const *)a
;
3429 const congruence_class_group
*g2
3430 = *(const congruence_class_group
* const *)b
;
3432 int uid1
= DECL_UID (g1
->classes
[0]->members
[0]->decl
);
3433 int uid2
= DECL_UID (g2
->classes
[0]->members
[0]->decl
);
3437 else if (uid1
> uid2
)
3443 /* After reduction is done, we can declare all items in a group
3444 to be equal. PREV_CLASS_COUNT is start number of classes
3445 before reduction. True is returned if there's a merge operation
3449 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3451 unsigned int item_count
= m_items
.length ();
3452 unsigned int class_count
= m_classes_count
;
3453 unsigned int equal_items
= item_count
- class_count
;
3455 unsigned int non_singular_classes_count
= 0;
3456 unsigned int non_singular_classes_sum
= 0;
3458 bool merged_p
= false;
3461 Sort functions in congruence classes by DECL_UID and do the same
3462 for the classes to not to break -fcompare-debug. */
3464 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3465 it
!= m_classes
.end (); ++it
)
3467 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3469 congruence_class
*c
= (*it
)->classes
[i
];
3470 c
->members
.qsort (sort_sem_items_by_decl_uid
);
3473 (*it
)->classes
.qsort (sort_congruence_classes_by_decl_uid
);
3476 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3477 it
!= m_classes
.end (); ++it
)
3478 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3480 congruence_class
*c
= (*it
)->classes
[i
];
3481 if (c
->members
.length () > 1)
3483 non_singular_classes_count
++;
3484 non_singular_classes_sum
+= c
->members
.length ();
3488 auto_vec
<congruence_class_group
*> classes (m_classes
.elements ());
3489 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3490 it
!= m_classes
.end (); ++it
)
3491 classes
.quick_push (*it
);
3493 classes
.qsort (sort_congruence_class_groups_by_decl_uid
);
3497 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3498 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3499 prev_class_count
, class_count
);
3500 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3501 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3502 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3503 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3504 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3505 non_singular_classes_count
: 0.0f
,
3506 non_singular_classes_count
);
3507 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3508 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3509 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3513 congruence_class_group
*it
;
3514 FOR_EACH_VEC_ELT (classes
, l
, it
)
3515 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
3517 congruence_class
*c
= it
->classes
[i
];
3519 if (c
->members
.length () == 1)
3522 sem_item
*source
= c
->members
[0];
3524 if (DECL_NAME (source
->decl
)
3525 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3526 /* If merge via wrappers, picking main as the target can be
3528 source
= c
->members
[1];
3530 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3532 sem_item
*alias
= c
->members
[j
];
3534 if (alias
== source
)
3539 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3540 xstrdup_for_dump (source
->node
->name ()),
3541 xstrdup_for_dump (alias
->node
->name ()));
3542 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3543 xstrdup_for_dump (source
->node
->asm_name ()),
3544 xstrdup_for_dump (alias
->node
->asm_name ()));
3547 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3551 "Merge operation is skipped due to no_icf "
3557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3559 source
->dump_to_file (dump_file
);
3560 alias
->dump_to_file (dump_file
);
3563 if (dbg_cnt (merged_ipa_icf
))
3565 bool merged
= source
->merge (alias
);
3568 if (merged
&& alias
->type
== VAR
)
3570 symtab_pair p
= symtab_pair (source
->node
, alias
->node
);
3571 m_merged_variables
.safe_push (p
);
3577 if (!m_merged_variables
.is_empty ())
3578 fixup_points_to_sets ();
3583 /* Fixup points to set PT. */
3586 sem_item_optimizer::fixup_pt_set (struct pt_solution
*pt
)
3588 if (pt
->vars
== NULL
)
3593 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3594 if (bitmap_bit_p (pt
->vars
, DECL_UID (item
->second
->decl
)))
3595 bitmap_set_bit (pt
->vars
, DECL_UID (item
->first
->decl
));
3598 /* Set all points-to UIDs of aliases pointing to node N as UID. */
3601 set_alias_uids (symtab_node
*n
, int uid
)
3604 FOR_EACH_ALIAS (n
, ref
)
3607 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
3608 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
3610 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
3611 set_alias_uids (ref
->referring
, uid
);
3615 /* Fixup points to analysis info. */
3618 sem_item_optimizer::fixup_points_to_sets (void)
3620 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3623 FOR_EACH_DEFINED_FUNCTION (cnode
)
3627 function
*fn
= DECL_STRUCT_FUNCTION (cnode
->decl
);
3628 if (!gimple_in_ssa_p (fn
))
3631 FOR_EACH_SSA_NAME (i
, name
, fn
)
3632 if (POINTER_TYPE_P (TREE_TYPE (name
))
3633 && SSA_NAME_PTR_INFO (name
))
3634 fixup_pt_set (&SSA_NAME_PTR_INFO (name
)->pt
);
3635 fixup_pt_set (&fn
->gimple_df
->escaped
);
3637 /* The above get's us to 99% I guess, at least catching the
3638 address compares. Below also gets us aliasing correct
3639 but as said we're giving leeway to the situation with
3640 readonly vars anyway, so ... */
3642 FOR_EACH_BB_FN (bb
, fn
)
3643 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
3646 gcall
*call
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
3649 fixup_pt_set (gimple_call_use_set (call
));
3650 fixup_pt_set (gimple_call_clobber_set (call
));
3657 FOR_EACH_VEC_ELT (m_merged_variables
, i
, item
)
3658 set_alias_uids (item
->first
, DECL_UID (item
->first
->decl
));
3661 /* Dump function prints all class members to a FILE with an INDENT. */
3664 congruence_class::dump (FILE *file
, unsigned int indent
) const
3666 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3667 id
, members
[0]->get_hash (), members
.length ());
3669 FPUTS_SPACES (file
, indent
+ 2, "");
3670 for (unsigned i
= 0; i
< members
.length (); i
++)
3671 fprintf (file
, "%s ", members
[i
]->node
->dump_asm_name ());
3673 fprintf (file
, "\n");
3676 /* Returns true if there's a member that is used from another group. */
3679 congruence_class::is_class_used (void)
3681 for (unsigned int i
= 0; i
< members
.length (); i
++)
3682 if (members
[i
]->usages
.length ())
3688 /* Generate pass summary for IPA ICF pass. */
3691 ipa_icf_generate_summary (void)
3694 optimizer
= new sem_item_optimizer ();
3696 optimizer
->register_hooks ();
3697 optimizer
->parse_funcs_and_vars ();
3700 /* Write pass summary for IPA ICF pass. */
3703 ipa_icf_write_summary (void)
3705 gcc_assert (optimizer
);
3707 optimizer
->write_summary ();
3710 /* Read pass summary for IPA ICF pass. */
3713 ipa_icf_read_summary (void)
3716 optimizer
= new sem_item_optimizer ();
3718 optimizer
->read_summary ();
3719 optimizer
->register_hooks ();
3722 /* Semantic equality exection function. */
3725 ipa_icf_driver (void)
3727 gcc_assert (optimizer
);
3729 bool merged_p
= optimizer
->execute ();
3734 return merged_p
? TODO_remove_functions
: 0;
3737 const pass_data pass_data_ipa_icf
=
3739 IPA_PASS
, /* type */
3741 OPTGROUP_IPA
, /* optinfo_flags */
3742 TV_IPA_ICF
, /* tv_id */
3743 0, /* properties_required */
3744 0, /* properties_provided */
3745 0, /* properties_destroyed */
3746 0, /* todo_flags_start */
3747 0, /* todo_flags_finish */
3750 class pass_ipa_icf
: public ipa_opt_pass_d
3753 pass_ipa_icf (gcc::context
*ctxt
)
3754 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3755 ipa_icf_generate_summary
, /* generate_summary */
3756 ipa_icf_write_summary
, /* write_summary */
3757 ipa_icf_read_summary
, /* read_summary */
3759 write_optimization_summary */
3761 read_optimization_summary */
3762 NULL
, /* stmt_fixup */
3763 0, /* function_transform_todo_flags_start */
3764 NULL
, /* function_transform */
3765 NULL
) /* variable_transform */
3768 /* opt_pass methods: */
3769 virtual bool gate (function
*)
3771 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3774 virtual unsigned int execute (function
*)
3776 return ipa_icf_driver();
3778 }; // class pass_ipa_icf
3780 } // ipa_icf namespace
3783 make_pass_ipa_icf (gcc::context
*ctxt
)
3785 return new ipa_icf::pass_ipa_icf (ctxt
);