1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2017 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-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
135 : item (_item
), index (_index
)
139 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
140 : type (_type
), m_hash (-1), m_hash_set (false)
145 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
146 bitmap_obstack
*stack
)
147 : type (_type
), node (_node
), m_hash (-1), m_hash_set (false)
153 /* Add reference to a semantic TARGET. */
156 sem_item::add_reference (sem_item
*target
)
158 refs
.safe_push (target
);
159 unsigned index
= refs
.length ();
160 target
->usages
.safe_push (new sem_usage_pair(this, index
));
161 bitmap_set_bit (target
->usage_index_bitmap
, index
);
162 refs_set
.add (target
->node
);
165 /* Initialize internal data structures. Bitmap STACK is used for
166 bitmap memory allocation process. */
169 sem_item::setup (bitmap_obstack
*stack
)
171 gcc_checking_assert (node
);
174 tree_refs
.create (0);
176 usage_index_bitmap
= BITMAP_ALLOC (stack
);
179 sem_item::~sem_item ()
181 for (unsigned i
= 0; i
< usages
.length (); i
++)
185 tree_refs
.release ();
188 BITMAP_FREE (usage_index_bitmap
);
191 /* Dump function for debugging purpose. */
194 sem_item::dump (void)
198 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
199 node
->name(), node
->order
, (void *) node
->decl
);
200 fprintf (dump_file
, " hash: %u\n", get_hash ());
201 fprintf (dump_file
, " references: ");
203 for (unsigned i
= 0; i
< refs
.length (); i
++)
204 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
205 i
< refs
.length() - 1 ? "," : "");
207 fprintf (dump_file
, "\n");
211 /* Return true if target supports alias symbols. */
214 sem_item::target_supports_symbol_aliases_p (void)
216 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
223 void sem_item::set_hash (hashval_t hash
)
229 /* Semantic function constructor that uses STACK as bitmap memory stack. */
231 sem_function::sem_function (bitmap_obstack
*stack
)
232 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
235 bb_sorted
.create (0);
238 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
239 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
242 bb_sorted
.create (0);
245 sem_function::~sem_function ()
247 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
248 delete (bb_sorted
[i
]);
251 bb_sorted
.release ();
254 /* Calculates hash value based on a BASIC_BLOCK. */
257 sem_function::get_bb_hash (const sem_bb
*basic_block
)
259 inchash::hash hstate
;
261 hstate
.add_int (basic_block
->nondbg_stmt_count
);
262 hstate
.add_int (basic_block
->edge_count
);
264 return hstate
.end ();
267 /* References independent hash function. */
270 sem_function::get_hash (void)
274 inchash::hash hstate
;
275 hstate
.add_int (177454); /* Random number for function type. */
277 hstate
.add_int (arg_count
);
278 hstate
.add_int (cfg_checksum
);
279 hstate
.add_int (gcode_hash
);
281 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
282 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
284 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
285 hstate
.add_int (bb_sizes
[i
]);
287 /* Add common features of declaration itself. */
288 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
290 (cl_target_option_hash
291 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
292 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
294 (cl_optimization_hash
295 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
296 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
297 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
299 set_hash (hstate
.end ());
305 /* Return ture if A1 and A2 represent equivalent function attribute lists.
306 Based on comp_type_attributes. */
309 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
314 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
316 const struct attribute_spec
*as
;
319 as
= lookup_attribute_spec (get_attribute_name (a
));
320 /* TODO: We can introduce as->affects_decl_identity
321 and as->affects_decl_reference_identity if attribute mismatch
322 gets a common reason to give up on merging. It may not be worth
324 For example returns_nonnull affects only references, while
325 optimize attribute can be ignored because it is already lowered
326 into flags representation and compared separately. */
330 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
331 if (!attr
|| !attribute_value_equal (a
, attr
))
336 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
338 const struct attribute_spec
*as
;
340 as
= lookup_attribute_spec (get_attribute_name (a
));
344 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
346 /* We don't need to compare trees again, as we did this
347 already in first loop. */
352 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
356 /* Compare properties of symbols N1 and N2 that does not affect semantics of
357 symbol itself but affects semantics of its references from USED_BY (which
358 may be NULL if it is unknown). If comparsion is false, symbols
359 can still be merged but any symbols referring them can't.
361 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
363 TODO: We can also split attributes to those that determine codegen of
364 a function body/variable constructor itself and those that are used when
368 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
373 if (is_a
<cgraph_node
*> (n1
))
375 /* Inline properties matters: we do now want to merge uses of inline
376 function to uses of normal function because inline hint would be lost.
377 We however can merge inline function to noinline because the alias
378 will keep its DECL_DECLARED_INLINE flag.
380 Also ignore inline flag when optimizing for size or when function
381 is known to not be inlinable.
383 TODO: the optimize_size checks can also be assumed to be true if
384 unit has no !optimize_size functions. */
386 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
387 || !opt_for_fn (used_by
->decl
, optimize_size
))
388 && !opt_for_fn (n1
->decl
, optimize_size
)
389 && n1
->get_availability () > AVAIL_INTERPOSABLE
390 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
392 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
393 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
394 return return_false_with_msg
395 ("DECL_DISREGARD_INLINE_LIMITS are different");
397 if (DECL_DECLARED_INLINE_P (n1
->decl
)
398 != DECL_DECLARED_INLINE_P (n2
->decl
))
399 return return_false_with_msg ("inline attributes are different");
402 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
403 != DECL_IS_OPERATOR_NEW (n2
->decl
))
404 return return_false_with_msg ("operator new flags are different");
407 /* Merging two definitions with a reference to equivalent vtables, but
408 belonging to a different type may result in ipa-polymorphic-call analysis
409 giving a wrong answer about the dynamic type of instance. */
410 if (is_a
<varpool_node
*> (n1
))
412 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
413 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
414 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
415 DECL_CONTEXT (n2
->decl
)))
416 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
417 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
418 return return_false_with_msg
419 ("references to virtual tables can not be merged");
421 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
422 return return_false_with_msg ("alignment mismatch");
424 /* For functions we compare attributes in equals_wpa, because we do
425 not know what attributes may cause codegen differences, but for
426 variables just compare attributes for references - the codegen
427 for constructors is affected only by those attributes that we lower
428 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
429 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
430 DECL_ATTRIBUTES (n2
->decl
)))
431 return return_false_with_msg ("different var decl attributes");
432 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
433 TREE_TYPE (n2
->decl
)) != 1)
434 return return_false_with_msg ("different var type attributes");
437 /* When matching virtual tables, be sure to also match information
438 relevant for polymorphic call analysis. */
439 if (used_by
&& is_a
<varpool_node
*> (used_by
)
440 && DECL_VIRTUAL_P (used_by
->decl
))
442 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
443 return return_false_with_msg ("virtual flag mismatch");
444 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
445 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
446 return return_false_with_msg ("final flag mismatch");
451 /* Hash properties that are compared by compare_referenced_symbol_properties. */
454 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
455 inchash::hash
&hstate
,
458 if (is_a
<cgraph_node
*> (ref
))
460 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
461 && !opt_for_fn (ref
->decl
, optimize_size
)
462 && !DECL_UNINLINABLE (ref
->decl
))
464 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
465 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
467 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
469 else if (is_a
<varpool_node
*> (ref
))
471 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
473 hstate
.add_int (DECL_ALIGN (ref
->decl
));
478 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
479 point to a same function. Comparison can be skipped if IGNORED_NODES
480 contains these nodes. ADDRESS indicate if address is taken. */
483 sem_item::compare_symbol_references (
484 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
485 symtab_node
*n1
, symtab_node
*n2
, bool address
)
487 enum availability avail1
, avail2
;
492 /* Never match variable and function. */
493 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
496 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
498 if (address
&& n1
->equal_address_to (n2
) == 1)
500 if (!address
&& n1
->semantically_equivalent_p (n2
))
503 n1
= n1
->ultimate_alias_target (&avail1
);
504 n2
= n2
->ultimate_alias_target (&avail2
);
506 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
507 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
510 return return_false_with_msg ("different references");
513 /* If cgraph edges E1 and E2 are indirect calls, verify that
514 ECF flags are the same. */
516 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
518 if (e1
->indirect_info
&& e2
->indirect_info
)
520 int e1_flags
= e1
->indirect_info
->ecf_flags
;
521 int e2_flags
= e2
->indirect_info
->ecf_flags
;
523 if (e1_flags
!= e2_flags
)
524 return return_false_with_msg ("ICF flags are different");
526 else if (e1
->indirect_info
|| e2
->indirect_info
)
532 /* Return true if parameter I may be used. */
535 sem_function::param_used_p (unsigned int i
)
537 if (ipa_node_params_sum
== NULL
)
540 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
542 if (parms_info
->descriptors
.is_empty ()
543 || parms_info
->descriptors
.length () <= i
)
546 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
549 /* Perform additional check needed to match types function parameters that are
550 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
551 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
554 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
556 /* Be sure that parameters are TBAA compatible. */
557 if (!func_checker::compatible_types_p (parm1
, parm2
))
558 return return_false_with_msg ("parameter type is not compatible");
560 if (POINTER_TYPE_P (parm1
)
561 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
562 return return_false_with_msg ("argument restrict flag mismatch");
564 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
565 if (POINTER_TYPE_P (parm1
)
566 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
567 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
568 return return_false_with_msg ("pointer wrt reference mismatch");
573 /* Fast equality function based on knowledge known in WPA. */
576 sem_function::equals_wpa (sem_item
*item
,
577 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
579 gcc_assert (item
->type
== FUNC
);
580 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
581 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
583 m_compared_func
= static_cast<sem_function
*> (item
);
585 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
586 return return_false_with_msg ("thunk_p mismatch");
588 if (cnode
->thunk
.thunk_p
)
590 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
591 return return_false_with_msg ("thunk fixed_offset mismatch");
592 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
593 return return_false_with_msg ("thunk virtual_value mismatch");
594 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
595 return return_false_with_msg ("thunk this_adjusting mismatch");
596 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
597 return return_false_with_msg ("thunk virtual_offset_p mismatch");
598 if (cnode
->thunk
.add_pointer_bounds_args
599 != cnode2
->thunk
.add_pointer_bounds_args
)
600 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
603 /* Compare special function DECL attributes. */
604 if (DECL_FUNCTION_PERSONALITY (decl
)
605 != DECL_FUNCTION_PERSONALITY (item
->decl
))
606 return return_false_with_msg ("function personalities are different");
608 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
609 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
610 return return_false_with_msg ("intrument function entry exit "
611 "attributes are different");
613 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
614 return return_false_with_msg ("no stack limit attributes are different");
616 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
617 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
619 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
620 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
622 /* TODO: pure/const flags mostly matters only for references, except for
623 the fact that codegen takes LOOPING flag as a hint that loops are
624 finite. We may arrange the code to always pick leader that has least
625 specified flags and then this can go into comparing symbol properties. */
626 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
627 return return_false_with_msg ("decl_or_type flags are different");
629 /* Do not match polymorphic constructors of different types. They calls
630 type memory location for ipa-polymorphic-call and we do not want
631 it to get confused by wrong type. */
632 if (DECL_CXX_CONSTRUCTOR_P (decl
)
633 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
635 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
636 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
637 else if (!func_checker::compatible_polymorphic_types_p
638 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
639 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
640 return return_false_with_msg ("ctor polymorphic type mismatch");
643 /* Checking function TARGET and OPTIMIZATION flags. */
644 cl_target_option
*tar1
= target_opts_for_fn (decl
);
645 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
647 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
651 fprintf (dump_file
, "target flags difference");
652 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
655 return return_false_with_msg ("Target flags are different");
658 cl_optimization
*opt1
= opts_for_fn (decl
);
659 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
661 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
665 fprintf (dump_file
, "optimization flags difference");
666 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
669 return return_false_with_msg ("optimization flags are different");
672 /* Result type checking. */
673 if (!func_checker::compatible_types_p
674 (TREE_TYPE (TREE_TYPE (decl
)),
675 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
676 return return_false_with_msg ("result types are different");
678 /* Checking types of arguments. */
679 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
680 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
681 for (unsigned i
= 0; list1
&& list2
;
682 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
684 tree parm1
= TREE_VALUE (list1
);
685 tree parm2
= TREE_VALUE (list2
);
687 /* This guard is here for function pointer with attributes (pr59927.c). */
688 if (!parm1
|| !parm2
)
689 return return_false_with_msg ("NULL argument type");
691 /* Verify that types are compatible to ensure that both functions
692 have same calling conventions. */
693 if (!types_compatible_p (parm1
, parm2
))
694 return return_false_with_msg ("parameter types are not compatible");
696 if (!param_used_p (i
))
699 /* Perform additional checks for used parameters. */
700 if (!compatible_parm_types_p (parm1
, parm2
))
705 return return_false_with_msg ("Mismatched number of parameters");
707 if (node
->num_references () != item
->node
->num_references ())
708 return return_false_with_msg ("different number of references");
710 /* Checking function attributes.
711 This is quadratic in number of attributes */
712 if (comp_type_attributes (TREE_TYPE (decl
),
713 TREE_TYPE (item
->decl
)) != 1)
714 return return_false_with_msg ("different type attributes");
715 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
716 DECL_ATTRIBUTES (item
->decl
)))
717 return return_false_with_msg ("different decl attributes");
719 /* The type of THIS pointer type memory location for
720 ipa-polymorphic-call-analysis. */
721 if (opt_for_fn (decl
, flag_devirtualize
)
722 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
723 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
725 && compare_polymorphic_p ())
727 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
728 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
729 if (!func_checker::compatible_polymorphic_types_p
730 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
731 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
732 return return_false_with_msg ("THIS pointer ODR type mismatch");
735 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
736 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
738 item
->node
->iterate_reference (i
, ref2
);
740 if (ref
->use
!= ref2
->use
)
741 return return_false_with_msg ("reference use mismatch");
743 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
745 ref
->address_matters_p ()))
749 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
750 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
754 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
757 if (!compare_edge_flags (e1
, e2
))
760 e1
= e1
->next_callee
;
761 e2
= e2
->next_callee
;
765 return return_false_with_msg ("different number of calls");
767 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
768 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
772 if (!compare_edge_flags (e1
, e2
))
775 e1
= e1
->next_callee
;
776 e2
= e2
->next_callee
;
780 return return_false_with_msg ("different number of indirect calls");
785 /* Update hash by address sensitive references. We iterate over all
786 sensitive references (address_matters_p) and we hash ultime alias
787 target of these nodes, which can improve a semantic item hash.
789 Also hash in referenced symbols properties. This can be done at any time
790 (as the properties should not change), but it is convenient to do it here
791 while we walk the references anyway. */
794 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
795 sem_item
*> &m_symtab_node_map
)
798 inchash::hash
hstate (get_hash ());
800 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
802 hstate
.add_int (ref
->use
);
803 hash_referenced_symbol_properties (ref
->referred
, hstate
,
804 ref
->use
== IPA_REF_ADDR
);
805 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
806 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
809 if (is_a
<cgraph_node
*> (node
))
811 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
814 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
815 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
817 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
821 set_hash (hstate
.end ());
824 /* Update hash by computed local hash values taken from different
826 TODO: stronger SCC based hashing would be desirable here. */
829 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
830 sem_item
*> &m_symtab_node_map
)
833 inchash::hash
state (get_hash ());
835 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
837 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
839 state
.merge_hash ((*result
)->get_hash ());
844 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
847 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
849 state
.merge_hash ((*result
)->get_hash ());
853 global_hash
= state
.end ();
856 /* Returns true if the item equals to ITEM given as argument. */
859 sem_function::equals (sem_item
*item
,
860 hash_map
<symtab_node
*, sem_item
*> &)
862 gcc_assert (item
->type
== FUNC
);
863 bool eq
= equals_private (item
);
865 if (m_checker
!= NULL
)
871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
873 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
874 xstrdup_for_dump (node
->name()),
875 xstrdup_for_dump (item
->node
->name ()),
878 xstrdup_for_dump (node
->asm_name ()),
879 xstrdup_for_dump (item
->node
->asm_name ()),
880 eq
? "true" : "false");
885 /* Processes function equality comparison. */
888 sem_function::equals_private (sem_item
*item
)
890 if (item
->type
!= FUNC
)
893 basic_block bb1
, bb2
;
895 edge_iterator ei1
, ei2
;
899 m_compared_func
= static_cast<sem_function
*> (item
);
901 gcc_assert (decl
!= item
->decl
);
903 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
904 || edge_count
!= m_compared_func
->edge_count
905 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
906 return return_false ();
908 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
909 compare_polymorphic_p (),
912 &m_compared_func
->refs_set
);
913 arg1
= DECL_ARGUMENTS (decl
);
914 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
916 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
918 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
919 return return_false_with_msg ("argument types are not compatible");
920 if (!param_used_p (i
))
922 /* Perform additional checks for used parameters. */
923 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
925 if (!m_checker
->compare_decl (arg1
, arg2
))
926 return return_false ();
929 return return_false_with_msg ("Mismatched number of arguments");
931 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
934 /* Fill-up label dictionary. */
935 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
937 m_checker
->parse_labels (bb_sorted
[i
]);
938 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
941 /* Checking all basic blocks. */
942 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
943 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
944 return return_false();
946 dump_message ("All BBs are equal\n");
948 auto_vec
<int> bb_dict
;
950 /* Basic block edges check. */
951 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
953 bb1
= bb_sorted
[i
]->bb
;
954 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
956 ei2
= ei_start (bb2
->preds
);
958 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
962 if (e1
->flags
!= e2
->flags
)
963 return return_false_with_msg ("flags comparison returns false");
965 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
966 return return_false_with_msg ("edge comparison returns false");
968 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
969 return return_false_with_msg ("BB comparison returns false");
971 if (!m_checker
->compare_edge (e1
, e2
))
972 return return_false_with_msg ("edge comparison returns false");
978 /* Basic block PHI nodes comparison. */
979 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
980 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
981 return return_false_with_msg ("PHI node comparison returns false");
986 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
987 Helper for call_for_symbol_thunks_and_aliases. */
990 set_local (cgraph_node
*node
, void *data
)
992 node
->local
.local
= data
!= NULL
;
996 /* TREE_ADDRESSABLE of NODE to true.
997 Helper for call_for_symbol_thunks_and_aliases. */
1000 set_addressable (varpool_node
*node
, void *)
1002 TREE_ADDRESSABLE (node
->decl
) = 1;
1006 /* Clear DECL_RTL of NODE.
1007 Helper for call_for_symbol_thunks_and_aliases. */
1010 clear_decl_rtl (symtab_node
*node
, void *)
1012 SET_DECL_RTL (node
->decl
, NULL
);
1016 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1017 possible. Return number of redirections made. */
1020 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1022 int nredirected
= 0;
1024 cgraph_edge
*e
= n
->callers
;
1028 /* Redirecting thunks to interposable symbols or symbols in other sections
1029 may not be supported by target output code. Play safe for now and
1030 punt on redirection. */
1031 if (!e
->caller
->thunk
.thunk_p
)
1033 struct cgraph_edge
*nexte
= e
->next_caller
;
1034 e
->redirect_callee (to
);
1041 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1043 bool removed
= false;
1044 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1046 if ((DECL_COMDAT_GROUP (n
->decl
)
1047 && (DECL_COMDAT_GROUP (n
->decl
)
1048 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1049 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1050 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1052 nredirected
+= redirect_all_callers (n_alias
, to
);
1053 if (n_alias
->can_remove_if_no_direct_calls_p ()
1054 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1056 && !n_alias
->has_aliases_p ())
1065 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1069 sem_function::merge (sem_item
*alias_item
)
1071 gcc_assert (alias_item
->type
== FUNC
);
1073 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1075 cgraph_node
*original
= get_node ();
1076 cgraph_node
*local_original
= NULL
;
1077 cgraph_node
*alias
= alias_func
->get_node ();
1079 bool create_wrapper
= false;
1080 bool create_alias
= false;
1081 bool redirect_callers
= false;
1082 bool remove
= false;
1084 bool original_discardable
= false;
1085 bool original_discarded
= false;
1087 bool original_address_matters
= original
->address_matters_p ();
1088 bool alias_address_matters
= alias
->address_matters_p ();
1090 if (DECL_EXTERNAL (alias
->decl
))
1093 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1097 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1098 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1103 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1107 /* Do not attempt to mix functions from different user sections;
1108 we do not know what user intends with those. */
1109 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1110 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1111 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1116 "original and alias are in different sections.\n\n");
1120 /* See if original is in a section that can be discarded if the main
1121 symbol is not used. */
1123 if (original
->can_be_discarded_p ())
1124 original_discardable
= true;
1125 /* Also consider case where we have resolution info and we know that
1126 original's definition is not going to be used. In this case we can not
1127 create alias to original. */
1128 if (node
->resolution
!= LDPR_UNKNOWN
1129 && !decl_binds_to_current_def_p (node
->decl
))
1130 original_discardable
= original_discarded
= true;
1132 /* Creating a symtab alias is the optimal way to merge.
1133 It however can not be used in the following cases:
1135 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1136 2) if ORIGINAL is in a section that may be discarded by linker or if
1137 it is an external functions where we can not create an alias
1138 (ORIGINAL_DISCARDABLE)
1139 3) if target do not support symbol aliases.
1140 4) original and alias lie in different comdat groups.
1142 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1143 and/or redirect all callers from ALIAS to ORIGINAL. */
1144 if ((original_address_matters
&& alias_address_matters
)
1145 || (original_discardable
1146 && (!DECL_COMDAT_GROUP (alias
->decl
)
1147 || (DECL_COMDAT_GROUP (alias
->decl
)
1148 != DECL_COMDAT_GROUP (original
->decl
))))
1149 || original_discarded
1150 || !sem_item::target_supports_symbol_aliases_p ()
1151 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1153 /* First see if we can produce wrapper. */
1155 /* Symbol properties that matter for references must be preserved.
1156 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1157 with proper properties. */
1158 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1159 alias
->address_taken
))
1163 "Wrapper cannot be created because referenced symbol "
1164 "properties mismatch\n");
1166 /* Do not turn function in one comdat group into wrapper to another
1167 comdat group. Other compiler producing the body of the
1168 another comdat group may make opossite decision and with unfortunate
1169 linker choices this may close a loop. */
1170 else if (DECL_COMDAT_GROUP (original
->decl
)
1171 && DECL_COMDAT_GROUP (alias
->decl
)
1172 && (DECL_COMDAT_GROUP (alias
->decl
)
1173 != DECL_COMDAT_GROUP (original
->decl
)))
1177 "Wrapper cannot be created because of COMDAT\n");
1179 else if (DECL_STATIC_CHAIN (alias
->decl
)
1180 || DECL_STATIC_CHAIN (original
->decl
))
1184 "Cannot create wrapper of nested function.\n");
1186 /* TODO: We can also deal with variadic functions never calling
1188 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1192 "can not create wrapper of stdarg function.\n");
1194 else if (inline_summaries
1195 && inline_summaries
->get (alias
)->self_size
<= 2)
1198 fprintf (dump_file
, "Wrapper creation is not "
1199 "profitable (function is too small).\n");
1201 /* If user paid attention to mark function noinline, assume it is
1202 somewhat special and do not try to turn it into a wrapper that can
1203 not be undone by inliner. */
1204 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1207 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1210 create_wrapper
= true;
1212 /* We can redirect local calls in the case both alias and orignal
1213 are not interposable. */
1215 = alias
->get_availability () > AVAIL_INTERPOSABLE
1216 && original
->get_availability () > AVAIL_INTERPOSABLE
1217 && !alias
->instrumented_version
;
1218 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1219 with proper properties. */
1220 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1221 alias
->address_taken
))
1222 redirect_callers
= false;
1224 if (!redirect_callers
&& !create_wrapper
)
1227 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1228 "produce wrapper\n\n");
1232 /* Work out the symbol the wrapper should call.
1233 If ORIGINAL is interposable, we need to call a local alias.
1234 Also produce local alias (if possible) as an optimization.
1236 Local aliases can not be created inside comdat groups because that
1237 prevents inlining. */
1238 if (!original_discardable
&& !original
->get_comdat_group ())
1241 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1243 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1244 local_original
= original
;
1246 /* If we can not use local alias, fallback to the original
1248 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1249 local_original
= original
;
1251 /* If original is COMDAT local, we can not really redirect calls outside
1252 of its comdat group to it. */
1253 if (original
->comdat_local_p ())
1254 redirect_callers
= false;
1255 if (!local_original
)
1258 fprintf (dump_file
, "Not unifying; "
1259 "can not produce local alias.\n\n");
1263 if (!redirect_callers
&& !create_wrapper
)
1266 fprintf (dump_file
, "Not unifying; "
1267 "can not redirect callers nor produce a wrapper\n\n");
1271 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1273 && !alias
->can_remove_if_no_direct_calls_p ())
1276 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1277 "function has other uses than direct calls\n\n");
1282 create_alias
= true;
1284 if (redirect_callers
)
1286 int nredirected
= redirect_all_callers (alias
, local_original
);
1290 alias
->icf_merged
= true;
1291 local_original
->icf_merged
= true;
1293 if (dump_file
&& nredirected
)
1294 fprintf (dump_file
, "%i local calls have been "
1295 "redirected.\n", nredirected
);
1298 /* If all callers was redirected, do not produce wrapper. */
1299 if (alias
->can_remove_if_no_direct_calls_p ()
1300 && !DECL_VIRTUAL_P (alias
->decl
)
1301 && !alias
->has_aliases_p ())
1303 create_wrapper
= false;
1306 gcc_assert (!create_alias
);
1308 else if (create_alias
)
1310 alias
->icf_merged
= true;
1312 /* Remove the function's body. */
1313 ipa_merge_profiles (original
, alias
);
1314 alias
->release_body (true);
1316 /* Notice global symbol possibly produced RTL. */
1317 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1320 /* Create the alias. */
1321 cgraph_node::create_alias (alias_func
->decl
, decl
);
1322 alias
->resolve_alias (original
);
1324 original
->call_for_symbol_thunks_and_aliases
1325 (set_local
, (void *)(size_t) original
->local_p (), true);
1328 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1332 gcc_assert (!create_alias
);
1333 alias
->icf_merged
= true;
1334 local_original
->icf_merged
= true;
1336 ipa_merge_profiles (local_original
, alias
, true);
1337 alias
->create_wrapper (local_original
);
1340 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1343 /* It's possible that redirection can hit thunks that block
1344 redirection opportunities. */
1345 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1346 original
->icf_merged
= true;
1348 /* We use merged flag to track cases where COMDAT function is known to be
1349 compatible its callers. If we merged in non-COMDAT, we need to give up
1350 on this optimization. */
1351 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1354 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1356 local_original
->merged_comdat
= false;
1357 original
->merged_comdat
= false;
1362 ipa_merge_profiles (original
, alias
);
1363 alias
->release_body ();
1365 alias
->body_removed
= true;
1366 alias
->icf_merged
= true;
1368 fprintf (dump_file
, "Unified; Function body was removed.\n");
1374 /* Semantic item initialization function. */
1377 sem_function::init (void)
1380 get_node ()->get_untransformed_body ();
1382 tree fndecl
= node
->decl
;
1383 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1386 gcc_assert (SSANAMES (func
));
1388 ssa_names_size
= SSANAMES (func
)->length ();
1392 region_tree
= func
->eh
->region_tree
;
1394 /* iterating all function arguments. */
1395 arg_count
= count_formal_params (fndecl
);
1397 edge_count
= n_edges_for_fn (func
);
1398 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1399 if (!cnode
->thunk
.thunk_p
)
1401 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1403 inchash::hash hstate
;
1406 FOR_EACH_BB_FN (bb
, func
)
1408 unsigned nondbg_stmt_count
= 0;
1411 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1413 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1416 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1419 gimple
*stmt
= gsi_stmt (gsi
);
1421 if (gimple_code (stmt
) != GIMPLE_DEBUG
1422 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1424 hash_stmt (stmt
, hstate
);
1425 nondbg_stmt_count
++;
1429 gcode_hash
= hstate
.end ();
1430 bb_sizes
.safe_push (nondbg_stmt_count
);
1432 /* Inserting basic block to hash table. */
1433 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1434 EDGE_COUNT (bb
->preds
)
1435 + EDGE_COUNT (bb
->succs
));
1437 bb_sorted
.safe_push (semantic_bb
);
1443 inchash::hash hstate
;
1444 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1445 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1446 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1447 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1448 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1449 gcode_hash
= hstate
.end ();
1453 /* Accumulate to HSTATE a hash of expression EXP.
1454 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1455 and DECL equality classes. */
1458 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1460 if (exp
== NULL_TREE
)
1462 hstate
.merge_hash (0);
1466 /* Handled component can be matched in a cureful way proving equivalence
1467 even if they syntactically differ. Just skip them. */
1469 while (handled_component_p (exp
))
1470 exp
= TREE_OPERAND (exp
, 0);
1472 enum tree_code code
= TREE_CODE (exp
);
1473 hstate
.add_int (code
);
1477 /* Use inchash::add_expr for everything that is LTO stable. */
1485 inchash::add_expr (exp
, hstate
);
1489 unsigned HOST_WIDE_INT idx
;
1492 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1494 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1496 add_expr (value
, hstate
);
1501 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1507 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1510 case POINTER_PLUS_EXPR
:
1513 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1514 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1518 inchash::hash one
, two
;
1519 add_expr (TREE_OPERAND (exp
, 0), one
);
1520 add_expr (TREE_OPERAND (exp
, 1), two
);
1521 hstate
.add_commutative (one
, two
);
1525 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1526 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1532 /* Accumulate to HSTATE a hash of type t.
1533 TYpes that may end up being compatible after LTO type merging needs to have
1537 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1539 if (type
== NULL_TREE
)
1541 hstate
.merge_hash (0);
1545 type
= TYPE_MAIN_VARIANT (type
);
1547 hstate
.add_int (TYPE_MODE (type
));
1549 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1551 hstate
.add_int (COMPLEX_TYPE
);
1552 sem_item::add_type (TREE_TYPE (type
), hstate
);
1554 else if (INTEGRAL_TYPE_P (type
))
1556 hstate
.add_int (INTEGER_TYPE
);
1557 hstate
.add_flag (TYPE_UNSIGNED (type
));
1558 hstate
.add_int (TYPE_PRECISION (type
));
1560 else if (VECTOR_TYPE_P (type
))
1562 hstate
.add_int (VECTOR_TYPE
);
1563 hstate
.add_int (TYPE_PRECISION (type
));
1564 sem_item::add_type (TREE_TYPE (type
), hstate
);
1566 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1568 hstate
.add_int (ARRAY_TYPE
);
1569 /* Do not hash size, so complete and incomplete types can match. */
1570 sem_item::add_type (TREE_TYPE (type
), hstate
);
1572 else if (RECORD_OR_UNION_TYPE_P (type
))
1574 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1575 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1579 inchash::hash hstate2
;
1584 hstate2
.add_int (RECORD_TYPE
);
1585 gcc_assert (COMPLETE_TYPE_P (type
));
1587 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1588 if (TREE_CODE (f
) == FIELD_DECL
)
1590 add_type (TREE_TYPE (f
), hstate2
);
1594 hstate2
.add_int (nf
);
1595 hash
= hstate2
.end ();
1596 hstate
.add_wide_int (hash
);
1597 optimizer
->m_type_hash_cache
.put (type
, hash
);
1600 hstate
.add_wide_int (*val
);
1604 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1607 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1609 enum gimple_code code
= gimple_code (stmt
);
1611 hstate
.add_int (code
);
1616 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1619 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1620 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1621 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1623 inchash::hash one
, two
;
1625 add_expr (gimple_assign_rhs1 (stmt
), one
);
1626 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1627 add_expr (gimple_assign_rhs2 (stmt
), two
);
1628 hstate
.add_commutative (one
, two
);
1629 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1631 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1632 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1634 add_expr (gimple_assign_lhs (stmt
), hstate
);
1635 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1644 /* All these statements are equivalent if their operands are. */
1645 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1647 add_expr (gimple_op (stmt
, i
), hstate
);
1648 if (gimple_op (stmt
, i
))
1649 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1657 /* Return true if polymorphic comparison must be processed. */
1660 sem_function::compare_polymorphic_p (void)
1662 struct cgraph_edge
*e
;
1664 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1666 if (get_node ()->indirect_calls
!= NULL
)
1668 /* TODO: We can do simple propagation determining what calls may lead to
1669 a polymorphic call. */
1670 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1671 if (e
->callee
->definition
1672 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1677 /* For a given call graph NODE, the function constructs new
1678 semantic function item. */
1681 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1683 tree fndecl
= node
->decl
;
1684 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1686 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1689 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1692 if (lookup_attribute_by_prefix ("oacc ",
1693 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1697 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1698 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1701 sem_function
*f
= new sem_function (node
, stack
);
1708 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1709 return true if phi nodes are semantically equivalent in these blocks . */
1712 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1714 gphi_iterator si1
, si2
;
1716 unsigned size1
, size2
, i
;
1720 gcc_assert (bb1
!= NULL
);
1721 gcc_assert (bb2
!= NULL
);
1723 si2
= gsi_start_phis (bb2
);
1724 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1727 gsi_next_nonvirtual_phi (&si1
);
1728 gsi_next_nonvirtual_phi (&si2
);
1730 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1733 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1734 return return_false();
1739 tree phi_result1
= gimple_phi_result (phi1
);
1740 tree phi_result2
= gimple_phi_result (phi2
);
1742 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1743 return return_false_with_msg ("PHI results are different");
1745 size1
= gimple_phi_num_args (phi1
);
1746 size2
= gimple_phi_num_args (phi2
);
1749 return return_false ();
1751 for (i
= 0; i
< size1
; ++i
)
1753 t1
= gimple_phi_arg (phi1
, i
)->def
;
1754 t2
= gimple_phi_arg (phi2
, i
)->def
;
1756 if (!m_checker
->compare_operand (t1
, t2
))
1757 return return_false ();
1759 e1
= gimple_phi_arg_edge (phi1
, i
);
1760 e2
= gimple_phi_arg_edge (phi2
, i
);
1762 if (!m_checker
->compare_edge (e1
, e2
))
1763 return return_false ();
1772 /* Returns true if tree T can be compared as a handled component. */
1775 sem_function::icf_handled_component_p (tree t
)
1777 tree_code tc
= TREE_CODE (t
);
1779 return (handled_component_p (t
)
1780 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1783 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1784 corresponds to TARGET. */
1787 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1792 if (bb_dict
->length () <= (unsigned)source
)
1793 bb_dict
->safe_grow_cleared (source
+ 1);
1795 if ((*bb_dict
)[source
] == 0)
1797 (*bb_dict
)[source
] = target
;
1801 return (*bb_dict
)[source
] == target
;
1804 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1808 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1809 : sem_item (VAR
, node
, stack
)
1811 gcc_checking_assert (node
);
1812 gcc_checking_assert (get_node ());
1815 /* Fast equality function based on knowledge known in WPA. */
1818 sem_variable::equals_wpa (sem_item
*item
,
1819 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1821 gcc_assert (item
->type
== VAR
);
1823 if (node
->num_references () != item
->node
->num_references ())
1824 return return_false_with_msg ("different number of references");
1826 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1827 return return_false_with_msg ("TLS model");
1829 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1830 alignment out of all aliases. */
1832 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1833 return return_false_with_msg ("Virtual flag mismatch");
1835 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1836 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1837 || !operand_equal_p (DECL_SIZE (decl
),
1838 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1839 return return_false_with_msg ("size mismatch");
1841 /* Do not attempt to mix data from different user sections;
1842 we do not know what user intends with those. */
1843 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1844 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1845 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1846 return return_false_with_msg ("user section mismatch");
1848 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1849 return return_false_with_msg ("text section");
1851 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1852 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1854 item
->node
->iterate_reference (i
, ref2
);
1856 if (ref
->use
!= ref2
->use
)
1857 return return_false_with_msg ("reference use mismatch");
1859 if (!compare_symbol_references (ignored_nodes
,
1860 ref
->referred
, ref2
->referred
,
1861 ref
->address_matters_p ()))
1868 /* Returns true if the item equals to ITEM given as argument. */
1871 sem_variable::equals (sem_item
*item
,
1872 hash_map
<symtab_node
*, sem_item
*> &)
1874 gcc_assert (item
->type
== VAR
);
1877 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1878 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1879 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1880 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1882 /* As seen in PR ipa/65303 we have to compare variables types. */
1883 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1884 TREE_TYPE (item
->decl
)))
1885 return return_false_with_msg ("variables types are different");
1887 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1888 DECL_INITIAL (item
->node
->decl
));
1889 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1891 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1892 xstrdup_for_dump (node
->name()),
1893 xstrdup_for_dump (item
->node
->name ()),
1894 node
->order
, item
->node
->order
,
1895 xstrdup_for_dump (node
->asm_name ()),
1896 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1901 /* Compares trees T1 and T2 for semantic equality. */
1904 sem_variable::equals (tree t1
, tree t2
)
1907 return return_with_debug (t1
== t2
);
1910 tree_code tc1
= TREE_CODE (t1
);
1911 tree_code tc2
= TREE_CODE (t2
);
1914 return return_false_with_msg ("TREE_CODE mismatch");
1920 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1921 unsigned HOST_WIDE_INT idx
;
1923 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1924 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1925 return return_false_with_msg ("constructor type mismatch");
1927 if (typecode
== ARRAY_TYPE
)
1929 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1930 /* For arrays, check that the sizes all match. */
1931 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1933 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1934 return return_false_with_msg ("constructor array size mismatch");
1936 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1938 return return_false_with_msg ("constructor type incompatible");
1940 v1
= CONSTRUCTOR_ELTS (t1
);
1941 v2
= CONSTRUCTOR_ELTS (t2
);
1942 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1943 return return_false_with_msg ("constructor number of elts mismatch");
1945 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1947 constructor_elt
*c1
= &(*v1
)[idx
];
1948 constructor_elt
*c2
= &(*v2
)[idx
];
1950 /* Check that each value is the same... */
1951 if (!sem_variable::equals (c1
->value
, c2
->value
))
1953 /* ... and that they apply to the same fields! */
1954 if (!sem_variable::equals (c1
->index
, c2
->index
))
1961 tree x1
= TREE_OPERAND (t1
, 0);
1962 tree x2
= TREE_OPERAND (t2
, 0);
1963 tree y1
= TREE_OPERAND (t1
, 1);
1964 tree y2
= TREE_OPERAND (t2
, 1);
1966 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1967 return return_false ();
1969 /* Type of the offset on MEM_REF does not matter. */
1970 return return_with_debug (sem_variable::equals (x1
, x2
)
1971 && wi::to_offset (y1
)
1972 == wi::to_offset (y2
));
1977 tree op1
= TREE_OPERAND (t1
, 0);
1978 tree op2
= TREE_OPERAND (t2
, 0);
1979 return sem_variable::equals (op1
, op2
);
1981 /* References to other vars/decls are compared using ipa-ref. */
1984 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1986 return return_false_with_msg ("Declaration mismatch");
1988 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1989 need to process its VAR/FUNCTION references without relying on ipa-ref
1993 return return_false_with_msg ("Declaration mismatch");
1995 /* Integer constants are the same only if the same width of type. */
1996 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1997 return return_false_with_msg ("INTEGER_CST precision mismatch");
1998 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1999 return return_false_with_msg ("INTEGER_CST mode mismatch");
2000 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2002 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2003 return return_false_with_msg ("STRING_CST mode mismatch");
2004 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2005 return return_false_with_msg ("STRING_CST length mismatch");
2006 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2007 TREE_STRING_LENGTH (t1
)))
2008 return return_false_with_msg ("STRING_CST mismatch");
2011 /* Fixed constants are the same only if the same width of type. */
2012 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2013 return return_false_with_msg ("FIXED_CST precision mismatch");
2015 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2016 TREE_FIXED_CST (t2
)));
2018 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2019 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2021 /* Real constants are the same only if the same width of type. */
2022 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2023 return return_false_with_msg ("REAL_CST precision mismatch");
2024 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2025 &TREE_REAL_CST (t2
)));
2030 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2031 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2033 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2034 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2035 VECTOR_CST_ELT (t2
, i
)))
2041 case ARRAY_RANGE_REF
:
2043 tree x1
= TREE_OPERAND (t1
, 0);
2044 tree x2
= TREE_OPERAND (t2
, 0);
2045 tree y1
= TREE_OPERAND (t1
, 1);
2046 tree y2
= TREE_OPERAND (t2
, 1);
2048 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2050 if (!sem_variable::equals (array_ref_low_bound (t1
),
2051 array_ref_low_bound (t2
)))
2053 if (!sem_variable::equals (array_ref_element_size (t1
),
2054 array_ref_element_size (t2
)))
2060 case POINTER_PLUS_EXPR
:
2065 tree x1
= TREE_OPERAND (t1
, 0);
2066 tree x2
= TREE_OPERAND (t2
, 0);
2067 tree y1
= TREE_OPERAND (t1
, 1);
2068 tree y2
= TREE_OPERAND (t2
, 1);
2070 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2074 case VIEW_CONVERT_EXPR
:
2075 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2076 return return_false ();
2077 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2079 return return_false_with_msg ("ERROR_MARK");
2081 return return_false_with_msg ("Unknown TREE code reached");
2085 /* Parser function that visits a varpool NODE. */
2088 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2090 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2094 sem_variable
*v
= new sem_variable (node
, stack
);
2101 /* References independent hash function. */
2104 sem_variable::get_hash (void)
2109 /* All WPA streamed in symbols should have their hashes computed at compile
2110 time. At this point, the constructor may not be in memory at all.
2111 DECL_INITIAL (decl) would be error_mark_node in that case. */
2112 gcc_assert (!node
->lto_file_data
);
2113 tree ctor
= DECL_INITIAL (decl
);
2114 inchash::hash hstate
;
2116 hstate
.add_int (456346417);
2117 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2118 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2119 add_expr (ctor
, hstate
);
2120 set_hash (hstate
.end ());
2125 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2128 set_alias_uids (symtab_node
*n
, int uid
)
2131 FOR_EACH_ALIAS (n
, ref
)
2134 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2135 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2137 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2138 set_alias_uids (ref
->referring
, uid
);
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");
2268 set_alias_uids (original
, DECL_UID (original
->decl
));
2273 /* Dump symbol to FILE. */
2276 sem_variable::dump_to_file (FILE *file
)
2280 print_node (file
, "", decl
, 0);
2281 fprintf (file
, "\n\n");
2284 unsigned int sem_item_optimizer::class_id
= 0;
2286 sem_item_optimizer::sem_item_optimizer ()
2287 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2288 m_varpool_node_hooks (NULL
)
2291 bitmap_obstack_initialize (&m_bmstack
);
2294 sem_item_optimizer::~sem_item_optimizer ()
2296 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2300 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2301 it
!= m_classes
.end (); ++it
)
2303 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2304 delete (*it
)->classes
[i
];
2306 (*it
)->classes
.release ();
2312 bitmap_obstack_release (&m_bmstack
);
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, uid:%u)\n",
2403 node
->asm_name (), (void *) node
->decl
, node
->order
);
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_node::dump_table (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
))
3564 merged_p
|= source
->merge (alias
);
3571 /* Dump function prints all class members to a FILE with an INDENT. */
3574 congruence_class::dump (FILE *file
, unsigned int indent
) const
3576 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3577 id
, members
[0]->get_hash (), members
.length ());
3579 FPUTS_SPACES (file
, indent
+ 2, "");
3580 for (unsigned i
= 0; i
< members
.length (); i
++)
3581 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3582 (void *) members
[i
]->decl
,
3583 members
[i
]->node
->order
);
3585 fprintf (file
, "\n");
3588 /* Returns true if there's a member that is used from another group. */
3591 congruence_class::is_class_used (void)
3593 for (unsigned int i
= 0; i
< members
.length (); i
++)
3594 if (members
[i
]->usages
.length ())
3600 /* Generate pass summary for IPA ICF pass. */
3603 ipa_icf_generate_summary (void)
3606 optimizer
= new sem_item_optimizer ();
3608 optimizer
->register_hooks ();
3609 optimizer
->parse_funcs_and_vars ();
3612 /* Write pass summary for IPA ICF pass. */
3615 ipa_icf_write_summary (void)
3617 gcc_assert (optimizer
);
3619 optimizer
->write_summary ();
3622 /* Read pass summary for IPA ICF pass. */
3625 ipa_icf_read_summary (void)
3628 optimizer
= new sem_item_optimizer ();
3630 optimizer
->read_summary ();
3631 optimizer
->register_hooks ();
3634 /* Semantic equality exection function. */
3637 ipa_icf_driver (void)
3639 gcc_assert (optimizer
);
3641 bool merged_p
= optimizer
->execute ();
3646 return merged_p
? TODO_remove_functions
: 0;
3649 const pass_data pass_data_ipa_icf
=
3651 IPA_PASS
, /* type */
3653 OPTGROUP_IPA
, /* optinfo_flags */
3654 TV_IPA_ICF
, /* tv_id */
3655 0, /* properties_required */
3656 0, /* properties_provided */
3657 0, /* properties_destroyed */
3658 0, /* todo_flags_start */
3659 0, /* todo_flags_finish */
3662 class pass_ipa_icf
: public ipa_opt_pass_d
3665 pass_ipa_icf (gcc::context
*ctxt
)
3666 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3667 ipa_icf_generate_summary
, /* generate_summary */
3668 ipa_icf_write_summary
, /* write_summary */
3669 ipa_icf_read_summary
, /* read_summary */
3671 write_optimization_summary */
3673 read_optimization_summary */
3674 NULL
, /* stmt_fixup */
3675 0, /* function_transform_todo_flags_start */
3676 NULL
, /* function_transform */
3677 NULL
) /* variable_transform */
3680 /* opt_pass methods: */
3681 virtual bool gate (function
*)
3683 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3686 virtual unsigned int execute (function
*)
3688 return ipa_icf_driver();
3690 }; // class pass_ipa_icf
3692 } // ipa_icf namespace
3695 make_pass_ipa_icf (gcc::context
*ctxt
)
3697 return new ipa_icf::pass_ipa_icf (ctxt
);