1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
66 #include "insn-config.h"
70 #include "gimple-pretty-print.h"
71 #include "data-streamer.h"
74 #include "fold-const.h"
75 #include "internal-fn.h"
83 #include "gimple-iterator.h"
86 #include "symbol-summary.h"
88 #include "ipa-inline.h"
92 #include "print-tree.h"
93 #include "ipa-utils.h"
94 #include "ipa-icf-gimple.h"
96 #include "stor-layout.h"
99 using namespace ipa_icf_gimple
;
103 /* Initialization and computation of symtab node hash, there data
104 are propagated later on. */
106 static sem_item_optimizer
*optimizer
= NULL
;
110 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
112 m_references
.create (0);
113 m_interposables
.create (0);
117 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
120 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
122 if (ref
->address_matters_p ())
123 m_references
.safe_push (ref
->referred
);
125 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
127 if (ref
->address_matters_p ())
128 m_references
.safe_push (ref
->referred
);
130 m_interposables
.safe_push (ref
->referred
);
134 if (is_a
<cgraph_node
*> (node
))
136 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
138 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
139 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
140 m_interposables
.safe_push (e
->callee
);
144 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
146 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
147 item (_item
), index (_index
)
151 /* Semantic item constructor for a node of _TYPE, where STACK is used
152 for bitmap memory allocation. */
154 sem_item::sem_item (sem_item_type _type
,
155 bitmap_obstack
*stack
): type(_type
), hash(0)
160 /* Semantic item constructor for a node of _TYPE, where STACK is used
161 for bitmap memory allocation. The item is based on symtab node _NODE
162 with computed _HASH. */
164 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
165 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
166 node (_node
), hash (_hash
)
172 /* Add reference to a semantic TARGET. */
175 sem_item::add_reference (sem_item
*target
)
177 refs
.safe_push (target
);
178 unsigned index
= refs
.length ();
179 target
->usages
.safe_push (new sem_usage_pair(this, index
));
180 bitmap_set_bit (target
->usage_index_bitmap
, index
);
181 refs_set
.add (target
->node
);
184 /* Initialize internal data structures. Bitmap STACK is used for
185 bitmap memory allocation process. */
188 sem_item::setup (bitmap_obstack
*stack
)
190 gcc_checking_assert (node
);
193 tree_refs
.create (0);
195 usage_index_bitmap
= BITMAP_ALLOC (stack
);
198 sem_item::~sem_item ()
200 for (unsigned i
= 0; i
< usages
.length (); i
++)
204 tree_refs
.release ();
207 BITMAP_FREE (usage_index_bitmap
);
210 /* Dump function for debugging purpose. */
213 sem_item::dump (void)
217 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
218 node
->name(), node
->order
, (void *) node
->decl
);
219 fprintf (dump_file
, " hash: %u\n", get_hash ());
220 fprintf (dump_file
, " references: ");
222 for (unsigned i
= 0; i
< refs
.length (); i
++)
223 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
224 i
< refs
.length() - 1 ? "," : "");
226 fprintf (dump_file
, "\n");
230 /* Return true if target supports alias symbols. */
233 sem_item::target_supports_symbol_aliases_p (void)
235 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
242 /* Semantic function constructor that uses STACK as bitmap memory stack. */
244 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
245 m_checker (NULL
), m_compared_func (NULL
)
248 bb_sorted
.create (0);
251 /* Constructor based on callgraph node _NODE with computed hash _HASH.
252 Bitmap STACK is used for memory allocation. */
253 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
254 bitmap_obstack
*stack
):
255 sem_item (FUNC
, node
, hash
, stack
),
256 m_checker (NULL
), m_compared_func (NULL
)
259 bb_sorted
.create (0);
262 sem_function::~sem_function ()
264 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
265 delete (bb_sorted
[i
]);
268 bb_sorted
.release ();
271 /* Calculates hash value based on a BASIC_BLOCK. */
274 sem_function::get_bb_hash (const sem_bb
*basic_block
)
276 inchash::hash hstate
;
278 hstate
.add_int (basic_block
->nondbg_stmt_count
);
279 hstate
.add_int (basic_block
->edge_count
);
281 return hstate
.end ();
284 /* References independent hash function. */
287 sem_function::get_hash (void)
291 inchash::hash hstate
;
292 hstate
.add_int (177454); /* Random number for function type. */
294 hstate
.add_int (arg_count
);
295 hstate
.add_int (cfg_checksum
);
296 hstate
.add_int (gcode_hash
);
298 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
299 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
301 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
302 hstate
.add_int (bb_sizes
[i
]);
305 /* Add common features of declaration itself. */
306 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
308 (cl_target_option_hash
309 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
310 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
311 (cl_optimization_hash
312 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
313 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
314 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
316 hash
= hstate
.end ();
322 /* Return ture if A1 and A2 represent equivalent function attribute lists.
323 Based on comp_type_attributes. */
326 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
331 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
333 const struct attribute_spec
*as
;
336 as
= lookup_attribute_spec (get_attribute_name (a
));
337 /* TODO: We can introduce as->affects_decl_identity
338 and as->affects_decl_reference_identity if attribute mismatch
339 gets a common reason to give up on merging. It may not be worth
341 For example returns_nonnull affects only references, while
342 optimize attribute can be ignored because it is already lowered
343 into flags representation and compared separately. */
347 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
348 if (!attr
|| !attribute_value_equal (a
, attr
))
353 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
355 const struct attribute_spec
*as
;
357 as
= lookup_attribute_spec (get_attribute_name (a
));
361 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
363 /* We don't need to compare trees again, as we did this
364 already in first loop. */
369 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
373 /* Compare properties of symbols N1 and N2 that does not affect semantics of
374 symbol itself but affects semantics of its references from USED_BY (which
375 may be NULL if it is unknown). If comparsion is false, symbols
376 can still be merged but any symbols referring them can't.
378 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
380 TODO: We can also split attributes to those that determine codegen of
381 a function body/variable constructor itself and those that are used when
385 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
390 if (is_a
<cgraph_node
*> (n1
))
392 /* Inline properties matters: we do now want to merge uses of inline
393 function to uses of normal function because inline hint would be lost.
394 We however can merge inline function to noinline because the alias
395 will keep its DECL_DECLARED_INLINE flag.
397 Also ignore inline flag when optimizing for size or when function
398 is known to not be inlinable.
400 TODO: the optimize_size checks can also be assumed to be true if
401 unit has no !optimize_size functions. */
403 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
404 || !opt_for_fn (used_by
->decl
, optimize_size
))
405 && !opt_for_fn (n1
->decl
, optimize_size
)
406 && n1
->get_availability () > AVAIL_INTERPOSABLE
407 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
409 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
410 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
411 return return_false_with_msg
412 ("DECL_DISREGARD_INLINE_LIMITS are different");
414 if (DECL_DECLARED_INLINE_P (n1
->decl
)
415 != DECL_DECLARED_INLINE_P (n2
->decl
))
416 return return_false_with_msg ("inline attributes are different");
419 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
420 != DECL_IS_OPERATOR_NEW (n2
->decl
))
421 return return_false_with_msg ("operator new flags are different");
424 /* Merging two definitions with a reference to equivalent vtables, but
425 belonging to a different type may result in ipa-polymorphic-call analysis
426 giving a wrong answer about the dynamic type of instance. */
427 if (is_a
<varpool_node
*> (n1
))
429 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
430 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
431 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
432 DECL_CONTEXT (n2
->decl
)))
433 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
434 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
435 return return_false_with_msg
436 ("references to virtual tables can not be merged");
438 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
439 return return_false_with_msg ("alignment mismatch");
441 /* For functions we compare attributes in equals_wpa, because we do
442 not know what attributes may cause codegen differences, but for
443 variables just compare attributes for references - the codegen
444 for constructors is affected only by those attributes that we lower
445 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
446 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
447 DECL_ATTRIBUTES (n2
->decl
)))
448 return return_false_with_msg ("different var decl attributes");
449 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
450 TREE_TYPE (n2
->decl
)) != 1)
451 return return_false_with_msg ("different var type attributes");
454 /* When matching virtual tables, be sure to also match information
455 relevant for polymorphic call analysis. */
456 if (used_by
&& is_a
<varpool_node
*> (used_by
)
457 && DECL_VIRTUAL_P (used_by
->decl
))
459 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
460 return return_false_with_msg ("virtual flag mismatch");
461 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
462 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
463 return return_false_with_msg ("final flag mismatch");
468 /* Hash properties that are compared by compare_referenced_symbol_properties. */
471 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
472 inchash::hash
&hstate
,
475 if (is_a
<cgraph_node
*> (ref
))
477 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
478 && !opt_for_fn (ref
->decl
, optimize_size
)
479 && !DECL_UNINLINABLE (ref
->decl
))
481 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
482 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
484 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
486 else if (is_a
<varpool_node
*> (ref
))
488 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
490 hstate
.add_int (DECL_ALIGN (ref
->decl
));
495 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
496 point to a same function. Comparison can be skipped if IGNORED_NODES
497 contains these nodes. ADDRESS indicate if address is taken. */
500 sem_item::compare_symbol_references (
501 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
502 symtab_node
*n1
, symtab_node
*n2
, bool address
)
504 enum availability avail1
, avail2
;
509 /* Never match variable and function. */
510 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
513 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
515 if (address
&& n1
->equal_address_to (n2
) == 1)
517 if (!address
&& n1
->semantically_equivalent_p (n2
))
520 n1
= n1
->ultimate_alias_target (&avail1
);
521 n2
= n2
->ultimate_alias_target (&avail2
);
523 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
524 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
527 return return_false_with_msg ("different references");
530 /* If cgraph edges E1 and E2 are indirect calls, verify that
531 ECF flags are the same. */
533 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
535 if (e1
->indirect_info
&& e2
->indirect_info
)
537 int e1_flags
= e1
->indirect_info
->ecf_flags
;
538 int e2_flags
= e2
->indirect_info
->ecf_flags
;
540 if (e1_flags
!= e2_flags
)
541 return return_false_with_msg ("ICF flags are different");
543 else if (e1
->indirect_info
|| e2
->indirect_info
)
549 /* Return true if parameter I may be used. */
552 sem_function::param_used_p (unsigned int i
)
554 if (ipa_node_params_sum
== NULL
)
557 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
559 if (parms_info
->descriptors
.is_empty ()
560 || parms_info
->descriptors
.length () <= i
)
563 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
566 /* Perform additional check needed to match types function parameters that are
567 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
568 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
571 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
573 /* Be sure that parameters are TBAA compatible. */
574 if (!func_checker::compatible_types_p (parm1
, parm2
))
575 return return_false_with_msg ("parameter type is not compatible");
577 if (POINTER_TYPE_P (parm1
)
578 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
579 return return_false_with_msg ("argument restrict flag mismatch");
581 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
582 if (POINTER_TYPE_P (parm1
)
583 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
584 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
585 return return_false_with_msg ("pointer wrt reference mismatch");
590 /* Fast equality function based on knowledge known in WPA. */
593 sem_function::equals_wpa (sem_item
*item
,
594 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
596 gcc_assert (item
->type
== FUNC
);
597 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
598 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
600 m_compared_func
= static_cast<sem_function
*> (item
);
602 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
603 return return_false_with_msg ("thunk_p mismatch");
605 if (cnode
->thunk
.thunk_p
)
607 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
608 return return_false_with_msg ("thunk fixed_offset mismatch");
609 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
610 return return_false_with_msg ("thunk virtual_value mismatch");
611 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
612 return return_false_with_msg ("thunk this_adjusting mismatch");
613 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
614 return return_false_with_msg ("thunk virtual_offset_p mismatch");
615 if (cnode
->thunk
.add_pointer_bounds_args
616 != cnode2
->thunk
.add_pointer_bounds_args
)
617 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
620 /* Compare special function DECL attributes. */
621 if (DECL_FUNCTION_PERSONALITY (decl
)
622 != DECL_FUNCTION_PERSONALITY (item
->decl
))
623 return return_false_with_msg ("function personalities are different");
625 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
626 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
627 return return_false_with_msg ("intrument function entry exit "
628 "attributes are different");
630 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
631 return return_false_with_msg ("no stack limit attributes are different");
633 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
634 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
636 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
637 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
639 /* TODO: pure/const flags mostly matters only for references, except for
640 the fact that codegen takes LOOPING flag as a hint that loops are
641 finite. We may arrange the code to always pick leader that has least
642 specified flags and then this can go into comparing symbol properties. */
643 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
644 return return_false_with_msg ("decl_or_type flags are different");
646 /* Do not match polymorphic constructors of different types. They calls
647 type memory location for ipa-polymorphic-call and we do not want
648 it to get confused by wrong type. */
649 if (DECL_CXX_CONSTRUCTOR_P (decl
)
650 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
652 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
653 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
654 else if (!func_checker::compatible_polymorphic_types_p
655 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
656 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
657 return return_false_with_msg ("ctor polymorphic type mismatch");
660 /* Checking function TARGET and OPTIMIZATION flags. */
661 cl_target_option
*tar1
= target_opts_for_fn (decl
);
662 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
664 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
668 fprintf (dump_file
, "target flags difference");
669 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
672 return return_false_with_msg ("Target flags are different");
675 cl_optimization
*opt1
= opts_for_fn (decl
);
676 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
678 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
682 fprintf (dump_file
, "optimization flags difference");
683 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
686 return return_false_with_msg ("optimization flags are different");
689 /* Result type checking. */
690 if (!func_checker::compatible_types_p
691 (TREE_TYPE (TREE_TYPE (decl
)),
692 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
693 return return_false_with_msg ("result types are different");
695 /* Checking types of arguments. */
696 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
697 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
698 for (unsigned i
= 0; list1
&& list2
;
699 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
701 tree parm1
= TREE_VALUE (list1
);
702 tree parm2
= TREE_VALUE (list2
);
704 /* This guard is here for function pointer with attributes (pr59927.c). */
705 if (!parm1
|| !parm2
)
706 return return_false_with_msg ("NULL argument type");
708 /* Verify that types are compatible to ensure that both functions
709 have same calling conventions. */
710 if (!types_compatible_p (parm1
, parm2
))
711 return return_false_with_msg ("parameter types are not compatible");
713 if (!param_used_p (i
))
716 /* Perform additional checks for used parameters. */
717 if (!compatible_parm_types_p (parm1
, parm2
))
722 return return_false_with_msg ("Mismatched number of parameters");
724 if (node
->num_references () != item
->node
->num_references ())
725 return return_false_with_msg ("different number of references");
727 /* Checking function attributes.
728 This is quadratic in number of attributes */
729 if (comp_type_attributes (TREE_TYPE (decl
),
730 TREE_TYPE (item
->decl
)) != 1)
731 return return_false_with_msg ("different type attributes");
732 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
733 DECL_ATTRIBUTES (item
->decl
)))
734 return return_false_with_msg ("different decl attributes");
736 /* The type of THIS pointer type memory location for
737 ipa-polymorphic-call-analysis. */
738 if (opt_for_fn (decl
, flag_devirtualize
)
739 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
740 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
742 && compare_polymorphic_p ())
744 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
745 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
746 if (!func_checker::compatible_polymorphic_types_p
747 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
748 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
749 return return_false_with_msg ("THIS pointer ODR type mismatch");
752 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
753 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
755 item
->node
->iterate_reference (i
, ref2
);
757 if (ref
->use
!= ref2
->use
)
758 return return_false_with_msg ("reference use mismatch");
760 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
762 ref
->address_matters_p ()))
766 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
767 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
771 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
774 if (!compare_edge_flags (e1
, e2
))
777 e1
= e1
->next_callee
;
778 e2
= e2
->next_callee
;
782 return return_false_with_msg ("different number of calls");
784 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
785 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
789 if (!compare_edge_flags (e1
, e2
))
792 e1
= e1
->next_callee
;
793 e2
= e2
->next_callee
;
797 return return_false_with_msg ("different number of indirect calls");
802 /* Update hash by address sensitive references. We iterate over all
803 sensitive references (address_matters_p) and we hash ultime alias
804 target of these nodes, which can improve a semantic item hash.
806 Also hash in referenced symbols properties. This can be done at any time
807 (as the properties should not change), but it is convenient to do it here
808 while we walk the references anyway. */
811 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
812 sem_item
*> &m_symtab_node_map
)
815 inchash::hash
hstate (hash
);
817 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
819 hstate
.add_int (ref
->use
);
820 hash_referenced_symbol_properties (ref
->referred
, hstate
,
821 ref
->use
== IPA_REF_ADDR
);
822 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
823 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
826 if (is_a
<cgraph_node
*> (node
))
828 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
831 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
832 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
834 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
838 hash
= hstate
.end ();
841 /* Update hash by computed local hash values taken from different
843 TODO: stronger SCC based hashing would be desirable here. */
846 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
847 sem_item
*> &m_symtab_node_map
)
850 inchash::hash
state (hash
);
852 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
854 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
856 state
.merge_hash ((*result
)->hash
);
861 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
864 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
866 state
.merge_hash ((*result
)->hash
);
870 global_hash
= state
.end ();
873 /* Returns true if the item equals to ITEM given as argument. */
876 sem_function::equals (sem_item
*item
,
877 hash_map
<symtab_node
*, sem_item
*> &)
879 gcc_assert (item
->type
== FUNC
);
880 bool eq
= equals_private (item
);
882 if (m_checker
!= NULL
)
888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
890 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
891 xstrdup_for_dump (node
->name()),
892 xstrdup_for_dump (item
->node
->name ()),
895 xstrdup_for_dump (node
->asm_name ()),
896 xstrdup_for_dump (item
->node
->asm_name ()),
897 eq
? "true" : "false");
902 /* Processes function equality comparison. */
905 sem_function::equals_private (sem_item
*item
)
907 if (item
->type
!= FUNC
)
910 basic_block bb1
, bb2
;
912 edge_iterator ei1
, ei2
;
916 m_compared_func
= static_cast<sem_function
*> (item
);
918 gcc_assert (decl
!= item
->decl
);
920 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
921 || edge_count
!= m_compared_func
->edge_count
922 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
923 return return_false ();
925 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
926 compare_polymorphic_p (),
929 &m_compared_func
->refs_set
);
930 arg1
= DECL_ARGUMENTS (decl
);
931 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
933 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
935 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
936 return return_false_with_msg ("argument types are not compatible");
937 if (!param_used_p (i
))
939 /* Perform additional checks for used parameters. */
940 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
942 if (!m_checker
->compare_decl (arg1
, arg2
))
943 return return_false ();
946 return return_false_with_msg ("Mismatched number of arguments");
948 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
951 /* Fill-up label dictionary. */
952 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
954 m_checker
->parse_labels (bb_sorted
[i
]);
955 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
958 /* Checking all basic blocks. */
959 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
960 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
961 return return_false();
963 dump_message ("All BBs are equal\n");
965 auto_vec
<int> bb_dict
;
967 /* Basic block edges check. */
968 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
970 bb1
= bb_sorted
[i
]->bb
;
971 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
973 ei2
= ei_start (bb2
->preds
);
975 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
979 if (e1
->flags
!= e2
->flags
)
980 return return_false_with_msg ("flags comparison returns false");
982 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
983 return return_false_with_msg ("edge comparison returns false");
985 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
986 return return_false_with_msg ("BB comparison returns false");
988 if (!m_checker
->compare_edge (e1
, e2
))
989 return return_false_with_msg ("edge comparison returns false");
995 /* Basic block PHI nodes comparison. */
996 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
997 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
998 return return_false_with_msg ("PHI node comparison returns false");
1003 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
1004 Helper for call_for_symbol_thunks_and_aliases. */
1007 set_local (cgraph_node
*node
, void *data
)
1009 node
->local
.local
= data
!= NULL
;
1013 /* TREE_ADDRESSABLE of NODE to true.
1014 Helper for call_for_symbol_thunks_and_aliases. */
1017 set_addressable (varpool_node
*node
, void *)
1019 TREE_ADDRESSABLE (node
->decl
) = 1;
1023 /* Clear DECL_RTL of NODE.
1024 Helper for call_for_symbol_thunks_and_aliases. */
1027 clear_decl_rtl (symtab_node
*node
, void *)
1029 SET_DECL_RTL (node
->decl
, NULL
);
1033 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1034 possible. Return number of redirections made. */
1037 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1039 int nredirected
= 0;
1041 cgraph_edge
*e
= n
->callers
;
1045 /* Redirecting thunks to interposable symbols or symbols in other sections
1046 may not be supported by target output code. Play safe for now and
1047 punt on redirection. */
1048 if (!e
->caller
->thunk
.thunk_p
)
1050 struct cgraph_edge
*nexte
= e
->next_caller
;
1051 e
->redirect_callee (to
);
1058 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1060 bool removed
= false;
1061 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1063 if ((DECL_COMDAT_GROUP (n
->decl
)
1064 && (DECL_COMDAT_GROUP (n
->decl
)
1065 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1066 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1067 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1069 nredirected
+= redirect_all_callers (n_alias
, to
);
1070 if (n_alias
->can_remove_if_no_direct_calls_p ()
1071 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1073 && !n_alias
->has_aliases_p ())
1082 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1086 sem_function::merge (sem_item
*alias_item
)
1088 gcc_assert (alias_item
->type
== FUNC
);
1090 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1092 cgraph_node
*original
= get_node ();
1093 cgraph_node
*local_original
= NULL
;
1094 cgraph_node
*alias
= alias_func
->get_node ();
1096 bool create_wrapper
= false;
1097 bool create_alias
= false;
1098 bool redirect_callers
= false;
1099 bool remove
= false;
1101 bool original_discardable
= false;
1102 bool original_discarded
= false;
1104 bool original_address_matters
= original
->address_matters_p ();
1105 bool alias_address_matters
= alias
->address_matters_p ();
1107 if (DECL_EXTERNAL (alias
->decl
))
1110 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1114 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1115 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1120 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1124 /* Do not attempt to mix functions from different user sections;
1125 we do not know what user intends with those. */
1126 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1127 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1128 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1133 "original and alias are in different sections.\n\n");
1137 /* See if original is in a section that can be discarded if the main
1138 symbol is not used. */
1140 if (original
->can_be_discarded_p ())
1141 original_discardable
= true;
1142 /* Also consider case where we have resolution info and we know that
1143 original's definition is not going to be used. In this case we can not
1144 create alias to original. */
1145 if (node
->resolution
!= LDPR_UNKNOWN
1146 && !decl_binds_to_current_def_p (node
->decl
))
1147 original_discardable
= original_discarded
= true;
1149 /* Creating a symtab alias is the optimal way to merge.
1150 It however can not be used in the following cases:
1152 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1153 2) if ORIGINAL is in a section that may be discarded by linker or if
1154 it is an external functions where we can not create an alias
1155 (ORIGINAL_DISCARDABLE)
1156 3) if target do not support symbol aliases.
1157 4) original and alias lie in different comdat groups.
1159 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1160 and/or redirect all callers from ALIAS to ORIGINAL. */
1161 if ((original_address_matters
&& alias_address_matters
)
1162 || (original_discardable
1163 && (!DECL_COMDAT_GROUP (alias
->decl
)
1164 || (DECL_COMDAT_GROUP (alias
->decl
)
1165 != DECL_COMDAT_GROUP (original
->decl
))))
1166 || original_discarded
1167 || !sem_item::target_supports_symbol_aliases_p ()
1168 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1170 /* First see if we can produce wrapper. */
1172 /* Symbol properties that matter for references must be preserved.
1173 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1174 with proper properties. */
1175 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1176 alias
->address_taken
))
1180 "Wrapper cannot be created because referenced symbol "
1181 "properties mismatch\n");
1183 /* Do not turn function in one comdat group into wrapper to another
1184 comdat group. Other compiler producing the body of the
1185 another comdat group may make opossite decision and with unfortunate
1186 linker choices this may close a loop. */
1187 else if (DECL_COMDAT_GROUP (original
->decl
)
1188 && DECL_COMDAT_GROUP (alias
->decl
)
1189 && (DECL_COMDAT_GROUP (alias
->decl
)
1190 != DECL_COMDAT_GROUP (original
->decl
)))
1194 "Wrapper cannot be created because of COMDAT\n");
1196 else if (DECL_STATIC_CHAIN (alias
->decl
))
1200 "Can not create wrapper of nested functions.\n");
1202 /* TODO: We can also deal with variadic functions never calling
1204 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1208 "can not create wrapper of stdarg function.\n");
1210 else if (inline_summaries
1211 && inline_summaries
->get (alias
)->self_size
<= 2)
1214 fprintf (dump_file
, "Wrapper creation is not "
1215 "profitable (function is too small).\n");
1217 /* If user paid attention to mark function noinline, assume it is
1218 somewhat special and do not try to turn it into a wrapper that can
1219 not be undone by inliner. */
1220 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1223 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1226 create_wrapper
= true;
1228 /* We can redirect local calls in the case both alias and orignal
1229 are not interposable. */
1231 = alias
->get_availability () > AVAIL_INTERPOSABLE
1232 && original
->get_availability () > AVAIL_INTERPOSABLE
1233 && !alias
->instrumented_version
;
1234 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1235 with proper properties. */
1236 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1237 alias
->address_taken
))
1238 redirect_callers
= false;
1240 if (!redirect_callers
&& !create_wrapper
)
1243 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1244 "produce wrapper\n\n");
1248 /* Work out the symbol the wrapper should call.
1249 If ORIGINAL is interposable, we need to call a local alias.
1250 Also produce local alias (if possible) as an optimization.
1252 Local aliases can not be created inside comdat groups because that
1253 prevents inlining. */
1254 if (!original_discardable
&& !original
->get_comdat_group ())
1257 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1259 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1260 local_original
= original
;
1262 /* If we can not use local alias, fallback to the original
1264 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1265 local_original
= original
;
1267 /* If original is COMDAT local, we can not really redirect calls outside
1268 of its comdat group to it. */
1269 if (original
->comdat_local_p ())
1270 redirect_callers
= false;
1271 if (!local_original
)
1274 fprintf (dump_file
, "Not unifying; "
1275 "can not produce local alias.\n\n");
1279 if (!redirect_callers
&& !create_wrapper
)
1282 fprintf (dump_file
, "Not unifying; "
1283 "can not redirect callers nor produce a wrapper\n\n");
1287 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1289 && !alias
->can_remove_if_no_direct_calls_p ())
1292 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1293 "function has other uses than direct calls\n\n");
1298 create_alias
= true;
1300 if (redirect_callers
)
1302 int nredirected
= redirect_all_callers (alias
, local_original
);
1306 alias
->icf_merged
= true;
1307 local_original
->icf_merged
= true;
1309 if (dump_file
&& nredirected
)
1310 fprintf (dump_file
, "%i local calls have been "
1311 "redirected.\n", nredirected
);
1314 /* If all callers was redirected, do not produce wrapper. */
1315 if (alias
->can_remove_if_no_direct_calls_p ()
1316 && !alias
->has_aliases_p ())
1318 create_wrapper
= false;
1321 gcc_assert (!create_alias
);
1323 else if (create_alias
)
1325 alias
->icf_merged
= true;
1327 /* Remove the function's body. */
1328 ipa_merge_profiles (original
, alias
);
1329 alias
->release_body (true);
1331 /* Notice global symbol possibly produced RTL. */
1332 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1335 /* Create the alias. */
1336 cgraph_node::create_alias (alias_func
->decl
, decl
);
1337 alias
->resolve_alias (original
);
1339 original
->call_for_symbol_thunks_and_aliases
1340 (set_local
, (void *)(size_t) original
->local_p (), true);
1343 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1347 gcc_assert (!create_alias
);
1348 alias
->icf_merged
= true;
1349 local_original
->icf_merged
= true;
1351 ipa_merge_profiles (local_original
, alias
, true);
1352 alias
->create_wrapper (local_original
);
1355 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1358 /* It's possible that redirection can hit thunks that block
1359 redirection opportunities. */
1360 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1361 original
->icf_merged
= true;
1363 /* Inform the inliner about cross-module merging. */
1364 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1365 && original
->lto_file_data
!= alias
->lto_file_data
)
1366 local_original
->merged
= original
->merged
= true;
1370 ipa_merge_profiles (original
, alias
);
1371 alias
->release_body ();
1373 alias
->body_removed
= true;
1374 alias
->icf_merged
= true;
1376 fprintf (dump_file
, "Unified; Function body was removed.\n");
1382 /* Semantic item initialization function. */
1385 sem_function::init (void)
1388 get_node ()->get_untransformed_body ();
1390 tree fndecl
= node
->decl
;
1391 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1394 gcc_assert (SSANAMES (func
));
1396 ssa_names_size
= SSANAMES (func
)->length ();
1400 region_tree
= func
->eh
->region_tree
;
1402 /* iterating all function arguments. */
1403 arg_count
= count_formal_params (fndecl
);
1405 edge_count
= n_edges_for_fn (func
);
1406 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1407 if (!cnode
->thunk
.thunk_p
)
1409 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1411 inchash::hash hstate
;
1414 FOR_EACH_BB_FN (bb
, func
)
1416 unsigned nondbg_stmt_count
= 0;
1419 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1421 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1424 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1427 gimple
*stmt
= gsi_stmt (gsi
);
1429 if (gimple_code (stmt
) != GIMPLE_DEBUG
1430 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1432 hash_stmt (stmt
, hstate
);
1433 nondbg_stmt_count
++;
1437 gcode_hash
= hstate
.end ();
1438 bb_sizes
.safe_push (nondbg_stmt_count
);
1440 /* Inserting basic block to hash table. */
1441 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1442 EDGE_COUNT (bb
->preds
)
1443 + EDGE_COUNT (bb
->succs
));
1445 bb_sorted
.safe_push (semantic_bb
);
1451 inchash::hash hstate
;
1452 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1453 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1454 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1455 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1456 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1457 gcode_hash
= hstate
.end ();
1461 /* Accumulate to HSTATE a hash of expression EXP.
1462 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1463 and DECL equality classes. */
1466 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1468 if (exp
== NULL_TREE
)
1470 hstate
.merge_hash (0);
1474 /* Handled component can be matched in a cureful way proving equivalence
1475 even if they syntactically differ. Just skip them. */
1477 while (handled_component_p (exp
))
1478 exp
= TREE_OPERAND (exp
, 0);
1480 enum tree_code code
= TREE_CODE (exp
);
1481 hstate
.add_int (code
);
1485 /* Use inchash::add_expr for everything that is LTO stable. */
1493 inchash::add_expr (exp
, hstate
);
1497 unsigned HOST_WIDE_INT idx
;
1500 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1502 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1504 add_expr (value
, hstate
);
1509 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1515 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1518 case POINTER_PLUS_EXPR
:
1521 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1522 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1526 inchash::hash one
, two
;
1527 add_expr (TREE_OPERAND (exp
, 0), one
);
1528 add_expr (TREE_OPERAND (exp
, 1), two
);
1529 hstate
.add_commutative (one
, two
);
1533 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1534 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1540 /* Accumulate to HSTATE a hash of type t.
1541 TYpes that may end up being compatible after LTO type merging needs to have
1545 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1547 if (type
== NULL_TREE
)
1549 hstate
.merge_hash (0);
1553 type
= TYPE_MAIN_VARIANT (type
);
1554 if (TYPE_CANONICAL (type
))
1555 type
= TYPE_CANONICAL (type
);
1557 if (!AGGREGATE_TYPE_P (type
))
1558 hstate
.add_int (TYPE_MODE (type
));
1560 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1562 hstate
.add_int (COMPLEX_TYPE
);
1563 sem_item::add_type (TREE_TYPE (type
), hstate
);
1565 else if (INTEGRAL_TYPE_P (type
))
1567 hstate
.add_int (INTEGER_TYPE
);
1568 hstate
.add_flag (TYPE_UNSIGNED (type
));
1569 hstate
.add_int (TYPE_PRECISION (type
));
1571 else if (VECTOR_TYPE_P (type
))
1573 hstate
.add_int (VECTOR_TYPE
);
1574 hstate
.add_int (TYPE_PRECISION (type
));
1575 sem_item::add_type (TREE_TYPE (type
), hstate
);
1577 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1579 hstate
.add_int (ARRAY_TYPE
);
1580 /* Do not hash size, so complete and incomplete types can match. */
1581 sem_item::add_type (TREE_TYPE (type
), hstate
);
1583 else if (RECORD_OR_UNION_TYPE_P (type
))
1585 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1589 inchash::hash hstate2
;
1594 hstate2
.add_int (RECORD_TYPE
);
1595 gcc_assert (COMPLETE_TYPE_P (type
));
1597 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1598 if (TREE_CODE (f
) == FIELD_DECL
)
1600 add_type (TREE_TYPE (f
), hstate2
);
1604 hstate2
.add_int (nf
);
1605 hash
= hstate2
.end ();
1606 hstate
.add_wide_int (hash
);
1607 optimizer
->m_type_hash_cache
.put (type
, hash
);
1610 hstate
.add_wide_int (*val
);
1614 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1617 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1619 enum gimple_code code
= gimple_code (stmt
);
1621 hstate
.add_int (code
);
1626 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1629 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1630 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1631 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1633 inchash::hash one
, two
;
1635 add_expr (gimple_assign_rhs1 (stmt
), one
);
1636 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1637 add_expr (gimple_assign_rhs2 (stmt
), two
);
1638 hstate
.add_commutative (one
, two
);
1639 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1641 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1642 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1644 add_expr (gimple_assign_lhs (stmt
), hstate
);
1645 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1648 /* ... fall through ... */
1654 /* All these statements are equivalent if their operands are. */
1655 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1657 add_expr (gimple_op (stmt
, i
), hstate
);
1658 if (gimple_op (stmt
, i
))
1659 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1667 /* Return true if polymorphic comparison must be processed. */
1670 sem_function::compare_polymorphic_p (void)
1672 struct cgraph_edge
*e
;
1674 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1676 if (get_node ()->indirect_calls
!= NULL
)
1678 /* TODO: We can do simple propagation determining what calls may lead to
1679 a polymorphic call. */
1680 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1681 if (e
->callee
->definition
1682 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1687 /* For a given call graph NODE, the function constructs new
1688 semantic function item. */
1691 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1693 tree fndecl
= node
->decl
;
1694 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1696 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1699 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1702 sem_function
*f
= new sem_function (node
, 0, stack
);
1709 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1710 return true if phi nodes are semantically equivalent in these blocks . */
1713 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1715 gphi_iterator si1
, si2
;
1717 unsigned size1
, size2
, i
;
1721 gcc_assert (bb1
!= NULL
);
1722 gcc_assert (bb2
!= NULL
);
1724 si2
= gsi_start_phis (bb2
);
1725 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1728 gsi_next_nonvirtual_phi (&si1
);
1729 gsi_next_nonvirtual_phi (&si2
);
1731 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1734 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1735 return return_false();
1740 tree phi_result1
= gimple_phi_result (phi1
);
1741 tree phi_result2
= gimple_phi_result (phi2
);
1743 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1744 return return_false_with_msg ("PHI results are different");
1746 size1
= gimple_phi_num_args (phi1
);
1747 size2
= gimple_phi_num_args (phi2
);
1750 return return_false ();
1752 for (i
= 0; i
< size1
; ++i
)
1754 t1
= gimple_phi_arg (phi1
, i
)->def
;
1755 t2
= gimple_phi_arg (phi2
, i
)->def
;
1757 if (!m_checker
->compare_operand (t1
, t2
))
1758 return return_false ();
1760 e1
= gimple_phi_arg_edge (phi1
, i
);
1761 e2
= gimple_phi_arg_edge (phi2
, i
);
1763 if (!m_checker
->compare_edge (e1
, e2
))
1764 return return_false ();
1773 /* Returns true if tree T can be compared as a handled component. */
1776 sem_function::icf_handled_component_p (tree t
)
1778 tree_code tc
= TREE_CODE (t
);
1780 return (handled_component_p (t
)
1781 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1784 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1785 corresponds to TARGET. */
1788 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1793 if (bb_dict
->length () <= (unsigned)source
)
1794 bb_dict
->safe_grow_cleared (source
+ 1);
1796 if ((*bb_dict
)[source
] == 0)
1798 (*bb_dict
)[source
] = target
;
1802 return (*bb_dict
)[source
] == target
;
1806 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1808 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1812 /* Constructor based on varpool node _NODE with computed hash _HASH.
1813 Bitmap STACK is used for memory allocation. */
1815 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1816 bitmap_obstack
*stack
): sem_item(VAR
,
1819 gcc_checking_assert (node
);
1820 gcc_checking_assert (get_node ());
1823 /* Fast equality function based on knowledge known in WPA. */
1826 sem_variable::equals_wpa (sem_item
*item
,
1827 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1829 gcc_assert (item
->type
== VAR
);
1831 if (node
->num_references () != item
->node
->num_references ())
1832 return return_false_with_msg ("different number of references");
1834 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1835 return return_false_with_msg ("TLS model");
1837 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1838 alignment out of all aliases. */
1840 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1841 return return_false_with_msg ("Virtual flag mismatch");
1843 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1844 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1845 || !operand_equal_p (DECL_SIZE (decl
),
1846 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1847 return return_false_with_msg ("size mismatch");
1849 /* Do not attempt to mix data from different user sections;
1850 we do not know what user intends with those. */
1851 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1852 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1853 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1854 return return_false_with_msg ("user section mismatch");
1856 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1857 return return_false_with_msg ("text section");
1859 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1860 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1862 item
->node
->iterate_reference (i
, ref2
);
1864 if (ref
->use
!= ref2
->use
)
1865 return return_false_with_msg ("reference use mismatch");
1867 if (!compare_symbol_references (ignored_nodes
,
1868 ref
->referred
, ref2
->referred
,
1869 ref
->address_matters_p ()))
1876 /* Returns true if the item equals to ITEM given as argument. */
1879 sem_variable::equals (sem_item
*item
,
1880 hash_map
<symtab_node
*, sem_item
*> &)
1882 gcc_assert (item
->type
== VAR
);
1885 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1886 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1887 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1888 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1890 /* As seen in PR ipa/65303 we have to compare variables types. */
1891 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1892 TREE_TYPE (item
->decl
)))
1893 return return_false_with_msg ("variables types are different");
1895 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1896 DECL_INITIAL (item
->node
->decl
));
1897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1899 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1900 xstrdup_for_dump (node
->name()),
1901 xstrdup_for_dump (item
->node
->name ()),
1902 node
->order
, item
->node
->order
,
1903 xstrdup_for_dump (node
->asm_name ()),
1904 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1909 /* Compares trees T1 and T2 for semantic equality. */
1912 sem_variable::equals (tree t1
, tree t2
)
1915 return return_with_debug (t1
== t2
);
1918 tree_code tc1
= TREE_CODE (t1
);
1919 tree_code tc2
= TREE_CODE (t2
);
1922 return return_false_with_msg ("TREE_CODE mismatch");
1928 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1929 unsigned HOST_WIDE_INT idx
;
1931 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1932 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1933 return return_false_with_msg ("constructor type mismatch");
1935 if (typecode
== ARRAY_TYPE
)
1937 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1938 /* For arrays, check that the sizes all match. */
1939 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1941 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1942 return return_false_with_msg ("constructor array size mismatch");
1944 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1946 return return_false_with_msg ("constructor type incompatible");
1948 v1
= CONSTRUCTOR_ELTS (t1
);
1949 v2
= CONSTRUCTOR_ELTS (t2
);
1950 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1951 return return_false_with_msg ("constructor number of elts mismatch");
1953 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1955 constructor_elt
*c1
= &(*v1
)[idx
];
1956 constructor_elt
*c2
= &(*v2
)[idx
];
1958 /* Check that each value is the same... */
1959 if (!sem_variable::equals (c1
->value
, c2
->value
))
1961 /* ... and that they apply to the same fields! */
1962 if (!sem_variable::equals (c1
->index
, c2
->index
))
1969 tree x1
= TREE_OPERAND (t1
, 0);
1970 tree x2
= TREE_OPERAND (t2
, 0);
1971 tree y1
= TREE_OPERAND (t1
, 1);
1972 tree y2
= TREE_OPERAND (t2
, 1);
1974 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1975 return return_false ();
1977 /* Type of the offset on MEM_REF does not matter. */
1978 return return_with_debug (sem_variable::equals (x1
, x2
)
1979 && wi::to_offset (y1
)
1980 == wi::to_offset (y2
));
1985 tree op1
= TREE_OPERAND (t1
, 0);
1986 tree op2
= TREE_OPERAND (t2
, 0);
1987 return sem_variable::equals (op1
, op2
);
1989 /* References to other vars/decls are compared using ipa-ref. */
1992 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1994 return return_false_with_msg ("Declaration mismatch");
1996 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1997 need to process its VAR/FUNCTION references without relying on ipa-ref
2001 return return_false_with_msg ("Declaration mismatch");
2003 /* Integer constants are the same only if the same width of type. */
2004 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2005 return return_false_with_msg ("INTEGER_CST precision mismatch");
2006 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2007 return return_false_with_msg ("INTEGER_CST mode mismatch");
2008 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2010 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2011 return return_false_with_msg ("STRING_CST mode mismatch");
2012 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2013 return return_false_with_msg ("STRING_CST length mismatch");
2014 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2015 TREE_STRING_LENGTH (t1
)))
2016 return return_false_with_msg ("STRING_CST mismatch");
2019 /* Fixed constants are the same only if the same width of type. */
2020 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2021 return return_false_with_msg ("FIXED_CST precision mismatch");
2023 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2024 TREE_FIXED_CST (t2
)));
2026 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2027 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2029 /* Real constants are the same only if the same width of type. */
2030 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2031 return return_false_with_msg ("REAL_CST precision mismatch");
2032 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2033 &TREE_REAL_CST (t2
)));
2038 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2039 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2041 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2042 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2043 VECTOR_CST_ELT (t2
, i
)))
2049 case ARRAY_RANGE_REF
:
2051 tree x1
= TREE_OPERAND (t1
, 0);
2052 tree x2
= TREE_OPERAND (t2
, 0);
2053 tree y1
= TREE_OPERAND (t1
, 1);
2054 tree y2
= TREE_OPERAND (t2
, 1);
2056 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2058 if (!sem_variable::equals (array_ref_low_bound (t1
),
2059 array_ref_low_bound (t2
)))
2061 if (!sem_variable::equals (array_ref_element_size (t1
),
2062 array_ref_element_size (t2
)))
2068 case POINTER_PLUS_EXPR
:
2073 tree x1
= TREE_OPERAND (t1
, 0);
2074 tree x2
= TREE_OPERAND (t2
, 0);
2075 tree y1
= TREE_OPERAND (t1
, 1);
2076 tree y2
= TREE_OPERAND (t2
, 1);
2078 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2082 case VIEW_CONVERT_EXPR
:
2083 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2084 return return_false ();
2085 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2087 return return_false_with_msg ("ERROR_MARK");
2089 return return_false_with_msg ("Unknown TREE code reached");
2093 /* Parser function that visits a varpool NODE. */
2096 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2098 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2102 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2109 /* References independent hash function. */
2112 sem_variable::get_hash (void)
2117 /* All WPA streamed in symbols should have their hashes computed at compile
2118 time. At this point, the constructor may not be in memory at all.
2119 DECL_INITIAL (decl) would be error_mark_node in that case. */
2120 gcc_assert (!node
->lto_file_data
);
2121 tree ctor
= DECL_INITIAL (decl
);
2122 inchash::hash hstate
;
2124 hstate
.add_int (456346417);
2125 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2126 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2127 add_expr (ctor
, hstate
);
2128 hash
= hstate
.end ();
2133 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2137 sem_variable::merge (sem_item
*alias_item
)
2139 gcc_assert (alias_item
->type
== VAR
);
2141 if (!sem_item::target_supports_symbol_aliases_p ())
2144 fprintf (dump_file
, "Not unifying; "
2145 "Symbol aliases are not supported by target\n\n");
2149 if (DECL_EXTERNAL (alias_item
->decl
))
2152 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2156 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2158 varpool_node
*original
= get_node ();
2159 varpool_node
*alias
= alias_var
->get_node ();
2160 bool original_discardable
= false;
2162 bool original_address_matters
= original
->address_matters_p ();
2163 bool alias_address_matters
= alias
->address_matters_p ();
2165 /* See if original is in a section that can be discarded if the main
2167 Also consider case where we have resolution info and we know that
2168 original's definition is not going to be used. In this case we can not
2169 create alias to original. */
2170 if (original
->can_be_discarded_p ()
2171 || (node
->resolution
!= LDPR_UNKNOWN
2172 && !decl_binds_to_current_def_p (node
->decl
)))
2173 original_discardable
= true;
2175 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2177 /* Constant pool machinery is not quite ready for aliases.
2178 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2179 For LTO merging does not happen that is an important missing feature.
2180 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2181 flag is dropped and non-local symbol name is assigned. */
2182 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2183 || DECL_IN_CONSTANT_POOL (original
->decl
))
2187 "Not unifying; constant pool variables.\n\n");
2191 /* Do not attempt to mix functions from different user sections;
2192 we do not know what user intends with those. */
2193 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2194 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2195 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2200 "original and alias are in different sections.\n\n");
2204 /* We can not merge if address comparsion metters. */
2205 if (original_address_matters
&& alias_address_matters
2206 && flag_merge_constants
< 2)
2211 "adress of original and alias may be compared.\n\n");
2214 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2217 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2218 "across comdat group boundary\n\n");
2223 if (original_discardable
)
2226 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2227 "target is discardable\n\n");
2233 gcc_assert (!original
->alias
);
2234 gcc_assert (!alias
->alias
);
2236 alias
->analyzed
= false;
2238 DECL_INITIAL (alias
->decl
) = NULL
;
2239 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2241 alias
->need_bounds_init
= false;
2242 alias
->remove_all_references ();
2243 if (TREE_ADDRESSABLE (alias
->decl
))
2244 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2246 varpool_node::create_alias (alias_var
->decl
, decl
);
2247 alias
->resolve_alias (original
);
2250 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2256 /* Dump symbol to FILE. */
2259 sem_variable::dump_to_file (FILE *file
)
2263 print_node (file
, "", decl
, 0);
2264 fprintf (file
, "\n\n");
2267 unsigned int sem_item_optimizer::class_id
= 0;
2269 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2270 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2273 bitmap_obstack_initialize (&m_bmstack
);
2276 sem_item_optimizer::~sem_item_optimizer ()
2278 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2281 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2282 it
!= m_classes
.end (); ++it
)
2284 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2285 delete (*it
)->classes
[i
];
2287 (*it
)->classes
.release ();
2293 bitmap_obstack_release (&m_bmstack
);
2296 /* Write IPA ICF summary for symbols. */
2299 sem_item_optimizer::write_summary (void)
2301 unsigned int count
= 0;
2303 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2304 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2307 /* Calculate number of symbols to be serialized. */
2308 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2310 lsei_next_in_partition (&lsei
))
2312 symtab_node
*node
= lsei_node (lsei
);
2314 if (m_symtab_node_map
.get (node
))
2318 streamer_write_uhwi (ob
, count
);
2320 /* Process all of the symbols. */
2321 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2323 lsei_next_in_partition (&lsei
))
2325 symtab_node
*node
= lsei_node (lsei
);
2327 sem_item
**item
= m_symtab_node_map
.get (node
);
2331 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2332 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2334 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2338 streamer_write_char_stream (ob
->main_stream
, 0);
2339 produce_asm (ob
, NULL
);
2340 destroy_output_block (ob
);
2343 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2344 contains LEN bytes. */
2347 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2348 const char *data
, size_t len
)
2350 const lto_function_header
*header
=
2351 (const lto_function_header
*) data
;
2352 const int cfg_offset
= sizeof (lto_function_header
);
2353 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2354 const int string_offset
= main_offset
+ header
->main_size
;
2359 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2360 header
->main_size
, file_data
->mode_table
);
2363 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2364 header
->string_size
, vNULL
);
2366 count
= streamer_read_uhwi (&ib_main
);
2368 for (i
= 0; i
< count
; i
++)
2372 lto_symtab_encoder_t encoder
;
2374 index
= streamer_read_uhwi (&ib_main
);
2375 encoder
= file_data
->symtab_node_encoder
;
2376 node
= lto_symtab_encoder_deref (encoder
, index
);
2378 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2380 gcc_assert (node
->definition
);
2383 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2384 node
->asm_name (), (void *) node
->decl
, node
->order
);
2386 if (is_a
<cgraph_node
*> (node
))
2388 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2390 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2394 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2396 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2400 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2402 lto_data_in_delete (data_in
);
2405 /* Read IPA ICF summary for symbols. */
2408 sem_item_optimizer::read_summary (void)
2410 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2411 lto_file_decl_data
*file_data
;
2414 while ((file_data
= file_data_vec
[j
++]))
2417 const char *data
= lto_get_section_data (file_data
,
2418 LTO_section_ipa_icf
, NULL
, &len
);
2421 read_section (file_data
, data
, len
);
2425 /* Register callgraph and varpool hooks. */
2428 sem_item_optimizer::register_hooks (void)
2430 if (!m_cgraph_node_hooks
)
2431 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2432 (&sem_item_optimizer::cgraph_removal_hook
, this);
2434 if (!m_varpool_node_hooks
)
2435 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2436 (&sem_item_optimizer::varpool_removal_hook
, this);
2439 /* Unregister callgraph and varpool hooks. */
2442 sem_item_optimizer::unregister_hooks (void)
2444 if (m_cgraph_node_hooks
)
2445 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2447 if (m_varpool_node_hooks
)
2448 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2451 /* Adds a CLS to hashtable associated by hash value. */
2454 sem_item_optimizer::add_class (congruence_class
*cls
)
2456 gcc_assert (cls
->members
.length ());
2458 congruence_class_group
*group
= get_group_by_hash (
2459 cls
->members
[0]->get_hash (),
2460 cls
->members
[0]->type
);
2461 group
->classes
.safe_push (cls
);
2464 /* Gets a congruence class group based on given HASH value and TYPE. */
2466 congruence_class_group
*
2467 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2469 congruence_class_group
*item
= XNEW (congruence_class_group
);
2473 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2479 item
->classes
.create (1);
2486 /* Callgraph removal hook called for a NODE with a custom DATA. */
2489 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2491 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2492 optimizer
->remove_symtab_node (node
);
2495 /* Varpool removal hook called for a NODE with a custom DATA. */
2498 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2500 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2501 optimizer
->remove_symtab_node (node
);
2504 /* Remove symtab NODE triggered by symtab removal hooks. */
2507 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2509 gcc_assert (!m_classes
.elements());
2511 m_removed_items_set
.add (node
);
2515 sem_item_optimizer::remove_item (sem_item
*item
)
2517 if (m_symtab_node_map
.get (item
->node
))
2518 m_symtab_node_map
.remove (item
->node
);
2522 /* Removes all callgraph and varpool nodes that are marked by symtab
2526 sem_item_optimizer::filter_removed_items (void)
2528 auto_vec
<sem_item
*> filtered
;
2530 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2532 sem_item
*item
= m_items
[i
];
2534 if (m_removed_items_set
.contains (item
->node
))
2540 if (item
->type
== FUNC
)
2542 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2544 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2547 filtered
.safe_push (item
);
2551 if (!flag_ipa_icf_variables
)
2555 /* Filter out non-readonly variables. */
2556 tree decl
= item
->decl
;
2557 if (TREE_READONLY (decl
))
2558 filtered
.safe_push (item
);
2565 /* Clean-up of released semantic items. */
2568 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2569 m_items
.safe_push (filtered
[i
]);
2572 /* Optimizer entry point which returns true in case it processes
2573 a merge operation. True is returned if there's a merge operation
2577 sem_item_optimizer::execute (void)
2579 filter_removed_items ();
2580 unregister_hooks ();
2583 update_hash_by_addr_refs ();
2584 build_hash_based_classes ();
2587 fprintf (dump_file
, "Dump after hash based groups\n");
2588 dump_cong_classes ();
2590 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2591 m_items
[i
]->init_wpa ();
2593 subdivide_classes_by_equality (true);
2596 fprintf (dump_file
, "Dump after WPA based types groups\n");
2598 dump_cong_classes ();
2600 process_cong_reduction ();
2601 checking_verify_classes ();
2604 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2606 dump_cong_classes ();
2608 parse_nonsingleton_classes ();
2609 subdivide_classes_by_equality ();
2612 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2614 dump_cong_classes ();
2616 unsigned int prev_class_count
= m_classes_count
;
2618 process_cong_reduction ();
2619 dump_cong_classes ();
2620 checking_verify_classes ();
2621 bool merged_p
= merge_classes (prev_class_count
);
2623 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2624 symtab_node::dump_table (dump_file
);
2629 /* Function responsible for visiting all potential functions and
2630 read-only variables that can be merged. */
2633 sem_item_optimizer::parse_funcs_and_vars (void)
2637 if (flag_ipa_icf_functions
)
2638 FOR_EACH_DEFINED_FUNCTION (cnode
)
2640 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2643 m_items
.safe_push (f
);
2644 m_symtab_node_map
.put (cnode
, f
);
2647 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 f
->dump_to_file (dump_file
);
2653 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2656 varpool_node
*vnode
;
2658 if (flag_ipa_icf_variables
)
2659 FOR_EACH_DEFINED_VARIABLE (vnode
)
2661 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2665 m_items
.safe_push (v
);
2666 m_symtab_node_map
.put (vnode
, v
);
2671 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2674 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2676 item
->index_in_class
= cls
->members
.length ();
2677 cls
->members
.safe_push (item
);
2681 /* For each semantic item, append hash values of references. */
2684 sem_item_optimizer::update_hash_by_addr_refs ()
2686 /* First, append to hash sensitive references and class type if it need to
2687 be matched for ODR. */
2688 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2690 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2691 if (m_items
[i
]->type
== FUNC
)
2693 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2694 && contains_polymorphic_type_p
2695 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2696 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2697 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2698 && static_cast<sem_function
*> (m_items
[i
])
2699 ->compare_polymorphic_p ())))
2702 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2703 inchash::hash
hstate (m_items
[i
]->hash
);
2705 if (TYPE_NAME (class_type
)
2706 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2708 (IDENTIFIER_HASH_VALUE
2709 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2711 m_items
[i
]->hash
= hstate
.end ();
2716 /* Once all symbols have enhanced hash value, we can append
2717 hash values of symbols that are seen by IPA ICF and are
2718 references by a semantic item. Newly computed values
2719 are saved to global_hash member variable. */
2720 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2721 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2723 /* Global hash value replace current hash values. */
2724 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2725 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2728 /* Congruence classes are built by hash value. */
2731 sem_item_optimizer::build_hash_based_classes (void)
2733 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2735 sem_item
*item
= m_items
[i
];
2737 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2740 if (!group
->classes
.length ())
2743 group
->classes
.safe_push (new congruence_class (class_id
++));
2746 add_item_to_class (group
->classes
[0], item
);
2750 /* Build references according to call graph. */
2753 sem_item_optimizer::build_graph (void)
2755 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2757 sem_item
*item
= m_items
[i
];
2758 m_symtab_node_map
.put (item
->node
, item
);
2761 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2763 sem_item
*item
= m_items
[i
];
2765 if (item
->type
== FUNC
)
2767 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2769 cgraph_edge
*e
= cnode
->callees
;
2772 sem_item
**slot
= m_symtab_node_map
.get
2773 (e
->callee
->ultimate_alias_target ());
2775 item
->add_reference (*slot
);
2781 ipa_ref
*ref
= NULL
;
2782 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2784 sem_item
**slot
= m_symtab_node_map
.get
2785 (ref
->referred
->ultimate_alias_target ());
2787 item
->add_reference (*slot
);
2792 /* Semantic items in classes having more than one element and initialized.
2793 In case of WPA, we load function body. */
2796 sem_item_optimizer::parse_nonsingleton_classes (void)
2798 unsigned int init_called_count
= 0;
2800 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2801 if (m_items
[i
]->cls
->members
.length () > 1)
2803 m_items
[i
]->init ();
2804 init_called_count
++;
2808 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2809 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2812 /* Equality function for semantic items is used to subdivide existing
2813 classes. If IN_WPA, fast equality function is invoked. */
2816 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2818 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2819 it
!= m_classes
.end (); ++it
)
2821 unsigned int class_count
= (*it
)->classes
.length ();
2823 for (unsigned i
= 0; i
< class_count
; i
++)
2825 congruence_class
*c
= (*it
)->classes
[i
];
2827 if (c
->members
.length() > 1)
2829 auto_vec
<sem_item
*> new_vector
;
2831 sem_item
*first
= c
->members
[0];
2832 new_vector
.safe_push (first
);
2834 unsigned class_split_first
= (*it
)->classes
.length ();
2836 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2838 sem_item
*item
= c
->members
[j
];
2840 bool equals
= in_wpa
? first
->equals_wpa (item
,
2841 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2844 new_vector
.safe_push (item
);
2847 bool integrated
= false;
2849 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2851 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2852 bool equals
= in_wpa
? x
->equals_wpa (item
,
2853 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2858 add_item_to_class ((*it
)->classes
[k
], item
);
2866 congruence_class
*c
= new congruence_class (class_id
++);
2868 add_item_to_class (c
, item
);
2870 (*it
)->classes
.safe_push (c
);
2875 // we replace newly created new_vector for the class we've just splitted
2876 c
->members
.release ();
2877 c
->members
.create (new_vector
.length ());
2879 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2880 add_item_to_class (c
, new_vector
[j
]);
2885 checking_verify_classes ();
2888 /* Subdivide classes by address references that members of the class
2889 reference. Example can be a pair of functions that have an address
2890 taken from a function. If these addresses are different the class
2894 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2896 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2898 unsigned newly_created_classes
= 0;
2900 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2901 it
!= m_classes
.end (); ++it
)
2903 unsigned int class_count
= (*it
)->classes
.length ();
2904 auto_vec
<congruence_class
*> new_classes
;
2906 for (unsigned i
= 0; i
< class_count
; i
++)
2908 congruence_class
*c
= (*it
)->classes
[i
];
2910 if (c
->members
.length() > 1)
2912 subdivide_hash_map split_map
;
2914 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2916 sem_item
*source_node
= c
->members
[j
];
2918 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2921 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2923 gcc_checking_assert (slot
);
2925 slot
->safe_push (source_node
);
2931 /* If the map contains more than one key, we have to split the map
2933 if (split_map
.elements () != 1)
2935 bool first_class
= true;
2937 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2938 it2
!= split_map
.end (); ++it2
)
2940 congruence_class
*new_cls
;
2941 new_cls
= new congruence_class (class_id
++);
2943 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2944 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2946 worklist_push (new_cls
);
2947 newly_created_classes
++;
2951 (*it
)->classes
[i
] = new_cls
;
2952 first_class
= false;
2956 new_classes
.safe_push (new_cls
);
2962 /* Release memory. */
2963 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2964 it2
!= split_map
.end (); ++it2
)
2966 delete (*it2
).first
;
2967 (*it2
).second
.release ();
2972 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2973 (*it
)->classes
.safe_push (new_classes
[i
]);
2976 return newly_created_classes
;
2979 /* Verify congruence classes, if checking is enabled. */
2982 sem_item_optimizer::checking_verify_classes (void)
2988 /* Verify congruence classes. */
2991 sem_item_optimizer::verify_classes (void)
2993 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2994 it
!= m_classes
.end (); ++it
)
2996 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2998 congruence_class
*cls
= (*it
)->classes
[i
];
3001 gcc_assert (cls
->members
.length () > 0);
3003 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3005 sem_item
*item
= cls
->members
[j
];
3008 gcc_assert (item
->cls
== cls
);
3010 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3012 sem_usage_pair
*usage
= item
->usages
[k
];
3013 gcc_assert (usage
->item
->index_in_class
<
3014 usage
->item
->cls
->members
.length ());
3021 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3022 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3023 but unused argument. */
3026 sem_item_optimizer::release_split_map (congruence_class
* const &,
3027 bitmap
const &b
, traverse_split_pair
*)
3036 /* Process split operation for a class given as pointer CLS_PTR,
3037 where bitmap B splits congruence class members. DATA is used
3038 as argument of split pair. */
3041 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3042 bitmap
const &b
, traverse_split_pair
*pair
)
3044 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3045 const congruence_class
*splitter_cls
= pair
->cls
;
3047 /* If counted bits are greater than zero and less than the number of members
3048 a group will be splitted. */
3049 unsigned popcount
= bitmap_count_bits (b
);
3051 if (popcount
> 0 && popcount
< cls
->members
.length ())
3053 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
3055 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3057 int target
= bitmap_bit_p (b
, i
);
3058 congruence_class
*tc
= newclasses
[target
];
3060 add_item_to_class (tc
, cls
->members
[i
]);
3065 for (unsigned int i
= 0; i
< 2; i
++)
3066 gcc_assert (newclasses
[i
]->members
.length ());
3069 if (splitter_cls
== cls
)
3070 optimizer
->splitter_class_removed
= true;
3072 /* Remove old class from worklist if presented. */
3073 bool in_worklist
= cls
->in_worklist
;
3076 cls
->in_worklist
= false;
3078 congruence_class_group g
;
3079 g
.hash
= cls
->members
[0]->get_hash ();
3080 g
.type
= cls
->members
[0]->type
;
3082 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3084 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3085 if (slot
->classes
[i
] == cls
)
3087 slot
->classes
.ordered_remove (i
);
3091 /* New class will be inserted and integrated to work list. */
3092 for (unsigned int i
= 0; i
< 2; i
++)
3093 optimizer
->add_class (newclasses
[i
]);
3095 /* Two classes replace one, so that increment just by one. */
3096 optimizer
->m_classes_count
++;
3098 /* If OLD class was presented in the worklist, we remove the class
3099 and replace it will both newly created classes. */
3101 for (unsigned int i
= 0; i
< 2; i
++)
3102 optimizer
->worklist_push (newclasses
[i
]);
3103 else /* Just smaller class is inserted. */
3105 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3106 newclasses
[1]->members
.length () ?
3108 optimizer
->worklist_push (newclasses
[smaller_index
]);
3111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3113 fprintf (dump_file
, " congruence class splitted:\n");
3114 cls
->dump (dump_file
, 4);
3116 fprintf (dump_file
, " newly created groups:\n");
3117 for (unsigned int i
= 0; i
< 2; i
++)
3118 newclasses
[i
]->dump (dump_file
, 4);
3121 /* Release class if not presented in work list. */
3130 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3131 Bitmap stack BMSTACK is used for bitmap allocation. */
3134 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3137 hash_map
<congruence_class
*, bitmap
> split_map
;
3139 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3141 sem_item
*item
= cls
->members
[i
];
3143 /* Iterate all usages that have INDEX as usage of the item. */
3144 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3146 sem_usage_pair
*usage
= item
->usages
[j
];
3148 if (usage
->index
!= index
)
3151 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3156 b
= BITMAP_ALLOC (&m_bmstack
);
3157 split_map
.put (usage
->item
->cls
, b
);
3162 gcc_checking_assert (usage
->item
->cls
);
3163 gcc_checking_assert (usage
->item
->index_in_class
<
3164 usage
->item
->cls
->members
.length ());
3166 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3170 traverse_split_pair pair
;
3171 pair
.optimizer
= this;
3174 splitter_class_removed
= false;
3176 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3178 /* Bitmap clean-up. */
3180 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3183 /* Every usage of a congruence class CLS is a candidate that can split the
3184 collection of classes. Bitmap stack BMSTACK is used for bitmap
3188 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3193 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3195 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3196 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3198 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3201 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3204 do_congruence_step_for_index (cls
, i
);
3206 if (splitter_class_removed
)
3210 BITMAP_FREE (usage
);
3213 /* Adds a newly created congruence class CLS to worklist. */
3216 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3218 /* Return if the class CLS is already presented in work list. */
3219 if (cls
->in_worklist
)
3222 cls
->in_worklist
= true;
3223 worklist
.push_back (cls
);
3226 /* Pops a class from worklist. */
3229 sem_item_optimizer::worklist_pop (void)
3231 congruence_class
*cls
;
3233 while (!worklist
.empty ())
3235 cls
= worklist
.front ();
3236 worklist
.pop_front ();
3237 if (cls
->in_worklist
)
3239 cls
->in_worklist
= false;
3245 /* Work list item was already intended to be removed.
3246 The only reason for doing it is to split a class.
3247 Thus, the class CLS is deleted. */
3255 /* Iterative congruence reduction function. */
3258 sem_item_optimizer::process_cong_reduction (void)
3260 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3261 it
!= m_classes
.end (); ++it
)
3262 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3263 if ((*it
)->classes
[i
]->is_class_used ())
3264 worklist_push ((*it
)->classes
[i
]);
3267 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3268 (unsigned long) worklist
.size ());
3270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3271 fprintf (dump_file
, "Congruence class reduction\n");
3273 congruence_class
*cls
;
3275 /* Process complete congruence reduction. */
3276 while ((cls
= worklist_pop ()) != NULL
)
3277 do_congruence_step (cls
);
3279 /* Subdivide newly created classes according to references. */
3280 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3283 fprintf (dump_file
, "Address reference subdivision created: %u "
3284 "new classes.\n", new_classes
);
3287 /* Debug function prints all informations about congruence classes. */
3290 sem_item_optimizer::dump_cong_classes (void)
3296 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3297 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3299 /* Histogram calculation. */
3300 unsigned int max_index
= 0;
3301 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3303 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3304 it
!= m_classes
.end (); ++it
)
3306 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3308 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3316 "Class size histogram [num of members]: number of classe number of classess\n");
3318 for (unsigned int i
= 0; i
<= max_index
; i
++)
3320 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3322 fprintf (dump_file
, "\n\n");
3325 if (dump_flags
& TDF_DETAILS
)
3326 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3327 it
!= m_classes
.end (); ++it
)
3329 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3331 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3333 (*it
)->classes
[i
]->dump (dump_file
, 4);
3335 if(i
< (*it
)->classes
.length () - 1)
3336 fprintf (dump_file
, " ");
3343 /* After reduction is done, we can declare all items in a group
3344 to be equal. PREV_CLASS_COUNT is start number of classes
3345 before reduction. True is returned if there's a merge operation
3349 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3351 unsigned int item_count
= m_items
.length ();
3352 unsigned int class_count
= m_classes_count
;
3353 unsigned int equal_items
= item_count
- class_count
;
3355 unsigned int non_singular_classes_count
= 0;
3356 unsigned int non_singular_classes_sum
= 0;
3358 bool merged_p
= false;
3360 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3361 it
!= m_classes
.end (); ++it
)
3362 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3364 congruence_class
*c
= (*it
)->classes
[i
];
3365 if (c
->members
.length () > 1)
3367 non_singular_classes_count
++;
3368 non_singular_classes_sum
+= c
->members
.length ();
3374 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3375 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3376 prev_class_count
, class_count
);
3377 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3378 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3379 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3380 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3381 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3382 non_singular_classes_count
: 0.0f
,
3383 non_singular_classes_count
);
3384 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3385 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3386 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3389 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3390 it
!= m_classes
.end (); ++it
)
3391 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3393 congruence_class
*c
= (*it
)->classes
[i
];
3395 if (c
->members
.length () == 1)
3398 gcc_assert (c
->members
.length ());
3400 sem_item
*source
= c
->members
[0];
3402 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3404 sem_item
*alias
= c
->members
[j
];
3408 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3409 xstrdup_for_dump (source
->node
->name ()),
3410 xstrdup_for_dump (alias
->node
->name ()));
3411 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3412 xstrdup_for_dump (source
->node
->asm_name ()),
3413 xstrdup_for_dump (alias
->node
->asm_name ()));
3416 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3420 "Merge operation is skipped due to no_icf "
3426 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3428 source
->dump_to_file (dump_file
);
3429 alias
->dump_to_file (dump_file
);
3432 if (dbg_cnt (merged_ipa_icf
))
3433 merged_p
|= source
->merge (alias
);
3440 /* Dump function prints all class members to a FILE with an INDENT. */
3443 congruence_class::dump (FILE *file
, unsigned int indent
) const
3445 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3446 id
, members
[0]->get_hash (), members
.length ());
3448 FPUTS_SPACES (file
, indent
+ 2, "");
3449 for (unsigned i
= 0; i
< members
.length (); i
++)
3450 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3451 (void *) members
[i
]->decl
,
3452 members
[i
]->node
->order
);
3454 fprintf (file
, "\n");
3457 /* Returns true if there's a member that is used from another group. */
3460 congruence_class::is_class_used (void)
3462 for (unsigned int i
= 0; i
< members
.length (); i
++)
3463 if (members
[i
]->usages
.length ())
3469 /* Generate pass summary for IPA ICF pass. */
3472 ipa_icf_generate_summary (void)
3475 optimizer
= new sem_item_optimizer ();
3477 optimizer
->register_hooks ();
3478 optimizer
->parse_funcs_and_vars ();
3481 /* Write pass summary for IPA ICF pass. */
3484 ipa_icf_write_summary (void)
3486 gcc_assert (optimizer
);
3488 optimizer
->write_summary ();
3491 /* Read pass summary for IPA ICF pass. */
3494 ipa_icf_read_summary (void)
3497 optimizer
= new sem_item_optimizer ();
3499 optimizer
->read_summary ();
3500 optimizer
->register_hooks ();
3503 /* Semantic equality exection function. */
3506 ipa_icf_driver (void)
3508 gcc_assert (optimizer
);
3510 bool merged_p
= optimizer
->execute ();
3515 return merged_p
? TODO_remove_functions
: 0;
3518 const pass_data pass_data_ipa_icf
=
3520 IPA_PASS
, /* type */
3522 OPTGROUP_IPA
, /* optinfo_flags */
3523 TV_IPA_ICF
, /* tv_id */
3524 0, /* properties_required */
3525 0, /* properties_provided */
3526 0, /* properties_destroyed */
3527 0, /* todo_flags_start */
3528 0, /* todo_flags_finish */
3531 class pass_ipa_icf
: public ipa_opt_pass_d
3534 pass_ipa_icf (gcc::context
*ctxt
)
3535 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3536 ipa_icf_generate_summary
, /* generate_summary */
3537 ipa_icf_write_summary
, /* write_summary */
3538 ipa_icf_read_summary
, /* read_summary */
3540 write_optimization_summary */
3542 read_optimization_summary */
3543 NULL
, /* stmt_fixup */
3544 0, /* function_transform_todo_flags_start */
3545 NULL
, /* function_transform */
3546 NULL
) /* variable_transform */
3549 /* opt_pass methods: */
3550 virtual bool gate (function
*)
3552 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3555 virtual unsigned int execute (function
*)
3557 return ipa_icf_driver();
3559 }; // class pass_ipa_icf
3561 } // ipa_icf namespace
3564 make_pass_ipa_icf (gcc::context
*ctxt
)
3566 return new ipa_icf::pass_ipa_icf (ctxt
);