1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2016 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
135 item (_item
), index (_index
)
139 /* 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
))
304 (cl_optimization_hash
305 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
306 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
307 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
309 set_hash (hstate
.end ());
315 /* Return ture if A1 and A2 represent equivalent function attribute lists.
316 Based on comp_type_attributes. */
319 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
324 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
326 const struct attribute_spec
*as
;
329 as
= lookup_attribute_spec (get_attribute_name (a
));
330 /* TODO: We can introduce as->affects_decl_identity
331 and as->affects_decl_reference_identity if attribute mismatch
332 gets a common reason to give up on merging. It may not be worth
334 For example returns_nonnull affects only references, while
335 optimize attribute can be ignored because it is already lowered
336 into flags representation and compared separately. */
340 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
341 if (!attr
|| !attribute_value_equal (a
, attr
))
346 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
348 const struct attribute_spec
*as
;
350 as
= lookup_attribute_spec (get_attribute_name (a
));
354 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
356 /* We don't need to compare trees again, as we did this
357 already in first loop. */
362 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
366 /* Compare properties of symbols N1 and N2 that does not affect semantics of
367 symbol itself but affects semantics of its references from USED_BY (which
368 may be NULL if it is unknown). If comparsion is false, symbols
369 can still be merged but any symbols referring them can't.
371 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
373 TODO: We can also split attributes to those that determine codegen of
374 a function body/variable constructor itself and those that are used when
378 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
383 if (is_a
<cgraph_node
*> (n1
))
385 /* Inline properties matters: we do now want to merge uses of inline
386 function to uses of normal function because inline hint would be lost.
387 We however can merge inline function to noinline because the alias
388 will keep its DECL_DECLARED_INLINE flag.
390 Also ignore inline flag when optimizing for size or when function
391 is known to not be inlinable.
393 TODO: the optimize_size checks can also be assumed to be true if
394 unit has no !optimize_size functions. */
396 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
397 || !opt_for_fn (used_by
->decl
, optimize_size
))
398 && !opt_for_fn (n1
->decl
, optimize_size
)
399 && n1
->get_availability () > AVAIL_INTERPOSABLE
400 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
402 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
403 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
404 return return_false_with_msg
405 ("DECL_DISREGARD_INLINE_LIMITS are different");
407 if (DECL_DECLARED_INLINE_P (n1
->decl
)
408 != DECL_DECLARED_INLINE_P (n2
->decl
))
409 return return_false_with_msg ("inline attributes are different");
412 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
413 != DECL_IS_OPERATOR_NEW (n2
->decl
))
414 return return_false_with_msg ("operator new flags are different");
417 /* Merging two definitions with a reference to equivalent vtables, but
418 belonging to a different type may result in ipa-polymorphic-call analysis
419 giving a wrong answer about the dynamic type of instance. */
420 if (is_a
<varpool_node
*> (n1
))
422 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
423 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
424 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
425 DECL_CONTEXT (n2
->decl
)))
426 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
427 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
428 return return_false_with_msg
429 ("references to virtual tables can not be merged");
431 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
432 return return_false_with_msg ("alignment mismatch");
434 /* For functions we compare attributes in equals_wpa, because we do
435 not know what attributes may cause codegen differences, but for
436 variables just compare attributes for references - the codegen
437 for constructors is affected only by those attributes that we lower
438 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
439 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
440 DECL_ATTRIBUTES (n2
->decl
)))
441 return return_false_with_msg ("different var decl attributes");
442 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
443 TREE_TYPE (n2
->decl
)) != 1)
444 return return_false_with_msg ("different var type attributes");
447 /* When matching virtual tables, be sure to also match information
448 relevant for polymorphic call analysis. */
449 if (used_by
&& is_a
<varpool_node
*> (used_by
)
450 && DECL_VIRTUAL_P (used_by
->decl
))
452 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
453 return return_false_with_msg ("virtual flag mismatch");
454 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
455 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
456 return return_false_with_msg ("final flag mismatch");
461 /* Hash properties that are compared by compare_referenced_symbol_properties. */
464 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
465 inchash::hash
&hstate
,
468 if (is_a
<cgraph_node
*> (ref
))
470 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
471 && !opt_for_fn (ref
->decl
, optimize_size
)
472 && !DECL_UNINLINABLE (ref
->decl
))
474 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
475 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
477 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
479 else if (is_a
<varpool_node
*> (ref
))
481 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
483 hstate
.add_int (DECL_ALIGN (ref
->decl
));
488 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
489 point to a same function. Comparison can be skipped if IGNORED_NODES
490 contains these nodes. ADDRESS indicate if address is taken. */
493 sem_item::compare_symbol_references (
494 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
495 symtab_node
*n1
, symtab_node
*n2
, bool address
)
497 enum availability avail1
, avail2
;
502 /* Never match variable and function. */
503 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
506 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
508 if (address
&& n1
->equal_address_to (n2
) == 1)
510 if (!address
&& n1
->semantically_equivalent_p (n2
))
513 n1
= n1
->ultimate_alias_target (&avail1
);
514 n2
= n2
->ultimate_alias_target (&avail2
);
516 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
517 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
520 return return_false_with_msg ("different references");
523 /* If cgraph edges E1 and E2 are indirect calls, verify that
524 ECF flags are the same. */
526 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
528 if (e1
->indirect_info
&& e2
->indirect_info
)
530 int e1_flags
= e1
->indirect_info
->ecf_flags
;
531 int e2_flags
= e2
->indirect_info
->ecf_flags
;
533 if (e1_flags
!= e2_flags
)
534 return return_false_with_msg ("ICF flags are different");
536 else if (e1
->indirect_info
|| e2
->indirect_info
)
542 /* Return true if parameter I may be used. */
545 sem_function::param_used_p (unsigned int i
)
547 if (ipa_node_params_sum
== NULL
)
550 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
552 if (parms_info
->descriptors
.is_empty ()
553 || parms_info
->descriptors
.length () <= i
)
556 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
559 /* Perform additional check needed to match types function parameters that are
560 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
561 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
564 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
566 /* Be sure that parameters are TBAA compatible. */
567 if (!func_checker::compatible_types_p (parm1
, parm2
))
568 return return_false_with_msg ("parameter type is not compatible");
570 if (POINTER_TYPE_P (parm1
)
571 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
572 return return_false_with_msg ("argument restrict flag mismatch");
574 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
575 if (POINTER_TYPE_P (parm1
)
576 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
577 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
578 return return_false_with_msg ("pointer wrt reference mismatch");
583 /* Fast equality function based on knowledge known in WPA. */
586 sem_function::equals_wpa (sem_item
*item
,
587 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
589 gcc_assert (item
->type
== FUNC
);
590 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
591 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
593 m_compared_func
= static_cast<sem_function
*> (item
);
595 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
596 return return_false_with_msg ("thunk_p mismatch");
598 if (cnode
->thunk
.thunk_p
)
600 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
601 return return_false_with_msg ("thunk fixed_offset mismatch");
602 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
603 return return_false_with_msg ("thunk virtual_value mismatch");
604 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
605 return return_false_with_msg ("thunk this_adjusting mismatch");
606 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
607 return return_false_with_msg ("thunk virtual_offset_p mismatch");
608 if (cnode
->thunk
.add_pointer_bounds_args
609 != cnode2
->thunk
.add_pointer_bounds_args
)
610 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
613 /* Compare special function DECL attributes. */
614 if (DECL_FUNCTION_PERSONALITY (decl
)
615 != DECL_FUNCTION_PERSONALITY (item
->decl
))
616 return return_false_with_msg ("function personalities are different");
618 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
619 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
620 return return_false_with_msg ("intrument function entry exit "
621 "attributes are different");
623 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
624 return return_false_with_msg ("no stack limit attributes are different");
626 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
627 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
629 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
630 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
632 /* TODO: pure/const flags mostly matters only for references, except for
633 the fact that codegen takes LOOPING flag as a hint that loops are
634 finite. We may arrange the code to always pick leader that has least
635 specified flags and then this can go into comparing symbol properties. */
636 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
637 return return_false_with_msg ("decl_or_type flags are different");
639 /* Do not match polymorphic constructors of different types. They calls
640 type memory location for ipa-polymorphic-call and we do not want
641 it to get confused by wrong type. */
642 if (DECL_CXX_CONSTRUCTOR_P (decl
)
643 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
645 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
646 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
647 else if (!func_checker::compatible_polymorphic_types_p
648 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
649 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
650 return return_false_with_msg ("ctor polymorphic type mismatch");
653 /* Checking function TARGET and OPTIMIZATION flags. */
654 cl_target_option
*tar1
= target_opts_for_fn (decl
);
655 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
657 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
659 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
661 fprintf (dump_file
, "target flags difference");
662 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
665 return return_false_with_msg ("Target flags are different");
668 cl_optimization
*opt1
= opts_for_fn (decl
);
669 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
671 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
675 fprintf (dump_file
, "optimization flags difference");
676 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
679 return return_false_with_msg ("optimization flags are different");
682 /* Result type checking. */
683 if (!func_checker::compatible_types_p
684 (TREE_TYPE (TREE_TYPE (decl
)),
685 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
686 return return_false_with_msg ("result types are different");
688 /* Checking types of arguments. */
689 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
690 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
691 for (unsigned i
= 0; list1
&& list2
;
692 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
694 tree parm1
= TREE_VALUE (list1
);
695 tree parm2
= TREE_VALUE (list2
);
697 /* This guard is here for function pointer with attributes (pr59927.c). */
698 if (!parm1
|| !parm2
)
699 return return_false_with_msg ("NULL argument type");
701 /* Verify that types are compatible to ensure that both functions
702 have same calling conventions. */
703 if (!types_compatible_p (parm1
, parm2
))
704 return return_false_with_msg ("parameter types are not compatible");
706 if (!param_used_p (i
))
709 /* Perform additional checks for used parameters. */
710 if (!compatible_parm_types_p (parm1
, parm2
))
715 return return_false_with_msg ("Mismatched number of parameters");
717 if (node
->num_references () != item
->node
->num_references ())
718 return return_false_with_msg ("different number of references");
720 /* Checking function attributes.
721 This is quadratic in number of attributes */
722 if (comp_type_attributes (TREE_TYPE (decl
),
723 TREE_TYPE (item
->decl
)) != 1)
724 return return_false_with_msg ("different type attributes");
725 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
726 DECL_ATTRIBUTES (item
->decl
)))
727 return return_false_with_msg ("different decl attributes");
729 /* The type of THIS pointer type memory location for
730 ipa-polymorphic-call-analysis. */
731 if (opt_for_fn (decl
, flag_devirtualize
)
732 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
733 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
735 && compare_polymorphic_p ())
737 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
738 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
739 if (!func_checker::compatible_polymorphic_types_p
740 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
741 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
742 return return_false_with_msg ("THIS pointer ODR type mismatch");
745 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
746 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
748 item
->node
->iterate_reference (i
, ref2
);
750 if (ref
->use
!= ref2
->use
)
751 return return_false_with_msg ("reference use mismatch");
753 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
755 ref
->address_matters_p ()))
759 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
760 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
764 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
767 if (!compare_edge_flags (e1
, e2
))
770 e1
= e1
->next_callee
;
771 e2
= e2
->next_callee
;
775 return return_false_with_msg ("different number of calls");
777 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
778 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
782 if (!compare_edge_flags (e1
, e2
))
785 e1
= e1
->next_callee
;
786 e2
= e2
->next_callee
;
790 return return_false_with_msg ("different number of indirect calls");
795 /* Update hash by address sensitive references. We iterate over all
796 sensitive references (address_matters_p) and we hash ultime alias
797 target of these nodes, which can improve a semantic item hash.
799 Also hash in referenced symbols properties. This can be done at any time
800 (as the properties should not change), but it is convenient to do it here
801 while we walk the references anyway. */
804 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
805 sem_item
*> &m_symtab_node_map
)
808 inchash::hash
hstate (get_hash ());
810 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
812 hstate
.add_int (ref
->use
);
813 hash_referenced_symbol_properties (ref
->referred
, hstate
,
814 ref
->use
== IPA_REF_ADDR
);
815 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
816 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
819 if (is_a
<cgraph_node
*> (node
))
821 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
824 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
825 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
827 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
831 set_hash (hstate
.end ());
834 /* Update hash by computed local hash values taken from different
836 TODO: stronger SCC based hashing would be desirable here. */
839 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
840 sem_item
*> &m_symtab_node_map
)
843 inchash::hash
state (get_hash ());
845 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
847 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
849 state
.merge_hash ((*result
)->get_hash ());
854 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
857 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
859 state
.merge_hash ((*result
)->get_hash ());
863 global_hash
= state
.end ();
866 /* Returns true if the item equals to ITEM given as argument. */
869 sem_function::equals (sem_item
*item
,
870 hash_map
<symtab_node
*, sem_item
*> &)
872 gcc_assert (item
->type
== FUNC
);
873 bool eq
= equals_private (item
);
875 if (m_checker
!= NULL
)
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
884 xstrdup_for_dump (node
->name()),
885 xstrdup_for_dump (item
->node
->name ()),
888 xstrdup_for_dump (node
->asm_name ()),
889 xstrdup_for_dump (item
->node
->asm_name ()),
890 eq
? "true" : "false");
895 /* Processes function equality comparison. */
898 sem_function::equals_private (sem_item
*item
)
900 if (item
->type
!= FUNC
)
903 basic_block bb1
, bb2
;
905 edge_iterator ei1
, ei2
;
909 m_compared_func
= static_cast<sem_function
*> (item
);
911 gcc_assert (decl
!= item
->decl
);
913 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
914 || edge_count
!= m_compared_func
->edge_count
915 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
916 return return_false ();
918 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
919 compare_polymorphic_p (),
922 &m_compared_func
->refs_set
);
923 arg1
= DECL_ARGUMENTS (decl
);
924 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
926 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
928 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
929 return return_false_with_msg ("argument types are not compatible");
930 if (!param_used_p (i
))
932 /* Perform additional checks for used parameters. */
933 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
935 if (!m_checker
->compare_decl (arg1
, arg2
))
936 return return_false ();
939 return return_false_with_msg ("Mismatched number of arguments");
941 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
944 /* Fill-up label dictionary. */
945 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
947 m_checker
->parse_labels (bb_sorted
[i
]);
948 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
951 /* Checking all basic blocks. */
952 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
953 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
954 return return_false();
956 dump_message ("All BBs are equal\n");
958 auto_vec
<int> bb_dict
;
960 /* Basic block edges check. */
961 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
963 bb1
= bb_sorted
[i
]->bb
;
964 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
966 ei2
= ei_start (bb2
->preds
);
968 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
972 if (e1
->flags
!= e2
->flags
)
973 return return_false_with_msg ("flags comparison returns false");
975 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
976 return return_false_with_msg ("edge comparison returns false");
978 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
979 return return_false_with_msg ("BB comparison returns false");
981 if (!m_checker
->compare_edge (e1
, e2
))
982 return return_false_with_msg ("edge comparison returns false");
988 /* Basic block PHI nodes comparison. */
989 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
990 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
991 return return_false_with_msg ("PHI node comparison returns false");
996 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
997 Helper for call_for_symbol_thunks_and_aliases. */
1000 set_local (cgraph_node
*node
, void *data
)
1002 node
->local
.local
= data
!= NULL
;
1006 /* TREE_ADDRESSABLE of NODE to true.
1007 Helper for call_for_symbol_thunks_and_aliases. */
1010 set_addressable (varpool_node
*node
, void *)
1012 TREE_ADDRESSABLE (node
->decl
) = 1;
1016 /* Clear DECL_RTL of NODE.
1017 Helper for call_for_symbol_thunks_and_aliases. */
1020 clear_decl_rtl (symtab_node
*node
, void *)
1022 SET_DECL_RTL (node
->decl
, NULL
);
1026 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1027 possible. Return number of redirections made. */
1030 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1032 int nredirected
= 0;
1034 cgraph_edge
*e
= n
->callers
;
1038 /* Redirecting thunks to interposable symbols or symbols in other sections
1039 may not be supported by target output code. Play safe for now and
1040 punt on redirection. */
1041 if (!e
->caller
->thunk
.thunk_p
)
1043 struct cgraph_edge
*nexte
= e
->next_caller
;
1044 e
->redirect_callee (to
);
1051 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1053 bool removed
= false;
1054 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1056 if ((DECL_COMDAT_GROUP (n
->decl
)
1057 && (DECL_COMDAT_GROUP (n
->decl
)
1058 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1059 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1060 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1062 nredirected
+= redirect_all_callers (n_alias
, to
);
1063 if (n_alias
->can_remove_if_no_direct_calls_p ()
1064 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1066 && !n_alias
->has_aliases_p ())
1075 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1079 sem_function::merge (sem_item
*alias_item
)
1081 gcc_assert (alias_item
->type
== FUNC
);
1083 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1085 cgraph_node
*original
= get_node ();
1086 cgraph_node
*local_original
= NULL
;
1087 cgraph_node
*alias
= alias_func
->get_node ();
1089 bool create_wrapper
= false;
1090 bool create_alias
= false;
1091 bool redirect_callers
= false;
1092 bool remove
= false;
1094 bool original_discardable
= false;
1095 bool original_discarded
= false;
1097 bool original_address_matters
= original
->address_matters_p ();
1098 bool alias_address_matters
= alias
->address_matters_p ();
1100 if (DECL_EXTERNAL (alias
->decl
))
1103 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1107 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1108 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1113 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1117 /* Do not attempt to mix functions from different user sections;
1118 we do not know what user intends with those. */
1119 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1120 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1121 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1126 "original and alias are in different sections.\n\n");
1130 /* See if original is in a section that can be discarded if the main
1131 symbol is not used. */
1133 if (original
->can_be_discarded_p ())
1134 original_discardable
= true;
1135 /* Also consider case where we have resolution info and we know that
1136 original's definition is not going to be used. In this case we can not
1137 create alias to original. */
1138 if (node
->resolution
!= LDPR_UNKNOWN
1139 && !decl_binds_to_current_def_p (node
->decl
))
1140 original_discardable
= original_discarded
= true;
1142 /* Creating a symtab alias is the optimal way to merge.
1143 It however can not be used in the following cases:
1145 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1146 2) if ORIGINAL is in a section that may be discarded by linker or if
1147 it is an external functions where we can not create an alias
1148 (ORIGINAL_DISCARDABLE)
1149 3) if target do not support symbol aliases.
1150 4) original and alias lie in different comdat groups.
1152 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1153 and/or redirect all callers from ALIAS to ORIGINAL. */
1154 if ((original_address_matters
&& alias_address_matters
)
1155 || (original_discardable
1156 && (!DECL_COMDAT_GROUP (alias
->decl
)
1157 || (DECL_COMDAT_GROUP (alias
->decl
)
1158 != DECL_COMDAT_GROUP (original
->decl
))))
1159 || original_discarded
1160 || !sem_item::target_supports_symbol_aliases_p ()
1161 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1163 /* First see if we can produce wrapper. */
1165 /* Symbol properties that matter for references must be preserved.
1166 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1167 with proper properties. */
1168 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1169 alias
->address_taken
))
1173 "Wrapper cannot be created because referenced symbol "
1174 "properties mismatch\n");
1176 /* Do not turn function in one comdat group into wrapper to another
1177 comdat group. Other compiler producing the body of the
1178 another comdat group may make opossite decision and with unfortunate
1179 linker choices this may close a loop. */
1180 else if (DECL_COMDAT_GROUP (original
->decl
)
1181 && DECL_COMDAT_GROUP (alias
->decl
)
1182 && (DECL_COMDAT_GROUP (alias
->decl
)
1183 != DECL_COMDAT_GROUP (original
->decl
)))
1187 "Wrapper cannot be created because of COMDAT\n");
1189 else if (DECL_STATIC_CHAIN (alias
->decl
))
1193 "Can not create wrapper of nested functions.\n");
1195 /* TODO: We can also deal with variadic functions never calling
1197 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1201 "can not create wrapper of stdarg function.\n");
1203 else if (inline_summaries
1204 && inline_summaries
->get (alias
)->self_size
<= 2)
1207 fprintf (dump_file
, "Wrapper creation is not "
1208 "profitable (function is too small).\n");
1210 /* If user paid attention to mark function noinline, assume it is
1211 somewhat special and do not try to turn it into a wrapper that can
1212 not be undone by inliner. */
1213 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1216 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1219 create_wrapper
= true;
1221 /* We can redirect local calls in the case both alias and orignal
1222 are not interposable. */
1224 = alias
->get_availability () > AVAIL_INTERPOSABLE
1225 && original
->get_availability () > AVAIL_INTERPOSABLE
1226 && !alias
->instrumented_version
;
1227 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1228 with proper properties. */
1229 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1230 alias
->address_taken
))
1231 redirect_callers
= false;
1233 if (!redirect_callers
&& !create_wrapper
)
1236 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1237 "produce wrapper\n\n");
1241 /* Work out the symbol the wrapper should call.
1242 If ORIGINAL is interposable, we need to call a local alias.
1243 Also produce local alias (if possible) as an optimization.
1245 Local aliases can not be created inside comdat groups because that
1246 prevents inlining. */
1247 if (!original_discardable
&& !original
->get_comdat_group ())
1250 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1252 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1253 local_original
= original
;
1255 /* If we can not use local alias, fallback to the original
1257 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1258 local_original
= original
;
1260 /* If original is COMDAT local, we can not really redirect calls outside
1261 of its comdat group to it. */
1262 if (original
->comdat_local_p ())
1263 redirect_callers
= false;
1264 if (!local_original
)
1267 fprintf (dump_file
, "Not unifying; "
1268 "can not produce local alias.\n\n");
1272 if (!redirect_callers
&& !create_wrapper
)
1275 fprintf (dump_file
, "Not unifying; "
1276 "can not redirect callers nor produce a wrapper\n\n");
1280 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1282 && !alias
->can_remove_if_no_direct_calls_p ())
1285 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1286 "function has other uses than direct calls\n\n");
1291 create_alias
= true;
1293 if (redirect_callers
)
1295 int nredirected
= redirect_all_callers (alias
, local_original
);
1299 alias
->icf_merged
= true;
1300 local_original
->icf_merged
= true;
1302 if (dump_file
&& nredirected
)
1303 fprintf (dump_file
, "%i local calls have been "
1304 "redirected.\n", nredirected
);
1307 /* If all callers was redirected, do not produce wrapper. */
1308 if (alias
->can_remove_if_no_direct_calls_p ()
1309 && !DECL_VIRTUAL_P (alias
->decl
)
1310 && !alias
->has_aliases_p ())
1312 create_wrapper
= false;
1315 gcc_assert (!create_alias
);
1317 else if (create_alias
)
1319 alias
->icf_merged
= true;
1321 /* Remove the function's body. */
1322 ipa_merge_profiles (original
, alias
);
1323 alias
->release_body (true);
1325 /* Notice global symbol possibly produced RTL. */
1326 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1329 /* Create the alias. */
1330 cgraph_node::create_alias (alias_func
->decl
, decl
);
1331 alias
->resolve_alias (original
);
1333 original
->call_for_symbol_thunks_and_aliases
1334 (set_local
, (void *)(size_t) original
->local_p (), true);
1337 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1341 gcc_assert (!create_alias
);
1342 alias
->icf_merged
= true;
1343 local_original
->icf_merged
= true;
1345 ipa_merge_profiles (local_original
, alias
, true);
1346 alias
->create_wrapper (local_original
);
1349 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1352 /* It's possible that redirection can hit thunks that block
1353 redirection opportunities. */
1354 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1355 original
->icf_merged
= true;
1357 /* We use merged flag to track cases where COMDAT function is known to be
1358 compatible its callers. If we merged in non-COMDAT, we need to give up
1359 on this optimization. */
1360 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1363 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1365 local_original
->merged_comdat
= false;
1366 original
->merged_comdat
= false;
1371 ipa_merge_profiles (original
, alias
);
1372 alias
->release_body ();
1374 alias
->body_removed
= true;
1375 alias
->icf_merged
= true;
1377 fprintf (dump_file
, "Unified; Function body was removed.\n");
1383 /* Semantic item initialization function. */
1386 sem_function::init (void)
1389 get_node ()->get_untransformed_body ();
1391 tree fndecl
= node
->decl
;
1392 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1395 gcc_assert (SSANAMES (func
));
1397 ssa_names_size
= SSANAMES (func
)->length ();
1401 region_tree
= func
->eh
->region_tree
;
1403 /* iterating all function arguments. */
1404 arg_count
= count_formal_params (fndecl
);
1406 edge_count
= n_edges_for_fn (func
);
1407 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1408 if (!cnode
->thunk
.thunk_p
)
1410 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1412 inchash::hash hstate
;
1415 FOR_EACH_BB_FN (bb
, func
)
1417 unsigned nondbg_stmt_count
= 0;
1420 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1422 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1425 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1428 gimple
*stmt
= gsi_stmt (gsi
);
1430 if (gimple_code (stmt
) != GIMPLE_DEBUG
1431 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1433 hash_stmt (stmt
, hstate
);
1434 nondbg_stmt_count
++;
1438 gcode_hash
= hstate
.end ();
1439 bb_sizes
.safe_push (nondbg_stmt_count
);
1441 /* Inserting basic block to hash table. */
1442 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1443 EDGE_COUNT (bb
->preds
)
1444 + EDGE_COUNT (bb
->succs
));
1446 bb_sorted
.safe_push (semantic_bb
);
1452 inchash::hash hstate
;
1453 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1454 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1455 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1456 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1457 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1458 gcode_hash
= hstate
.end ();
1462 /* Accumulate to HSTATE a hash of expression EXP.
1463 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1464 and DECL equality classes. */
1467 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1469 if (exp
== NULL_TREE
)
1471 hstate
.merge_hash (0);
1475 /* Handled component can be matched in a cureful way proving equivalence
1476 even if they syntactically differ. Just skip them. */
1478 while (handled_component_p (exp
))
1479 exp
= TREE_OPERAND (exp
, 0);
1481 enum tree_code code
= TREE_CODE (exp
);
1482 hstate
.add_int (code
);
1486 /* Use inchash::add_expr for everything that is LTO stable. */
1494 inchash::add_expr (exp
, hstate
);
1498 unsigned HOST_WIDE_INT idx
;
1501 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1503 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1505 add_expr (value
, hstate
);
1510 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1516 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1519 case POINTER_PLUS_EXPR
:
1522 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1523 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1527 inchash::hash one
, two
;
1528 add_expr (TREE_OPERAND (exp
, 0), one
);
1529 add_expr (TREE_OPERAND (exp
, 1), two
);
1530 hstate
.add_commutative (one
, two
);
1534 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1535 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1541 /* Accumulate to HSTATE a hash of type t.
1542 TYpes that may end up being compatible after LTO type merging needs to have
1546 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1548 if (type
== NULL_TREE
)
1550 hstate
.merge_hash (0);
1554 type
= TYPE_MAIN_VARIANT (type
);
1556 hstate
.add_int (TYPE_MODE (type
));
1558 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1560 hstate
.add_int (COMPLEX_TYPE
);
1561 sem_item::add_type (TREE_TYPE (type
), hstate
);
1563 else if (INTEGRAL_TYPE_P (type
))
1565 hstate
.add_int (INTEGER_TYPE
);
1566 hstate
.add_flag (TYPE_UNSIGNED (type
));
1567 hstate
.add_int (TYPE_PRECISION (type
));
1569 else if (VECTOR_TYPE_P (type
))
1571 hstate
.add_int (VECTOR_TYPE
);
1572 hstate
.add_int (TYPE_PRECISION (type
));
1573 sem_item::add_type (TREE_TYPE (type
), hstate
);
1575 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1577 hstate
.add_int (ARRAY_TYPE
);
1578 /* Do not hash size, so complete and incomplete types can match. */
1579 sem_item::add_type (TREE_TYPE (type
), hstate
);
1581 else if (RECORD_OR_UNION_TYPE_P (type
))
1583 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1584 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1588 inchash::hash hstate2
;
1593 hstate2
.add_int (RECORD_TYPE
);
1594 gcc_assert (COMPLETE_TYPE_P (type
));
1596 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1597 if (TREE_CODE (f
) == FIELD_DECL
)
1599 add_type (TREE_TYPE (f
), hstate2
);
1603 hstate2
.add_int (nf
);
1604 hash
= hstate2
.end ();
1605 hstate
.add_wide_int (hash
);
1606 optimizer
->m_type_hash_cache
.put (type
, hash
);
1609 hstate
.add_wide_int (*val
);
1613 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1616 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1618 enum gimple_code code
= gimple_code (stmt
);
1620 hstate
.add_int (code
);
1625 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1628 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1629 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1630 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1632 inchash::hash one
, two
;
1634 add_expr (gimple_assign_rhs1 (stmt
), one
);
1635 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1636 add_expr (gimple_assign_rhs2 (stmt
), two
);
1637 hstate
.add_commutative (one
, two
);
1638 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1640 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1641 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1643 add_expr (gimple_assign_lhs (stmt
), hstate
);
1644 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1653 /* All these statements are equivalent if their operands are. */
1654 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1656 add_expr (gimple_op (stmt
, i
), hstate
);
1657 if (gimple_op (stmt
, i
))
1658 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1666 /* Return true if polymorphic comparison must be processed. */
1669 sem_function::compare_polymorphic_p (void)
1671 struct cgraph_edge
*e
;
1673 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1675 if (get_node ()->indirect_calls
!= NULL
)
1677 /* TODO: We can do simple propagation determining what calls may lead to
1678 a polymorphic call. */
1679 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1680 if (e
->callee
->definition
1681 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1686 /* For a given call graph NODE, the function constructs new
1687 semantic function item. */
1690 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1692 tree fndecl
= node
->decl
;
1693 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1695 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1698 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1702 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1703 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1706 sem_function
*f
= new sem_function (node
, 0, stack
);
1713 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1714 return true if phi nodes are semantically equivalent in these blocks . */
1717 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1719 gphi_iterator si1
, si2
;
1721 unsigned size1
, size2
, i
;
1725 gcc_assert (bb1
!= NULL
);
1726 gcc_assert (bb2
!= NULL
);
1728 si2
= gsi_start_phis (bb2
);
1729 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1732 gsi_next_nonvirtual_phi (&si1
);
1733 gsi_next_nonvirtual_phi (&si2
);
1735 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1738 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1739 return return_false();
1744 tree phi_result1
= gimple_phi_result (phi1
);
1745 tree phi_result2
= gimple_phi_result (phi2
);
1747 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1748 return return_false_with_msg ("PHI results are different");
1750 size1
= gimple_phi_num_args (phi1
);
1751 size2
= gimple_phi_num_args (phi2
);
1754 return return_false ();
1756 for (i
= 0; i
< size1
; ++i
)
1758 t1
= gimple_phi_arg (phi1
, i
)->def
;
1759 t2
= gimple_phi_arg (phi2
, i
)->def
;
1761 if (!m_checker
->compare_operand (t1
, t2
))
1762 return return_false ();
1764 e1
= gimple_phi_arg_edge (phi1
, i
);
1765 e2
= gimple_phi_arg_edge (phi2
, i
);
1767 if (!m_checker
->compare_edge (e1
, e2
))
1768 return return_false ();
1777 /* Returns true if tree T can be compared as a handled component. */
1780 sem_function::icf_handled_component_p (tree t
)
1782 tree_code tc
= TREE_CODE (t
);
1784 return (handled_component_p (t
)
1785 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1788 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1789 corresponds to TARGET. */
1792 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1797 if (bb_dict
->length () <= (unsigned)source
)
1798 bb_dict
->safe_grow_cleared (source
+ 1);
1800 if ((*bb_dict
)[source
] == 0)
1802 (*bb_dict
)[source
] = target
;
1806 return (*bb_dict
)[source
] == target
;
1810 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1812 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1816 /* Constructor based on varpool node _NODE with computed hash _HASH.
1817 Bitmap STACK is used for memory allocation. */
1819 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1820 bitmap_obstack
*stack
): sem_item(VAR
,
1823 gcc_checking_assert (node
);
1824 gcc_checking_assert (get_node ());
1827 /* Fast equality function based on knowledge known in WPA. */
1830 sem_variable::equals_wpa (sem_item
*item
,
1831 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1833 gcc_assert (item
->type
== VAR
);
1835 if (node
->num_references () != item
->node
->num_references ())
1836 return return_false_with_msg ("different number of references");
1838 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1839 return return_false_with_msg ("TLS model");
1841 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1842 alignment out of all aliases. */
1844 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1845 return return_false_with_msg ("Virtual flag mismatch");
1847 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1848 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1849 || !operand_equal_p (DECL_SIZE (decl
),
1850 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1851 return return_false_with_msg ("size mismatch");
1853 /* Do not attempt to mix data from different user sections;
1854 we do not know what user intends with those. */
1855 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1856 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1857 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1858 return return_false_with_msg ("user section mismatch");
1860 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1861 return return_false_with_msg ("text section");
1863 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1864 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1866 item
->node
->iterate_reference (i
, ref2
);
1868 if (ref
->use
!= ref2
->use
)
1869 return return_false_with_msg ("reference use mismatch");
1871 if (!compare_symbol_references (ignored_nodes
,
1872 ref
->referred
, ref2
->referred
,
1873 ref
->address_matters_p ()))
1880 /* Returns true if the item equals to ITEM given as argument. */
1883 sem_variable::equals (sem_item
*item
,
1884 hash_map
<symtab_node
*, sem_item
*> &)
1886 gcc_assert (item
->type
== VAR
);
1889 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1890 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1891 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1892 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1894 /* As seen in PR ipa/65303 we have to compare variables types. */
1895 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1896 TREE_TYPE (item
->decl
)))
1897 return return_false_with_msg ("variables types are different");
1899 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1900 DECL_INITIAL (item
->node
->decl
));
1901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1903 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1904 xstrdup_for_dump (node
->name()),
1905 xstrdup_for_dump (item
->node
->name ()),
1906 node
->order
, item
->node
->order
,
1907 xstrdup_for_dump (node
->asm_name ()),
1908 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1913 /* Compares trees T1 and T2 for semantic equality. */
1916 sem_variable::equals (tree t1
, tree t2
)
1919 return return_with_debug (t1
== t2
);
1922 tree_code tc1
= TREE_CODE (t1
);
1923 tree_code tc2
= TREE_CODE (t2
);
1926 return return_false_with_msg ("TREE_CODE mismatch");
1932 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1933 unsigned HOST_WIDE_INT idx
;
1935 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1936 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1937 return return_false_with_msg ("constructor type mismatch");
1939 if (typecode
== ARRAY_TYPE
)
1941 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1942 /* For arrays, check that the sizes all match. */
1943 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1945 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1946 return return_false_with_msg ("constructor array size mismatch");
1948 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1950 return return_false_with_msg ("constructor type incompatible");
1952 v1
= CONSTRUCTOR_ELTS (t1
);
1953 v2
= CONSTRUCTOR_ELTS (t2
);
1954 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1955 return return_false_with_msg ("constructor number of elts mismatch");
1957 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1959 constructor_elt
*c1
= &(*v1
)[idx
];
1960 constructor_elt
*c2
= &(*v2
)[idx
];
1962 /* Check that each value is the same... */
1963 if (!sem_variable::equals (c1
->value
, c2
->value
))
1965 /* ... and that they apply to the same fields! */
1966 if (!sem_variable::equals (c1
->index
, c2
->index
))
1973 tree x1
= TREE_OPERAND (t1
, 0);
1974 tree x2
= TREE_OPERAND (t2
, 0);
1975 tree y1
= TREE_OPERAND (t1
, 1);
1976 tree y2
= TREE_OPERAND (t2
, 1);
1978 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1979 return return_false ();
1981 /* Type of the offset on MEM_REF does not matter. */
1982 return return_with_debug (sem_variable::equals (x1
, x2
)
1983 && wi::to_offset (y1
)
1984 == wi::to_offset (y2
));
1989 tree op1
= TREE_OPERAND (t1
, 0);
1990 tree op2
= TREE_OPERAND (t2
, 0);
1991 return sem_variable::equals (op1
, op2
);
1993 /* References to other vars/decls are compared using ipa-ref. */
1996 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1998 return return_false_with_msg ("Declaration mismatch");
2000 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2001 need to process its VAR/FUNCTION references without relying on ipa-ref
2005 return return_false_with_msg ("Declaration mismatch");
2007 /* Integer constants are the same only if the same width of type. */
2008 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2009 return return_false_with_msg ("INTEGER_CST precision mismatch");
2010 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2011 return return_false_with_msg ("INTEGER_CST mode mismatch");
2012 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2014 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2015 return return_false_with_msg ("STRING_CST mode mismatch");
2016 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2017 return return_false_with_msg ("STRING_CST length mismatch");
2018 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2019 TREE_STRING_LENGTH (t1
)))
2020 return return_false_with_msg ("STRING_CST mismatch");
2023 /* Fixed constants are the same only if the same width of type. */
2024 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2025 return return_false_with_msg ("FIXED_CST precision mismatch");
2027 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2028 TREE_FIXED_CST (t2
)));
2030 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2031 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2033 /* Real constants are the same only if the same width of type. */
2034 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2035 return return_false_with_msg ("REAL_CST precision mismatch");
2036 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2037 &TREE_REAL_CST (t2
)));
2042 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2043 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2045 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2046 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2047 VECTOR_CST_ELT (t2
, i
)))
2053 case ARRAY_RANGE_REF
:
2055 tree x1
= TREE_OPERAND (t1
, 0);
2056 tree x2
= TREE_OPERAND (t2
, 0);
2057 tree y1
= TREE_OPERAND (t1
, 1);
2058 tree y2
= TREE_OPERAND (t2
, 1);
2060 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2062 if (!sem_variable::equals (array_ref_low_bound (t1
),
2063 array_ref_low_bound (t2
)))
2065 if (!sem_variable::equals (array_ref_element_size (t1
),
2066 array_ref_element_size (t2
)))
2072 case POINTER_PLUS_EXPR
:
2077 tree x1
= TREE_OPERAND (t1
, 0);
2078 tree x2
= TREE_OPERAND (t2
, 0);
2079 tree y1
= TREE_OPERAND (t1
, 1);
2080 tree y2
= TREE_OPERAND (t2
, 1);
2082 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2086 case VIEW_CONVERT_EXPR
:
2087 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2088 return return_false ();
2089 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2091 return return_false_with_msg ("ERROR_MARK");
2093 return return_false_with_msg ("Unknown TREE code reached");
2097 /* Parser function that visits a varpool NODE. */
2100 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2102 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2106 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2113 /* References independent hash function. */
2116 sem_variable::get_hash (void)
2121 /* All WPA streamed in symbols should have their hashes computed at compile
2122 time. At this point, the constructor may not be in memory at all.
2123 DECL_INITIAL (decl) would be error_mark_node in that case. */
2124 gcc_assert (!node
->lto_file_data
);
2125 tree ctor
= DECL_INITIAL (decl
);
2126 inchash::hash hstate
;
2128 hstate
.add_int (456346417);
2129 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2130 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2131 add_expr (ctor
, hstate
);
2132 set_hash (hstate
.end ());
2137 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2140 set_alias_uids (symtab_node
*n
, int uid
)
2143 FOR_EACH_ALIAS (n
, ref
)
2146 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2147 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2149 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2150 set_alias_uids (ref
->referring
, uid
);
2154 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2158 sem_variable::merge (sem_item
*alias_item
)
2160 gcc_assert (alias_item
->type
== VAR
);
2162 if (!sem_item::target_supports_symbol_aliases_p ())
2165 fprintf (dump_file
, "Not unifying; "
2166 "Symbol aliases are not supported by target\n\n");
2170 if (DECL_EXTERNAL (alias_item
->decl
))
2173 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2177 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2179 varpool_node
*original
= get_node ();
2180 varpool_node
*alias
= alias_var
->get_node ();
2181 bool original_discardable
= false;
2183 bool alias_address_matters
= alias
->address_matters_p ();
2185 /* See if original is in a section that can be discarded if the main
2187 Also consider case where we have resolution info and we know that
2188 original's definition is not going to be used. In this case we can not
2189 create alias to original. */
2190 if (original
->can_be_discarded_p ()
2191 || (node
->resolution
!= LDPR_UNKNOWN
2192 && !decl_binds_to_current_def_p (node
->decl
)))
2193 original_discardable
= true;
2195 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2197 /* Constant pool machinery is not quite ready for aliases.
2198 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2199 For LTO merging does not happen that is an important missing feature.
2200 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2201 flag is dropped and non-local symbol name is assigned. */
2202 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2203 || DECL_IN_CONSTANT_POOL (original
->decl
))
2207 "Not unifying; constant pool variables.\n\n");
2211 /* Do not attempt to mix functions from different user sections;
2212 we do not know what user intends with those. */
2213 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2214 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2215 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2220 "original and alias are in different sections.\n\n");
2224 /* We can not merge if address comparsion metters. */
2225 if (alias_address_matters
&& flag_merge_constants
< 2)
2229 "Not unifying; address of original may be compared.\n\n");
2233 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2236 fprintf (dump_file
, "Not unifying; "
2237 "original and alias have incompatible alignments\n\n");
2242 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2245 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2246 "across comdat group boundary\n\n");
2251 if (original_discardable
)
2254 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2255 "target is discardable\n\n");
2261 gcc_assert (!original
->alias
);
2262 gcc_assert (!alias
->alias
);
2264 alias
->analyzed
= false;
2266 DECL_INITIAL (alias
->decl
) = NULL
;
2267 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2269 alias
->need_bounds_init
= false;
2270 alias
->remove_all_references ();
2271 if (TREE_ADDRESSABLE (alias
->decl
))
2272 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2274 varpool_node::create_alias (alias_var
->decl
, decl
);
2275 alias
->resolve_alias (original
);
2278 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2280 set_alias_uids (original
, DECL_UID (original
->decl
));
2285 /* Dump symbol to FILE. */
2288 sem_variable::dump_to_file (FILE *file
)
2292 print_node (file
, "", decl
, 0);
2293 fprintf (file
, "\n\n");
2296 unsigned int sem_item_optimizer::class_id
= 0;
2298 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2299 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2302 bitmap_obstack_initialize (&m_bmstack
);
2305 sem_item_optimizer::~sem_item_optimizer ()
2307 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2310 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2311 it
!= m_classes
.end (); ++it
)
2313 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2314 delete (*it
)->classes
[i
];
2316 (*it
)->classes
.release ();
2322 bitmap_obstack_release (&m_bmstack
);
2325 /* Write IPA ICF summary for symbols. */
2328 sem_item_optimizer::write_summary (void)
2330 unsigned int count
= 0;
2332 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2333 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2336 /* Calculate number of symbols to be serialized. */
2337 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2339 lsei_next_in_partition (&lsei
))
2341 symtab_node
*node
= lsei_node (lsei
);
2343 if (m_symtab_node_map
.get (node
))
2347 streamer_write_uhwi (ob
, count
);
2349 /* Process all of the symbols. */
2350 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2352 lsei_next_in_partition (&lsei
))
2354 symtab_node
*node
= lsei_node (lsei
);
2356 sem_item
**item
= m_symtab_node_map
.get (node
);
2360 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2361 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2363 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2367 streamer_write_char_stream (ob
->main_stream
, 0);
2368 produce_asm (ob
, NULL
);
2369 destroy_output_block (ob
);
2372 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2373 contains LEN bytes. */
2376 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2377 const char *data
, size_t len
)
2379 const lto_function_header
*header
=
2380 (const lto_function_header
*) data
;
2381 const int cfg_offset
= sizeof (lto_function_header
);
2382 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2383 const int string_offset
= main_offset
+ header
->main_size
;
2388 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2389 header
->main_size
, file_data
->mode_table
);
2392 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2393 header
->string_size
, vNULL
);
2395 count
= streamer_read_uhwi (&ib_main
);
2397 for (i
= 0; i
< count
; i
++)
2401 lto_symtab_encoder_t encoder
;
2403 index
= streamer_read_uhwi (&ib_main
);
2404 encoder
= file_data
->symtab_node_encoder
;
2405 node
= lto_symtab_encoder_deref (encoder
, index
);
2407 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2409 gcc_assert (node
->definition
);
2412 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2413 node
->asm_name (), (void *) node
->decl
, node
->order
);
2415 if (is_a
<cgraph_node
*> (node
))
2417 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2419 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2423 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2425 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2429 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2431 lto_data_in_delete (data_in
);
2434 /* Read IPA ICF summary for symbols. */
2437 sem_item_optimizer::read_summary (void)
2439 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2440 lto_file_decl_data
*file_data
;
2443 while ((file_data
= file_data_vec
[j
++]))
2446 const char *data
= lto_get_section_data (file_data
,
2447 LTO_section_ipa_icf
, NULL
, &len
);
2450 read_section (file_data
, data
, len
);
2454 /* Register callgraph and varpool hooks. */
2457 sem_item_optimizer::register_hooks (void)
2459 if (!m_cgraph_node_hooks
)
2460 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2461 (&sem_item_optimizer::cgraph_removal_hook
, this);
2463 if (!m_varpool_node_hooks
)
2464 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2465 (&sem_item_optimizer::varpool_removal_hook
, this);
2468 /* Unregister callgraph and varpool hooks. */
2471 sem_item_optimizer::unregister_hooks (void)
2473 if (m_cgraph_node_hooks
)
2474 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2476 if (m_varpool_node_hooks
)
2477 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2480 /* Adds a CLS to hashtable associated by hash value. */
2483 sem_item_optimizer::add_class (congruence_class
*cls
)
2485 gcc_assert (cls
->members
.length ());
2487 congruence_class_group
*group
= get_group_by_hash (
2488 cls
->members
[0]->get_hash (),
2489 cls
->members
[0]->type
);
2490 group
->classes
.safe_push (cls
);
2493 /* Gets a congruence class group based on given HASH value and TYPE. */
2495 congruence_class_group
*
2496 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2498 congruence_class_group
*item
= XNEW (congruence_class_group
);
2502 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2508 item
->classes
.create (1);
2515 /* Callgraph removal hook called for a NODE with a custom DATA. */
2518 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2520 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2521 optimizer
->remove_symtab_node (node
);
2524 /* Varpool removal hook called for a NODE with a custom DATA. */
2527 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2529 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2530 optimizer
->remove_symtab_node (node
);
2533 /* Remove symtab NODE triggered by symtab removal hooks. */
2536 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2538 gcc_assert (!m_classes
.elements());
2540 m_removed_items_set
.add (node
);
2544 sem_item_optimizer::remove_item (sem_item
*item
)
2546 if (m_symtab_node_map
.get (item
->node
))
2547 m_symtab_node_map
.remove (item
->node
);
2551 /* Removes all callgraph and varpool nodes that are marked by symtab
2555 sem_item_optimizer::filter_removed_items (void)
2557 auto_vec
<sem_item
*> filtered
;
2559 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2561 sem_item
*item
= m_items
[i
];
2563 if (m_removed_items_set
.contains (item
->node
))
2569 if (item
->type
== FUNC
)
2571 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2573 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2576 filtered
.safe_push (item
);
2580 if (!flag_ipa_icf_variables
)
2584 /* Filter out non-readonly variables. */
2585 tree decl
= item
->decl
;
2586 if (TREE_READONLY (decl
))
2587 filtered
.safe_push (item
);
2594 /* Clean-up of released semantic items. */
2597 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2598 m_items
.safe_push (filtered
[i
]);
2601 /* Optimizer entry point which returns true in case it processes
2602 a merge operation. True is returned if there's a merge operation
2606 sem_item_optimizer::execute (void)
2608 filter_removed_items ();
2609 unregister_hooks ();
2612 update_hash_by_addr_refs ();
2613 build_hash_based_classes ();
2616 fprintf (dump_file
, "Dump after hash based groups\n");
2617 dump_cong_classes ();
2619 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2620 m_items
[i
]->init_wpa ();
2622 subdivide_classes_by_equality (true);
2625 fprintf (dump_file
, "Dump after WPA based types groups\n");
2627 dump_cong_classes ();
2629 process_cong_reduction ();
2630 checking_verify_classes ();
2633 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2635 dump_cong_classes ();
2637 parse_nonsingleton_classes ();
2638 subdivide_classes_by_equality ();
2641 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2643 dump_cong_classes ();
2645 unsigned int prev_class_count
= m_classes_count
;
2647 process_cong_reduction ();
2648 dump_cong_classes ();
2649 checking_verify_classes ();
2650 bool merged_p
= merge_classes (prev_class_count
);
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2653 symtab_node::dump_table (dump_file
);
2658 /* Function responsible for visiting all potential functions and
2659 read-only variables that can be merged. */
2662 sem_item_optimizer::parse_funcs_and_vars (void)
2666 if (flag_ipa_icf_functions
)
2667 FOR_EACH_DEFINED_FUNCTION (cnode
)
2669 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2672 m_items
.safe_push (f
);
2673 m_symtab_node_map
.put (cnode
, f
);
2676 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2679 f
->dump_to_file (dump_file
);
2682 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2685 varpool_node
*vnode
;
2687 if (flag_ipa_icf_variables
)
2688 FOR_EACH_DEFINED_VARIABLE (vnode
)
2690 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2694 m_items
.safe_push (v
);
2695 m_symtab_node_map
.put (vnode
, v
);
2700 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2703 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2705 item
->index_in_class
= cls
->members
.length ();
2706 cls
->members
.safe_push (item
);
2710 /* For each semantic item, append hash values of references. */
2713 sem_item_optimizer::update_hash_by_addr_refs ()
2715 /* First, append to hash sensitive references and class type if it need to
2716 be matched for ODR. */
2717 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2719 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2720 if (m_items
[i
]->type
== FUNC
)
2722 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2723 && contains_polymorphic_type_p
2724 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2725 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2726 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2727 && static_cast<sem_function
*> (m_items
[i
])
2728 ->compare_polymorphic_p ())))
2731 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2732 inchash::hash
hstate (m_items
[i
]->get_hash ());
2734 if (TYPE_NAME (class_type
)
2735 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2737 (IDENTIFIER_HASH_VALUE
2738 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2740 m_items
[i
]->set_hash (hstate
.end ());
2745 /* Once all symbols have enhanced hash value, we can append
2746 hash values of symbols that are seen by IPA ICF and are
2747 references by a semantic item. Newly computed values
2748 are saved to global_hash member variable. */
2749 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2750 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2752 /* Global hash value replace current hash values. */
2753 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2754 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2757 /* Congruence classes are built by hash value. */
2760 sem_item_optimizer::build_hash_based_classes (void)
2762 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2764 sem_item
*item
= m_items
[i
];
2766 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2769 if (!group
->classes
.length ())
2772 group
->classes
.safe_push (new congruence_class (class_id
++));
2775 add_item_to_class (group
->classes
[0], item
);
2779 /* Build references according to call graph. */
2782 sem_item_optimizer::build_graph (void)
2784 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2786 sem_item
*item
= m_items
[i
];
2787 m_symtab_node_map
.put (item
->node
, item
);
2789 /* Initialize hash values if we are not in LTO mode. */
2794 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2796 sem_item
*item
= m_items
[i
];
2798 if (item
->type
== FUNC
)
2800 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2802 cgraph_edge
*e
= cnode
->callees
;
2805 sem_item
**slot
= m_symtab_node_map
.get
2806 (e
->callee
->ultimate_alias_target ());
2808 item
->add_reference (*slot
);
2814 ipa_ref
*ref
= NULL
;
2815 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2817 sem_item
**slot
= m_symtab_node_map
.get
2818 (ref
->referred
->ultimate_alias_target ());
2820 item
->add_reference (*slot
);
2825 /* Semantic items in classes having more than one element and initialized.
2826 In case of WPA, we load function body. */
2829 sem_item_optimizer::parse_nonsingleton_classes (void)
2831 unsigned int init_called_count
= 0;
2833 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2834 if (m_items
[i
]->cls
->members
.length () > 1)
2836 m_items
[i
]->init ();
2837 init_called_count
++;
2841 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2842 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2845 /* Equality function for semantic items is used to subdivide existing
2846 classes. If IN_WPA, fast equality function is invoked. */
2849 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2851 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2852 it
!= m_classes
.end (); ++it
)
2854 unsigned int class_count
= (*it
)->classes
.length ();
2856 for (unsigned i
= 0; i
< class_count
; i
++)
2858 congruence_class
*c
= (*it
)->classes
[i
];
2860 if (c
->members
.length() > 1)
2862 auto_vec
<sem_item
*> new_vector
;
2864 sem_item
*first
= c
->members
[0];
2865 new_vector
.safe_push (first
);
2867 unsigned class_split_first
= (*it
)->classes
.length ();
2869 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2871 sem_item
*item
= c
->members
[j
];
2873 bool equals
= in_wpa
? first
->equals_wpa (item
,
2874 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2877 new_vector
.safe_push (item
);
2880 bool integrated
= false;
2882 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2884 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2885 bool equals
= in_wpa
? x
->equals_wpa (item
,
2886 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2891 add_item_to_class ((*it
)->classes
[k
], item
);
2899 congruence_class
*c
= new congruence_class (class_id
++);
2901 add_item_to_class (c
, item
);
2903 (*it
)->classes
.safe_push (c
);
2908 // we replace newly created new_vector for the class we've just splitted
2909 c
->members
.release ();
2910 c
->members
.create (new_vector
.length ());
2912 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2913 add_item_to_class (c
, new_vector
[j
]);
2918 checking_verify_classes ();
2921 /* Subdivide classes by address references that members of the class
2922 reference. Example can be a pair of functions that have an address
2923 taken from a function. If these addresses are different the class
2927 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2929 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2931 unsigned newly_created_classes
= 0;
2933 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2934 it
!= m_classes
.end (); ++it
)
2936 unsigned int class_count
= (*it
)->classes
.length ();
2937 auto_vec
<congruence_class
*> new_classes
;
2939 for (unsigned i
= 0; i
< class_count
; i
++)
2941 congruence_class
*c
= (*it
)->classes
[i
];
2943 if (c
->members
.length() > 1)
2945 subdivide_hash_map split_map
;
2947 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2949 sem_item
*source_node
= c
->members
[j
];
2951 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2954 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2956 gcc_checking_assert (slot
);
2958 slot
->safe_push (source_node
);
2964 /* If the map contains more than one key, we have to split the map
2966 if (split_map
.elements () != 1)
2968 bool first_class
= true;
2970 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2971 it2
!= split_map
.end (); ++it2
)
2973 congruence_class
*new_cls
;
2974 new_cls
= new congruence_class (class_id
++);
2976 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2977 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2979 worklist_push (new_cls
);
2980 newly_created_classes
++;
2984 (*it
)->classes
[i
] = new_cls
;
2985 first_class
= false;
2989 new_classes
.safe_push (new_cls
);
2995 /* Release memory. */
2996 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2997 it2
!= split_map
.end (); ++it2
)
2999 delete (*it2
).first
;
3000 (*it2
).second
.release ();
3005 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
3006 (*it
)->classes
.safe_push (new_classes
[i
]);
3009 return newly_created_classes
;
3012 /* Verify congruence classes, if checking is enabled. */
3015 sem_item_optimizer::checking_verify_classes (void)
3021 /* Verify congruence classes. */
3024 sem_item_optimizer::verify_classes (void)
3026 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3027 it
!= m_classes
.end (); ++it
)
3029 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3031 congruence_class
*cls
= (*it
)->classes
[i
];
3034 gcc_assert (cls
->members
.length () > 0);
3036 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3038 sem_item
*item
= cls
->members
[j
];
3041 gcc_assert (item
->cls
== cls
);
3043 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3045 sem_usage_pair
*usage
= item
->usages
[k
];
3046 gcc_assert (usage
->item
->index_in_class
<
3047 usage
->item
->cls
->members
.length ());
3054 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3055 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3056 but unused argument. */
3059 sem_item_optimizer::release_split_map (congruence_class
* const &,
3060 bitmap
const &b
, traverse_split_pair
*)
3069 /* Process split operation for a class given as pointer CLS_PTR,
3070 where bitmap B splits congruence class members. DATA is used
3071 as argument of split pair. */
3074 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3075 bitmap
const &b
, traverse_split_pair
*pair
)
3077 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3078 const congruence_class
*splitter_cls
= pair
->cls
;
3080 /* If counted bits are greater than zero and less than the number of members
3081 a group will be splitted. */
3082 unsigned popcount
= bitmap_count_bits (b
);
3084 if (popcount
> 0 && popcount
< cls
->members
.length ())
3086 auto_vec
<congruence_class
*, 2> newclasses
;
3087 newclasses
.quick_push (new congruence_class (class_id
++));
3088 newclasses
.quick_push (new congruence_class (class_id
++));
3090 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3092 int target
= bitmap_bit_p (b
, i
);
3093 congruence_class
*tc
= newclasses
[target
];
3095 add_item_to_class (tc
, cls
->members
[i
]);
3100 for (unsigned int i
= 0; i
< 2; i
++)
3101 gcc_assert (newclasses
[i
]->members
.length ());
3104 if (splitter_cls
== cls
)
3105 optimizer
->splitter_class_removed
= true;
3107 /* Remove old class from worklist if presented. */
3108 bool in_worklist
= cls
->in_worklist
;
3111 cls
->in_worklist
= false;
3113 congruence_class_group g
;
3114 g
.hash
= cls
->members
[0]->get_hash ();
3115 g
.type
= cls
->members
[0]->type
;
3117 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3119 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3120 if (slot
->classes
[i
] == cls
)
3122 slot
->classes
.ordered_remove (i
);
3126 /* New class will be inserted and integrated to work list. */
3127 for (unsigned int i
= 0; i
< 2; i
++)
3128 optimizer
->add_class (newclasses
[i
]);
3130 /* Two classes replace one, so that increment just by one. */
3131 optimizer
->m_classes_count
++;
3133 /* If OLD class was presented in the worklist, we remove the class
3134 and replace it will both newly created classes. */
3136 for (unsigned int i
= 0; i
< 2; i
++)
3137 optimizer
->worklist_push (newclasses
[i
]);
3138 else /* Just smaller class is inserted. */
3140 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3141 newclasses
[1]->members
.length () ?
3143 optimizer
->worklist_push (newclasses
[smaller_index
]);
3146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3148 fprintf (dump_file
, " congruence class splitted:\n");
3149 cls
->dump (dump_file
, 4);
3151 fprintf (dump_file
, " newly created groups:\n");
3152 for (unsigned int i
= 0; i
< 2; i
++)
3153 newclasses
[i
]->dump (dump_file
, 4);
3156 /* Release class if not presented in work list. */
3165 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3166 Bitmap stack BMSTACK is used for bitmap allocation. */
3169 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3172 hash_map
<congruence_class
*, bitmap
> split_map
;
3174 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3176 sem_item
*item
= cls
->members
[i
];
3178 /* Iterate all usages that have INDEX as usage of the item. */
3179 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3181 sem_usage_pair
*usage
= item
->usages
[j
];
3183 if (usage
->index
!= index
)
3186 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3191 b
= BITMAP_ALLOC (&m_bmstack
);
3192 split_map
.put (usage
->item
->cls
, b
);
3197 gcc_checking_assert (usage
->item
->cls
);
3198 gcc_checking_assert (usage
->item
->index_in_class
<
3199 usage
->item
->cls
->members
.length ());
3201 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3205 traverse_split_pair pair
;
3206 pair
.optimizer
= this;
3209 splitter_class_removed
= false;
3211 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3213 /* Bitmap clean-up. */
3215 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3218 /* Every usage of a congruence class CLS is a candidate that can split the
3219 collection of classes. Bitmap stack BMSTACK is used for bitmap
3223 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3228 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3230 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3231 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3233 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3236 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3239 do_congruence_step_for_index (cls
, i
);
3241 if (splitter_class_removed
)
3245 BITMAP_FREE (usage
);
3248 /* Adds a newly created congruence class CLS to worklist. */
3251 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3253 /* Return if the class CLS is already presented in work list. */
3254 if (cls
->in_worklist
)
3257 cls
->in_worklist
= true;
3258 worklist
.push_back (cls
);
3261 /* Pops a class from worklist. */
3264 sem_item_optimizer::worklist_pop (void)
3266 congruence_class
*cls
;
3268 while (!worklist
.empty ())
3270 cls
= worklist
.front ();
3271 worklist
.pop_front ();
3272 if (cls
->in_worklist
)
3274 cls
->in_worklist
= false;
3280 /* Work list item was already intended to be removed.
3281 The only reason for doing it is to split a class.
3282 Thus, the class CLS is deleted. */
3290 /* Iterative congruence reduction function. */
3293 sem_item_optimizer::process_cong_reduction (void)
3295 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3296 it
!= m_classes
.end (); ++it
)
3297 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3298 if ((*it
)->classes
[i
]->is_class_used ())
3299 worklist_push ((*it
)->classes
[i
]);
3302 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3303 (unsigned long) worklist
.size ());
3305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3306 fprintf (dump_file
, "Congruence class reduction\n");
3308 congruence_class
*cls
;
3310 /* Process complete congruence reduction. */
3311 while ((cls
= worklist_pop ()) != NULL
)
3312 do_congruence_step (cls
);
3314 /* Subdivide newly created classes according to references. */
3315 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3318 fprintf (dump_file
, "Address reference subdivision created: %u "
3319 "new classes.\n", new_classes
);
3322 /* Debug function prints all informations about congruence classes. */
3325 sem_item_optimizer::dump_cong_classes (void)
3331 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3332 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3334 /* Histogram calculation. */
3335 unsigned int max_index
= 0;
3336 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3338 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3339 it
!= m_classes
.end (); ++it
)
3341 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3343 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3351 "Class size histogram [num of members]: number of classe number of classess\n");
3353 for (unsigned int i
= 0; i
<= max_index
; i
++)
3355 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3357 fprintf (dump_file
, "\n\n");
3360 if (dump_flags
& TDF_DETAILS
)
3361 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3362 it
!= m_classes
.end (); ++it
)
3364 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3366 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3368 (*it
)->classes
[i
]->dump (dump_file
, 4);
3370 if(i
< (*it
)->classes
.length () - 1)
3371 fprintf (dump_file
, " ");
3378 /* After reduction is done, we can declare all items in a group
3379 to be equal. PREV_CLASS_COUNT is start number of classes
3380 before reduction. True is returned if there's a merge operation
3384 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3386 unsigned int item_count
= m_items
.length ();
3387 unsigned int class_count
= m_classes_count
;
3388 unsigned int equal_items
= item_count
- class_count
;
3390 unsigned int non_singular_classes_count
= 0;
3391 unsigned int non_singular_classes_sum
= 0;
3393 bool merged_p
= false;
3395 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3396 it
!= m_classes
.end (); ++it
)
3397 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3399 congruence_class
*c
= (*it
)->classes
[i
];
3400 if (c
->members
.length () > 1)
3402 non_singular_classes_count
++;
3403 non_singular_classes_sum
+= c
->members
.length ();
3409 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3410 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3411 prev_class_count
, class_count
);
3412 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3413 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3414 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3415 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3416 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3417 non_singular_classes_count
: 0.0f
,
3418 non_singular_classes_count
);
3419 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3420 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3421 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3424 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3425 it
!= m_classes
.end (); ++it
)
3426 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3428 congruence_class
*c
= (*it
)->classes
[i
];
3430 if (c
->members
.length () == 1)
3433 sem_item
*source
= c
->members
[0];
3435 if (DECL_NAME (source
->decl
)
3436 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3437 /* If merge via wrappers, picking main as the target can be
3439 source
= c
->members
[1];
3441 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3443 sem_item
*alias
= c
->members
[j
];
3445 if (alias
== source
)
3450 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3451 xstrdup_for_dump (source
->node
->name ()),
3452 xstrdup_for_dump (alias
->node
->name ()));
3453 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3454 xstrdup_for_dump (source
->node
->asm_name ()),
3455 xstrdup_for_dump (alias
->node
->asm_name ()));
3458 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3462 "Merge operation is skipped due to no_icf "
3468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3470 source
->dump_to_file (dump_file
);
3471 alias
->dump_to_file (dump_file
);
3474 if (dbg_cnt (merged_ipa_icf
))
3475 merged_p
|= source
->merge (alias
);
3482 /* Dump function prints all class members to a FILE with an INDENT. */
3485 congruence_class::dump (FILE *file
, unsigned int indent
) const
3487 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3488 id
, members
[0]->get_hash (), members
.length ());
3490 FPUTS_SPACES (file
, indent
+ 2, "");
3491 for (unsigned i
= 0; i
< members
.length (); i
++)
3492 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3493 (void *) members
[i
]->decl
,
3494 members
[i
]->node
->order
);
3496 fprintf (file
, "\n");
3499 /* Returns true if there's a member that is used from another group. */
3502 congruence_class::is_class_used (void)
3504 for (unsigned int i
= 0; i
< members
.length (); i
++)
3505 if (members
[i
]->usages
.length ())
3511 /* Generate pass summary for IPA ICF pass. */
3514 ipa_icf_generate_summary (void)
3517 optimizer
= new sem_item_optimizer ();
3519 optimizer
->register_hooks ();
3520 optimizer
->parse_funcs_and_vars ();
3523 /* Write pass summary for IPA ICF pass. */
3526 ipa_icf_write_summary (void)
3528 gcc_assert (optimizer
);
3530 optimizer
->write_summary ();
3533 /* Read pass summary for IPA ICF pass. */
3536 ipa_icf_read_summary (void)
3539 optimizer
= new sem_item_optimizer ();
3541 optimizer
->read_summary ();
3542 optimizer
->register_hooks ();
3545 /* Semantic equality exection function. */
3548 ipa_icf_driver (void)
3550 gcc_assert (optimizer
);
3552 bool merged_p
= optimizer
->execute ();
3557 return merged_p
? TODO_remove_functions
: 0;
3560 const pass_data pass_data_ipa_icf
=
3562 IPA_PASS
, /* type */
3564 OPTGROUP_IPA
, /* optinfo_flags */
3565 TV_IPA_ICF
, /* tv_id */
3566 0, /* properties_required */
3567 0, /* properties_provided */
3568 0, /* properties_destroyed */
3569 0, /* todo_flags_start */
3570 0, /* todo_flags_finish */
3573 class pass_ipa_icf
: public ipa_opt_pass_d
3576 pass_ipa_icf (gcc::context
*ctxt
)
3577 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3578 ipa_icf_generate_summary
, /* generate_summary */
3579 ipa_icf_write_summary
, /* write_summary */
3580 ipa_icf_read_summary
, /* read_summary */
3582 write_optimization_summary */
3584 read_optimization_summary */
3585 NULL
, /* stmt_fixup */
3586 0, /* function_transform_todo_flags_start */
3587 NULL
, /* function_transform */
3588 NULL
) /* variable_transform */
3591 /* opt_pass methods: */
3592 virtual bool gate (function
*)
3594 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3597 virtual unsigned int execute (function
*)
3599 return ipa_icf_driver();
3601 }; // class pass_ipa_icf
3603 } // ipa_icf namespace
3606 make_pass_ipa_icf (gcc::context
*ctxt
)
3608 return new ipa_icf::pass_ipa_icf (ctxt
);