1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2016 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
67 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
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 /* Semantic item constructor for a node of _TYPE, where STACK is used
140 for bitmap memory allocation. */
142 sem_item::sem_item (sem_item_type _type
,
143 bitmap_obstack
*stack
): type (_type
), m_hash (0)
148 /* Semantic item constructor for a node of _TYPE, where STACK is used
149 for bitmap memory allocation. The item is based on symtab node _NODE
150 with computed _HASH. */
152 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
153 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
154 node (_node
), m_hash (_hash
)
160 /* Add reference to a semantic TARGET. */
163 sem_item::add_reference (sem_item
*target
)
165 refs
.safe_push (target
);
166 unsigned index
= refs
.length ();
167 target
->usages
.safe_push (new sem_usage_pair(this, index
));
168 bitmap_set_bit (target
->usage_index_bitmap
, index
);
169 refs_set
.add (target
->node
);
172 /* Initialize internal data structures. Bitmap STACK is used for
173 bitmap memory allocation process. */
176 sem_item::setup (bitmap_obstack
*stack
)
178 gcc_checking_assert (node
);
181 tree_refs
.create (0);
183 usage_index_bitmap
= BITMAP_ALLOC (stack
);
186 sem_item::~sem_item ()
188 for (unsigned i
= 0; i
< usages
.length (); i
++)
192 tree_refs
.release ();
195 BITMAP_FREE (usage_index_bitmap
);
198 /* Dump function for debugging purpose. */
201 sem_item::dump (void)
205 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
206 node
->name(), node
->order
, (void *) node
->decl
);
207 fprintf (dump_file
, " hash: %u\n", get_hash ());
208 fprintf (dump_file
, " references: ");
210 for (unsigned i
= 0; i
< refs
.length (); i
++)
211 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
212 i
< refs
.length() - 1 ? "," : "");
214 fprintf (dump_file
, "\n");
218 /* Return true if target supports alias symbols. */
221 sem_item::target_supports_symbol_aliases_p (void)
223 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
230 void sem_item::set_hash (hashval_t hash
)
235 /* Semantic function constructor that uses STACK as bitmap memory stack. */
237 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
238 m_checker (NULL
), m_compared_func (NULL
)
241 bb_sorted
.create (0);
244 /* Constructor based on callgraph node _NODE with computed hash _HASH.
245 Bitmap STACK is used for memory allocation. */
246 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
247 bitmap_obstack
*stack
):
248 sem_item (FUNC
, node
, hash
, stack
),
249 m_checker (NULL
), m_compared_func (NULL
)
252 bb_sorted
.create (0);
255 sem_function::~sem_function ()
257 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
258 delete (bb_sorted
[i
]);
261 bb_sorted
.release ();
264 /* Calculates hash value based on a BASIC_BLOCK. */
267 sem_function::get_bb_hash (const sem_bb
*basic_block
)
269 inchash::hash hstate
;
271 hstate
.add_int (basic_block
->nondbg_stmt_count
);
272 hstate
.add_int (basic_block
->edge_count
);
274 return hstate
.end ();
277 /* References independent hash function. */
280 sem_function::get_hash (void)
284 inchash::hash hstate
;
285 hstate
.add_int (177454); /* Random number for function type. */
287 hstate
.add_int (arg_count
);
288 hstate
.add_int (cfg_checksum
);
289 hstate
.add_int (gcode_hash
);
291 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
292 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
294 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
295 hstate
.add_int (bb_sizes
[i
]);
297 /* Add common features of declaration itself. */
298 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
300 (cl_target_option_hash
301 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
302 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
303 (cl_optimization_hash
304 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
305 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
306 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
308 set_hash (hstate
.end ());
314 /* Return ture if A1 and A2 represent equivalent function attribute lists.
315 Based on comp_type_attributes. */
318 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
323 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
325 const struct attribute_spec
*as
;
328 as
= lookup_attribute_spec (get_attribute_name (a
));
329 /* TODO: We can introduce as->affects_decl_identity
330 and as->affects_decl_reference_identity if attribute mismatch
331 gets a common reason to give up on merging. It may not be worth
333 For example returns_nonnull affects only references, while
334 optimize attribute can be ignored because it is already lowered
335 into flags representation and compared separately. */
339 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
340 if (!attr
|| !attribute_value_equal (a
, attr
))
345 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
347 const struct attribute_spec
*as
;
349 as
= lookup_attribute_spec (get_attribute_name (a
));
353 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
355 /* We don't need to compare trees again, as we did this
356 already in first loop. */
361 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
365 /* Compare properties of symbols N1 and N2 that does not affect semantics of
366 symbol itself but affects semantics of its references from USED_BY (which
367 may be NULL if it is unknown). If comparsion is false, symbols
368 can still be merged but any symbols referring them can't.
370 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
372 TODO: We can also split attributes to those that determine codegen of
373 a function body/variable constructor itself and those that are used when
377 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
382 if (is_a
<cgraph_node
*> (n1
))
384 /* Inline properties matters: we do now want to merge uses of inline
385 function to uses of normal function because inline hint would be lost.
386 We however can merge inline function to noinline because the alias
387 will keep its DECL_DECLARED_INLINE flag.
389 Also ignore inline flag when optimizing for size or when function
390 is known to not be inlinable.
392 TODO: the optimize_size checks can also be assumed to be true if
393 unit has no !optimize_size functions. */
395 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
396 || !opt_for_fn (used_by
->decl
, optimize_size
))
397 && !opt_for_fn (n1
->decl
, optimize_size
)
398 && n1
->get_availability () > AVAIL_INTERPOSABLE
399 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
401 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
402 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
403 return return_false_with_msg
404 ("DECL_DISREGARD_INLINE_LIMITS are different");
406 if (DECL_DECLARED_INLINE_P (n1
->decl
)
407 != DECL_DECLARED_INLINE_P (n2
->decl
))
408 return return_false_with_msg ("inline attributes are different");
411 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
412 != DECL_IS_OPERATOR_NEW (n2
->decl
))
413 return return_false_with_msg ("operator new flags are different");
416 /* Merging two definitions with a reference to equivalent vtables, but
417 belonging to a different type may result in ipa-polymorphic-call analysis
418 giving a wrong answer about the dynamic type of instance. */
419 if (is_a
<varpool_node
*> (n1
))
421 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
422 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
423 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
424 DECL_CONTEXT (n2
->decl
)))
425 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
426 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
427 return return_false_with_msg
428 ("references to virtual tables can not be merged");
430 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
431 return return_false_with_msg ("alignment mismatch");
433 /* For functions we compare attributes in equals_wpa, because we do
434 not know what attributes may cause codegen differences, but for
435 variables just compare attributes for references - the codegen
436 for constructors is affected only by those attributes that we lower
437 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
438 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
439 DECL_ATTRIBUTES (n2
->decl
)))
440 return return_false_with_msg ("different var decl attributes");
441 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
442 TREE_TYPE (n2
->decl
)) != 1)
443 return return_false_with_msg ("different var type attributes");
446 /* When matching virtual tables, be sure to also match information
447 relevant for polymorphic call analysis. */
448 if (used_by
&& is_a
<varpool_node
*> (used_by
)
449 && DECL_VIRTUAL_P (used_by
->decl
))
451 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
452 return return_false_with_msg ("virtual flag mismatch");
453 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
454 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
455 return return_false_with_msg ("final flag mismatch");
460 /* Hash properties that are compared by compare_referenced_symbol_properties. */
463 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
464 inchash::hash
&hstate
,
467 if (is_a
<cgraph_node
*> (ref
))
469 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
470 && !opt_for_fn (ref
->decl
, optimize_size
)
471 && !DECL_UNINLINABLE (ref
->decl
))
473 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
474 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
476 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
478 else if (is_a
<varpool_node
*> (ref
))
480 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
482 hstate
.add_int (DECL_ALIGN (ref
->decl
));
487 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
488 point to a same function. Comparison can be skipped if IGNORED_NODES
489 contains these nodes. ADDRESS indicate if address is taken. */
492 sem_item::compare_symbol_references (
493 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
494 symtab_node
*n1
, symtab_node
*n2
, bool address
)
496 enum availability avail1
, avail2
;
501 /* Never match variable and function. */
502 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
505 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
507 if (address
&& n1
->equal_address_to (n2
) == 1)
509 if (!address
&& n1
->semantically_equivalent_p (n2
))
512 n1
= n1
->ultimate_alias_target (&avail1
);
513 n2
= n2
->ultimate_alias_target (&avail2
);
515 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
516 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
519 return return_false_with_msg ("different references");
522 /* If cgraph edges E1 and E2 are indirect calls, verify that
523 ECF flags are the same. */
525 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
527 if (e1
->indirect_info
&& e2
->indirect_info
)
529 int e1_flags
= e1
->indirect_info
->ecf_flags
;
530 int e2_flags
= e2
->indirect_info
->ecf_flags
;
532 if (e1_flags
!= e2_flags
)
533 return return_false_with_msg ("ICF flags are different");
535 else if (e1
->indirect_info
|| e2
->indirect_info
)
541 /* Return true if parameter I may be used. */
544 sem_function::param_used_p (unsigned int i
)
546 if (ipa_node_params_sum
== NULL
)
549 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
551 if (parms_info
->descriptors
.is_empty ()
552 || parms_info
->descriptors
.length () <= i
)
555 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
558 /* Perform additional check needed to match types function parameters that are
559 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
560 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
563 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
565 /* Be sure that parameters are TBAA compatible. */
566 if (!func_checker::compatible_types_p (parm1
, parm2
))
567 return return_false_with_msg ("parameter type is not compatible");
569 if (POINTER_TYPE_P (parm1
)
570 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
571 return return_false_with_msg ("argument restrict flag mismatch");
573 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
574 if (POINTER_TYPE_P (parm1
)
575 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
576 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
577 return return_false_with_msg ("pointer wrt reference mismatch");
582 /* Fast equality function based on knowledge known in WPA. */
585 sem_function::equals_wpa (sem_item
*item
,
586 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
588 gcc_assert (item
->type
== FUNC
);
589 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
590 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
592 m_compared_func
= static_cast<sem_function
*> (item
);
594 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
595 return return_false_with_msg ("thunk_p mismatch");
597 if (cnode
->thunk
.thunk_p
)
599 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
600 return return_false_with_msg ("thunk fixed_offset mismatch");
601 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
602 return return_false_with_msg ("thunk virtual_value mismatch");
603 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
604 return return_false_with_msg ("thunk this_adjusting mismatch");
605 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
606 return return_false_with_msg ("thunk virtual_offset_p mismatch");
607 if (cnode
->thunk
.add_pointer_bounds_args
608 != cnode2
->thunk
.add_pointer_bounds_args
)
609 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
612 /* Compare special function DECL attributes. */
613 if (DECL_FUNCTION_PERSONALITY (decl
)
614 != DECL_FUNCTION_PERSONALITY (item
->decl
))
615 return return_false_with_msg ("function personalities are different");
617 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
618 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
619 return return_false_with_msg ("intrument function entry exit "
620 "attributes are different");
622 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
623 return return_false_with_msg ("no stack limit attributes are different");
625 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
626 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
628 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
629 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
631 /* TODO: pure/const flags mostly matters only for references, except for
632 the fact that codegen takes LOOPING flag as a hint that loops are
633 finite. We may arrange the code to always pick leader that has least
634 specified flags and then this can go into comparing symbol properties. */
635 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
636 return return_false_with_msg ("decl_or_type flags are different");
638 /* Do not match polymorphic constructors of different types. They calls
639 type memory location for ipa-polymorphic-call and we do not want
640 it to get confused by wrong type. */
641 if (DECL_CXX_CONSTRUCTOR_P (decl
)
642 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
644 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
645 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
646 else if (!func_checker::compatible_polymorphic_types_p
647 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
648 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
649 return return_false_with_msg ("ctor polymorphic type mismatch");
652 /* Checking function TARGET and OPTIMIZATION flags. */
653 cl_target_option
*tar1
= target_opts_for_fn (decl
);
654 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
656 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
660 fprintf (dump_file
, "target flags difference");
661 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
664 return return_false_with_msg ("Target flags are different");
667 cl_optimization
*opt1
= opts_for_fn (decl
);
668 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
670 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
674 fprintf (dump_file
, "optimization flags difference");
675 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
678 return return_false_with_msg ("optimization flags are different");
681 /* Result type checking. */
682 if (!func_checker::compatible_types_p
683 (TREE_TYPE (TREE_TYPE (decl
)),
684 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
685 return return_false_with_msg ("result types are different");
687 /* Checking types of arguments. */
688 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
689 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
690 for (unsigned i
= 0; list1
&& list2
;
691 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
693 tree parm1
= TREE_VALUE (list1
);
694 tree parm2
= TREE_VALUE (list2
);
696 /* This guard is here for function pointer with attributes (pr59927.c). */
697 if (!parm1
|| !parm2
)
698 return return_false_with_msg ("NULL argument type");
700 /* Verify that types are compatible to ensure that both functions
701 have same calling conventions. */
702 if (!types_compatible_p (parm1
, parm2
))
703 return return_false_with_msg ("parameter types are not compatible");
705 if (!param_used_p (i
))
708 /* Perform additional checks for used parameters. */
709 if (!compatible_parm_types_p (parm1
, parm2
))
714 return return_false_with_msg ("Mismatched number of parameters");
716 if (node
->num_references () != item
->node
->num_references ())
717 return return_false_with_msg ("different number of references");
719 /* Checking function attributes.
720 This is quadratic in number of attributes */
721 if (comp_type_attributes (TREE_TYPE (decl
),
722 TREE_TYPE (item
->decl
)) != 1)
723 return return_false_with_msg ("different type attributes");
724 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
725 DECL_ATTRIBUTES (item
->decl
)))
726 return return_false_with_msg ("different decl attributes");
728 /* The type of THIS pointer type memory location for
729 ipa-polymorphic-call-analysis. */
730 if (opt_for_fn (decl
, flag_devirtualize
)
731 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
732 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
734 && compare_polymorphic_p ())
736 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
737 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
738 if (!func_checker::compatible_polymorphic_types_p
739 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
740 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
741 return return_false_with_msg ("THIS pointer ODR type mismatch");
744 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
745 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
747 item
->node
->iterate_reference (i
, ref2
);
749 if (ref
->use
!= ref2
->use
)
750 return return_false_with_msg ("reference use mismatch");
752 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
754 ref
->address_matters_p ()))
758 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
759 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
763 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
766 if (!compare_edge_flags (e1
, e2
))
769 e1
= e1
->next_callee
;
770 e2
= e2
->next_callee
;
774 return return_false_with_msg ("different number of calls");
776 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
777 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
781 if (!compare_edge_flags (e1
, e2
))
784 e1
= e1
->next_callee
;
785 e2
= e2
->next_callee
;
789 return return_false_with_msg ("different number of indirect calls");
794 /* Update hash by address sensitive references. We iterate over all
795 sensitive references (address_matters_p) and we hash ultime alias
796 target of these nodes, which can improve a semantic item hash.
798 Also hash in referenced symbols properties. This can be done at any time
799 (as the properties should not change), but it is convenient to do it here
800 while we walk the references anyway. */
803 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
804 sem_item
*> &m_symtab_node_map
)
807 inchash::hash
hstate (get_hash ());
809 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
811 hstate
.add_int (ref
->use
);
812 hash_referenced_symbol_properties (ref
->referred
, hstate
,
813 ref
->use
== IPA_REF_ADDR
);
814 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
815 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
818 if (is_a
<cgraph_node
*> (node
))
820 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
823 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
824 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
826 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
830 set_hash (hstate
.end ());
833 /* Update hash by computed local hash values taken from different
835 TODO: stronger SCC based hashing would be desirable here. */
838 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
839 sem_item
*> &m_symtab_node_map
)
842 inchash::hash
state (get_hash ());
844 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
846 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
848 state
.merge_hash ((*result
)->get_hash ());
853 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
856 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
858 state
.merge_hash ((*result
)->get_hash ());
862 global_hash
= state
.end ();
865 /* Returns true if the item equals to ITEM given as argument. */
868 sem_function::equals (sem_item
*item
,
869 hash_map
<symtab_node
*, sem_item
*> &)
871 gcc_assert (item
->type
== FUNC
);
872 bool eq
= equals_private (item
);
874 if (m_checker
!= NULL
)
880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
883 xstrdup_for_dump (node
->name()),
884 xstrdup_for_dump (item
->node
->name ()),
887 xstrdup_for_dump (node
->asm_name ()),
888 xstrdup_for_dump (item
->node
->asm_name ()),
889 eq
? "true" : "false");
894 /* Processes function equality comparison. */
897 sem_function::equals_private (sem_item
*item
)
899 if (item
->type
!= FUNC
)
902 basic_block bb1
, bb2
;
904 edge_iterator ei1
, ei2
;
908 m_compared_func
= static_cast<sem_function
*> (item
);
910 gcc_assert (decl
!= item
->decl
);
912 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
913 || edge_count
!= m_compared_func
->edge_count
914 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
915 return return_false ();
917 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
918 compare_polymorphic_p (),
921 &m_compared_func
->refs_set
);
922 arg1
= DECL_ARGUMENTS (decl
);
923 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
925 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
927 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
928 return return_false_with_msg ("argument types are not compatible");
929 if (!param_used_p (i
))
931 /* Perform additional checks for used parameters. */
932 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
934 if (!m_checker
->compare_decl (arg1
, arg2
))
935 return return_false ();
938 return return_false_with_msg ("Mismatched number of arguments");
940 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
943 /* Fill-up label dictionary. */
944 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
946 m_checker
->parse_labels (bb_sorted
[i
]);
947 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
950 /* Checking all basic blocks. */
951 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
952 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
953 return return_false();
955 dump_message ("All BBs are equal\n");
957 auto_vec
<int> bb_dict
;
959 /* Basic block edges check. */
960 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
962 bb1
= bb_sorted
[i
]->bb
;
963 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
965 ei2
= ei_start (bb2
->preds
);
967 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
971 if (e1
->flags
!= e2
->flags
)
972 return return_false_with_msg ("flags comparison returns false");
974 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
975 return return_false_with_msg ("edge comparison returns false");
977 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
978 return return_false_with_msg ("BB comparison returns false");
980 if (!m_checker
->compare_edge (e1
, e2
))
981 return return_false_with_msg ("edge comparison returns false");
987 /* Basic block PHI nodes comparison. */
988 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
989 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
990 return return_false_with_msg ("PHI node comparison returns false");
995 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
996 Helper for call_for_symbol_thunks_and_aliases. */
999 set_local (cgraph_node
*node
, void *data
)
1001 node
->local
.local
= data
!= NULL
;
1005 /* TREE_ADDRESSABLE of NODE to true.
1006 Helper for call_for_symbol_thunks_and_aliases. */
1009 set_addressable (varpool_node
*node
, void *)
1011 TREE_ADDRESSABLE (node
->decl
) = 1;
1015 /* Clear DECL_RTL of NODE.
1016 Helper for call_for_symbol_thunks_and_aliases. */
1019 clear_decl_rtl (symtab_node
*node
, void *)
1021 SET_DECL_RTL (node
->decl
, NULL
);
1025 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1026 possible. Return number of redirections made. */
1029 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1031 int nredirected
= 0;
1033 cgraph_edge
*e
= n
->callers
;
1037 /* Redirecting thunks to interposable symbols or symbols in other sections
1038 may not be supported by target output code. Play safe for now and
1039 punt on redirection. */
1040 if (!e
->caller
->thunk
.thunk_p
)
1042 struct cgraph_edge
*nexte
= e
->next_caller
;
1043 e
->redirect_callee (to
);
1050 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1052 bool removed
= false;
1053 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1055 if ((DECL_COMDAT_GROUP (n
->decl
)
1056 && (DECL_COMDAT_GROUP (n
->decl
)
1057 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1058 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1059 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1061 nredirected
+= redirect_all_callers (n_alias
, to
);
1062 if (n_alias
->can_remove_if_no_direct_calls_p ()
1063 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1065 && !n_alias
->has_aliases_p ())
1074 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1078 sem_function::merge (sem_item
*alias_item
)
1080 gcc_assert (alias_item
->type
== FUNC
);
1082 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1084 cgraph_node
*original
= get_node ();
1085 cgraph_node
*local_original
= NULL
;
1086 cgraph_node
*alias
= alias_func
->get_node ();
1088 bool create_wrapper
= false;
1089 bool create_alias
= false;
1090 bool redirect_callers
= false;
1091 bool remove
= false;
1093 bool original_discardable
= false;
1094 bool original_discarded
= false;
1096 bool original_address_matters
= original
->address_matters_p ();
1097 bool alias_address_matters
= alias
->address_matters_p ();
1099 if (DECL_EXTERNAL (alias
->decl
))
1102 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1106 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1107 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1112 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1116 /* Do not attempt to mix functions from different user sections;
1117 we do not know what user intends with those. */
1118 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1119 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1120 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1125 "original and alias are in different sections.\n\n");
1129 /* See if original is in a section that can be discarded if the main
1130 symbol is not used. */
1132 if (original
->can_be_discarded_p ())
1133 original_discardable
= true;
1134 /* Also consider case where we have resolution info and we know that
1135 original's definition is not going to be used. In this case we can not
1136 create alias to original. */
1137 if (node
->resolution
!= LDPR_UNKNOWN
1138 && !decl_binds_to_current_def_p (node
->decl
))
1139 original_discardable
= original_discarded
= true;
1141 /* Creating a symtab alias is the optimal way to merge.
1142 It however can not be used in the following cases:
1144 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1145 2) if ORIGINAL is in a section that may be discarded by linker or if
1146 it is an external functions where we can not create an alias
1147 (ORIGINAL_DISCARDABLE)
1148 3) if target do not support symbol aliases.
1149 4) original and alias lie in different comdat groups.
1151 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1152 and/or redirect all callers from ALIAS to ORIGINAL. */
1153 if ((original_address_matters
&& alias_address_matters
)
1154 || (original_discardable
1155 && (!DECL_COMDAT_GROUP (alias
->decl
)
1156 || (DECL_COMDAT_GROUP (alias
->decl
)
1157 != DECL_COMDAT_GROUP (original
->decl
))))
1158 || original_discarded
1159 || !sem_item::target_supports_symbol_aliases_p ()
1160 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1162 /* First see if we can produce wrapper. */
1164 /* Symbol properties that matter for references must be preserved.
1165 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1166 with proper properties. */
1167 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1168 alias
->address_taken
))
1172 "Wrapper cannot be created because referenced symbol "
1173 "properties mismatch\n");
1175 /* Do not turn function in one comdat group into wrapper to another
1176 comdat group. Other compiler producing the body of the
1177 another comdat group may make opossite decision and with unfortunate
1178 linker choices this may close a loop. */
1179 else if (DECL_COMDAT_GROUP (original
->decl
)
1180 && DECL_COMDAT_GROUP (alias
->decl
)
1181 && (DECL_COMDAT_GROUP (alias
->decl
)
1182 != DECL_COMDAT_GROUP (original
->decl
)))
1186 "Wrapper cannot be created because of COMDAT\n");
1188 else if (DECL_STATIC_CHAIN (alias
->decl
))
1192 "Can not create wrapper of nested functions.\n");
1194 /* TODO: We can also deal with variadic functions never calling
1196 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1200 "can not create wrapper of stdarg function.\n");
1202 else if (inline_summaries
1203 && inline_summaries
->get (alias
)->self_size
<= 2)
1206 fprintf (dump_file
, "Wrapper creation is not "
1207 "profitable (function is too small).\n");
1209 /* If user paid attention to mark function noinline, assume it is
1210 somewhat special and do not try to turn it into a wrapper that can
1211 not be undone by inliner. */
1212 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1215 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1218 create_wrapper
= true;
1220 /* We can redirect local calls in the case both alias and orignal
1221 are not interposable. */
1223 = alias
->get_availability () > AVAIL_INTERPOSABLE
1224 && original
->get_availability () > AVAIL_INTERPOSABLE
1225 && !alias
->instrumented_version
;
1226 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1227 with proper properties. */
1228 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1229 alias
->address_taken
))
1230 redirect_callers
= false;
1232 if (!redirect_callers
&& !create_wrapper
)
1235 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1236 "produce wrapper\n\n");
1240 /* Work out the symbol the wrapper should call.
1241 If ORIGINAL is interposable, we need to call a local alias.
1242 Also produce local alias (if possible) as an optimization.
1244 Local aliases can not be created inside comdat groups because that
1245 prevents inlining. */
1246 if (!original_discardable
&& !original
->get_comdat_group ())
1249 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1251 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1252 local_original
= original
;
1254 /* If we can not use local alias, fallback to the original
1256 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1257 local_original
= original
;
1259 /* If original is COMDAT local, we can not really redirect calls outside
1260 of its comdat group to it. */
1261 if (original
->comdat_local_p ())
1262 redirect_callers
= false;
1263 if (!local_original
)
1266 fprintf (dump_file
, "Not unifying; "
1267 "can not produce local alias.\n\n");
1271 if (!redirect_callers
&& !create_wrapper
)
1274 fprintf (dump_file
, "Not unifying; "
1275 "can not redirect callers nor produce a wrapper\n\n");
1279 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1281 && !alias
->can_remove_if_no_direct_calls_p ())
1284 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1285 "function has other uses than direct calls\n\n");
1290 create_alias
= true;
1292 if (redirect_callers
)
1294 int nredirected
= redirect_all_callers (alias
, local_original
);
1298 alias
->icf_merged
= true;
1299 local_original
->icf_merged
= true;
1301 if (dump_file
&& nredirected
)
1302 fprintf (dump_file
, "%i local calls have been "
1303 "redirected.\n", nredirected
);
1306 /* If all callers was redirected, do not produce wrapper. */
1307 if (alias
->can_remove_if_no_direct_calls_p ()
1308 && !DECL_VIRTUAL_P (alias
->decl
)
1309 && !alias
->has_aliases_p ())
1311 create_wrapper
= false;
1314 gcc_assert (!create_alias
);
1316 else if (create_alias
)
1318 alias
->icf_merged
= true;
1320 /* Remove the function's body. */
1321 ipa_merge_profiles (original
, alias
);
1322 alias
->release_body (true);
1324 /* Notice global symbol possibly produced RTL. */
1325 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1328 /* Create the alias. */
1329 cgraph_node::create_alias (alias_func
->decl
, decl
);
1330 alias
->resolve_alias (original
);
1332 original
->call_for_symbol_thunks_and_aliases
1333 (set_local
, (void *)(size_t) original
->local_p (), true);
1336 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1340 gcc_assert (!create_alias
);
1341 alias
->icf_merged
= true;
1342 local_original
->icf_merged
= true;
1344 ipa_merge_profiles (local_original
, alias
, true);
1345 alias
->create_wrapper (local_original
);
1348 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1351 /* It's possible that redirection can hit thunks that block
1352 redirection opportunities. */
1353 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1354 original
->icf_merged
= true;
1356 /* We use merged flag to track cases where COMDAT function is known to be
1357 compatible its callers. If we merged in non-COMDAT, we need to give up
1358 on this optimization. */
1359 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1362 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1364 local_original
->merged_comdat
= false;
1365 original
->merged_comdat
= false;
1370 ipa_merge_profiles (original
, alias
);
1371 alias
->release_body ();
1373 alias
->body_removed
= true;
1374 alias
->icf_merged
= true;
1376 fprintf (dump_file
, "Unified; Function body was removed.\n");
1382 /* Semantic item initialization function. */
1385 sem_function::init (void)
1388 get_node ()->get_untransformed_body ();
1390 tree fndecl
= node
->decl
;
1391 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1394 gcc_assert (SSANAMES (func
));
1396 ssa_names_size
= SSANAMES (func
)->length ();
1400 region_tree
= func
->eh
->region_tree
;
1402 /* iterating all function arguments. */
1403 arg_count
= count_formal_params (fndecl
);
1405 edge_count
= n_edges_for_fn (func
);
1406 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1407 if (!cnode
->thunk
.thunk_p
)
1409 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1411 inchash::hash hstate
;
1414 FOR_EACH_BB_FN (bb
, func
)
1416 unsigned nondbg_stmt_count
= 0;
1419 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1421 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1424 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1427 gimple
*stmt
= gsi_stmt (gsi
);
1429 if (gimple_code (stmt
) != GIMPLE_DEBUG
1430 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1432 hash_stmt (stmt
, hstate
);
1433 nondbg_stmt_count
++;
1437 gcode_hash
= hstate
.end ();
1438 bb_sizes
.safe_push (nondbg_stmt_count
);
1440 /* Inserting basic block to hash table. */
1441 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1442 EDGE_COUNT (bb
->preds
)
1443 + EDGE_COUNT (bb
->succs
));
1445 bb_sorted
.safe_push (semantic_bb
);
1451 inchash::hash hstate
;
1452 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1453 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1454 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1455 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1456 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1457 gcode_hash
= hstate
.end ();
1461 /* Accumulate to HSTATE a hash of expression EXP.
1462 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1463 and DECL equality classes. */
1466 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1468 if (exp
== NULL_TREE
)
1470 hstate
.merge_hash (0);
1474 /* Handled component can be matched in a cureful way proving equivalence
1475 even if they syntactically differ. Just skip them. */
1477 while (handled_component_p (exp
))
1478 exp
= TREE_OPERAND (exp
, 0);
1480 enum tree_code code
= TREE_CODE (exp
);
1481 hstate
.add_int (code
);
1485 /* Use inchash::add_expr for everything that is LTO stable. */
1493 inchash::add_expr (exp
, hstate
);
1497 unsigned HOST_WIDE_INT idx
;
1500 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1502 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1504 add_expr (value
, hstate
);
1509 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1515 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1518 case POINTER_PLUS_EXPR
:
1521 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1522 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1526 inchash::hash one
, two
;
1527 add_expr (TREE_OPERAND (exp
, 0), one
);
1528 add_expr (TREE_OPERAND (exp
, 1), two
);
1529 hstate
.add_commutative (one
, two
);
1533 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1534 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1540 /* Accumulate to HSTATE a hash of type t.
1541 TYpes that may end up being compatible after LTO type merging needs to have
1545 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1547 if (type
== NULL_TREE
)
1549 hstate
.merge_hash (0);
1553 type
= TYPE_MAIN_VARIANT (type
);
1555 hstate
.add_int (TYPE_MODE (type
));
1557 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1559 hstate
.add_int (COMPLEX_TYPE
);
1560 sem_item::add_type (TREE_TYPE (type
), hstate
);
1562 else if (INTEGRAL_TYPE_P (type
))
1564 hstate
.add_int (INTEGER_TYPE
);
1565 hstate
.add_flag (TYPE_UNSIGNED (type
));
1566 hstate
.add_int (TYPE_PRECISION (type
));
1568 else if (VECTOR_TYPE_P (type
))
1570 hstate
.add_int (VECTOR_TYPE
);
1571 hstate
.add_int (TYPE_PRECISION (type
));
1572 sem_item::add_type (TREE_TYPE (type
), hstate
);
1574 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1576 hstate
.add_int (ARRAY_TYPE
);
1577 /* Do not hash size, so complete and incomplete types can match. */
1578 sem_item::add_type (TREE_TYPE (type
), hstate
);
1580 else if (RECORD_OR_UNION_TYPE_P (type
))
1582 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1583 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1587 inchash::hash hstate2
;
1592 hstate2
.add_int (RECORD_TYPE
);
1593 gcc_assert (COMPLETE_TYPE_P (type
));
1595 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1596 if (TREE_CODE (f
) == FIELD_DECL
)
1598 add_type (TREE_TYPE (f
), hstate2
);
1602 hstate2
.add_int (nf
);
1603 hash
= hstate2
.end ();
1604 hstate
.add_wide_int (hash
);
1605 optimizer
->m_type_hash_cache
.put (type
, hash
);
1608 hstate
.add_wide_int (*val
);
1612 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1615 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1617 enum gimple_code code
= gimple_code (stmt
);
1619 hstate
.add_int (code
);
1624 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1627 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1628 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1629 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1631 inchash::hash one
, two
;
1633 add_expr (gimple_assign_rhs1 (stmt
), one
);
1634 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1635 add_expr (gimple_assign_rhs2 (stmt
), two
);
1636 hstate
.add_commutative (one
, two
);
1637 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1639 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1640 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1642 add_expr (gimple_assign_lhs (stmt
), hstate
);
1643 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1646 /* ... fall through ... */
1652 /* All these statements are equivalent if their operands are. */
1653 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1655 add_expr (gimple_op (stmt
, i
), hstate
);
1656 if (gimple_op (stmt
, i
))
1657 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1665 /* Return true if polymorphic comparison must be processed. */
1668 sem_function::compare_polymorphic_p (void)
1670 struct cgraph_edge
*e
;
1672 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1674 if (get_node ()->indirect_calls
!= NULL
)
1676 /* TODO: We can do simple propagation determining what calls may lead to
1677 a polymorphic call. */
1678 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1679 if (e
->callee
->definition
1680 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1685 /* For a given call graph NODE, the function constructs new
1686 semantic function item. */
1689 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1691 tree fndecl
= node
->decl
;
1692 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1694 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1697 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1700 sem_function
*f
= new sem_function (node
, 0, stack
);
1707 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1708 return true if phi nodes are semantically equivalent in these blocks . */
1711 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1713 gphi_iterator si1
, si2
;
1715 unsigned size1
, size2
, i
;
1719 gcc_assert (bb1
!= NULL
);
1720 gcc_assert (bb2
!= NULL
);
1722 si2
= gsi_start_phis (bb2
);
1723 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1726 gsi_next_nonvirtual_phi (&si1
);
1727 gsi_next_nonvirtual_phi (&si2
);
1729 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1732 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1733 return return_false();
1738 tree phi_result1
= gimple_phi_result (phi1
);
1739 tree phi_result2
= gimple_phi_result (phi2
);
1741 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1742 return return_false_with_msg ("PHI results are different");
1744 size1
= gimple_phi_num_args (phi1
);
1745 size2
= gimple_phi_num_args (phi2
);
1748 return return_false ();
1750 for (i
= 0; i
< size1
; ++i
)
1752 t1
= gimple_phi_arg (phi1
, i
)->def
;
1753 t2
= gimple_phi_arg (phi2
, i
)->def
;
1755 if (!m_checker
->compare_operand (t1
, t2
))
1756 return return_false ();
1758 e1
= gimple_phi_arg_edge (phi1
, i
);
1759 e2
= gimple_phi_arg_edge (phi2
, i
);
1761 if (!m_checker
->compare_edge (e1
, e2
))
1762 return return_false ();
1771 /* Returns true if tree T can be compared as a handled component. */
1774 sem_function::icf_handled_component_p (tree t
)
1776 tree_code tc
= TREE_CODE (t
);
1778 return (handled_component_p (t
)
1779 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1782 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1783 corresponds to TARGET. */
1786 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1791 if (bb_dict
->length () <= (unsigned)source
)
1792 bb_dict
->safe_grow_cleared (source
+ 1);
1794 if ((*bb_dict
)[source
] == 0)
1796 (*bb_dict
)[source
] = target
;
1800 return (*bb_dict
)[source
] == target
;
1804 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1806 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1810 /* Constructor based on varpool node _NODE with computed hash _HASH.
1811 Bitmap STACK is used for memory allocation. */
1813 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1814 bitmap_obstack
*stack
): sem_item(VAR
,
1817 gcc_checking_assert (node
);
1818 gcc_checking_assert (get_node ());
1821 /* Fast equality function based on knowledge known in WPA. */
1824 sem_variable::equals_wpa (sem_item
*item
,
1825 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1827 gcc_assert (item
->type
== VAR
);
1829 if (node
->num_references () != item
->node
->num_references ())
1830 return return_false_with_msg ("different number of references");
1832 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1833 return return_false_with_msg ("TLS model");
1835 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1836 alignment out of all aliases. */
1838 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1839 return return_false_with_msg ("Virtual flag mismatch");
1841 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1842 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1843 || !operand_equal_p (DECL_SIZE (decl
),
1844 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1845 return return_false_with_msg ("size mismatch");
1847 /* Do not attempt to mix data from different user sections;
1848 we do not know what user intends with those. */
1849 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1850 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1851 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1852 return return_false_with_msg ("user section mismatch");
1854 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1855 return return_false_with_msg ("text section");
1857 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1858 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1860 item
->node
->iterate_reference (i
, ref2
);
1862 if (ref
->use
!= ref2
->use
)
1863 return return_false_with_msg ("reference use mismatch");
1865 if (!compare_symbol_references (ignored_nodes
,
1866 ref
->referred
, ref2
->referred
,
1867 ref
->address_matters_p ()))
1874 /* Returns true if the item equals to ITEM given as argument. */
1877 sem_variable::equals (sem_item
*item
,
1878 hash_map
<symtab_node
*, sem_item
*> &)
1880 gcc_assert (item
->type
== VAR
);
1883 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1884 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1885 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1886 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1888 /* As seen in PR ipa/65303 we have to compare variables types. */
1889 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1890 TREE_TYPE (item
->decl
)))
1891 return return_false_with_msg ("variables types are different");
1893 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1894 DECL_INITIAL (item
->node
->decl
));
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1897 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1898 xstrdup_for_dump (node
->name()),
1899 xstrdup_for_dump (item
->node
->name ()),
1900 node
->order
, item
->node
->order
,
1901 xstrdup_for_dump (node
->asm_name ()),
1902 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1907 /* Compares trees T1 and T2 for semantic equality. */
1910 sem_variable::equals (tree t1
, tree t2
)
1913 return return_with_debug (t1
== t2
);
1916 tree_code tc1
= TREE_CODE (t1
);
1917 tree_code tc2
= TREE_CODE (t2
);
1920 return return_false_with_msg ("TREE_CODE mismatch");
1926 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1927 unsigned HOST_WIDE_INT idx
;
1929 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1930 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1931 return return_false_with_msg ("constructor type mismatch");
1933 if (typecode
== ARRAY_TYPE
)
1935 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1936 /* For arrays, check that the sizes all match. */
1937 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1939 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1940 return return_false_with_msg ("constructor array size mismatch");
1942 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1944 return return_false_with_msg ("constructor type incompatible");
1946 v1
= CONSTRUCTOR_ELTS (t1
);
1947 v2
= CONSTRUCTOR_ELTS (t2
);
1948 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1949 return return_false_with_msg ("constructor number of elts mismatch");
1951 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1953 constructor_elt
*c1
= &(*v1
)[idx
];
1954 constructor_elt
*c2
= &(*v2
)[idx
];
1956 /* Check that each value is the same... */
1957 if (!sem_variable::equals (c1
->value
, c2
->value
))
1959 /* ... and that they apply to the same fields! */
1960 if (!sem_variable::equals (c1
->index
, c2
->index
))
1967 tree x1
= TREE_OPERAND (t1
, 0);
1968 tree x2
= TREE_OPERAND (t2
, 0);
1969 tree y1
= TREE_OPERAND (t1
, 1);
1970 tree y2
= TREE_OPERAND (t2
, 1);
1972 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1973 return return_false ();
1975 /* Type of the offset on MEM_REF does not matter. */
1976 return return_with_debug (sem_variable::equals (x1
, x2
)
1977 && wi::to_offset (y1
)
1978 == wi::to_offset (y2
));
1983 tree op1
= TREE_OPERAND (t1
, 0);
1984 tree op2
= TREE_OPERAND (t2
, 0);
1985 return sem_variable::equals (op1
, op2
);
1987 /* References to other vars/decls are compared using ipa-ref. */
1990 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1992 return return_false_with_msg ("Declaration mismatch");
1994 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1995 need to process its VAR/FUNCTION references without relying on ipa-ref
1999 return return_false_with_msg ("Declaration mismatch");
2001 /* Integer constants are the same only if the same width of type. */
2002 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2003 return return_false_with_msg ("INTEGER_CST precision mismatch");
2004 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2005 return return_false_with_msg ("INTEGER_CST mode mismatch");
2006 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2008 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2009 return return_false_with_msg ("STRING_CST mode mismatch");
2010 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2011 return return_false_with_msg ("STRING_CST length mismatch");
2012 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2013 TREE_STRING_LENGTH (t1
)))
2014 return return_false_with_msg ("STRING_CST mismatch");
2017 /* Fixed constants are the same only if the same width of type. */
2018 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2019 return return_false_with_msg ("FIXED_CST precision mismatch");
2021 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2022 TREE_FIXED_CST (t2
)));
2024 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2025 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2027 /* Real constants are the same only if the same width of type. */
2028 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2029 return return_false_with_msg ("REAL_CST precision mismatch");
2030 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2031 &TREE_REAL_CST (t2
)));
2036 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2037 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2039 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2040 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2041 VECTOR_CST_ELT (t2
, i
)))
2047 case ARRAY_RANGE_REF
:
2049 tree x1
= TREE_OPERAND (t1
, 0);
2050 tree x2
= TREE_OPERAND (t2
, 0);
2051 tree y1
= TREE_OPERAND (t1
, 1);
2052 tree y2
= TREE_OPERAND (t2
, 1);
2054 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2056 if (!sem_variable::equals (array_ref_low_bound (t1
),
2057 array_ref_low_bound (t2
)))
2059 if (!sem_variable::equals (array_ref_element_size (t1
),
2060 array_ref_element_size (t2
)))
2066 case POINTER_PLUS_EXPR
:
2071 tree x1
= TREE_OPERAND (t1
, 0);
2072 tree x2
= TREE_OPERAND (t2
, 0);
2073 tree y1
= TREE_OPERAND (t1
, 1);
2074 tree y2
= TREE_OPERAND (t2
, 1);
2076 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2080 case VIEW_CONVERT_EXPR
:
2081 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2082 return return_false ();
2083 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2085 return return_false_with_msg ("ERROR_MARK");
2087 return return_false_with_msg ("Unknown TREE code reached");
2091 /* Parser function that visits a varpool NODE. */
2094 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2096 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2100 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2107 /* References independent hash function. */
2110 sem_variable::get_hash (void)
2115 /* All WPA streamed in symbols should have their hashes computed at compile
2116 time. At this point, the constructor may not be in memory at all.
2117 DECL_INITIAL (decl) would be error_mark_node in that case. */
2118 gcc_assert (!node
->lto_file_data
);
2119 tree ctor
= DECL_INITIAL (decl
);
2120 inchash::hash hstate
;
2122 hstate
.add_int (456346417);
2123 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2124 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2125 add_expr (ctor
, hstate
);
2126 set_hash (hstate
.end ());
2131 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2135 sem_variable::merge (sem_item
*alias_item
)
2137 gcc_assert (alias_item
->type
== VAR
);
2139 if (!sem_item::target_supports_symbol_aliases_p ())
2142 fprintf (dump_file
, "Not unifying; "
2143 "Symbol aliases are not supported by target\n\n");
2147 if (DECL_EXTERNAL (alias_item
->decl
))
2150 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2154 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2156 varpool_node
*original
= get_node ();
2157 varpool_node
*alias
= alias_var
->get_node ();
2158 bool original_discardable
= false;
2160 bool original_address_matters
= original
->address_matters_p ();
2161 bool alias_address_matters
= alias
->address_matters_p ();
2163 /* See if original is in a section that can be discarded if the main
2165 Also consider case where we have resolution info and we know that
2166 original's definition is not going to be used. In this case we can not
2167 create alias to original. */
2168 if (original
->can_be_discarded_p ()
2169 || (node
->resolution
!= LDPR_UNKNOWN
2170 && !decl_binds_to_current_def_p (node
->decl
)))
2171 original_discardable
= true;
2173 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2175 /* Constant pool machinery is not quite ready for aliases.
2176 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2177 For LTO merging does not happen that is an important missing feature.
2178 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2179 flag is dropped and non-local symbol name is assigned. */
2180 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2181 || DECL_IN_CONSTANT_POOL (original
->decl
))
2185 "Not unifying; constant pool variables.\n\n");
2189 /* Do not attempt to mix functions from different user sections;
2190 we do not know what user intends with those. */
2191 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2192 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2193 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2198 "original and alias are in different sections.\n\n");
2202 /* We can not merge if address comparsion metters. */
2203 if (original_address_matters
&& alias_address_matters
2204 && flag_merge_constants
< 2)
2209 "adress of original and alias may be compared.\n\n");
2212 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2215 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2216 "across comdat group boundary\n\n");
2221 if (original_discardable
)
2224 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2225 "target is discardable\n\n");
2231 gcc_assert (!original
->alias
);
2232 gcc_assert (!alias
->alias
);
2234 alias
->analyzed
= false;
2236 DECL_INITIAL (alias
->decl
) = NULL
;
2237 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2239 alias
->need_bounds_init
= false;
2240 alias
->remove_all_references ();
2241 if (TREE_ADDRESSABLE (alias
->decl
))
2242 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2244 varpool_node::create_alias (alias_var
->decl
, decl
);
2245 alias
->resolve_alias (original
);
2248 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2254 /* Dump symbol to FILE. */
2257 sem_variable::dump_to_file (FILE *file
)
2261 print_node (file
, "", decl
, 0);
2262 fprintf (file
, "\n\n");
2265 unsigned int sem_item_optimizer::class_id
= 0;
2267 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2268 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2271 bitmap_obstack_initialize (&m_bmstack
);
2274 sem_item_optimizer::~sem_item_optimizer ()
2276 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2279 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2280 it
!= m_classes
.end (); ++it
)
2282 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2283 delete (*it
)->classes
[i
];
2285 (*it
)->classes
.release ();
2291 bitmap_obstack_release (&m_bmstack
);
2294 /* Write IPA ICF summary for symbols. */
2297 sem_item_optimizer::write_summary (void)
2299 unsigned int count
= 0;
2301 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2302 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2305 /* Calculate number of symbols to be serialized. */
2306 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2308 lsei_next_in_partition (&lsei
))
2310 symtab_node
*node
= lsei_node (lsei
);
2312 if (m_symtab_node_map
.get (node
))
2316 streamer_write_uhwi (ob
, count
);
2318 /* Process all of the symbols. */
2319 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2321 lsei_next_in_partition (&lsei
))
2323 symtab_node
*node
= lsei_node (lsei
);
2325 sem_item
**item
= m_symtab_node_map
.get (node
);
2329 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2330 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2332 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2336 streamer_write_char_stream (ob
->main_stream
, 0);
2337 produce_asm (ob
, NULL
);
2338 destroy_output_block (ob
);
2341 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2342 contains LEN bytes. */
2345 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2346 const char *data
, size_t len
)
2348 const lto_function_header
*header
=
2349 (const lto_function_header
*) data
;
2350 const int cfg_offset
= sizeof (lto_function_header
);
2351 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2352 const int string_offset
= main_offset
+ header
->main_size
;
2357 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2358 header
->main_size
, file_data
->mode_table
);
2361 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2362 header
->string_size
, vNULL
);
2364 count
= streamer_read_uhwi (&ib_main
);
2366 for (i
= 0; i
< count
; i
++)
2370 lto_symtab_encoder_t encoder
;
2372 index
= streamer_read_uhwi (&ib_main
);
2373 encoder
= file_data
->symtab_node_encoder
;
2374 node
= lto_symtab_encoder_deref (encoder
, index
);
2376 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2378 gcc_assert (node
->definition
);
2381 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2382 node
->asm_name (), (void *) node
->decl
, node
->order
);
2384 if (is_a
<cgraph_node
*> (node
))
2386 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2388 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2392 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2394 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2398 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2400 lto_data_in_delete (data_in
);
2403 /* Read IPA ICF summary for symbols. */
2406 sem_item_optimizer::read_summary (void)
2408 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2409 lto_file_decl_data
*file_data
;
2412 while ((file_data
= file_data_vec
[j
++]))
2415 const char *data
= lto_get_section_data (file_data
,
2416 LTO_section_ipa_icf
, NULL
, &len
);
2419 read_section (file_data
, data
, len
);
2423 /* Register callgraph and varpool hooks. */
2426 sem_item_optimizer::register_hooks (void)
2428 if (!m_cgraph_node_hooks
)
2429 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2430 (&sem_item_optimizer::cgraph_removal_hook
, this);
2432 if (!m_varpool_node_hooks
)
2433 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2434 (&sem_item_optimizer::varpool_removal_hook
, this);
2437 /* Unregister callgraph and varpool hooks. */
2440 sem_item_optimizer::unregister_hooks (void)
2442 if (m_cgraph_node_hooks
)
2443 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2445 if (m_varpool_node_hooks
)
2446 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2449 /* Adds a CLS to hashtable associated by hash value. */
2452 sem_item_optimizer::add_class (congruence_class
*cls
)
2454 gcc_assert (cls
->members
.length ());
2456 congruence_class_group
*group
= get_group_by_hash (
2457 cls
->members
[0]->get_hash (),
2458 cls
->members
[0]->type
);
2459 group
->classes
.safe_push (cls
);
2462 /* Gets a congruence class group based on given HASH value and TYPE. */
2464 congruence_class_group
*
2465 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2467 congruence_class_group
*item
= XNEW (congruence_class_group
);
2471 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2477 item
->classes
.create (1);
2484 /* Callgraph removal hook called for a NODE with a custom DATA. */
2487 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2489 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2490 optimizer
->remove_symtab_node (node
);
2493 /* Varpool removal hook called for a NODE with a custom DATA. */
2496 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2498 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2499 optimizer
->remove_symtab_node (node
);
2502 /* Remove symtab NODE triggered by symtab removal hooks. */
2505 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2507 gcc_assert (!m_classes
.elements());
2509 m_removed_items_set
.add (node
);
2513 sem_item_optimizer::remove_item (sem_item
*item
)
2515 if (m_symtab_node_map
.get (item
->node
))
2516 m_symtab_node_map
.remove (item
->node
);
2520 /* Removes all callgraph and varpool nodes that are marked by symtab
2524 sem_item_optimizer::filter_removed_items (void)
2526 auto_vec
<sem_item
*> filtered
;
2528 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2530 sem_item
*item
= m_items
[i
];
2532 if (m_removed_items_set
.contains (item
->node
))
2538 if (item
->type
== FUNC
)
2540 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2542 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2545 filtered
.safe_push (item
);
2549 if (!flag_ipa_icf_variables
)
2553 /* Filter out non-readonly variables. */
2554 tree decl
= item
->decl
;
2555 if (TREE_READONLY (decl
))
2556 filtered
.safe_push (item
);
2563 /* Clean-up of released semantic items. */
2566 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2567 m_items
.safe_push (filtered
[i
]);
2570 /* Optimizer entry point which returns true in case it processes
2571 a merge operation. True is returned if there's a merge operation
2575 sem_item_optimizer::execute (void)
2577 filter_removed_items ();
2578 unregister_hooks ();
2581 update_hash_by_addr_refs ();
2582 build_hash_based_classes ();
2585 fprintf (dump_file
, "Dump after hash based groups\n");
2586 dump_cong_classes ();
2588 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2589 m_items
[i
]->init_wpa ();
2591 subdivide_classes_by_equality (true);
2594 fprintf (dump_file
, "Dump after WPA based types groups\n");
2596 dump_cong_classes ();
2598 process_cong_reduction ();
2599 checking_verify_classes ();
2602 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2604 dump_cong_classes ();
2606 parse_nonsingleton_classes ();
2607 subdivide_classes_by_equality ();
2610 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2612 dump_cong_classes ();
2614 unsigned int prev_class_count
= m_classes_count
;
2616 process_cong_reduction ();
2617 dump_cong_classes ();
2618 checking_verify_classes ();
2619 bool merged_p
= merge_classes (prev_class_count
);
2621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2622 symtab_node::dump_table (dump_file
);
2627 /* Function responsible for visiting all potential functions and
2628 read-only variables that can be merged. */
2631 sem_item_optimizer::parse_funcs_and_vars (void)
2635 if (flag_ipa_icf_functions
)
2636 FOR_EACH_DEFINED_FUNCTION (cnode
)
2638 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2641 m_items
.safe_push (f
);
2642 m_symtab_node_map
.put (cnode
, f
);
2645 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2648 f
->dump_to_file (dump_file
);
2651 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2654 varpool_node
*vnode
;
2656 if (flag_ipa_icf_variables
)
2657 FOR_EACH_DEFINED_VARIABLE (vnode
)
2659 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2663 m_items
.safe_push (v
);
2664 m_symtab_node_map
.put (vnode
, v
);
2669 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2672 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2674 item
->index_in_class
= cls
->members
.length ();
2675 cls
->members
.safe_push (item
);
2679 /* For each semantic item, append hash values of references. */
2682 sem_item_optimizer::update_hash_by_addr_refs ()
2684 /* First, append to hash sensitive references and class type if it need to
2685 be matched for ODR. */
2686 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2688 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2689 if (m_items
[i
]->type
== FUNC
)
2691 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2692 && contains_polymorphic_type_p
2693 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2694 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2695 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2696 && static_cast<sem_function
*> (m_items
[i
])
2697 ->compare_polymorphic_p ())))
2700 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2701 inchash::hash
hstate (m_items
[i
]->get_hash ());
2703 if (TYPE_NAME (class_type
)
2704 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2706 (IDENTIFIER_HASH_VALUE
2707 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2709 m_items
[i
]->set_hash (hstate
.end ());
2714 /* Once all symbols have enhanced hash value, we can append
2715 hash values of symbols that are seen by IPA ICF and are
2716 references by a semantic item. Newly computed values
2717 are saved to global_hash member variable. */
2718 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2719 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2721 /* Global hash value replace current hash values. */
2722 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2723 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2726 /* Congruence classes are built by hash value. */
2729 sem_item_optimizer::build_hash_based_classes (void)
2731 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2733 sem_item
*item
= m_items
[i
];
2735 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2738 if (!group
->classes
.length ())
2741 group
->classes
.safe_push (new congruence_class (class_id
++));
2744 add_item_to_class (group
->classes
[0], item
);
2748 /* Build references according to call graph. */
2751 sem_item_optimizer::build_graph (void)
2753 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2755 sem_item
*item
= m_items
[i
];
2756 m_symtab_node_map
.put (item
->node
, item
);
2758 /* Initialize hash values if we are not in LTO mode. */
2763 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2765 sem_item
*item
= m_items
[i
];
2767 if (item
->type
== FUNC
)
2769 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2771 cgraph_edge
*e
= cnode
->callees
;
2774 sem_item
**slot
= m_symtab_node_map
.get
2775 (e
->callee
->ultimate_alias_target ());
2777 item
->add_reference (*slot
);
2783 ipa_ref
*ref
= NULL
;
2784 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2786 sem_item
**slot
= m_symtab_node_map
.get
2787 (ref
->referred
->ultimate_alias_target ());
2789 item
->add_reference (*slot
);
2794 /* Semantic items in classes having more than one element and initialized.
2795 In case of WPA, we load function body. */
2798 sem_item_optimizer::parse_nonsingleton_classes (void)
2800 unsigned int init_called_count
= 0;
2802 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2803 if (m_items
[i
]->cls
->members
.length () > 1)
2805 m_items
[i
]->init ();
2806 init_called_count
++;
2810 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2811 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2814 /* Equality function for semantic items is used to subdivide existing
2815 classes. If IN_WPA, fast equality function is invoked. */
2818 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2820 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2821 it
!= m_classes
.end (); ++it
)
2823 unsigned int class_count
= (*it
)->classes
.length ();
2825 for (unsigned i
= 0; i
< class_count
; i
++)
2827 congruence_class
*c
= (*it
)->classes
[i
];
2829 if (c
->members
.length() > 1)
2831 auto_vec
<sem_item
*> new_vector
;
2833 sem_item
*first
= c
->members
[0];
2834 new_vector
.safe_push (first
);
2836 unsigned class_split_first
= (*it
)->classes
.length ();
2838 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2840 sem_item
*item
= c
->members
[j
];
2842 bool equals
= in_wpa
? first
->equals_wpa (item
,
2843 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2846 new_vector
.safe_push (item
);
2849 bool integrated
= false;
2851 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2853 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2854 bool equals
= in_wpa
? x
->equals_wpa (item
,
2855 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2860 add_item_to_class ((*it
)->classes
[k
], item
);
2868 congruence_class
*c
= new congruence_class (class_id
++);
2870 add_item_to_class (c
, item
);
2872 (*it
)->classes
.safe_push (c
);
2877 // we replace newly created new_vector for the class we've just splitted
2878 c
->members
.release ();
2879 c
->members
.create (new_vector
.length ());
2881 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2882 add_item_to_class (c
, new_vector
[j
]);
2887 checking_verify_classes ();
2890 /* Subdivide classes by address references that members of the class
2891 reference. Example can be a pair of functions that have an address
2892 taken from a function. If these addresses are different the class
2896 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2898 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2900 unsigned newly_created_classes
= 0;
2902 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2903 it
!= m_classes
.end (); ++it
)
2905 unsigned int class_count
= (*it
)->classes
.length ();
2906 auto_vec
<congruence_class
*> new_classes
;
2908 for (unsigned i
= 0; i
< class_count
; i
++)
2910 congruence_class
*c
= (*it
)->classes
[i
];
2912 if (c
->members
.length() > 1)
2914 subdivide_hash_map split_map
;
2916 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2918 sem_item
*source_node
= c
->members
[j
];
2920 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2923 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2925 gcc_checking_assert (slot
);
2927 slot
->safe_push (source_node
);
2933 /* If the map contains more than one key, we have to split the map
2935 if (split_map
.elements () != 1)
2937 bool first_class
= true;
2939 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2940 it2
!= split_map
.end (); ++it2
)
2942 congruence_class
*new_cls
;
2943 new_cls
= new congruence_class (class_id
++);
2945 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2946 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2948 worklist_push (new_cls
);
2949 newly_created_classes
++;
2953 (*it
)->classes
[i
] = new_cls
;
2954 first_class
= false;
2958 new_classes
.safe_push (new_cls
);
2964 /* Release memory. */
2965 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2966 it2
!= split_map
.end (); ++it2
)
2968 delete (*it2
).first
;
2969 (*it2
).second
.release ();
2974 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2975 (*it
)->classes
.safe_push (new_classes
[i
]);
2978 return newly_created_classes
;
2981 /* Verify congruence classes, if checking is enabled. */
2984 sem_item_optimizer::checking_verify_classes (void)
2990 /* Verify congruence classes. */
2993 sem_item_optimizer::verify_classes (void)
2995 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2996 it
!= m_classes
.end (); ++it
)
2998 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3000 congruence_class
*cls
= (*it
)->classes
[i
];
3003 gcc_assert (cls
->members
.length () > 0);
3005 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3007 sem_item
*item
= cls
->members
[j
];
3010 gcc_assert (item
->cls
== cls
);
3012 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3014 sem_usage_pair
*usage
= item
->usages
[k
];
3015 gcc_assert (usage
->item
->index_in_class
<
3016 usage
->item
->cls
->members
.length ());
3023 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3024 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3025 but unused argument. */
3028 sem_item_optimizer::release_split_map (congruence_class
* const &,
3029 bitmap
const &b
, traverse_split_pair
*)
3038 /* Process split operation for a class given as pointer CLS_PTR,
3039 where bitmap B splits congruence class members. DATA is used
3040 as argument of split pair. */
3043 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3044 bitmap
const &b
, traverse_split_pair
*pair
)
3046 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3047 const congruence_class
*splitter_cls
= pair
->cls
;
3049 /* If counted bits are greater than zero and less than the number of members
3050 a group will be splitted. */
3051 unsigned popcount
= bitmap_count_bits (b
);
3053 if (popcount
> 0 && popcount
< cls
->members
.length ())
3055 auto_vec
<congruence_class
*, 2> newclasses
;
3056 newclasses
.quick_push (new congruence_class (class_id
++));
3057 newclasses
.quick_push (new congruence_class (class_id
++));
3059 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3061 int target
= bitmap_bit_p (b
, i
);
3062 congruence_class
*tc
= newclasses
[target
];
3064 add_item_to_class (tc
, cls
->members
[i
]);
3069 for (unsigned int i
= 0; i
< 2; i
++)
3070 gcc_assert (newclasses
[i
]->members
.length ());
3073 if (splitter_cls
== cls
)
3074 optimizer
->splitter_class_removed
= true;
3076 /* Remove old class from worklist if presented. */
3077 bool in_worklist
= cls
->in_worklist
;
3080 cls
->in_worklist
= false;
3082 congruence_class_group g
;
3083 g
.hash
= cls
->members
[0]->get_hash ();
3084 g
.type
= cls
->members
[0]->type
;
3086 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3088 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3089 if (slot
->classes
[i
] == cls
)
3091 slot
->classes
.ordered_remove (i
);
3095 /* New class will be inserted and integrated to work list. */
3096 for (unsigned int i
= 0; i
< 2; i
++)
3097 optimizer
->add_class (newclasses
[i
]);
3099 /* Two classes replace one, so that increment just by one. */
3100 optimizer
->m_classes_count
++;
3102 /* If OLD class was presented in the worklist, we remove the class
3103 and replace it will both newly created classes. */
3105 for (unsigned int i
= 0; i
< 2; i
++)
3106 optimizer
->worklist_push (newclasses
[i
]);
3107 else /* Just smaller class is inserted. */
3109 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3110 newclasses
[1]->members
.length () ?
3112 optimizer
->worklist_push (newclasses
[smaller_index
]);
3115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3117 fprintf (dump_file
, " congruence class splitted:\n");
3118 cls
->dump (dump_file
, 4);
3120 fprintf (dump_file
, " newly created groups:\n");
3121 for (unsigned int i
= 0; i
< 2; i
++)
3122 newclasses
[i
]->dump (dump_file
, 4);
3125 /* Release class if not presented in work list. */
3134 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3135 Bitmap stack BMSTACK is used for bitmap allocation. */
3138 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3141 hash_map
<congruence_class
*, bitmap
> split_map
;
3143 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3145 sem_item
*item
= cls
->members
[i
];
3147 /* Iterate all usages that have INDEX as usage of the item. */
3148 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3150 sem_usage_pair
*usage
= item
->usages
[j
];
3152 if (usage
->index
!= index
)
3155 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3160 b
= BITMAP_ALLOC (&m_bmstack
);
3161 split_map
.put (usage
->item
->cls
, b
);
3166 gcc_checking_assert (usage
->item
->cls
);
3167 gcc_checking_assert (usage
->item
->index_in_class
<
3168 usage
->item
->cls
->members
.length ());
3170 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3174 traverse_split_pair pair
;
3175 pair
.optimizer
= this;
3178 splitter_class_removed
= false;
3180 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3182 /* Bitmap clean-up. */
3184 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3187 /* Every usage of a congruence class CLS is a candidate that can split the
3188 collection of classes. Bitmap stack BMSTACK is used for bitmap
3192 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3197 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3199 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3200 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3202 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3205 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3208 do_congruence_step_for_index (cls
, i
);
3210 if (splitter_class_removed
)
3214 BITMAP_FREE (usage
);
3217 /* Adds a newly created congruence class CLS to worklist. */
3220 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3222 /* Return if the class CLS is already presented in work list. */
3223 if (cls
->in_worklist
)
3226 cls
->in_worklist
= true;
3227 worklist
.push_back (cls
);
3230 /* Pops a class from worklist. */
3233 sem_item_optimizer::worklist_pop (void)
3235 congruence_class
*cls
;
3237 while (!worklist
.empty ())
3239 cls
= worklist
.front ();
3240 worklist
.pop_front ();
3241 if (cls
->in_worklist
)
3243 cls
->in_worklist
= false;
3249 /* Work list item was already intended to be removed.
3250 The only reason for doing it is to split a class.
3251 Thus, the class CLS is deleted. */
3259 /* Iterative congruence reduction function. */
3262 sem_item_optimizer::process_cong_reduction (void)
3264 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3265 it
!= m_classes
.end (); ++it
)
3266 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3267 if ((*it
)->classes
[i
]->is_class_used ())
3268 worklist_push ((*it
)->classes
[i
]);
3271 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3272 (unsigned long) worklist
.size ());
3274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3275 fprintf (dump_file
, "Congruence class reduction\n");
3277 congruence_class
*cls
;
3279 /* Process complete congruence reduction. */
3280 while ((cls
= worklist_pop ()) != NULL
)
3281 do_congruence_step (cls
);
3283 /* Subdivide newly created classes according to references. */
3284 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3287 fprintf (dump_file
, "Address reference subdivision created: %u "
3288 "new classes.\n", new_classes
);
3291 /* Debug function prints all informations about congruence classes. */
3294 sem_item_optimizer::dump_cong_classes (void)
3300 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3301 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3303 /* Histogram calculation. */
3304 unsigned int max_index
= 0;
3305 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3307 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3308 it
!= m_classes
.end (); ++it
)
3310 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3312 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3320 "Class size histogram [num of members]: number of classe number of classess\n");
3322 for (unsigned int i
= 0; i
<= max_index
; i
++)
3324 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3326 fprintf (dump_file
, "\n\n");
3329 if (dump_flags
& TDF_DETAILS
)
3330 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3331 it
!= m_classes
.end (); ++it
)
3333 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3335 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3337 (*it
)->classes
[i
]->dump (dump_file
, 4);
3339 if(i
< (*it
)->classes
.length () - 1)
3340 fprintf (dump_file
, " ");
3347 /* After reduction is done, we can declare all items in a group
3348 to be equal. PREV_CLASS_COUNT is start number of classes
3349 before reduction. True is returned if there's a merge operation
3353 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3355 unsigned int item_count
= m_items
.length ();
3356 unsigned int class_count
= m_classes_count
;
3357 unsigned int equal_items
= item_count
- class_count
;
3359 unsigned int non_singular_classes_count
= 0;
3360 unsigned int non_singular_classes_sum
= 0;
3362 bool merged_p
= false;
3364 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3365 it
!= m_classes
.end (); ++it
)
3366 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3368 congruence_class
*c
= (*it
)->classes
[i
];
3369 if (c
->members
.length () > 1)
3371 non_singular_classes_count
++;
3372 non_singular_classes_sum
+= c
->members
.length ();
3378 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3379 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3380 prev_class_count
, class_count
);
3381 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3382 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3383 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3384 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3385 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3386 non_singular_classes_count
: 0.0f
,
3387 non_singular_classes_count
);
3388 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3389 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3390 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3393 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3394 it
!= m_classes
.end (); ++it
)
3395 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3397 congruence_class
*c
= (*it
)->classes
[i
];
3399 if (c
->members
.length () == 1)
3402 sem_item
*source
= c
->members
[0];
3404 if (DECL_NAME (source
->decl
)
3405 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3406 /* If merge via wrappers, picking main as the target can be
3408 source
= c
->members
[1];
3410 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3412 sem_item
*alias
= c
->members
[j
];
3414 if (alias
== source
)
3419 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3420 xstrdup_for_dump (source
->node
->name ()),
3421 xstrdup_for_dump (alias
->node
->name ()));
3422 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3423 xstrdup_for_dump (source
->node
->asm_name ()),
3424 xstrdup_for_dump (alias
->node
->asm_name ()));
3427 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3431 "Merge operation is skipped due to no_icf "
3437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3439 source
->dump_to_file (dump_file
);
3440 alias
->dump_to_file (dump_file
);
3443 if (dbg_cnt (merged_ipa_icf
))
3444 merged_p
|= source
->merge (alias
);
3451 /* Dump function prints all class members to a FILE with an INDENT. */
3454 congruence_class::dump (FILE *file
, unsigned int indent
) const
3456 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3457 id
, members
[0]->get_hash (), members
.length ());
3459 FPUTS_SPACES (file
, indent
+ 2, "");
3460 for (unsigned i
= 0; i
< members
.length (); i
++)
3461 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3462 (void *) members
[i
]->decl
,
3463 members
[i
]->node
->order
);
3465 fprintf (file
, "\n");
3468 /* Returns true if there's a member that is used from another group. */
3471 congruence_class::is_class_used (void)
3473 for (unsigned int i
= 0; i
< members
.length (); i
++)
3474 if (members
[i
]->usages
.length ())
3480 /* Generate pass summary for IPA ICF pass. */
3483 ipa_icf_generate_summary (void)
3486 optimizer
= new sem_item_optimizer ();
3488 optimizer
->register_hooks ();
3489 optimizer
->parse_funcs_and_vars ();
3492 /* Write pass summary for IPA ICF pass. */
3495 ipa_icf_write_summary (void)
3497 gcc_assert (optimizer
);
3499 optimizer
->write_summary ();
3502 /* Read pass summary for IPA ICF pass. */
3505 ipa_icf_read_summary (void)
3508 optimizer
= new sem_item_optimizer ();
3510 optimizer
->read_summary ();
3511 optimizer
->register_hooks ();
3514 /* Semantic equality exection function. */
3517 ipa_icf_driver (void)
3519 gcc_assert (optimizer
);
3521 bool merged_p
= optimizer
->execute ();
3526 return merged_p
? TODO_remove_functions
: 0;
3529 const pass_data pass_data_ipa_icf
=
3531 IPA_PASS
, /* type */
3533 OPTGROUP_IPA
, /* optinfo_flags */
3534 TV_IPA_ICF
, /* tv_id */
3535 0, /* properties_required */
3536 0, /* properties_provided */
3537 0, /* properties_destroyed */
3538 0, /* todo_flags_start */
3539 0, /* todo_flags_finish */
3542 class pass_ipa_icf
: public ipa_opt_pass_d
3545 pass_ipa_icf (gcc::context
*ctxt
)
3546 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3547 ipa_icf_generate_summary
, /* generate_summary */
3548 ipa_icf_write_summary
, /* write_summary */
3549 ipa_icf_read_summary
, /* read_summary */
3551 write_optimization_summary */
3553 read_optimization_summary */
3554 NULL
, /* stmt_fixup */
3555 0, /* function_transform_todo_flags_start */
3556 NULL
, /* function_transform */
3557 NULL
) /* variable_transform */
3560 /* opt_pass methods: */
3561 virtual bool gate (function
*)
3563 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3566 virtual unsigned int execute (function
*)
3568 return ipa_icf_driver();
3570 }; // class pass_ipa_icf
3572 } // ipa_icf namespace
3575 make_pass_ipa_icf (gcc::context
*ctxt
)
3577 return new ipa_icf::pass_ipa_icf (ctxt
);