1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2017 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
135 : item (_item
), index (_index
)
139 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
140 : type (_type
), m_hash (-1), m_hash_set (false)
145 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
146 bitmap_obstack
*stack
)
147 : type (_type
), node (_node
), m_hash (-1), m_hash_set (false)
153 /* Add reference to a semantic TARGET. */
156 sem_item::add_reference (sem_item
*target
)
158 refs
.safe_push (target
);
159 unsigned index
= refs
.length ();
160 target
->usages
.safe_push (new sem_usage_pair(this, index
));
161 bitmap_set_bit (target
->usage_index_bitmap
, index
);
162 refs_set
.add (target
->node
);
165 /* Initialize internal data structures. Bitmap STACK is used for
166 bitmap memory allocation process. */
169 sem_item::setup (bitmap_obstack
*stack
)
171 gcc_checking_assert (node
);
174 tree_refs
.create (0);
176 usage_index_bitmap
= BITMAP_ALLOC (stack
);
179 sem_item::~sem_item ()
181 for (unsigned i
= 0; i
< usages
.length (); i
++)
185 tree_refs
.release ();
188 BITMAP_FREE (usage_index_bitmap
);
191 /* Dump function for debugging purpose. */
194 sem_item::dump (void)
198 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
199 node
->name(), node
->order
, (void *) node
->decl
);
200 fprintf (dump_file
, " hash: %u\n", get_hash ());
201 fprintf (dump_file
, " references: ");
203 for (unsigned i
= 0; i
< refs
.length (); i
++)
204 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
205 i
< refs
.length() - 1 ? "," : "");
207 fprintf (dump_file
, "\n");
211 /* Return true if target supports alias symbols. */
214 sem_item::target_supports_symbol_aliases_p (void)
216 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
223 void sem_item::set_hash (hashval_t hash
)
229 /* Semantic function constructor that uses STACK as bitmap memory stack. */
231 sem_function::sem_function (bitmap_obstack
*stack
)
232 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
235 bb_sorted
.create (0);
238 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
239 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
242 bb_sorted
.create (0);
245 sem_function::~sem_function ()
247 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
248 delete (bb_sorted
[i
]);
251 bb_sorted
.release ();
254 /* Calculates hash value based on a BASIC_BLOCK. */
257 sem_function::get_bb_hash (const sem_bb
*basic_block
)
259 inchash::hash hstate
;
261 hstate
.add_int (basic_block
->nondbg_stmt_count
);
262 hstate
.add_int (basic_block
->edge_count
);
264 return hstate
.end ();
267 /* References independent hash function. */
270 sem_function::get_hash (void)
274 inchash::hash hstate
;
275 hstate
.add_int (177454); /* Random number for function type. */
277 hstate
.add_int (arg_count
);
278 hstate
.add_int (cfg_checksum
);
279 hstate
.add_int (gcode_hash
);
281 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
282 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
284 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
285 hstate
.add_int (bb_sizes
[i
]);
287 /* Add common features of declaration itself. */
288 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
290 (cl_target_option_hash
291 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
292 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
294 (cl_optimization_hash
295 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
296 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
297 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
299 set_hash (hstate
.end ());
305 /* Return ture if A1 and A2 represent equivalent function attribute lists.
306 Based on comp_type_attributes. */
309 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
314 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
316 const struct attribute_spec
*as
;
319 as
= lookup_attribute_spec (get_attribute_name (a
));
320 /* TODO: We can introduce as->affects_decl_identity
321 and as->affects_decl_reference_identity if attribute mismatch
322 gets a common reason to give up on merging. It may not be worth
324 For example returns_nonnull affects only references, while
325 optimize attribute can be ignored because it is already lowered
326 into flags representation and compared separately. */
330 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
331 if (!attr
|| !attribute_value_equal (a
, attr
))
336 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
338 const struct attribute_spec
*as
;
340 as
= lookup_attribute_spec (get_attribute_name (a
));
344 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
346 /* We don't need to compare trees again, as we did this
347 already in first loop. */
352 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
356 /* Compare properties of symbols N1 and N2 that does not affect semantics of
357 symbol itself but affects semantics of its references from USED_BY (which
358 may be NULL if it is unknown). If comparsion is false, symbols
359 can still be merged but any symbols referring them can't.
361 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
363 TODO: We can also split attributes to those that determine codegen of
364 a function body/variable constructor itself and those that are used when
368 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
373 if (is_a
<cgraph_node
*> (n1
))
375 /* Inline properties matters: we do now want to merge uses of inline
376 function to uses of normal function because inline hint would be lost.
377 We however can merge inline function to noinline because the alias
378 will keep its DECL_DECLARED_INLINE flag.
380 Also ignore inline flag when optimizing for size or when function
381 is known to not be inlinable.
383 TODO: the optimize_size checks can also be assumed to be true if
384 unit has no !optimize_size functions. */
386 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
387 || !opt_for_fn (used_by
->decl
, optimize_size
))
388 && !opt_for_fn (n1
->decl
, optimize_size
)
389 && n1
->get_availability () > AVAIL_INTERPOSABLE
390 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
392 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
393 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
394 return return_false_with_msg
395 ("DECL_DISREGARD_INLINE_LIMITS are different");
397 if (DECL_DECLARED_INLINE_P (n1
->decl
)
398 != DECL_DECLARED_INLINE_P (n2
->decl
))
399 return return_false_with_msg ("inline attributes are different");
402 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
403 != DECL_IS_OPERATOR_NEW (n2
->decl
))
404 return return_false_with_msg ("operator new flags are different");
407 /* Merging two definitions with a reference to equivalent vtables, but
408 belonging to a different type may result in ipa-polymorphic-call analysis
409 giving a wrong answer about the dynamic type of instance. */
410 if (is_a
<varpool_node
*> (n1
))
412 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
413 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
414 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
415 DECL_CONTEXT (n2
->decl
)))
416 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
417 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
418 return return_false_with_msg
419 ("references to virtual tables can not be merged");
421 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
422 return return_false_with_msg ("alignment mismatch");
424 /* For functions we compare attributes in equals_wpa, because we do
425 not know what attributes may cause codegen differences, but for
426 variables just compare attributes for references - the codegen
427 for constructors is affected only by those attributes that we lower
428 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
429 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
430 DECL_ATTRIBUTES (n2
->decl
)))
431 return return_false_with_msg ("different var decl attributes");
432 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
433 TREE_TYPE (n2
->decl
)) != 1)
434 return return_false_with_msg ("different var type attributes");
437 /* When matching virtual tables, be sure to also match information
438 relevant for polymorphic call analysis. */
439 if (used_by
&& is_a
<varpool_node
*> (used_by
)
440 && DECL_VIRTUAL_P (used_by
->decl
))
442 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
443 return return_false_with_msg ("virtual flag mismatch");
444 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
445 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
446 return return_false_with_msg ("final flag mismatch");
451 /* Hash properties that are compared by compare_referenced_symbol_properties. */
454 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
455 inchash::hash
&hstate
,
458 if (is_a
<cgraph_node
*> (ref
))
460 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
461 && !opt_for_fn (ref
->decl
, optimize_size
)
462 && !DECL_UNINLINABLE (ref
->decl
))
464 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
465 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
467 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
469 else if (is_a
<varpool_node
*> (ref
))
471 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
473 hstate
.add_int (DECL_ALIGN (ref
->decl
));
478 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
479 point to a same function. Comparison can be skipped if IGNORED_NODES
480 contains these nodes. ADDRESS indicate if address is taken. */
483 sem_item::compare_symbol_references (
484 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
485 symtab_node
*n1
, symtab_node
*n2
, bool address
)
487 enum availability avail1
, avail2
;
492 /* Never match variable and function. */
493 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
496 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
498 if (address
&& n1
->equal_address_to (n2
) == 1)
500 if (!address
&& n1
->semantically_equivalent_p (n2
))
503 n1
= n1
->ultimate_alias_target (&avail1
);
504 n2
= n2
->ultimate_alias_target (&avail2
);
506 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
507 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
510 return return_false_with_msg ("different references");
513 /* If cgraph edges E1 and E2 are indirect calls, verify that
514 ECF flags are the same. */
516 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
518 if (e1
->indirect_info
&& e2
->indirect_info
)
520 int e1_flags
= e1
->indirect_info
->ecf_flags
;
521 int e2_flags
= e2
->indirect_info
->ecf_flags
;
523 if (e1_flags
!= e2_flags
)
524 return return_false_with_msg ("ICF flags are different");
526 else if (e1
->indirect_info
|| e2
->indirect_info
)
532 /* Return true if parameter I may be used. */
535 sem_function::param_used_p (unsigned int i
)
537 if (ipa_node_params_sum
== NULL
)
540 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
542 if (parms_info
->descriptors
.is_empty ()
543 || parms_info
->descriptors
.length () <= i
)
546 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
549 /* Perform additional check needed to match types function parameters that are
550 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
551 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
554 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
556 /* Be sure that parameters are TBAA compatible. */
557 if (!func_checker::compatible_types_p (parm1
, parm2
))
558 return return_false_with_msg ("parameter type is not compatible");
560 if (POINTER_TYPE_P (parm1
)
561 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
562 return return_false_with_msg ("argument restrict flag mismatch");
564 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
565 if (POINTER_TYPE_P (parm1
)
566 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
567 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
568 return return_false_with_msg ("pointer wrt reference mismatch");
573 /* Fast equality function based on knowledge known in WPA. */
576 sem_function::equals_wpa (sem_item
*item
,
577 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
579 gcc_assert (item
->type
== FUNC
);
580 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
581 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
583 m_compared_func
= static_cast<sem_function
*> (item
);
585 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
586 return return_false_with_msg ("thunk_p mismatch");
588 if (cnode
->thunk
.thunk_p
)
590 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
591 return return_false_with_msg ("thunk fixed_offset mismatch");
592 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
593 return return_false_with_msg ("thunk virtual_value mismatch");
594 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
595 return return_false_with_msg ("thunk this_adjusting mismatch");
596 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
597 return return_false_with_msg ("thunk virtual_offset_p mismatch");
598 if (cnode
->thunk
.add_pointer_bounds_args
599 != cnode2
->thunk
.add_pointer_bounds_args
)
600 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
603 /* Compare special function DECL attributes. */
604 if (DECL_FUNCTION_PERSONALITY (decl
)
605 != DECL_FUNCTION_PERSONALITY (item
->decl
))
606 return return_false_with_msg ("function personalities are different");
608 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
609 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
610 return return_false_with_msg ("intrument function entry exit "
611 "attributes are different");
613 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
614 return return_false_with_msg ("no stack limit attributes are different");
616 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
617 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
619 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
620 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
622 /* TODO: pure/const flags mostly matters only for references, except for
623 the fact that codegen takes LOOPING flag as a hint that loops are
624 finite. We may arrange the code to always pick leader that has least
625 specified flags and then this can go into comparing symbol properties. */
626 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
627 return return_false_with_msg ("decl_or_type flags are different");
629 /* Do not match polymorphic constructors of different types. They calls
630 type memory location for ipa-polymorphic-call and we do not want
631 it to get confused by wrong type. */
632 if (DECL_CXX_CONSTRUCTOR_P (decl
)
633 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
635 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
636 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
637 else if (!func_checker::compatible_polymorphic_types_p
638 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
639 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
640 return return_false_with_msg ("ctor polymorphic type mismatch");
643 /* Checking function TARGET and OPTIMIZATION flags. */
644 cl_target_option
*tar1
= target_opts_for_fn (decl
);
645 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
647 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
651 fprintf (dump_file
, "target flags difference");
652 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
655 return return_false_with_msg ("Target flags are different");
658 cl_optimization
*opt1
= opts_for_fn (decl
);
659 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
661 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
665 fprintf (dump_file
, "optimization flags difference");
666 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
669 return return_false_with_msg ("optimization flags are different");
672 /* Result type checking. */
673 if (!func_checker::compatible_types_p
674 (TREE_TYPE (TREE_TYPE (decl
)),
675 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
676 return return_false_with_msg ("result types are different");
678 /* Checking types of arguments. */
679 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
680 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
681 for (unsigned i
= 0; list1
&& list2
;
682 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
684 tree parm1
= TREE_VALUE (list1
);
685 tree parm2
= TREE_VALUE (list2
);
687 /* This guard is here for function pointer with attributes (pr59927.c). */
688 if (!parm1
|| !parm2
)
689 return return_false_with_msg ("NULL argument type");
691 /* Verify that types are compatible to ensure that both functions
692 have same calling conventions. */
693 if (!types_compatible_p (parm1
, parm2
))
694 return return_false_with_msg ("parameter types are not compatible");
696 if (!param_used_p (i
))
699 /* Perform additional checks for used parameters. */
700 if (!compatible_parm_types_p (parm1
, parm2
))
705 return return_false_with_msg ("Mismatched number of parameters");
707 if (node
->num_references () != item
->node
->num_references ())
708 return return_false_with_msg ("different number of references");
710 /* Checking function attributes.
711 This is quadratic in number of attributes */
712 if (comp_type_attributes (TREE_TYPE (decl
),
713 TREE_TYPE (item
->decl
)) != 1)
714 return return_false_with_msg ("different type attributes");
715 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
716 DECL_ATTRIBUTES (item
->decl
)))
717 return return_false_with_msg ("different decl attributes");
719 /* The type of THIS pointer type memory location for
720 ipa-polymorphic-call-analysis. */
721 if (opt_for_fn (decl
, flag_devirtualize
)
722 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
723 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
725 && compare_polymorphic_p ())
727 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
728 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
729 if (!func_checker::compatible_polymorphic_types_p
730 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
731 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
732 return return_false_with_msg ("THIS pointer ODR type mismatch");
735 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
736 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
738 item
->node
->iterate_reference (i
, ref2
);
740 if (ref
->use
!= ref2
->use
)
741 return return_false_with_msg ("reference use mismatch");
743 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
745 ref
->address_matters_p ()))
749 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
750 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
754 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
757 if (!compare_edge_flags (e1
, e2
))
760 e1
= e1
->next_callee
;
761 e2
= e2
->next_callee
;
765 return return_false_with_msg ("different number of calls");
767 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
768 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
772 if (!compare_edge_flags (e1
, e2
))
775 e1
= e1
->next_callee
;
776 e2
= e2
->next_callee
;
780 return return_false_with_msg ("different number of indirect calls");
785 /* Update hash by address sensitive references. We iterate over all
786 sensitive references (address_matters_p) and we hash ultime alias
787 target of these nodes, which can improve a semantic item hash.
789 Also hash in referenced symbols properties. This can be done at any time
790 (as the properties should not change), but it is convenient to do it here
791 while we walk the references anyway. */
794 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
795 sem_item
*> &m_symtab_node_map
)
798 inchash::hash
hstate (get_hash ());
800 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
802 hstate
.add_int (ref
->use
);
803 hash_referenced_symbol_properties (ref
->referred
, hstate
,
804 ref
->use
== IPA_REF_ADDR
);
805 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
806 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
809 if (is_a
<cgraph_node
*> (node
))
811 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
814 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
815 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
817 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
821 set_hash (hstate
.end ());
824 /* Update hash by computed local hash values taken from different
826 TODO: stronger SCC based hashing would be desirable here. */
829 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
830 sem_item
*> &m_symtab_node_map
)
833 inchash::hash
state (get_hash ());
835 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
837 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
839 state
.merge_hash ((*result
)->get_hash ());
844 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
847 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
849 state
.merge_hash ((*result
)->get_hash ());
853 global_hash
= state
.end ();
856 /* Returns true if the item equals to ITEM given as argument. */
859 sem_function::equals (sem_item
*item
,
860 hash_map
<symtab_node
*, sem_item
*> &)
862 gcc_assert (item
->type
== FUNC
);
863 bool eq
= equals_private (item
);
865 if (m_checker
!= NULL
)
871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
873 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
874 xstrdup_for_dump (node
->name()),
875 xstrdup_for_dump (item
->node
->name ()),
878 xstrdup_for_dump (node
->asm_name ()),
879 xstrdup_for_dump (item
->node
->asm_name ()),
880 eq
? "true" : "false");
885 /* Processes function equality comparison. */
888 sem_function::equals_private (sem_item
*item
)
890 if (item
->type
!= FUNC
)
893 basic_block bb1
, bb2
;
895 edge_iterator ei1
, ei2
;
899 m_compared_func
= static_cast<sem_function
*> (item
);
901 gcc_assert (decl
!= item
->decl
);
903 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
904 || edge_count
!= m_compared_func
->edge_count
905 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
906 return return_false ();
908 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
909 compare_polymorphic_p (),
912 &m_compared_func
->refs_set
);
913 arg1
= DECL_ARGUMENTS (decl
);
914 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
916 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
918 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
919 return return_false_with_msg ("argument types are not compatible");
920 if (!param_used_p (i
))
922 /* Perform additional checks for used parameters. */
923 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
925 if (!m_checker
->compare_decl (arg1
, arg2
))
926 return return_false ();
929 return return_false_with_msg ("Mismatched number of arguments");
931 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
934 /* Fill-up label dictionary. */
935 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
937 m_checker
->parse_labels (bb_sorted
[i
]);
938 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
941 /* Checking all basic blocks. */
942 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
943 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
944 return return_false();
946 dump_message ("All BBs are equal\n");
948 auto_vec
<int> bb_dict
;
950 /* Basic block edges check. */
951 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
953 bb1
= bb_sorted
[i
]->bb
;
954 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
956 ei2
= ei_start (bb2
->preds
);
958 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
962 if (e1
->flags
!= e2
->flags
)
963 return return_false_with_msg ("flags comparison returns false");
965 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
966 return return_false_with_msg ("edge comparison returns false");
968 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
969 return return_false_with_msg ("BB comparison returns false");
971 if (!m_checker
->compare_edge (e1
, e2
))
972 return return_false_with_msg ("edge comparison returns false");
978 /* Basic block PHI nodes comparison. */
979 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
980 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
981 return return_false_with_msg ("PHI node comparison returns false");
986 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
987 Helper for call_for_symbol_thunks_and_aliases. */
990 set_local (cgraph_node
*node
, void *data
)
992 node
->local
.local
= data
!= NULL
;
996 /* TREE_ADDRESSABLE of NODE to true.
997 Helper for call_for_symbol_thunks_and_aliases. */
1000 set_addressable (varpool_node
*node
, void *)
1002 TREE_ADDRESSABLE (node
->decl
) = 1;
1006 /* Clear DECL_RTL of NODE.
1007 Helper for call_for_symbol_thunks_and_aliases. */
1010 clear_decl_rtl (symtab_node
*node
, void *)
1012 SET_DECL_RTL (node
->decl
, NULL
);
1016 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1017 possible. Return number of redirections made. */
1020 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1022 int nredirected
= 0;
1024 cgraph_edge
*e
= n
->callers
;
1028 /* Redirecting thunks to interposable symbols or symbols in other sections
1029 may not be supported by target output code. Play safe for now and
1030 punt on redirection. */
1031 if (!e
->caller
->thunk
.thunk_p
)
1033 struct cgraph_edge
*nexte
= e
->next_caller
;
1034 e
->redirect_callee (to
);
1041 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1043 bool removed
= false;
1044 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1046 if ((DECL_COMDAT_GROUP (n
->decl
)
1047 && (DECL_COMDAT_GROUP (n
->decl
)
1048 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1049 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1050 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1052 nredirected
+= redirect_all_callers (n_alias
, to
);
1053 if (n_alias
->can_remove_if_no_direct_calls_p ()
1054 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1056 && !n_alias
->has_aliases_p ())
1065 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1069 sem_function::merge (sem_item
*alias_item
)
1071 gcc_assert (alias_item
->type
== FUNC
);
1073 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1075 cgraph_node
*original
= get_node ();
1076 cgraph_node
*local_original
= NULL
;
1077 cgraph_node
*alias
= alias_func
->get_node ();
1079 bool create_wrapper
= false;
1080 bool create_alias
= false;
1081 bool redirect_callers
= false;
1082 bool remove
= false;
1084 bool original_discardable
= false;
1085 bool original_discarded
= false;
1087 bool original_address_matters
= original
->address_matters_p ();
1088 bool alias_address_matters
= alias
->address_matters_p ();
1090 if (DECL_EXTERNAL (alias
->decl
))
1093 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1097 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1098 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1103 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1107 /* Do not attempt to mix functions from different user sections;
1108 we do not know what user intends with those. */
1109 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1110 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1111 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1116 "original and alias are in different sections.\n\n");
1120 /* See if original is in a section that can be discarded if the main
1121 symbol is not used. */
1123 if (original
->can_be_discarded_p ())
1124 original_discardable
= true;
1125 /* Also consider case where we have resolution info and we know that
1126 original's definition is not going to be used. In this case we can not
1127 create alias to original. */
1128 if (node
->resolution
!= LDPR_UNKNOWN
1129 && !decl_binds_to_current_def_p (node
->decl
))
1130 original_discardable
= original_discarded
= true;
1132 /* Creating a symtab alias is the optimal way to merge.
1133 It however can not be used in the following cases:
1135 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1136 2) if ORIGINAL is in a section that may be discarded by linker or if
1137 it is an external functions where we can not create an alias
1138 (ORIGINAL_DISCARDABLE)
1139 3) if target do not support symbol aliases.
1140 4) original and alias lie in different comdat groups.
1142 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1143 and/or redirect all callers from ALIAS to ORIGINAL. */
1144 if ((original_address_matters
&& alias_address_matters
)
1145 || (original_discardable
1146 && (!DECL_COMDAT_GROUP (alias
->decl
)
1147 || (DECL_COMDAT_GROUP (alias
->decl
)
1148 != DECL_COMDAT_GROUP (original
->decl
))))
1149 || original_discarded
1150 || !sem_item::target_supports_symbol_aliases_p ()
1151 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1153 /* First see if we can produce wrapper. */
1155 /* Symbol properties that matter for references must be preserved.
1156 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1157 with proper properties. */
1158 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1159 alias
->address_taken
))
1163 "Wrapper cannot be created because referenced symbol "
1164 "properties mismatch\n");
1166 /* Do not turn function in one comdat group into wrapper to another
1167 comdat group. Other compiler producing the body of the
1168 another comdat group may make opossite decision and with unfortunate
1169 linker choices this may close a loop. */
1170 else if (DECL_COMDAT_GROUP (original
->decl
)
1171 && DECL_COMDAT_GROUP (alias
->decl
)
1172 && (DECL_COMDAT_GROUP (alias
->decl
)
1173 != DECL_COMDAT_GROUP (original
->decl
)))
1177 "Wrapper cannot be created because of COMDAT\n");
1179 else if (DECL_STATIC_CHAIN (alias
->decl
)
1180 || DECL_STATIC_CHAIN (original
->decl
))
1184 "Cannot create wrapper of nested function.\n");
1186 /* TODO: We can also deal with variadic functions never calling
1188 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1192 "can not create wrapper of stdarg function.\n");
1194 else if (inline_summaries
1195 && inline_summaries
->get (alias
)->self_size
<= 2)
1198 fprintf (dump_file
, "Wrapper creation is not "
1199 "profitable (function is too small).\n");
1201 /* If user paid attention to mark function noinline, assume it is
1202 somewhat special and do not try to turn it into a wrapper that can
1203 not be undone by inliner. */
1204 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1207 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1210 create_wrapper
= true;
1212 /* We can redirect local calls in the case both alias and orignal
1213 are not interposable. */
1215 = alias
->get_availability () > AVAIL_INTERPOSABLE
1216 && original
->get_availability () > AVAIL_INTERPOSABLE
1217 && !alias
->instrumented_version
;
1218 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1219 with proper properties. */
1220 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1221 alias
->address_taken
))
1222 redirect_callers
= false;
1224 if (!redirect_callers
&& !create_wrapper
)
1227 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1228 "produce wrapper\n\n");
1232 /* Work out the symbol the wrapper should call.
1233 If ORIGINAL is interposable, we need to call a local alias.
1234 Also produce local alias (if possible) as an optimization.
1236 Local aliases can not be created inside comdat groups because that
1237 prevents inlining. */
1238 if (!original_discardable
&& !original
->get_comdat_group ())
1241 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1243 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1244 local_original
= original
;
1246 /* If we can not use local alias, fallback to the original
1248 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1249 local_original
= original
;
1251 /* If original is COMDAT local, we can not really redirect calls outside
1252 of its comdat group to it. */
1253 if (original
->comdat_local_p ())
1254 redirect_callers
= false;
1255 if (!local_original
)
1258 fprintf (dump_file
, "Not unifying; "
1259 "can not produce local alias.\n\n");
1263 if (!redirect_callers
&& !create_wrapper
)
1266 fprintf (dump_file
, "Not unifying; "
1267 "can not redirect callers nor produce a wrapper\n\n");
1271 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1273 && !alias
->can_remove_if_no_direct_calls_p ())
1276 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1277 "function has other uses than direct calls\n\n");
1282 create_alias
= true;
1284 if (redirect_callers
)
1286 int nredirected
= redirect_all_callers (alias
, local_original
);
1290 alias
->icf_merged
= true;
1291 local_original
->icf_merged
= true;
1293 if (dump_file
&& nredirected
)
1294 fprintf (dump_file
, "%i local calls have been "
1295 "redirected.\n", nredirected
);
1298 /* If all callers was redirected, do not produce wrapper. */
1299 if (alias
->can_remove_if_no_direct_calls_p ()
1300 && !DECL_VIRTUAL_P (alias
->decl
)
1301 && !alias
->has_aliases_p ())
1303 create_wrapper
= false;
1306 gcc_assert (!create_alias
);
1308 else if (create_alias
)
1310 alias
->icf_merged
= true;
1312 /* Remove the function's body. */
1313 ipa_merge_profiles (original
, alias
);
1314 alias
->release_body (true);
1316 /* Notice global symbol possibly produced RTL. */
1317 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1320 /* Create the alias. */
1321 cgraph_node::create_alias (alias_func
->decl
, decl
);
1322 alias
->resolve_alias (original
);
1324 original
->call_for_symbol_thunks_and_aliases
1325 (set_local
, (void *)(size_t) original
->local_p (), true);
1328 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1332 gcc_assert (!create_alias
);
1333 alias
->icf_merged
= true;
1334 local_original
->icf_merged
= true;
1336 ipa_merge_profiles (local_original
, alias
, true);
1337 alias
->create_wrapper (local_original
);
1340 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1343 /* It's possible that redirection can hit thunks that block
1344 redirection opportunities. */
1345 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1346 original
->icf_merged
= true;
1348 /* We use merged flag to track cases where COMDAT function is known to be
1349 compatible its callers. If we merged in non-COMDAT, we need to give up
1350 on this optimization. */
1351 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1354 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1356 local_original
->merged_comdat
= false;
1357 original
->merged_comdat
= false;
1362 ipa_merge_profiles (original
, alias
);
1363 alias
->release_body ();
1365 alias
->body_removed
= true;
1366 alias
->icf_merged
= true;
1368 fprintf (dump_file
, "Unified; Function body was removed.\n");
1374 /* Semantic item initialization function. */
1377 sem_function::init (void)
1380 get_node ()->get_untransformed_body ();
1382 tree fndecl
= node
->decl
;
1383 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1386 gcc_assert (SSANAMES (func
));
1388 ssa_names_size
= SSANAMES (func
)->length ();
1392 region_tree
= func
->eh
->region_tree
;
1394 /* iterating all function arguments. */
1395 arg_count
= count_formal_params (fndecl
);
1397 edge_count
= n_edges_for_fn (func
);
1398 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1399 if (!cnode
->thunk
.thunk_p
)
1401 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1403 inchash::hash hstate
;
1406 FOR_EACH_BB_FN (bb
, func
)
1408 unsigned nondbg_stmt_count
= 0;
1411 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1413 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1416 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1419 gimple
*stmt
= gsi_stmt (gsi
);
1421 if (gimple_code (stmt
) != GIMPLE_DEBUG
1422 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1424 hash_stmt (stmt
, hstate
);
1425 nondbg_stmt_count
++;
1429 gcode_hash
= hstate
.end ();
1430 bb_sizes
.safe_push (nondbg_stmt_count
);
1432 /* Inserting basic block to hash table. */
1433 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1434 EDGE_COUNT (bb
->preds
)
1435 + EDGE_COUNT (bb
->succs
));
1437 bb_sorted
.safe_push (semantic_bb
);
1443 inchash::hash hstate
;
1444 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1445 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1446 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1447 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1448 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1449 gcode_hash
= hstate
.end ();
1453 /* Accumulate to HSTATE a hash of expression EXP.
1454 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1455 and DECL equality classes. */
1458 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1460 if (exp
== NULL_TREE
)
1462 hstate
.merge_hash (0);
1466 /* Handled component can be matched in a cureful way proving equivalence
1467 even if they syntactically differ. Just skip them. */
1469 while (handled_component_p (exp
))
1470 exp
= TREE_OPERAND (exp
, 0);
1472 enum tree_code code
= TREE_CODE (exp
);
1473 hstate
.add_int (code
);
1477 /* Use inchash::add_expr for everything that is LTO stable. */
1485 inchash::add_expr (exp
, hstate
);
1489 unsigned HOST_WIDE_INT idx
;
1492 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1494 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1496 add_expr (value
, hstate
);
1501 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1507 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1510 case POINTER_PLUS_EXPR
:
1513 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1514 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1518 inchash::hash one
, two
;
1519 add_expr (TREE_OPERAND (exp
, 0), one
);
1520 add_expr (TREE_OPERAND (exp
, 1), two
);
1521 hstate
.add_commutative (one
, two
);
1525 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1526 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1532 /* Accumulate to HSTATE a hash of type t.
1533 TYpes that may end up being compatible after LTO type merging needs to have
1537 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1539 if (type
== NULL_TREE
)
1541 hstate
.merge_hash (0);
1545 type
= TYPE_MAIN_VARIANT (type
);
1547 hstate
.add_int (TYPE_MODE (type
));
1549 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1551 hstate
.add_int (COMPLEX_TYPE
);
1552 sem_item::add_type (TREE_TYPE (type
), hstate
);
1554 else if (INTEGRAL_TYPE_P (type
))
1556 hstate
.add_int (INTEGER_TYPE
);
1557 hstate
.add_flag (TYPE_UNSIGNED (type
));
1558 hstate
.add_int (TYPE_PRECISION (type
));
1560 else if (VECTOR_TYPE_P (type
))
1562 hstate
.add_int (VECTOR_TYPE
);
1563 hstate
.add_int (TYPE_PRECISION (type
));
1564 sem_item::add_type (TREE_TYPE (type
), hstate
);
1566 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1568 hstate
.add_int (ARRAY_TYPE
);
1569 /* Do not hash size, so complete and incomplete types can match. */
1570 sem_item::add_type (TREE_TYPE (type
), hstate
);
1572 else if (RECORD_OR_UNION_TYPE_P (type
))
1574 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1575 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1579 inchash::hash hstate2
;
1584 hstate2
.add_int (RECORD_TYPE
);
1585 gcc_assert (COMPLETE_TYPE_P (type
));
1587 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1588 if (TREE_CODE (f
) == FIELD_DECL
)
1590 add_type (TREE_TYPE (f
), hstate2
);
1594 hstate2
.add_int (nf
);
1595 hash
= hstate2
.end ();
1596 hstate
.add_wide_int (hash
);
1597 optimizer
->m_type_hash_cache
.put (type
, hash
);
1600 hstate
.add_wide_int (*val
);
1604 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1607 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1609 enum gimple_code code
= gimple_code (stmt
);
1611 hstate
.add_int (code
);
1616 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1619 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1620 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1621 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1623 inchash::hash one
, two
;
1625 add_expr (gimple_assign_rhs1 (stmt
), one
);
1626 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1627 add_expr (gimple_assign_rhs2 (stmt
), two
);
1628 hstate
.add_commutative (one
, two
);
1629 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1631 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1632 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1634 add_expr (gimple_assign_lhs (stmt
), hstate
);
1635 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1644 /* All these statements are equivalent if their operands are. */
1645 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1647 add_expr (gimple_op (stmt
, i
), hstate
);
1648 if (gimple_op (stmt
, i
))
1649 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1657 /* Return true if polymorphic comparison must be processed. */
1660 sem_function::compare_polymorphic_p (void)
1662 struct cgraph_edge
*e
;
1664 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1666 if (get_node ()->indirect_calls
!= NULL
)
1668 /* TODO: We can do simple propagation determining what calls may lead to
1669 a polymorphic call. */
1670 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1671 if (e
->callee
->definition
1672 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1677 /* For a given call graph NODE, the function constructs new
1678 semantic function item. */
1681 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1683 tree fndecl
= node
->decl
;
1684 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1686 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1689 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1692 if (lookup_attribute_by_prefix ("oacc ",
1693 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1697 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1698 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1701 sem_function
*f
= new sem_function (node
, stack
);
1708 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1709 return true if phi nodes are semantically equivalent in these blocks . */
1712 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1714 gphi_iterator si1
, si2
;
1716 unsigned size1
, size2
, i
;
1720 gcc_assert (bb1
!= NULL
);
1721 gcc_assert (bb2
!= NULL
);
1723 si2
= gsi_start_phis (bb2
);
1724 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1727 gsi_next_nonvirtual_phi (&si1
);
1728 gsi_next_nonvirtual_phi (&si2
);
1730 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1733 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1734 return return_false();
1739 tree phi_result1
= gimple_phi_result (phi1
);
1740 tree phi_result2
= gimple_phi_result (phi2
);
1742 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1743 return return_false_with_msg ("PHI results are different");
1745 size1
= gimple_phi_num_args (phi1
);
1746 size2
= gimple_phi_num_args (phi2
);
1749 return return_false ();
1751 for (i
= 0; i
< size1
; ++i
)
1753 t1
= gimple_phi_arg (phi1
, i
)->def
;
1754 t2
= gimple_phi_arg (phi2
, i
)->def
;
1756 if (!m_checker
->compare_operand (t1
, t2
))
1757 return return_false ();
1759 e1
= gimple_phi_arg_edge (phi1
, i
);
1760 e2
= gimple_phi_arg_edge (phi2
, i
);
1762 if (!m_checker
->compare_edge (e1
, e2
))
1763 return return_false ();
1772 /* Returns true if tree T can be compared as a handled component. */
1775 sem_function::icf_handled_component_p (tree t
)
1777 tree_code tc
= TREE_CODE (t
);
1779 return (handled_component_p (t
)
1780 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1783 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1784 corresponds to TARGET. */
1787 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1792 if (bb_dict
->length () <= (unsigned)source
)
1793 bb_dict
->safe_grow_cleared (source
+ 1);
1795 if ((*bb_dict
)[source
] == 0)
1797 (*bb_dict
)[source
] = target
;
1801 return (*bb_dict
)[source
] == target
;
1804 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1808 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1809 : sem_item (VAR
, node
, stack
)
1811 gcc_checking_assert (node
);
1812 gcc_checking_assert (get_node ());
1815 /* Fast equality function based on knowledge known in WPA. */
1818 sem_variable::equals_wpa (sem_item
*item
,
1819 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1821 gcc_assert (item
->type
== VAR
);
1823 if (node
->num_references () != item
->node
->num_references ())
1824 return return_false_with_msg ("different number of references");
1826 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1827 return return_false_with_msg ("TLS model");
1829 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1830 alignment out of all aliases. */
1832 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1833 return return_false_with_msg ("Virtual flag mismatch");
1835 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1836 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1837 || !operand_equal_p (DECL_SIZE (decl
),
1838 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1839 return return_false_with_msg ("size mismatch");
1841 /* Do not attempt to mix data from different user sections;
1842 we do not know what user intends with those. */
1843 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1844 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1845 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1846 return return_false_with_msg ("user section mismatch");
1848 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1849 return return_false_with_msg ("text section");
1851 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1852 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1854 item
->node
->iterate_reference (i
, ref2
);
1856 if (ref
->use
!= ref2
->use
)
1857 return return_false_with_msg ("reference use mismatch");
1859 if (!compare_symbol_references (ignored_nodes
,
1860 ref
->referred
, ref2
->referred
,
1861 ref
->address_matters_p ()))
1868 /* Returns true if the item equals to ITEM given as argument. */
1871 sem_variable::equals (sem_item
*item
,
1872 hash_map
<symtab_node
*, sem_item
*> &)
1874 gcc_assert (item
->type
== VAR
);
1877 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1878 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1879 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1880 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1882 /* As seen in PR ipa/65303 we have to compare variables types. */
1883 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1884 TREE_TYPE (item
->decl
)))
1885 return return_false_with_msg ("variables types are different");
1887 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1888 DECL_INITIAL (item
->node
->decl
));
1889 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1891 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1892 xstrdup_for_dump (node
->name()),
1893 xstrdup_for_dump (item
->node
->name ()),
1894 node
->order
, item
->node
->order
,
1895 xstrdup_for_dump (node
->asm_name ()),
1896 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1901 /* Compares trees T1 and T2 for semantic equality. */
1904 sem_variable::equals (tree t1
, tree t2
)
1907 return return_with_debug (t1
== t2
);
1910 tree_code tc1
= TREE_CODE (t1
);
1911 tree_code tc2
= TREE_CODE (t2
);
1914 return return_false_with_msg ("TREE_CODE mismatch");
1920 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1921 unsigned HOST_WIDE_INT idx
;
1923 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1924 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1925 return return_false_with_msg ("constructor type mismatch");
1927 if (typecode
== ARRAY_TYPE
)
1929 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1930 /* For arrays, check that the sizes all match. */
1931 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1933 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1934 return return_false_with_msg ("constructor array size mismatch");
1936 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1938 return return_false_with_msg ("constructor type incompatible");
1940 v1
= CONSTRUCTOR_ELTS (t1
);
1941 v2
= CONSTRUCTOR_ELTS (t2
);
1942 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1943 return return_false_with_msg ("constructor number of elts mismatch");
1945 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1947 constructor_elt
*c1
= &(*v1
)[idx
];
1948 constructor_elt
*c2
= &(*v2
)[idx
];
1950 /* Check that each value is the same... */
1951 if (!sem_variable::equals (c1
->value
, c2
->value
))
1953 /* ... and that they apply to the same fields! */
1954 if (!sem_variable::equals (c1
->index
, c2
->index
))
1961 tree x1
= TREE_OPERAND (t1
, 0);
1962 tree x2
= TREE_OPERAND (t2
, 0);
1963 tree y1
= TREE_OPERAND (t1
, 1);
1964 tree y2
= TREE_OPERAND (t2
, 1);
1966 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1967 return return_false ();
1969 /* Type of the offset on MEM_REF does not matter. */
1970 return return_with_debug (sem_variable::equals (x1
, x2
)
1971 && wi::to_offset (y1
)
1972 == wi::to_offset (y2
));
1977 tree op1
= TREE_OPERAND (t1
, 0);
1978 tree op2
= TREE_OPERAND (t2
, 0);
1979 return sem_variable::equals (op1
, op2
);
1981 /* References to other vars/decls are compared using ipa-ref. */
1984 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1986 return return_false_with_msg ("Declaration mismatch");
1988 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1989 need to process its VAR/FUNCTION references without relying on ipa-ref
1993 return return_false_with_msg ("Declaration mismatch");
1995 /* Integer constants are the same only if the same width of type. */
1996 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1997 return return_false_with_msg ("INTEGER_CST precision mismatch");
1998 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1999 return return_false_with_msg ("INTEGER_CST mode mismatch");
2000 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2002 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2003 return return_false_with_msg ("STRING_CST mode mismatch");
2004 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2005 return return_false_with_msg ("STRING_CST length mismatch");
2006 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2007 TREE_STRING_LENGTH (t1
)))
2008 return return_false_with_msg ("STRING_CST mismatch");
2011 /* Fixed constants are the same only if the same width of type. */
2012 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2013 return return_false_with_msg ("FIXED_CST precision mismatch");
2015 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2016 TREE_FIXED_CST (t2
)));
2018 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2019 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2021 /* Real constants are the same only if the same width of type. */
2022 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2023 return return_false_with_msg ("REAL_CST precision mismatch");
2024 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2025 &TREE_REAL_CST (t2
)));
2030 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2031 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2033 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2034 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2035 VECTOR_CST_ELT (t2
, i
)))
2041 case ARRAY_RANGE_REF
:
2043 tree x1
= TREE_OPERAND (t1
, 0);
2044 tree x2
= TREE_OPERAND (t2
, 0);
2045 tree y1
= TREE_OPERAND (t1
, 1);
2046 tree y2
= TREE_OPERAND (t2
, 1);
2048 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2050 if (!sem_variable::equals (array_ref_low_bound (t1
),
2051 array_ref_low_bound (t2
)))
2053 if (!sem_variable::equals (array_ref_element_size (t1
),
2054 array_ref_element_size (t2
)))
2060 case POINTER_PLUS_EXPR
:
2065 tree x1
= TREE_OPERAND (t1
, 0);
2066 tree x2
= TREE_OPERAND (t2
, 0);
2067 tree y1
= TREE_OPERAND (t1
, 1);
2068 tree y2
= TREE_OPERAND (t2
, 1);
2070 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2074 case VIEW_CONVERT_EXPR
:
2075 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2076 return return_false ();
2077 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2079 return return_false_with_msg ("ERROR_MARK");
2081 return return_false_with_msg ("Unknown TREE code reached");
2085 /* Parser function that visits a varpool NODE. */
2088 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2090 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2094 sem_variable
*v
= new sem_variable (node
, stack
);
2101 /* References independent hash function. */
2104 sem_variable::get_hash (void)
2109 /* All WPA streamed in symbols should have their hashes computed at compile
2110 time. At this point, the constructor may not be in memory at all.
2111 DECL_INITIAL (decl) would be error_mark_node in that case. */
2112 gcc_assert (!node
->lto_file_data
);
2113 tree ctor
= DECL_INITIAL (decl
);
2114 inchash::hash hstate
;
2116 hstate
.add_int (456346417);
2117 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2118 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2119 add_expr (ctor
, hstate
);
2120 set_hash (hstate
.end ());
2125 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2128 set_alias_uids (symtab_node
*n
, int uid
)
2131 FOR_EACH_ALIAS (n
, ref
)
2134 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2135 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2137 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2138 set_alias_uids (ref
->referring
, uid
);
2142 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2146 sem_variable::merge (sem_item
*alias_item
)
2148 gcc_assert (alias_item
->type
== VAR
);
2150 if (!sem_item::target_supports_symbol_aliases_p ())
2153 fprintf (dump_file
, "Not unifying; "
2154 "Symbol aliases are not supported by target\n\n");
2158 if (DECL_EXTERNAL (alias_item
->decl
))
2161 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2165 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2167 varpool_node
*original
= get_node ();
2168 varpool_node
*alias
= alias_var
->get_node ();
2169 bool original_discardable
= false;
2171 bool alias_address_matters
= alias
->address_matters_p ();
2173 /* See if original is in a section that can be discarded if the main
2175 Also consider case where we have resolution info and we know that
2176 original's definition is not going to be used. In this case we can not
2177 create alias to original. */
2178 if (original
->can_be_discarded_p ()
2179 || (node
->resolution
!= LDPR_UNKNOWN
2180 && !decl_binds_to_current_def_p (node
->decl
)))
2181 original_discardable
= true;
2183 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2185 /* Constant pool machinery is not quite ready for aliases.
2186 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2187 For LTO merging does not happen that is an important missing feature.
2188 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2189 flag is dropped and non-local symbol name is assigned. */
2190 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2191 || DECL_IN_CONSTANT_POOL (original
->decl
))
2195 "Not unifying; constant pool variables.\n\n");
2199 /* Do not attempt to mix functions from different user sections;
2200 we do not know what user intends with those. */
2201 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2202 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2203 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2208 "original and alias are in different sections.\n\n");
2212 /* We can not merge if address comparsion metters. */
2213 if (alias_address_matters
&& flag_merge_constants
< 2)
2217 "Not unifying; address of original may be compared.\n\n");
2221 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2224 fprintf (dump_file
, "Not unifying; "
2225 "original and alias have incompatible alignments\n\n");
2230 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2233 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2234 "across comdat group boundary\n\n");
2239 if (original_discardable
)
2242 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2243 "target is discardable\n\n");
2249 gcc_assert (!original
->alias
);
2250 gcc_assert (!alias
->alias
);
2252 alias
->analyzed
= false;
2254 DECL_INITIAL (alias
->decl
) = NULL
;
2255 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2257 alias
->need_bounds_init
= false;
2258 alias
->remove_all_references ();
2259 if (TREE_ADDRESSABLE (alias
->decl
))
2260 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2262 varpool_node::create_alias (alias_var
->decl
, decl
);
2263 alias
->resolve_alias (original
);
2266 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2268 set_alias_uids (original
, DECL_UID (original
->decl
));
2273 /* Dump symbol to FILE. */
2276 sem_variable::dump_to_file (FILE *file
)
2280 print_node (file
, "", decl
, 0);
2281 fprintf (file
, "\n\n");
2284 unsigned int sem_item_optimizer::class_id
= 0;
2286 sem_item_optimizer::sem_item_optimizer ()
2287 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2288 m_varpool_node_hooks (NULL
)
2291 m_classes_vec
.create (0);
2292 bitmap_obstack_initialize (&m_bmstack
);
2295 sem_item_optimizer::~sem_item_optimizer ()
2297 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2301 congruence_class_group
*it
;
2302 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
2304 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
2305 delete it
->classes
[i
];
2307 it
->classes
.release ();
2312 m_classes_vec
.release ();
2314 bitmap_obstack_release (&m_bmstack
);
2317 /* Write IPA ICF summary for symbols. */
2320 sem_item_optimizer::write_summary (void)
2322 unsigned int count
= 0;
2324 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2325 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2328 /* Calculate number of symbols to be serialized. */
2329 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2331 lsei_next_in_partition (&lsei
))
2333 symtab_node
*node
= lsei_node (lsei
);
2335 if (m_symtab_node_map
.get (node
))
2339 streamer_write_uhwi (ob
, count
);
2341 /* Process all of the symbols. */
2342 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2344 lsei_next_in_partition (&lsei
))
2346 symtab_node
*node
= lsei_node (lsei
);
2348 sem_item
**item
= m_symtab_node_map
.get (node
);
2352 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2353 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2355 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2359 streamer_write_char_stream (ob
->main_stream
, 0);
2360 produce_asm (ob
, NULL
);
2361 destroy_output_block (ob
);
2364 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2365 contains LEN bytes. */
2368 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2369 const char *data
, size_t len
)
2371 const lto_function_header
*header
2372 = (const lto_function_header
*) data
;
2373 const int cfg_offset
= sizeof (lto_function_header
);
2374 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2375 const int string_offset
= main_offset
+ header
->main_size
;
2380 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2381 header
->main_size
, file_data
->mode_table
);
2384 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2385 header
->string_size
, vNULL
);
2387 count
= streamer_read_uhwi (&ib_main
);
2389 for (i
= 0; i
< count
; i
++)
2393 lto_symtab_encoder_t encoder
;
2395 index
= streamer_read_uhwi (&ib_main
);
2396 encoder
= file_data
->symtab_node_encoder
;
2397 node
= lto_symtab_encoder_deref (encoder
, index
);
2399 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2401 gcc_assert (node
->definition
);
2404 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2405 node
->asm_name (), (void *) node
->decl
, node
->order
);
2407 if (is_a
<cgraph_node
*> (node
))
2409 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2411 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2412 fn
->set_hash (hash
);
2413 m_items
.safe_push (fn
);
2417 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2419 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2420 var
->set_hash (hash
);
2421 m_items
.safe_push (var
);
2425 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2427 lto_data_in_delete (data_in
);
2430 /* Read IPA ICF summary for symbols. */
2433 sem_item_optimizer::read_summary (void)
2435 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2436 lto_file_decl_data
*file_data
;
2439 while ((file_data
= file_data_vec
[j
++]))
2442 const char *data
= lto_get_section_data (file_data
,
2443 LTO_section_ipa_icf
, NULL
, &len
);
2446 read_section (file_data
, data
, len
);
2450 /* Register callgraph and varpool hooks. */
2453 sem_item_optimizer::register_hooks (void)
2455 if (!m_cgraph_node_hooks
)
2456 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2457 (&sem_item_optimizer::cgraph_removal_hook
, this);
2459 if (!m_varpool_node_hooks
)
2460 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2461 (&sem_item_optimizer::varpool_removal_hook
, this);
2464 /* Unregister callgraph and varpool hooks. */
2467 sem_item_optimizer::unregister_hooks (void)
2469 if (m_cgraph_node_hooks
)
2470 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2472 if (m_varpool_node_hooks
)
2473 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2476 /* Adds a CLS to hashtable associated by hash value. */
2479 sem_item_optimizer::add_class (congruence_class
*cls
)
2481 gcc_assert (cls
->members
.length ());
2483 congruence_class_group
*group
2484 = get_group_by_hash (cls
->members
[0]->get_hash (),
2485 cls
->members
[0]->type
);
2486 group
->classes
.safe_push (cls
);
2489 /* Gets a congruence class group based on given HASH value and TYPE. */
2491 congruence_class_group
*
2492 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2494 congruence_class_group
*item
= XNEW (congruence_class_group
);
2498 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2504 item
->classes
.create (1);
2505 m_classes_vec
.safe_push (item
);
2512 /* Callgraph removal hook called for a NODE with a custom DATA. */
2515 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2517 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2518 optimizer
->remove_symtab_node (node
);
2521 /* Varpool removal hook called for a NODE with a custom DATA. */
2524 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2526 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2527 optimizer
->remove_symtab_node (node
);
2530 /* Remove symtab NODE triggered by symtab removal hooks. */
2533 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2535 gcc_assert (!m_classes
.elements ());
2537 m_removed_items_set
.add (node
);
2541 sem_item_optimizer::remove_item (sem_item
*item
)
2543 if (m_symtab_node_map
.get (item
->node
))
2544 m_symtab_node_map
.remove (item
->node
);
2548 /* Removes all callgraph and varpool nodes that are marked by symtab
2552 sem_item_optimizer::filter_removed_items (void)
2554 auto_vec
<sem_item
*> filtered
;
2556 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2558 sem_item
*item
= m_items
[i
];
2560 if (m_removed_items_set
.contains (item
->node
))
2566 if (item
->type
== FUNC
)
2568 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2570 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2573 filtered
.safe_push (item
);
2577 if (!flag_ipa_icf_variables
)
2581 /* Filter out non-readonly variables. */
2582 tree decl
= item
->decl
;
2583 if (TREE_READONLY (decl
))
2584 filtered
.safe_push (item
);
2591 /* Clean-up of released semantic items. */
2594 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2595 m_items
.safe_push (filtered
[i
]);
2598 /* Optimizer entry point which returns true in case it processes
2599 a merge operation. True is returned if there's a merge operation
2603 sem_item_optimizer::execute (void)
2605 filter_removed_items ();
2606 unregister_hooks ();
2609 update_hash_by_addr_refs ();
2610 build_hash_based_classes ();
2613 fprintf (dump_file
, "Dump after hash based groups\n");
2614 dump_cong_classes ();
2616 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2617 m_items
[i
]->init_wpa ();
2619 subdivide_classes_by_equality (true);
2622 fprintf (dump_file
, "Dump after WPA based types groups\n");
2624 dump_cong_classes ();
2626 process_cong_reduction ();
2627 checking_verify_classes ();
2630 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2632 dump_cong_classes ();
2634 parse_nonsingleton_classes ();
2635 subdivide_classes_by_equality ();
2638 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2640 dump_cong_classes ();
2642 unsigned int prev_class_count
= m_classes_count
;
2644 process_cong_reduction ();
2645 dump_cong_classes ();
2646 checking_verify_classes ();
2647 bool merged_p
= merge_classes (prev_class_count
);
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 symtab_node::dump_table (dump_file
);
2655 /* Function responsible for visiting all potential functions and
2656 read-only variables that can be merged. */
2659 sem_item_optimizer::parse_funcs_and_vars (void)
2663 if (flag_ipa_icf_functions
)
2664 FOR_EACH_DEFINED_FUNCTION (cnode
)
2666 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2669 m_items
.safe_push (f
);
2670 m_symtab_node_map
.put (cnode
, f
);
2673 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2675 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2676 f
->dump_to_file (dump_file
);
2679 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2682 varpool_node
*vnode
;
2684 if (flag_ipa_icf_variables
)
2685 FOR_EACH_DEFINED_VARIABLE (vnode
)
2687 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2691 m_items
.safe_push (v
);
2692 m_symtab_node_map
.put (vnode
, v
);
2697 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2700 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2702 item
->index_in_class
= cls
->members
.length ();
2703 cls
->members
.safe_push (item
);
2707 /* For each semantic item, append hash values of references. */
2710 sem_item_optimizer::update_hash_by_addr_refs ()
2712 /* First, append to hash sensitive references and class type if it need to
2713 be matched for ODR. */
2714 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2716 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2717 if (m_items
[i
]->type
== FUNC
)
2719 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2720 && contains_polymorphic_type_p
2721 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2722 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2723 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2724 && static_cast<sem_function
*> (m_items
[i
])
2725 ->compare_polymorphic_p ())))
2728 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2729 inchash::hash
hstate (m_items
[i
]->get_hash ());
2731 if (TYPE_NAME (class_type
)
2732 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2734 (IDENTIFIER_HASH_VALUE
2735 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2737 m_items
[i
]->set_hash (hstate
.end ());
2742 /* Once all symbols have enhanced hash value, we can append
2743 hash values of symbols that are seen by IPA ICF and are
2744 references by a semantic item. Newly computed values
2745 are saved to global_hash member variable. */
2746 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2747 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2749 /* Global hash value replace current hash values. */
2750 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2751 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2754 /* Congruence classes are built by hash value. */
2757 sem_item_optimizer::build_hash_based_classes (void)
2759 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2761 sem_item
*item
= m_items
[i
];
2763 congruence_class_group
*group
2764 = get_group_by_hash (item
->get_hash (), item
->type
);
2766 if (!group
->classes
.length ())
2769 group
->classes
.safe_push (new congruence_class (class_id
++));
2772 add_item_to_class (group
->classes
[0], item
);
2776 /* Build references according to call graph. */
2779 sem_item_optimizer::build_graph (void)
2781 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2783 sem_item
*item
= m_items
[i
];
2784 m_symtab_node_map
.put (item
->node
, item
);
2786 /* Initialize hash values if we are not in LTO mode. */
2791 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2793 sem_item
*item
= m_items
[i
];
2795 if (item
->type
== FUNC
)
2797 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2799 cgraph_edge
*e
= cnode
->callees
;
2802 sem_item
**slot
= m_symtab_node_map
.get
2803 (e
->callee
->ultimate_alias_target ());
2805 item
->add_reference (*slot
);
2811 ipa_ref
*ref
= NULL
;
2812 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2814 sem_item
**slot
= m_symtab_node_map
.get
2815 (ref
->referred
->ultimate_alias_target ());
2817 item
->add_reference (*slot
);
2822 /* Semantic items in classes having more than one element and initialized.
2823 In case of WPA, we load function body. */
2826 sem_item_optimizer::parse_nonsingleton_classes (void)
2828 unsigned int init_called_count
= 0;
2830 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2831 if (m_items
[i
]->cls
->members
.length () > 1)
2833 m_items
[i
]->init ();
2834 init_called_count
++;
2838 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n",
2840 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length ()
2844 /* Equality function for semantic items is used to subdivide existing
2845 classes. If IN_WPA, fast equality function is invoked. */
2848 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2851 congruence_class_group
*it
;
2852 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
2854 unsigned int class_count
= it
->classes
.length ();
2856 for (unsigned i
= 0; i
< class_count
; i
++)
2858 congruence_class
*c
= it
->classes
[i
];
2860 if (c
->members
.length() > 1)
2862 auto_vec
<sem_item
*> new_vector
;
2864 sem_item
*first
= c
->members
[0];
2865 new_vector
.safe_push (first
);
2867 unsigned class_split_first
= it
->classes
.length ();
2869 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2871 sem_item
*item
= c
->members
[j
];
2874 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2875 : first
->equals (item
, m_symtab_node_map
);
2878 new_vector
.safe_push (item
);
2881 bool integrated
= false;
2883 for (unsigned k
= class_split_first
;
2884 k
< it
->classes
.length (); k
++)
2886 sem_item
*x
= it
->classes
[k
]->members
[0];
2888 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2889 : x
->equals (item
, m_symtab_node_map
);
2894 add_item_to_class (it
->classes
[k
], item
);
2903 = new congruence_class (class_id
++);
2905 add_item_to_class (c
, item
);
2907 it
->classes
.safe_push (c
);
2912 // We replace newly created new_vector for the class we've just
2914 c
->members
.release ();
2915 c
->members
.create (new_vector
.length ());
2917 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2918 add_item_to_class (c
, new_vector
[j
]);
2923 checking_verify_classes ();
2926 /* Subdivide classes by address references that members of the class
2927 reference. Example can be a pair of functions that have an address
2928 taken from a function. If these addresses are different the class
2932 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2934 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2936 unsigned newly_created_classes
= 0;
2939 congruence_class_group
*it
;
2940 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
2942 unsigned int class_count
= it
->classes
.length ();
2943 auto_vec
<congruence_class
*> new_classes
;
2945 for (unsigned i
= 0; i
< class_count
; i
++)
2947 congruence_class
*c
= it
->classes
[i
];
2949 if (c
->members
.length() > 1)
2951 subdivide_hash_map split_map
;
2953 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2955 sem_item
*source_node
= c
->members
[j
];
2957 symbol_compare_collection
*collection
2958 = new symbol_compare_collection (source_node
->node
);
2961 vec
<sem_item
*> *slot
2962 = &split_map
.get_or_insert (collection
, &existed
);
2963 gcc_checking_assert (slot
);
2965 slot
->safe_push (source_node
);
2971 /* If the map contains more than one key, we have to split
2972 the map appropriately. */
2973 if (split_map
.elements () != 1)
2975 bool first_class
= true;
2977 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2978 it2
!= split_map
.end (); ++it2
)
2980 congruence_class
*new_cls
;
2981 new_cls
= new congruence_class (class_id
++);
2983 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2984 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2986 worklist_push (new_cls
);
2987 newly_created_classes
++;
2991 it
->classes
[i
] = new_cls
;
2992 first_class
= false;
2996 new_classes
.safe_push (new_cls
);
3002 /* Release memory. */
3003 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
3004 it2
!= split_map
.end (); ++it2
)
3006 delete (*it2
).first
;
3007 (*it2
).second
.release ();
3012 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
3013 it
->classes
.safe_push (new_classes
[i
]);
3016 return newly_created_classes
;
3019 /* Verify congruence classes, if checking is enabled. */
3022 sem_item_optimizer::checking_verify_classes (void)
3028 /* Verify congruence classes. */
3031 sem_item_optimizer::verify_classes (void)
3034 congruence_class_group
*it
;
3035 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3037 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
3039 congruence_class
*cls
= it
->classes
[i
];
3042 gcc_assert (cls
->members
.length () > 0);
3044 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3046 sem_item
*item
= cls
->members
[j
];
3049 gcc_assert (item
->cls
== cls
);
3051 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3053 sem_usage_pair
*usage
= item
->usages
[k
];
3054 gcc_assert (usage
->item
->index_in_class
3055 < usage
->item
->cls
->members
.length ());
3062 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3063 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3064 but unused argument. */
3067 sem_item_optimizer::release_split_map (congruence_class
* const &,
3068 bitmap
const &b
, traverse_split_pair
*)
3077 /* Process split operation for a class given as pointer CLS_PTR,
3078 where bitmap B splits congruence class members. DATA is used
3079 as argument of split pair. */
3082 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3084 traverse_split_pair
*pair
)
3086 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3087 const congruence_class
*splitter_cls
= pair
->cls
;
3089 /* If counted bits are greater than zero and less than the number of members
3090 a group will be splitted. */
3091 unsigned popcount
= bitmap_count_bits (b
);
3093 if (popcount
> 0 && popcount
< cls
->members
.length ())
3095 auto_vec
<congruence_class
*, 2> newclasses
;
3096 newclasses
.quick_push (new congruence_class (class_id
++));
3097 newclasses
.quick_push (new congruence_class (class_id
++));
3099 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3101 int target
= bitmap_bit_p (b
, i
);
3102 congruence_class
*tc
= newclasses
[target
];
3104 add_item_to_class (tc
, cls
->members
[i
]);
3109 for (unsigned int i
= 0; i
< 2; i
++)
3110 gcc_assert (newclasses
[i
]->members
.length ());
3113 if (splitter_cls
== cls
)
3114 optimizer
->splitter_class_removed
= true;
3116 /* Remove old class from worklist if presented. */
3117 bool in_worklist
= cls
->in_worklist
;
3120 cls
->in_worklist
= false;
3122 congruence_class_group g
;
3123 g
.hash
= cls
->members
[0]->get_hash ();
3124 g
.type
= cls
->members
[0]->type
;
3126 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
3128 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3129 if (slot
->classes
[i
] == cls
)
3131 slot
->classes
.ordered_remove (i
);
3135 /* New class will be inserted and integrated to work list. */
3136 for (unsigned int i
= 0; i
< 2; i
++)
3137 optimizer
->add_class (newclasses
[i
]);
3139 /* Two classes replace one, so that increment just by one. */
3140 optimizer
->m_classes_count
++;
3142 /* If OLD class was presented in the worklist, we remove the class
3143 and replace it will both newly created classes. */
3145 for (unsigned int i
= 0; i
< 2; i
++)
3146 optimizer
->worklist_push (newclasses
[i
]);
3147 else /* Just smaller class is inserted. */
3149 unsigned int smaller_index
3150 = (newclasses
[0]->members
.length ()
3151 < newclasses
[1]->members
.length ()
3153 optimizer
->worklist_push (newclasses
[smaller_index
]);
3156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3158 fprintf (dump_file
, " congruence class splitted:\n");
3159 cls
->dump (dump_file
, 4);
3161 fprintf (dump_file
, " newly created groups:\n");
3162 for (unsigned int i
= 0; i
< 2; i
++)
3163 newclasses
[i
]->dump (dump_file
, 4);
3166 /* Release class if not presented in work list. */
3175 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3176 Bitmap stack BMSTACK is used for bitmap allocation. */
3179 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3182 hash_map
<congruence_class
*, bitmap
> split_map
;
3184 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3186 sem_item
*item
= cls
->members
[i
];
3188 /* Iterate all usages that have INDEX as usage of the item. */
3189 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3191 sem_usage_pair
*usage
= item
->usages
[j
];
3193 if (usage
->index
!= index
)
3196 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3201 b
= BITMAP_ALLOC (&m_bmstack
);
3202 split_map
.put (usage
->item
->cls
, b
);
3207 gcc_checking_assert (usage
->item
->cls
);
3208 gcc_checking_assert (usage
->item
->index_in_class
3209 < usage
->item
->cls
->members
.length ());
3211 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3215 traverse_split_pair pair
;
3216 pair
.optimizer
= this;
3219 splitter_class_removed
= false;
3220 split_map
.traverse
<traverse_split_pair
*,
3221 sem_item_optimizer::traverse_congruence_split
> (&pair
);
3223 /* Bitmap clean-up. */
3224 split_map
.traverse
<traverse_split_pair
*,
3225 sem_item_optimizer::release_split_map
> (NULL
);
3228 /* Every usage of a congruence class CLS is a candidate that can split the
3229 collection of classes. Bitmap stack BMSTACK is used for bitmap
3233 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3238 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3240 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3241 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3243 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3246 fprintf (dump_file
, " processing congruence step for class: %u, "
3247 "index: %u\n", cls
->id
, i
);
3249 do_congruence_step_for_index (cls
, i
);
3251 if (splitter_class_removed
)
3255 BITMAP_FREE (usage
);
3258 /* Adds a newly created congruence class CLS to worklist. */
3261 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3263 /* Return if the class CLS is already presented in work list. */
3264 if (cls
->in_worklist
)
3267 cls
->in_worklist
= true;
3268 worklist
.push_back (cls
);
3271 /* Pops a class from worklist. */
3274 sem_item_optimizer::worklist_pop (void)
3276 congruence_class
*cls
;
3278 while (!worklist
.empty ())
3280 cls
= worklist
.front ();
3281 worklist
.pop_front ();
3282 if (cls
->in_worklist
)
3284 cls
->in_worklist
= false;
3290 /* Work list item was already intended to be removed.
3291 The only reason for doing it is to split a class.
3292 Thus, the class CLS is deleted. */
3300 /* Iterative congruence reduction function. */
3303 sem_item_optimizer::process_cong_reduction (void)
3306 congruence_class_group
*it
;
3307 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3308 for (unsigned i
= 0; i
< it
->classes
.length (); i
++)
3309 if (it
->classes
[i
]->is_class_used ())
3310 worklist_push (it
->classes
[i
]);
3313 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3314 (unsigned long) worklist
.size ());
3316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3317 fprintf (dump_file
, "Congruence class reduction\n");
3319 congruence_class
*cls
;
3321 /* Process complete congruence reduction. */
3322 while ((cls
= worklist_pop ()) != NULL
)
3323 do_congruence_step (cls
);
3325 /* Subdivide newly created classes according to references. */
3326 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3329 fprintf (dump_file
, "Address reference subdivision created: %u "
3330 "new classes.\n", new_classes
);
3333 /* Debug function prints all informations about congruence classes. */
3336 sem_item_optimizer::dump_cong_classes (void)
3342 "Congruence classes: %u (unique hash values: %lu), with total: "
3343 "%u items\n", m_classes_count
,
3344 (unsigned long) m_classes
.elements (), m_items
.length ());
3346 /* Histogram calculation. */
3347 unsigned int max_index
= 0;
3348 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3351 congruence_class_group
*it
;
3352 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3353 for (unsigned i
= 0; i
< it
->classes
.length (); i
++)
3355 unsigned int c
= it
->classes
[i
]->members
.length ();
3363 "Class size histogram [num of members]: number of classe number "
3366 for (unsigned int i
= 0; i
<= max_index
; i
++)
3368 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3370 fprintf (dump_file
, "\n\n");
3373 if (dump_flags
& TDF_DETAILS
)
3374 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3376 fprintf (dump_file
, " group: with %u classes:\n",
3377 it
->classes
.length ());
3379 for (unsigned i
= 0; i
< it
->classes
.length (); i
++)
3381 it
->classes
[i
]->dump (dump_file
, 4);
3383 if (i
< it
->classes
.length () - 1)
3384 fprintf (dump_file
, " ");
3391 /* After reduction is done, we can declare all items in a group
3392 to be equal. PREV_CLASS_COUNT is start number of classes
3393 before reduction. True is returned if there's a merge operation
3397 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3399 unsigned int item_count
= m_items
.length ();
3400 unsigned int class_count
= m_classes_count
;
3401 unsigned int equal_items
= item_count
- class_count
;
3403 unsigned int non_singular_classes_count
= 0;
3404 unsigned int non_singular_classes_sum
= 0;
3406 bool merged_p
= false;
3409 congruence_class_group
*it
;
3410 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3411 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
3413 congruence_class
*c
= it
->classes
[i
];
3414 if (c
->members
.length () > 1)
3416 non_singular_classes_count
++;
3417 non_singular_classes_sum
+= c
->members
.length ();
3423 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3424 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3425 prev_class_count
, class_count
);
3426 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3427 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3428 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3429 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3430 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3431 non_singular_classes_count
: 0.0f
,
3432 non_singular_classes_count
);
3433 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3434 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3435 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3438 FOR_EACH_VEC_ELT (m_classes_vec
, l
, it
)
3439 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
3441 congruence_class
*c
= it
->classes
[i
];
3443 if (c
->members
.length () == 1)
3446 sem_item
*source
= c
->members
[0];
3448 if (DECL_NAME (source
->decl
)
3449 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3450 /* If merge via wrappers, picking main as the target can be
3452 source
= c
->members
[1];
3454 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3456 sem_item
*alias
= c
->members
[j
];
3458 if (alias
== source
)
3463 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3464 xstrdup_for_dump (source
->node
->name ()),
3465 xstrdup_for_dump (alias
->node
->name ()));
3466 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3467 xstrdup_for_dump (source
->node
->asm_name ()),
3468 xstrdup_for_dump (alias
->node
->asm_name ()));
3471 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3475 "Merge operation is skipped due to no_icf "
3481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3483 source
->dump_to_file (dump_file
);
3484 alias
->dump_to_file (dump_file
);
3487 if (dbg_cnt (merged_ipa_icf
))
3488 merged_p
|= source
->merge (alias
);
3495 /* Dump function prints all class members to a FILE with an INDENT. */
3498 congruence_class::dump (FILE *file
, unsigned int indent
) const
3500 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3501 id
, members
[0]->get_hash (), members
.length ());
3503 FPUTS_SPACES (file
, indent
+ 2, "");
3504 for (unsigned i
= 0; i
< members
.length (); i
++)
3505 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3506 (void *) members
[i
]->decl
,
3507 members
[i
]->node
->order
);
3509 fprintf (file
, "\n");
3512 /* Returns true if there's a member that is used from another group. */
3515 congruence_class::is_class_used (void)
3517 for (unsigned int i
= 0; i
< members
.length (); i
++)
3518 if (members
[i
]->usages
.length ())
3524 /* Generate pass summary for IPA ICF pass. */
3527 ipa_icf_generate_summary (void)
3530 optimizer
= new sem_item_optimizer ();
3532 optimizer
->register_hooks ();
3533 optimizer
->parse_funcs_and_vars ();
3536 /* Write pass summary for IPA ICF pass. */
3539 ipa_icf_write_summary (void)
3541 gcc_assert (optimizer
);
3543 optimizer
->write_summary ();
3546 /* Read pass summary for IPA ICF pass. */
3549 ipa_icf_read_summary (void)
3552 optimizer
= new sem_item_optimizer ();
3554 optimizer
->read_summary ();
3555 optimizer
->register_hooks ();
3558 /* Semantic equality exection function. */
3561 ipa_icf_driver (void)
3563 gcc_assert (optimizer
);
3565 bool merged_p
= optimizer
->execute ();
3570 return merged_p
? TODO_remove_functions
: 0;
3573 const pass_data pass_data_ipa_icf
=
3575 IPA_PASS
, /* type */
3577 OPTGROUP_IPA
, /* optinfo_flags */
3578 TV_IPA_ICF
, /* tv_id */
3579 0, /* properties_required */
3580 0, /* properties_provided */
3581 0, /* properties_destroyed */
3582 0, /* todo_flags_start */
3583 0, /* todo_flags_finish */
3586 class pass_ipa_icf
: public ipa_opt_pass_d
3589 pass_ipa_icf (gcc::context
*ctxt
)
3590 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3591 ipa_icf_generate_summary
, /* generate_summary */
3592 ipa_icf_write_summary
, /* write_summary */
3593 ipa_icf_read_summary
, /* read_summary */
3595 write_optimization_summary */
3597 read_optimization_summary */
3598 NULL
, /* stmt_fixup */
3599 0, /* function_transform_todo_flags_start */
3600 NULL
, /* function_transform */
3601 NULL
) /* variable_transform */
3604 /* opt_pass methods: */
3605 virtual bool gate (function
*)
3607 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3610 virtual unsigned int execute (function
*)
3612 return ipa_icf_driver();
3614 }; // class pass_ipa_icf
3616 } // ipa_icf namespace
3619 make_pass_ipa_icf (gcc::context
*ctxt
)
3621 return new ipa_icf::pass_ipa_icf (ctxt
);