1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2016 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
)
1693 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1694 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1697 sem_function
*f
= new sem_function (node
, stack
);
1704 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1705 return true if phi nodes are semantically equivalent in these blocks . */
1708 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1710 gphi_iterator si1
, si2
;
1712 unsigned size1
, size2
, i
;
1716 gcc_assert (bb1
!= NULL
);
1717 gcc_assert (bb2
!= NULL
);
1719 si2
= gsi_start_phis (bb2
);
1720 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1723 gsi_next_nonvirtual_phi (&si1
);
1724 gsi_next_nonvirtual_phi (&si2
);
1726 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1729 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1730 return return_false();
1735 tree phi_result1
= gimple_phi_result (phi1
);
1736 tree phi_result2
= gimple_phi_result (phi2
);
1738 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1739 return return_false_with_msg ("PHI results are different");
1741 size1
= gimple_phi_num_args (phi1
);
1742 size2
= gimple_phi_num_args (phi2
);
1745 return return_false ();
1747 for (i
= 0; i
< size1
; ++i
)
1749 t1
= gimple_phi_arg (phi1
, i
)->def
;
1750 t2
= gimple_phi_arg (phi2
, i
)->def
;
1752 if (!m_checker
->compare_operand (t1
, t2
))
1753 return return_false ();
1755 e1
= gimple_phi_arg_edge (phi1
, i
);
1756 e2
= gimple_phi_arg_edge (phi2
, i
);
1758 if (!m_checker
->compare_edge (e1
, e2
))
1759 return return_false ();
1768 /* Returns true if tree T can be compared as a handled component. */
1771 sem_function::icf_handled_component_p (tree t
)
1773 tree_code tc
= TREE_CODE (t
);
1775 return (handled_component_p (t
)
1776 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1779 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1780 corresponds to TARGET. */
1783 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1788 if (bb_dict
->length () <= (unsigned)source
)
1789 bb_dict
->safe_grow_cleared (source
+ 1);
1791 if ((*bb_dict
)[source
] == 0)
1793 (*bb_dict
)[source
] = target
;
1797 return (*bb_dict
)[source
] == target
;
1800 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1804 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1805 : sem_item (VAR
, node
, stack
)
1807 gcc_checking_assert (node
);
1808 gcc_checking_assert (get_node ());
1811 /* Fast equality function based on knowledge known in WPA. */
1814 sem_variable::equals_wpa (sem_item
*item
,
1815 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1817 gcc_assert (item
->type
== VAR
);
1819 if (node
->num_references () != item
->node
->num_references ())
1820 return return_false_with_msg ("different number of references");
1822 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1823 return return_false_with_msg ("TLS model");
1825 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1826 alignment out of all aliases. */
1828 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1829 return return_false_with_msg ("Virtual flag mismatch");
1831 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1832 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1833 || !operand_equal_p (DECL_SIZE (decl
),
1834 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1835 return return_false_with_msg ("size mismatch");
1837 /* Do not attempt to mix data from different user sections;
1838 we do not know what user intends with those. */
1839 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1840 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1841 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1842 return return_false_with_msg ("user section mismatch");
1844 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1845 return return_false_with_msg ("text section");
1847 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1848 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1850 item
->node
->iterate_reference (i
, ref2
);
1852 if (ref
->use
!= ref2
->use
)
1853 return return_false_with_msg ("reference use mismatch");
1855 if (!compare_symbol_references (ignored_nodes
,
1856 ref
->referred
, ref2
->referred
,
1857 ref
->address_matters_p ()))
1864 /* Returns true if the item equals to ITEM given as argument. */
1867 sem_variable::equals (sem_item
*item
,
1868 hash_map
<symtab_node
*, sem_item
*> &)
1870 gcc_assert (item
->type
== VAR
);
1873 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1874 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1875 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1876 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1878 /* As seen in PR ipa/65303 we have to compare variables types. */
1879 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1880 TREE_TYPE (item
->decl
)))
1881 return return_false_with_msg ("variables types are different");
1883 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1884 DECL_INITIAL (item
->node
->decl
));
1885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1887 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1888 xstrdup_for_dump (node
->name()),
1889 xstrdup_for_dump (item
->node
->name ()),
1890 node
->order
, item
->node
->order
,
1891 xstrdup_for_dump (node
->asm_name ()),
1892 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1897 /* Compares trees T1 and T2 for semantic equality. */
1900 sem_variable::equals (tree t1
, tree t2
)
1903 return return_with_debug (t1
== t2
);
1906 tree_code tc1
= TREE_CODE (t1
);
1907 tree_code tc2
= TREE_CODE (t2
);
1910 return return_false_with_msg ("TREE_CODE mismatch");
1916 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1917 unsigned HOST_WIDE_INT idx
;
1919 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1920 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1921 return return_false_with_msg ("constructor type mismatch");
1923 if (typecode
== ARRAY_TYPE
)
1925 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1926 /* For arrays, check that the sizes all match. */
1927 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1929 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1930 return return_false_with_msg ("constructor array size mismatch");
1932 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1934 return return_false_with_msg ("constructor type incompatible");
1936 v1
= CONSTRUCTOR_ELTS (t1
);
1937 v2
= CONSTRUCTOR_ELTS (t2
);
1938 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1939 return return_false_with_msg ("constructor number of elts mismatch");
1941 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1943 constructor_elt
*c1
= &(*v1
)[idx
];
1944 constructor_elt
*c2
= &(*v2
)[idx
];
1946 /* Check that each value is the same... */
1947 if (!sem_variable::equals (c1
->value
, c2
->value
))
1949 /* ... and that they apply to the same fields! */
1950 if (!sem_variable::equals (c1
->index
, c2
->index
))
1957 tree x1
= TREE_OPERAND (t1
, 0);
1958 tree x2
= TREE_OPERAND (t2
, 0);
1959 tree y1
= TREE_OPERAND (t1
, 1);
1960 tree y2
= TREE_OPERAND (t2
, 1);
1962 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1963 return return_false ();
1965 /* Type of the offset on MEM_REF does not matter. */
1966 return return_with_debug (sem_variable::equals (x1
, x2
)
1967 && wi::to_offset (y1
)
1968 == wi::to_offset (y2
));
1973 tree op1
= TREE_OPERAND (t1
, 0);
1974 tree op2
= TREE_OPERAND (t2
, 0);
1975 return sem_variable::equals (op1
, op2
);
1977 /* References to other vars/decls are compared using ipa-ref. */
1980 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1982 return return_false_with_msg ("Declaration mismatch");
1984 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1985 need to process its VAR/FUNCTION references without relying on ipa-ref
1989 return return_false_with_msg ("Declaration mismatch");
1991 /* Integer constants are the same only if the same width of type. */
1992 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1993 return return_false_with_msg ("INTEGER_CST precision mismatch");
1994 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1995 return return_false_with_msg ("INTEGER_CST mode mismatch");
1996 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1998 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1999 return return_false_with_msg ("STRING_CST mode mismatch");
2000 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2001 return return_false_with_msg ("STRING_CST length mismatch");
2002 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2003 TREE_STRING_LENGTH (t1
)))
2004 return return_false_with_msg ("STRING_CST mismatch");
2007 /* Fixed constants are the same only if the same width of type. */
2008 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2009 return return_false_with_msg ("FIXED_CST precision mismatch");
2011 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2012 TREE_FIXED_CST (t2
)));
2014 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2015 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2017 /* Real constants are the same only if the same width of type. */
2018 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2019 return return_false_with_msg ("REAL_CST precision mismatch");
2020 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2021 &TREE_REAL_CST (t2
)));
2026 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2027 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2029 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2030 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2031 VECTOR_CST_ELT (t2
, i
)))
2037 case ARRAY_RANGE_REF
:
2039 tree x1
= TREE_OPERAND (t1
, 0);
2040 tree x2
= TREE_OPERAND (t2
, 0);
2041 tree y1
= TREE_OPERAND (t1
, 1);
2042 tree y2
= TREE_OPERAND (t2
, 1);
2044 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2046 if (!sem_variable::equals (array_ref_low_bound (t1
),
2047 array_ref_low_bound (t2
)))
2049 if (!sem_variable::equals (array_ref_element_size (t1
),
2050 array_ref_element_size (t2
)))
2056 case POINTER_PLUS_EXPR
:
2061 tree x1
= TREE_OPERAND (t1
, 0);
2062 tree x2
= TREE_OPERAND (t2
, 0);
2063 tree y1
= TREE_OPERAND (t1
, 1);
2064 tree y2
= TREE_OPERAND (t2
, 1);
2066 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2070 case VIEW_CONVERT_EXPR
:
2071 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2072 return return_false ();
2073 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2075 return return_false_with_msg ("ERROR_MARK");
2077 return return_false_with_msg ("Unknown TREE code reached");
2081 /* Parser function that visits a varpool NODE. */
2084 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2086 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2090 sem_variable
*v
= new sem_variable (node
, stack
);
2097 /* References independent hash function. */
2100 sem_variable::get_hash (void)
2105 /* All WPA streamed in symbols should have their hashes computed at compile
2106 time. At this point, the constructor may not be in memory at all.
2107 DECL_INITIAL (decl) would be error_mark_node in that case. */
2108 gcc_assert (!node
->lto_file_data
);
2109 tree ctor
= DECL_INITIAL (decl
);
2110 inchash::hash hstate
;
2112 hstate
.add_int (456346417);
2113 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2114 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2115 add_expr (ctor
, hstate
);
2116 set_hash (hstate
.end ());
2121 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2124 set_alias_uids (symtab_node
*n
, int uid
)
2127 FOR_EACH_ALIAS (n
, ref
)
2130 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2131 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2133 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2134 set_alias_uids (ref
->referring
, uid
);
2138 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2142 sem_variable::merge (sem_item
*alias_item
)
2144 gcc_assert (alias_item
->type
== VAR
);
2146 if (!sem_item::target_supports_symbol_aliases_p ())
2149 fprintf (dump_file
, "Not unifying; "
2150 "Symbol aliases are not supported by target\n\n");
2154 if (DECL_EXTERNAL (alias_item
->decl
))
2157 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2161 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2163 varpool_node
*original
= get_node ();
2164 varpool_node
*alias
= alias_var
->get_node ();
2165 bool original_discardable
= false;
2167 bool alias_address_matters
= alias
->address_matters_p ();
2169 /* See if original is in a section that can be discarded if the main
2171 Also consider case where we have resolution info and we know that
2172 original's definition is not going to be used. In this case we can not
2173 create alias to original. */
2174 if (original
->can_be_discarded_p ()
2175 || (node
->resolution
!= LDPR_UNKNOWN
2176 && !decl_binds_to_current_def_p (node
->decl
)))
2177 original_discardable
= true;
2179 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2181 /* Constant pool machinery is not quite ready for aliases.
2182 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2183 For LTO merging does not happen that is an important missing feature.
2184 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2185 flag is dropped and non-local symbol name is assigned. */
2186 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2187 || DECL_IN_CONSTANT_POOL (original
->decl
))
2191 "Not unifying; constant pool variables.\n\n");
2195 /* Do not attempt to mix functions from different user sections;
2196 we do not know what user intends with those. */
2197 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2198 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2199 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2204 "original and alias are in different sections.\n\n");
2208 /* We can not merge if address comparsion metters. */
2209 if (alias_address_matters
&& flag_merge_constants
< 2)
2213 "Not unifying; address of original may be compared.\n\n");
2217 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2220 fprintf (dump_file
, "Not unifying; "
2221 "original and alias have incompatible alignments\n\n");
2226 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2229 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2230 "across comdat group boundary\n\n");
2235 if (original_discardable
)
2238 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2239 "target is discardable\n\n");
2245 gcc_assert (!original
->alias
);
2246 gcc_assert (!alias
->alias
);
2248 alias
->analyzed
= false;
2250 DECL_INITIAL (alias
->decl
) = NULL
;
2251 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2253 alias
->need_bounds_init
= false;
2254 alias
->remove_all_references ();
2255 if (TREE_ADDRESSABLE (alias
->decl
))
2256 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2258 varpool_node::create_alias (alias_var
->decl
, decl
);
2259 alias
->resolve_alias (original
);
2262 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2264 set_alias_uids (original
, DECL_UID (original
->decl
));
2269 /* Dump symbol to FILE. */
2272 sem_variable::dump_to_file (FILE *file
)
2276 print_node (file
, "", decl
, 0);
2277 fprintf (file
, "\n\n");
2280 unsigned int sem_item_optimizer::class_id
= 0;
2282 sem_item_optimizer::sem_item_optimizer ()
2283 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2284 m_varpool_node_hooks (NULL
)
2287 bitmap_obstack_initialize (&m_bmstack
);
2290 sem_item_optimizer::~sem_item_optimizer ()
2292 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2295 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2296 it
!= m_classes
.end (); ++it
)
2298 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2299 delete (*it
)->classes
[i
];
2301 (*it
)->classes
.release ();
2307 bitmap_obstack_release (&m_bmstack
);
2310 /* Write IPA ICF summary for symbols. */
2313 sem_item_optimizer::write_summary (void)
2315 unsigned int count
= 0;
2317 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2318 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2321 /* Calculate number of symbols to be serialized. */
2322 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2324 lsei_next_in_partition (&lsei
))
2326 symtab_node
*node
= lsei_node (lsei
);
2328 if (m_symtab_node_map
.get (node
))
2332 streamer_write_uhwi (ob
, count
);
2334 /* Process all of the symbols. */
2335 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2337 lsei_next_in_partition (&lsei
))
2339 symtab_node
*node
= lsei_node (lsei
);
2341 sem_item
**item
= m_symtab_node_map
.get (node
);
2345 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2346 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2348 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2352 streamer_write_char_stream (ob
->main_stream
, 0);
2353 produce_asm (ob
, NULL
);
2354 destroy_output_block (ob
);
2357 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2358 contains LEN bytes. */
2361 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2362 const char *data
, size_t len
)
2364 const lto_function_header
*header
=
2365 (const lto_function_header
*) data
;
2366 const int cfg_offset
= sizeof (lto_function_header
);
2367 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2368 const int string_offset
= main_offset
+ header
->main_size
;
2373 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2374 header
->main_size
, file_data
->mode_table
);
2377 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2378 header
->string_size
, vNULL
);
2380 count
= streamer_read_uhwi (&ib_main
);
2382 for (i
= 0; i
< count
; i
++)
2386 lto_symtab_encoder_t encoder
;
2388 index
= streamer_read_uhwi (&ib_main
);
2389 encoder
= file_data
->symtab_node_encoder
;
2390 node
= lto_symtab_encoder_deref (encoder
, index
);
2392 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2394 gcc_assert (node
->definition
);
2397 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2398 node
->asm_name (), (void *) node
->decl
, node
->order
);
2400 if (is_a
<cgraph_node
*> (node
))
2402 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2404 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2405 fn
->set_hash (hash
);
2406 m_items
.safe_push (fn
);
2410 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2412 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2413 var
->set_hash (hash
);
2414 m_items
.safe_push (var
);
2418 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2420 lto_data_in_delete (data_in
);
2423 /* Read IPA ICF summary for symbols. */
2426 sem_item_optimizer::read_summary (void)
2428 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2429 lto_file_decl_data
*file_data
;
2432 while ((file_data
= file_data_vec
[j
++]))
2435 const char *data
= lto_get_section_data (file_data
,
2436 LTO_section_ipa_icf
, NULL
, &len
);
2439 read_section (file_data
, data
, len
);
2443 /* Register callgraph and varpool hooks. */
2446 sem_item_optimizer::register_hooks (void)
2448 if (!m_cgraph_node_hooks
)
2449 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2450 (&sem_item_optimizer::cgraph_removal_hook
, this);
2452 if (!m_varpool_node_hooks
)
2453 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2454 (&sem_item_optimizer::varpool_removal_hook
, this);
2457 /* Unregister callgraph and varpool hooks. */
2460 sem_item_optimizer::unregister_hooks (void)
2462 if (m_cgraph_node_hooks
)
2463 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2465 if (m_varpool_node_hooks
)
2466 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2469 /* Adds a CLS to hashtable associated by hash value. */
2472 sem_item_optimizer::add_class (congruence_class
*cls
)
2474 gcc_assert (cls
->members
.length ());
2476 congruence_class_group
*group
= get_group_by_hash (
2477 cls
->members
[0]->get_hash (),
2478 cls
->members
[0]->type
);
2479 group
->classes
.safe_push (cls
);
2482 /* Gets a congruence class group based on given HASH value and TYPE. */
2484 congruence_class_group
*
2485 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2487 congruence_class_group
*item
= XNEW (congruence_class_group
);
2491 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2497 item
->classes
.create (1);
2504 /* Callgraph removal hook called for a NODE with a custom DATA. */
2507 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2509 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2510 optimizer
->remove_symtab_node (node
);
2513 /* Varpool removal hook called for a NODE with a custom DATA. */
2516 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2518 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2519 optimizer
->remove_symtab_node (node
);
2522 /* Remove symtab NODE triggered by symtab removal hooks. */
2525 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2527 gcc_assert (!m_classes
.elements());
2529 m_removed_items_set
.add (node
);
2533 sem_item_optimizer::remove_item (sem_item
*item
)
2535 if (m_symtab_node_map
.get (item
->node
))
2536 m_symtab_node_map
.remove (item
->node
);
2540 /* Removes all callgraph and varpool nodes that are marked by symtab
2544 sem_item_optimizer::filter_removed_items (void)
2546 auto_vec
<sem_item
*> filtered
;
2548 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2550 sem_item
*item
= m_items
[i
];
2552 if (m_removed_items_set
.contains (item
->node
))
2558 if (item
->type
== FUNC
)
2560 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2562 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2565 filtered
.safe_push (item
);
2569 if (!flag_ipa_icf_variables
)
2573 /* Filter out non-readonly variables. */
2574 tree decl
= item
->decl
;
2575 if (TREE_READONLY (decl
))
2576 filtered
.safe_push (item
);
2583 /* Clean-up of released semantic items. */
2586 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2587 m_items
.safe_push (filtered
[i
]);
2590 /* Optimizer entry point which returns true in case it processes
2591 a merge operation. True is returned if there's a merge operation
2595 sem_item_optimizer::execute (void)
2597 filter_removed_items ();
2598 unregister_hooks ();
2601 update_hash_by_addr_refs ();
2602 build_hash_based_classes ();
2605 fprintf (dump_file
, "Dump after hash based groups\n");
2606 dump_cong_classes ();
2608 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2609 m_items
[i
]->init_wpa ();
2611 subdivide_classes_by_equality (true);
2614 fprintf (dump_file
, "Dump after WPA based types groups\n");
2616 dump_cong_classes ();
2618 process_cong_reduction ();
2619 checking_verify_classes ();
2622 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2624 dump_cong_classes ();
2626 parse_nonsingleton_classes ();
2627 subdivide_classes_by_equality ();
2630 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2632 dump_cong_classes ();
2634 unsigned int prev_class_count
= m_classes_count
;
2636 process_cong_reduction ();
2637 dump_cong_classes ();
2638 checking_verify_classes ();
2639 bool merged_p
= merge_classes (prev_class_count
);
2641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2642 symtab_node::dump_table (dump_file
);
2647 /* Function responsible for visiting all potential functions and
2648 read-only variables that can be merged. */
2651 sem_item_optimizer::parse_funcs_and_vars (void)
2655 if (flag_ipa_icf_functions
)
2656 FOR_EACH_DEFINED_FUNCTION (cnode
)
2658 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2661 m_items
.safe_push (f
);
2662 m_symtab_node_map
.put (cnode
, f
);
2665 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 f
->dump_to_file (dump_file
);
2671 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2674 varpool_node
*vnode
;
2676 if (flag_ipa_icf_variables
)
2677 FOR_EACH_DEFINED_VARIABLE (vnode
)
2679 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2683 m_items
.safe_push (v
);
2684 m_symtab_node_map
.put (vnode
, v
);
2689 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2692 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2694 item
->index_in_class
= cls
->members
.length ();
2695 cls
->members
.safe_push (item
);
2699 /* For each semantic item, append hash values of references. */
2702 sem_item_optimizer::update_hash_by_addr_refs ()
2704 /* First, append to hash sensitive references and class type if it need to
2705 be matched for ODR. */
2706 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2708 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2709 if (m_items
[i
]->type
== FUNC
)
2711 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2712 && contains_polymorphic_type_p
2713 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2714 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2715 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2716 && static_cast<sem_function
*> (m_items
[i
])
2717 ->compare_polymorphic_p ())))
2720 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2721 inchash::hash
hstate (m_items
[i
]->get_hash ());
2723 if (TYPE_NAME (class_type
)
2724 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2726 (IDENTIFIER_HASH_VALUE
2727 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2729 m_items
[i
]->set_hash (hstate
.end ());
2734 /* Once all symbols have enhanced hash value, we can append
2735 hash values of symbols that are seen by IPA ICF and are
2736 references by a semantic item. Newly computed values
2737 are saved to global_hash member variable. */
2738 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2739 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2741 /* Global hash value replace current hash values. */
2742 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2743 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2746 /* Congruence classes are built by hash value. */
2749 sem_item_optimizer::build_hash_based_classes (void)
2751 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2753 sem_item
*item
= m_items
[i
];
2755 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2758 if (!group
->classes
.length ())
2761 group
->classes
.safe_push (new congruence_class (class_id
++));
2764 add_item_to_class (group
->classes
[0], item
);
2768 /* Build references according to call graph. */
2771 sem_item_optimizer::build_graph (void)
2773 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2775 sem_item
*item
= m_items
[i
];
2776 m_symtab_node_map
.put (item
->node
, item
);
2778 /* Initialize hash values if we are not in LTO mode. */
2783 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2785 sem_item
*item
= m_items
[i
];
2787 if (item
->type
== FUNC
)
2789 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2791 cgraph_edge
*e
= cnode
->callees
;
2794 sem_item
**slot
= m_symtab_node_map
.get
2795 (e
->callee
->ultimate_alias_target ());
2797 item
->add_reference (*slot
);
2803 ipa_ref
*ref
= NULL
;
2804 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2806 sem_item
**slot
= m_symtab_node_map
.get
2807 (ref
->referred
->ultimate_alias_target ());
2809 item
->add_reference (*slot
);
2814 /* Semantic items in classes having more than one element and initialized.
2815 In case of WPA, we load function body. */
2818 sem_item_optimizer::parse_nonsingleton_classes (void)
2820 unsigned int init_called_count
= 0;
2822 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2823 if (m_items
[i
]->cls
->members
.length () > 1)
2825 m_items
[i
]->init ();
2826 init_called_count
++;
2830 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2831 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2834 /* Equality function for semantic items is used to subdivide existing
2835 classes. If IN_WPA, fast equality function is invoked. */
2838 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2840 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2841 it
!= m_classes
.end (); ++it
)
2843 unsigned int class_count
= (*it
)->classes
.length ();
2845 for (unsigned i
= 0; i
< class_count
; i
++)
2847 congruence_class
*c
= (*it
)->classes
[i
];
2849 if (c
->members
.length() > 1)
2851 auto_vec
<sem_item
*> new_vector
;
2853 sem_item
*first
= c
->members
[0];
2854 new_vector
.safe_push (first
);
2856 unsigned class_split_first
= (*it
)->classes
.length ();
2858 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2860 sem_item
*item
= c
->members
[j
];
2862 bool equals
= in_wpa
? first
->equals_wpa (item
,
2863 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2866 new_vector
.safe_push (item
);
2869 bool integrated
= false;
2871 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2873 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2874 bool equals
= in_wpa
? x
->equals_wpa (item
,
2875 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2880 add_item_to_class ((*it
)->classes
[k
], item
);
2888 congruence_class
*c
= new congruence_class (class_id
++);
2890 add_item_to_class (c
, item
);
2892 (*it
)->classes
.safe_push (c
);
2897 // we replace newly created new_vector for the class we've just splitted
2898 c
->members
.release ();
2899 c
->members
.create (new_vector
.length ());
2901 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2902 add_item_to_class (c
, new_vector
[j
]);
2907 checking_verify_classes ();
2910 /* Subdivide classes by address references that members of the class
2911 reference. Example can be a pair of functions that have an address
2912 taken from a function. If these addresses are different the class
2916 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2918 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2920 unsigned newly_created_classes
= 0;
2922 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2923 it
!= m_classes
.end (); ++it
)
2925 unsigned int class_count
= (*it
)->classes
.length ();
2926 auto_vec
<congruence_class
*> new_classes
;
2928 for (unsigned i
= 0; i
< class_count
; i
++)
2930 congruence_class
*c
= (*it
)->classes
[i
];
2932 if (c
->members
.length() > 1)
2934 subdivide_hash_map split_map
;
2936 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2938 sem_item
*source_node
= c
->members
[j
];
2940 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2943 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2945 gcc_checking_assert (slot
);
2947 slot
->safe_push (source_node
);
2953 /* If the map contains more than one key, we have to split the map
2955 if (split_map
.elements () != 1)
2957 bool first_class
= true;
2959 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2960 it2
!= split_map
.end (); ++it2
)
2962 congruence_class
*new_cls
;
2963 new_cls
= new congruence_class (class_id
++);
2965 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2966 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2968 worklist_push (new_cls
);
2969 newly_created_classes
++;
2973 (*it
)->classes
[i
] = new_cls
;
2974 first_class
= false;
2978 new_classes
.safe_push (new_cls
);
2984 /* Release memory. */
2985 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2986 it2
!= split_map
.end (); ++it2
)
2988 delete (*it2
).first
;
2989 (*it2
).second
.release ();
2994 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2995 (*it
)->classes
.safe_push (new_classes
[i
]);
2998 return newly_created_classes
;
3001 /* Verify congruence classes, if checking is enabled. */
3004 sem_item_optimizer::checking_verify_classes (void)
3010 /* Verify congruence classes. */
3013 sem_item_optimizer::verify_classes (void)
3015 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3016 it
!= m_classes
.end (); ++it
)
3018 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3020 congruence_class
*cls
= (*it
)->classes
[i
];
3023 gcc_assert (cls
->members
.length () > 0);
3025 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3027 sem_item
*item
= cls
->members
[j
];
3030 gcc_assert (item
->cls
== cls
);
3032 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3034 sem_usage_pair
*usage
= item
->usages
[k
];
3035 gcc_assert (usage
->item
->index_in_class
<
3036 usage
->item
->cls
->members
.length ());
3043 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3044 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3045 but unused argument. */
3048 sem_item_optimizer::release_split_map (congruence_class
* const &,
3049 bitmap
const &b
, traverse_split_pair
*)
3058 /* Process split operation for a class given as pointer CLS_PTR,
3059 where bitmap B splits congruence class members. DATA is used
3060 as argument of split pair. */
3063 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3064 bitmap
const &b
, traverse_split_pair
*pair
)
3066 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3067 const congruence_class
*splitter_cls
= pair
->cls
;
3069 /* If counted bits are greater than zero and less than the number of members
3070 a group will be splitted. */
3071 unsigned popcount
= bitmap_count_bits (b
);
3073 if (popcount
> 0 && popcount
< cls
->members
.length ())
3075 auto_vec
<congruence_class
*, 2> newclasses
;
3076 newclasses
.quick_push (new congruence_class (class_id
++));
3077 newclasses
.quick_push (new congruence_class (class_id
++));
3079 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3081 int target
= bitmap_bit_p (b
, i
);
3082 congruence_class
*tc
= newclasses
[target
];
3084 add_item_to_class (tc
, cls
->members
[i
]);
3089 for (unsigned int i
= 0; i
< 2; i
++)
3090 gcc_assert (newclasses
[i
]->members
.length ());
3093 if (splitter_cls
== cls
)
3094 optimizer
->splitter_class_removed
= true;
3096 /* Remove old class from worklist if presented. */
3097 bool in_worklist
= cls
->in_worklist
;
3100 cls
->in_worklist
= false;
3102 congruence_class_group g
;
3103 g
.hash
= cls
->members
[0]->get_hash ();
3104 g
.type
= cls
->members
[0]->type
;
3106 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3108 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3109 if (slot
->classes
[i
] == cls
)
3111 slot
->classes
.ordered_remove (i
);
3115 /* New class will be inserted and integrated to work list. */
3116 for (unsigned int i
= 0; i
< 2; i
++)
3117 optimizer
->add_class (newclasses
[i
]);
3119 /* Two classes replace one, so that increment just by one. */
3120 optimizer
->m_classes_count
++;
3122 /* If OLD class was presented in the worklist, we remove the class
3123 and replace it will both newly created classes. */
3125 for (unsigned int i
= 0; i
< 2; i
++)
3126 optimizer
->worklist_push (newclasses
[i
]);
3127 else /* Just smaller class is inserted. */
3129 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3130 newclasses
[1]->members
.length () ?
3132 optimizer
->worklist_push (newclasses
[smaller_index
]);
3135 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3137 fprintf (dump_file
, " congruence class splitted:\n");
3138 cls
->dump (dump_file
, 4);
3140 fprintf (dump_file
, " newly created groups:\n");
3141 for (unsigned int i
= 0; i
< 2; i
++)
3142 newclasses
[i
]->dump (dump_file
, 4);
3145 /* Release class if not presented in work list. */
3154 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3155 Bitmap stack BMSTACK is used for bitmap allocation. */
3158 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3161 hash_map
<congruence_class
*, bitmap
> split_map
;
3163 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3165 sem_item
*item
= cls
->members
[i
];
3167 /* Iterate all usages that have INDEX as usage of the item. */
3168 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3170 sem_usage_pair
*usage
= item
->usages
[j
];
3172 if (usage
->index
!= index
)
3175 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3180 b
= BITMAP_ALLOC (&m_bmstack
);
3181 split_map
.put (usage
->item
->cls
, b
);
3186 gcc_checking_assert (usage
->item
->cls
);
3187 gcc_checking_assert (usage
->item
->index_in_class
<
3188 usage
->item
->cls
->members
.length ());
3190 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3194 traverse_split_pair pair
;
3195 pair
.optimizer
= this;
3198 splitter_class_removed
= false;
3200 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3202 /* Bitmap clean-up. */
3204 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3207 /* Every usage of a congruence class CLS is a candidate that can split the
3208 collection of classes. Bitmap stack BMSTACK is used for bitmap
3212 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3217 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3219 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3220 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3222 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3225 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3228 do_congruence_step_for_index (cls
, i
);
3230 if (splitter_class_removed
)
3234 BITMAP_FREE (usage
);
3237 /* Adds a newly created congruence class CLS to worklist. */
3240 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3242 /* Return if the class CLS is already presented in work list. */
3243 if (cls
->in_worklist
)
3246 cls
->in_worklist
= true;
3247 worklist
.push_back (cls
);
3250 /* Pops a class from worklist. */
3253 sem_item_optimizer::worklist_pop (void)
3255 congruence_class
*cls
;
3257 while (!worklist
.empty ())
3259 cls
= worklist
.front ();
3260 worklist
.pop_front ();
3261 if (cls
->in_worklist
)
3263 cls
->in_worklist
= false;
3269 /* Work list item was already intended to be removed.
3270 The only reason for doing it is to split a class.
3271 Thus, the class CLS is deleted. */
3279 /* Iterative congruence reduction function. */
3282 sem_item_optimizer::process_cong_reduction (void)
3284 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3285 it
!= m_classes
.end (); ++it
)
3286 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3287 if ((*it
)->classes
[i
]->is_class_used ())
3288 worklist_push ((*it
)->classes
[i
]);
3291 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3292 (unsigned long) worklist
.size ());
3294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3295 fprintf (dump_file
, "Congruence class reduction\n");
3297 congruence_class
*cls
;
3299 /* Process complete congruence reduction. */
3300 while ((cls
= worklist_pop ()) != NULL
)
3301 do_congruence_step (cls
);
3303 /* Subdivide newly created classes according to references. */
3304 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3307 fprintf (dump_file
, "Address reference subdivision created: %u "
3308 "new classes.\n", new_classes
);
3311 /* Debug function prints all informations about congruence classes. */
3314 sem_item_optimizer::dump_cong_classes (void)
3320 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3321 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3323 /* Histogram calculation. */
3324 unsigned int max_index
= 0;
3325 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3327 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3328 it
!= m_classes
.end (); ++it
)
3330 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3332 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3340 "Class size histogram [num of members]: number of classe number of classess\n");
3342 for (unsigned int i
= 0; i
<= max_index
; i
++)
3344 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3346 fprintf (dump_file
, "\n\n");
3349 if (dump_flags
& TDF_DETAILS
)
3350 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3351 it
!= m_classes
.end (); ++it
)
3353 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3355 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3357 (*it
)->classes
[i
]->dump (dump_file
, 4);
3359 if(i
< (*it
)->classes
.length () - 1)
3360 fprintf (dump_file
, " ");
3367 /* After reduction is done, we can declare all items in a group
3368 to be equal. PREV_CLASS_COUNT is start number of classes
3369 before reduction. True is returned if there's a merge operation
3373 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3375 unsigned int item_count
= m_items
.length ();
3376 unsigned int class_count
= m_classes_count
;
3377 unsigned int equal_items
= item_count
- class_count
;
3379 unsigned int non_singular_classes_count
= 0;
3380 unsigned int non_singular_classes_sum
= 0;
3382 bool merged_p
= false;
3384 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3385 it
!= m_classes
.end (); ++it
)
3386 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3388 congruence_class
*c
= (*it
)->classes
[i
];
3389 if (c
->members
.length () > 1)
3391 non_singular_classes_count
++;
3392 non_singular_classes_sum
+= c
->members
.length ();
3398 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3399 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3400 prev_class_count
, class_count
);
3401 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3402 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3403 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3404 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3405 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3406 non_singular_classes_count
: 0.0f
,
3407 non_singular_classes_count
);
3408 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3409 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3410 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3413 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3414 it
!= m_classes
.end (); ++it
)
3415 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3417 congruence_class
*c
= (*it
)->classes
[i
];
3419 if (c
->members
.length () == 1)
3422 sem_item
*source
= c
->members
[0];
3424 if (DECL_NAME (source
->decl
)
3425 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3426 /* If merge via wrappers, picking main as the target can be
3428 source
= c
->members
[1];
3430 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3432 sem_item
*alias
= c
->members
[j
];
3434 if (alias
== source
)
3439 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3440 xstrdup_for_dump (source
->node
->name ()),
3441 xstrdup_for_dump (alias
->node
->name ()));
3442 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3443 xstrdup_for_dump (source
->node
->asm_name ()),
3444 xstrdup_for_dump (alias
->node
->asm_name ()));
3447 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3451 "Merge operation is skipped due to no_icf "
3457 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3459 source
->dump_to_file (dump_file
);
3460 alias
->dump_to_file (dump_file
);
3463 if (dbg_cnt (merged_ipa_icf
))
3464 merged_p
|= source
->merge (alias
);
3471 /* Dump function prints all class members to a FILE with an INDENT. */
3474 congruence_class::dump (FILE *file
, unsigned int indent
) const
3476 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3477 id
, members
[0]->get_hash (), members
.length ());
3479 FPUTS_SPACES (file
, indent
+ 2, "");
3480 for (unsigned i
= 0; i
< members
.length (); i
++)
3481 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3482 (void *) members
[i
]->decl
,
3483 members
[i
]->node
->order
);
3485 fprintf (file
, "\n");
3488 /* Returns true if there's a member that is used from another group. */
3491 congruence_class::is_class_used (void)
3493 for (unsigned int i
= 0; i
< members
.length (); i
++)
3494 if (members
[i
]->usages
.length ())
3500 /* Generate pass summary for IPA ICF pass. */
3503 ipa_icf_generate_summary (void)
3506 optimizer
= new sem_item_optimizer ();
3508 optimizer
->register_hooks ();
3509 optimizer
->parse_funcs_and_vars ();
3512 /* Write pass summary for IPA ICF pass. */
3515 ipa_icf_write_summary (void)
3517 gcc_assert (optimizer
);
3519 optimizer
->write_summary ();
3522 /* Read pass summary for IPA ICF pass. */
3525 ipa_icf_read_summary (void)
3528 optimizer
= new sem_item_optimizer ();
3530 optimizer
->read_summary ();
3531 optimizer
->register_hooks ();
3534 /* Semantic equality exection function. */
3537 ipa_icf_driver (void)
3539 gcc_assert (optimizer
);
3541 bool merged_p
= optimizer
->execute ();
3546 return merged_p
? TODO_remove_functions
: 0;
3549 const pass_data pass_data_ipa_icf
=
3551 IPA_PASS
, /* type */
3553 OPTGROUP_IPA
, /* optinfo_flags */
3554 TV_IPA_ICF
, /* tv_id */
3555 0, /* properties_required */
3556 0, /* properties_provided */
3557 0, /* properties_destroyed */
3558 0, /* todo_flags_start */
3559 0, /* todo_flags_finish */
3562 class pass_ipa_icf
: public ipa_opt_pass_d
3565 pass_ipa_icf (gcc::context
*ctxt
)
3566 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3567 ipa_icf_generate_summary
, /* generate_summary */
3568 ipa_icf_write_summary
, /* write_summary */
3569 ipa_icf_read_summary
, /* read_summary */
3571 write_optimization_summary */
3573 read_optimization_summary */
3574 NULL
, /* stmt_fixup */
3575 0, /* function_transform_todo_flags_start */
3576 NULL
, /* function_transform */
3577 NULL
) /* variable_transform */
3580 /* opt_pass methods: */
3581 virtual bool gate (function
*)
3583 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3586 virtual unsigned int execute (function
*)
3588 return ipa_icf_driver();
3590 }; // class pass_ipa_icf
3592 } // ipa_icf namespace
3595 make_pass_ipa_icf (gcc::context
*ctxt
)
3597 return new ipa_icf::pass_ipa_icf (ctxt
);