1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2016 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
135 : item (_item
), index (_index
)
139 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
140 : type (_type
), m_hash (-1), m_hash_set (false)
145 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
146 bitmap_obstack
*stack
)
147 : type (_type
), node (_node
), m_hash (-1), m_hash_set (false)
153 /* Add reference to a semantic TARGET. */
156 sem_item::add_reference (sem_item
*target
)
158 refs
.safe_push (target
);
159 unsigned index
= refs
.length ();
160 target
->usages
.safe_push (new sem_usage_pair(this, index
));
161 bitmap_set_bit (target
->usage_index_bitmap
, index
);
162 refs_set
.add (target
->node
);
165 /* Initialize internal data structures. Bitmap STACK is used for
166 bitmap memory allocation process. */
169 sem_item::setup (bitmap_obstack
*stack
)
171 gcc_checking_assert (node
);
174 tree_refs
.create (0);
176 usage_index_bitmap
= BITMAP_ALLOC (stack
);
179 sem_item::~sem_item ()
181 for (unsigned i
= 0; i
< usages
.length (); i
++)
185 tree_refs
.release ();
188 BITMAP_FREE (usage_index_bitmap
);
191 /* Dump function for debugging purpose. */
194 sem_item::dump (void)
198 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
199 node
->name(), node
->order
, (void *) node
->decl
);
200 fprintf (dump_file
, " hash: %u\n", get_hash ());
201 fprintf (dump_file
, " references: ");
203 for (unsigned i
= 0; i
< refs
.length (); i
++)
204 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
205 i
< refs
.length() - 1 ? "," : "");
207 fprintf (dump_file
, "\n");
211 /* Return true if target supports alias symbols. */
214 sem_item::target_supports_symbol_aliases_p (void)
216 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
223 void sem_item::set_hash (hashval_t hash
)
229 /* Semantic function constructor that uses STACK as bitmap memory stack. */
231 sem_function::sem_function (bitmap_obstack
*stack
)
232 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
235 bb_sorted
.create (0);
238 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
239 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
242 bb_sorted
.create (0);
245 sem_function::~sem_function ()
247 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
248 delete (bb_sorted
[i
]);
251 bb_sorted
.release ();
254 /* Calculates hash value based on a BASIC_BLOCK. */
257 sem_function::get_bb_hash (const sem_bb
*basic_block
)
259 inchash::hash hstate
;
261 hstate
.add_int (basic_block
->nondbg_stmt_count
);
262 hstate
.add_int (basic_block
->edge_count
);
264 return hstate
.end ();
267 /* References independent hash function. */
270 sem_function::get_hash (void)
274 inchash::hash hstate
;
275 hstate
.add_int (177454); /* Random number for function type. */
277 hstate
.add_int (arg_count
);
278 hstate
.add_int (cfg_checksum
);
279 hstate
.add_int (gcode_hash
);
281 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
282 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
284 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
285 hstate
.add_int (bb_sizes
[i
]);
287 /* Add common features of declaration itself. */
288 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
290 (cl_target_option_hash
291 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
292 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
293 (cl_optimization_hash
294 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
295 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
296 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
298 set_hash (hstate
.end ());
304 /* Return ture if A1 and A2 represent equivalent function attribute lists.
305 Based on comp_type_attributes. */
308 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
313 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
315 const struct attribute_spec
*as
;
318 as
= lookup_attribute_spec (get_attribute_name (a
));
319 /* TODO: We can introduce as->affects_decl_identity
320 and as->affects_decl_reference_identity if attribute mismatch
321 gets a common reason to give up on merging. It may not be worth
323 For example returns_nonnull affects only references, while
324 optimize attribute can be ignored because it is already lowered
325 into flags representation and compared separately. */
329 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
330 if (!attr
|| !attribute_value_equal (a
, attr
))
335 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
337 const struct attribute_spec
*as
;
339 as
= lookup_attribute_spec (get_attribute_name (a
));
343 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
345 /* We don't need to compare trees again, as we did this
346 already in first loop. */
351 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
355 /* Compare properties of symbols N1 and N2 that does not affect semantics of
356 symbol itself but affects semantics of its references from USED_BY (which
357 may be NULL if it is unknown). If comparsion is false, symbols
358 can still be merged but any symbols referring them can't.
360 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
362 TODO: We can also split attributes to those that determine codegen of
363 a function body/variable constructor itself and those that are used when
367 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
372 if (is_a
<cgraph_node
*> (n1
))
374 /* Inline properties matters: we do now want to merge uses of inline
375 function to uses of normal function because inline hint would be lost.
376 We however can merge inline function to noinline because the alias
377 will keep its DECL_DECLARED_INLINE flag.
379 Also ignore inline flag when optimizing for size or when function
380 is known to not be inlinable.
382 TODO: the optimize_size checks can also be assumed to be true if
383 unit has no !optimize_size functions. */
385 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
386 || !opt_for_fn (used_by
->decl
, optimize_size
))
387 && !opt_for_fn (n1
->decl
, optimize_size
)
388 && n1
->get_availability () > AVAIL_INTERPOSABLE
389 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
391 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
392 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
393 return return_false_with_msg
394 ("DECL_DISREGARD_INLINE_LIMITS are different");
396 if (DECL_DECLARED_INLINE_P (n1
->decl
)
397 != DECL_DECLARED_INLINE_P (n2
->decl
))
398 return return_false_with_msg ("inline attributes are different");
401 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
402 != DECL_IS_OPERATOR_NEW (n2
->decl
))
403 return return_false_with_msg ("operator new flags are different");
406 /* Merging two definitions with a reference to equivalent vtables, but
407 belonging to a different type may result in ipa-polymorphic-call analysis
408 giving a wrong answer about the dynamic type of instance. */
409 if (is_a
<varpool_node
*> (n1
))
411 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
412 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
413 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
414 DECL_CONTEXT (n2
->decl
)))
415 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
416 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
417 return return_false_with_msg
418 ("references to virtual tables can not be merged");
420 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
421 return return_false_with_msg ("alignment mismatch");
423 /* For functions we compare attributes in equals_wpa, because we do
424 not know what attributes may cause codegen differences, but for
425 variables just compare attributes for references - the codegen
426 for constructors is affected only by those attributes that we lower
427 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
428 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
429 DECL_ATTRIBUTES (n2
->decl
)))
430 return return_false_with_msg ("different var decl attributes");
431 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
432 TREE_TYPE (n2
->decl
)) != 1)
433 return return_false_with_msg ("different var type attributes");
436 /* When matching virtual tables, be sure to also match information
437 relevant for polymorphic call analysis. */
438 if (used_by
&& is_a
<varpool_node
*> (used_by
)
439 && DECL_VIRTUAL_P (used_by
->decl
))
441 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
442 return return_false_with_msg ("virtual flag mismatch");
443 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
444 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
445 return return_false_with_msg ("final flag mismatch");
450 /* Hash properties that are compared by compare_referenced_symbol_properties. */
453 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
454 inchash::hash
&hstate
,
457 if (is_a
<cgraph_node
*> (ref
))
459 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
460 && !opt_for_fn (ref
->decl
, optimize_size
)
461 && !DECL_UNINLINABLE (ref
->decl
))
463 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
464 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
466 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
468 else if (is_a
<varpool_node
*> (ref
))
470 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
472 hstate
.add_int (DECL_ALIGN (ref
->decl
));
477 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
478 point to a same function. Comparison can be skipped if IGNORED_NODES
479 contains these nodes. ADDRESS indicate if address is taken. */
482 sem_item::compare_symbol_references (
483 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
484 symtab_node
*n1
, symtab_node
*n2
, bool address
)
486 enum availability avail1
, avail2
;
491 /* Never match variable and function. */
492 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
495 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
497 if (address
&& n1
->equal_address_to (n2
) == 1)
499 if (!address
&& n1
->semantically_equivalent_p (n2
))
502 n1
= n1
->ultimate_alias_target (&avail1
);
503 n2
= n2
->ultimate_alias_target (&avail2
);
505 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
506 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
509 return return_false_with_msg ("different references");
512 /* If cgraph edges E1 and E2 are indirect calls, verify that
513 ECF flags are the same. */
515 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
517 if (e1
->indirect_info
&& e2
->indirect_info
)
519 int e1_flags
= e1
->indirect_info
->ecf_flags
;
520 int e2_flags
= e2
->indirect_info
->ecf_flags
;
522 if (e1_flags
!= e2_flags
)
523 return return_false_with_msg ("ICF flags are different");
525 else if (e1
->indirect_info
|| e2
->indirect_info
)
531 /* Return true if parameter I may be used. */
534 sem_function::param_used_p (unsigned int i
)
536 if (ipa_node_params_sum
== NULL
)
539 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
541 if (parms_info
->descriptors
.is_empty ()
542 || parms_info
->descriptors
.length () <= i
)
545 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
548 /* Perform additional check needed to match types function parameters that are
549 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
550 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
553 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
555 /* Be sure that parameters are TBAA compatible. */
556 if (!func_checker::compatible_types_p (parm1
, parm2
))
557 return return_false_with_msg ("parameter type is not compatible");
559 if (POINTER_TYPE_P (parm1
)
560 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
561 return return_false_with_msg ("argument restrict flag mismatch");
563 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
564 if (POINTER_TYPE_P (parm1
)
565 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
566 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
567 return return_false_with_msg ("pointer wrt reference mismatch");
572 /* Fast equality function based on knowledge known in WPA. */
575 sem_function::equals_wpa (sem_item
*item
,
576 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
578 gcc_assert (item
->type
== FUNC
);
579 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
580 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
582 m_compared_func
= static_cast<sem_function
*> (item
);
584 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
585 return return_false_with_msg ("thunk_p mismatch");
587 if (cnode
->thunk
.thunk_p
)
589 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
590 return return_false_with_msg ("thunk fixed_offset mismatch");
591 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
592 return return_false_with_msg ("thunk virtual_value mismatch");
593 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
594 return return_false_with_msg ("thunk this_adjusting mismatch");
595 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
596 return return_false_with_msg ("thunk virtual_offset_p mismatch");
597 if (cnode
->thunk
.add_pointer_bounds_args
598 != cnode2
->thunk
.add_pointer_bounds_args
)
599 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
602 /* Compare special function DECL attributes. */
603 if (DECL_FUNCTION_PERSONALITY (decl
)
604 != DECL_FUNCTION_PERSONALITY (item
->decl
))
605 return return_false_with_msg ("function personalities are different");
607 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
608 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
609 return return_false_with_msg ("intrument function entry exit "
610 "attributes are different");
612 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
613 return return_false_with_msg ("no stack limit attributes are different");
615 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
616 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
618 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
619 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
621 /* TODO: pure/const flags mostly matters only for references, except for
622 the fact that codegen takes LOOPING flag as a hint that loops are
623 finite. We may arrange the code to always pick leader that has least
624 specified flags and then this can go into comparing symbol properties. */
625 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
626 return return_false_with_msg ("decl_or_type flags are different");
628 /* Do not match polymorphic constructors of different types. They calls
629 type memory location for ipa-polymorphic-call and we do not want
630 it to get confused by wrong type. */
631 if (DECL_CXX_CONSTRUCTOR_P (decl
)
632 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
634 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
635 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
636 else if (!func_checker::compatible_polymorphic_types_p
637 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
638 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
639 return return_false_with_msg ("ctor polymorphic type mismatch");
642 /* Checking function TARGET and OPTIMIZATION flags. */
643 cl_target_option
*tar1
= target_opts_for_fn (decl
);
644 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
646 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
650 fprintf (dump_file
, "target flags difference");
651 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
654 return return_false_with_msg ("Target flags are different");
657 cl_optimization
*opt1
= opts_for_fn (decl
);
658 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
660 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
664 fprintf (dump_file
, "optimization flags difference");
665 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
668 return return_false_with_msg ("optimization flags are different");
671 /* Result type checking. */
672 if (!func_checker::compatible_types_p
673 (TREE_TYPE (TREE_TYPE (decl
)),
674 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
675 return return_false_with_msg ("result types are different");
677 /* Checking types of arguments. */
678 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
679 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
680 for (unsigned i
= 0; list1
&& list2
;
681 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
683 tree parm1
= TREE_VALUE (list1
);
684 tree parm2
= TREE_VALUE (list2
);
686 /* This guard is here for function pointer with attributes (pr59927.c). */
687 if (!parm1
|| !parm2
)
688 return return_false_with_msg ("NULL argument type");
690 /* Verify that types are compatible to ensure that both functions
691 have same calling conventions. */
692 if (!types_compatible_p (parm1
, parm2
))
693 return return_false_with_msg ("parameter types are not compatible");
695 if (!param_used_p (i
))
698 /* Perform additional checks for used parameters. */
699 if (!compatible_parm_types_p (parm1
, parm2
))
704 return return_false_with_msg ("Mismatched number of parameters");
706 if (node
->num_references () != item
->node
->num_references ())
707 return return_false_with_msg ("different number of references");
709 /* Checking function attributes.
710 This is quadratic in number of attributes */
711 if (comp_type_attributes (TREE_TYPE (decl
),
712 TREE_TYPE (item
->decl
)) != 1)
713 return return_false_with_msg ("different type attributes");
714 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
715 DECL_ATTRIBUTES (item
->decl
)))
716 return return_false_with_msg ("different decl attributes");
718 /* The type of THIS pointer type memory location for
719 ipa-polymorphic-call-analysis. */
720 if (opt_for_fn (decl
, flag_devirtualize
)
721 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
722 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
724 && compare_polymorphic_p ())
726 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
727 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
728 if (!func_checker::compatible_polymorphic_types_p
729 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
730 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
731 return return_false_with_msg ("THIS pointer ODR type mismatch");
734 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
735 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
737 item
->node
->iterate_reference (i
, ref2
);
739 if (ref
->use
!= ref2
->use
)
740 return return_false_with_msg ("reference use mismatch");
742 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
744 ref
->address_matters_p ()))
748 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
749 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
753 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
756 if (!compare_edge_flags (e1
, e2
))
759 e1
= e1
->next_callee
;
760 e2
= e2
->next_callee
;
764 return return_false_with_msg ("different number of calls");
766 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
767 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
771 if (!compare_edge_flags (e1
, e2
))
774 e1
= e1
->next_callee
;
775 e2
= e2
->next_callee
;
779 return return_false_with_msg ("different number of indirect calls");
784 /* Update hash by address sensitive references. We iterate over all
785 sensitive references (address_matters_p) and we hash ultime alias
786 target of these nodes, which can improve a semantic item hash.
788 Also hash in referenced symbols properties. This can be done at any time
789 (as the properties should not change), but it is convenient to do it here
790 while we walk the references anyway. */
793 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
794 sem_item
*> &m_symtab_node_map
)
797 inchash::hash
hstate (get_hash ());
799 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
801 hstate
.add_int (ref
->use
);
802 hash_referenced_symbol_properties (ref
->referred
, hstate
,
803 ref
->use
== IPA_REF_ADDR
);
804 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
805 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
808 if (is_a
<cgraph_node
*> (node
))
810 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
813 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
814 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
816 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
820 set_hash (hstate
.end ());
823 /* Update hash by computed local hash values taken from different
825 TODO: stronger SCC based hashing would be desirable here. */
828 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
829 sem_item
*> &m_symtab_node_map
)
832 inchash::hash
state (get_hash ());
834 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
836 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
838 state
.merge_hash ((*result
)->get_hash ());
843 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
846 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
848 state
.merge_hash ((*result
)->get_hash ());
852 global_hash
= state
.end ();
855 /* Returns true if the item equals to ITEM given as argument. */
858 sem_function::equals (sem_item
*item
,
859 hash_map
<symtab_node
*, sem_item
*> &)
861 gcc_assert (item
->type
== FUNC
);
862 bool eq
= equals_private (item
);
864 if (m_checker
!= NULL
)
870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
872 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
873 xstrdup_for_dump (node
->name()),
874 xstrdup_for_dump (item
->node
->name ()),
877 xstrdup_for_dump (node
->asm_name ()),
878 xstrdup_for_dump (item
->node
->asm_name ()),
879 eq
? "true" : "false");
884 /* Processes function equality comparison. */
887 sem_function::equals_private (sem_item
*item
)
889 if (item
->type
!= FUNC
)
892 basic_block bb1
, bb2
;
894 edge_iterator ei1
, ei2
;
898 m_compared_func
= static_cast<sem_function
*> (item
);
900 gcc_assert (decl
!= item
->decl
);
902 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
903 || edge_count
!= m_compared_func
->edge_count
904 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
905 return return_false ();
907 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
908 compare_polymorphic_p (),
911 &m_compared_func
->refs_set
);
912 arg1
= DECL_ARGUMENTS (decl
);
913 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
915 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
917 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
918 return return_false_with_msg ("argument types are not compatible");
919 if (!param_used_p (i
))
921 /* Perform additional checks for used parameters. */
922 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
924 if (!m_checker
->compare_decl (arg1
, arg2
))
925 return return_false ();
928 return return_false_with_msg ("Mismatched number of arguments");
930 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
933 /* Fill-up label dictionary. */
934 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
936 m_checker
->parse_labels (bb_sorted
[i
]);
937 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
940 /* Checking all basic blocks. */
941 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
942 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
943 return return_false();
945 dump_message ("All BBs are equal\n");
947 auto_vec
<int> bb_dict
;
949 /* Basic block edges check. */
950 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
952 bb1
= bb_sorted
[i
]->bb
;
953 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
955 ei2
= ei_start (bb2
->preds
);
957 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
961 if (e1
->flags
!= e2
->flags
)
962 return return_false_with_msg ("flags comparison returns false");
964 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
965 return return_false_with_msg ("edge comparison returns false");
967 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
968 return return_false_with_msg ("BB comparison returns false");
970 if (!m_checker
->compare_edge (e1
, e2
))
971 return return_false_with_msg ("edge comparison returns false");
977 /* Basic block PHI nodes comparison. */
978 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
979 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
980 return return_false_with_msg ("PHI node comparison returns false");
985 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
986 Helper for call_for_symbol_thunks_and_aliases. */
989 set_local (cgraph_node
*node
, void *data
)
991 node
->local
.local
= data
!= NULL
;
995 /* TREE_ADDRESSABLE of NODE to true.
996 Helper for call_for_symbol_thunks_and_aliases. */
999 set_addressable (varpool_node
*node
, void *)
1001 TREE_ADDRESSABLE (node
->decl
) = 1;
1005 /* Clear DECL_RTL of NODE.
1006 Helper for call_for_symbol_thunks_and_aliases. */
1009 clear_decl_rtl (symtab_node
*node
, void *)
1011 SET_DECL_RTL (node
->decl
, NULL
);
1015 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1016 possible. Return number of redirections made. */
1019 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1021 int nredirected
= 0;
1023 cgraph_edge
*e
= n
->callers
;
1027 /* Redirecting thunks to interposable symbols or symbols in other sections
1028 may not be supported by target output code. Play safe for now and
1029 punt on redirection. */
1030 if (!e
->caller
->thunk
.thunk_p
)
1032 struct cgraph_edge
*nexte
= e
->next_caller
;
1033 e
->redirect_callee (to
);
1040 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1042 bool removed
= false;
1043 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1045 if ((DECL_COMDAT_GROUP (n
->decl
)
1046 && (DECL_COMDAT_GROUP (n
->decl
)
1047 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1048 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1049 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1051 nredirected
+= redirect_all_callers (n_alias
, to
);
1052 if (n_alias
->can_remove_if_no_direct_calls_p ()
1053 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1055 && !n_alias
->has_aliases_p ())
1064 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1068 sem_function::merge (sem_item
*alias_item
)
1070 gcc_assert (alias_item
->type
== FUNC
);
1072 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1074 cgraph_node
*original
= get_node ();
1075 cgraph_node
*local_original
= NULL
;
1076 cgraph_node
*alias
= alias_func
->get_node ();
1078 bool create_wrapper
= false;
1079 bool create_alias
= false;
1080 bool redirect_callers
= false;
1081 bool remove
= false;
1083 bool original_discardable
= false;
1084 bool original_discarded
= false;
1086 bool original_address_matters
= original
->address_matters_p ();
1087 bool alias_address_matters
= alias
->address_matters_p ();
1089 if (DECL_EXTERNAL (alias
->decl
))
1092 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1096 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1097 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1102 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1106 /* Do not attempt to mix functions from different user sections;
1107 we do not know what user intends with those. */
1108 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1109 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1110 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1115 "original and alias are in different sections.\n\n");
1119 /* See if original is in a section that can be discarded if the main
1120 symbol is not used. */
1122 if (original
->can_be_discarded_p ())
1123 original_discardable
= true;
1124 /* Also consider case where we have resolution info and we know that
1125 original's definition is not going to be used. In this case we can not
1126 create alias to original. */
1127 if (node
->resolution
!= LDPR_UNKNOWN
1128 && !decl_binds_to_current_def_p (node
->decl
))
1129 original_discardable
= original_discarded
= true;
1131 /* Creating a symtab alias is the optimal way to merge.
1132 It however can not be used in the following cases:
1134 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1135 2) if ORIGINAL is in a section that may be discarded by linker or if
1136 it is an external functions where we can not create an alias
1137 (ORIGINAL_DISCARDABLE)
1138 3) if target do not support symbol aliases.
1139 4) original and alias lie in different comdat groups.
1141 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1142 and/or redirect all callers from ALIAS to ORIGINAL. */
1143 if ((original_address_matters
&& alias_address_matters
)
1144 || (original_discardable
1145 && (!DECL_COMDAT_GROUP (alias
->decl
)
1146 || (DECL_COMDAT_GROUP (alias
->decl
)
1147 != DECL_COMDAT_GROUP (original
->decl
))))
1148 || original_discarded
1149 || !sem_item::target_supports_symbol_aliases_p ()
1150 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1152 /* First see if we can produce wrapper. */
1154 /* Symbol properties that matter for references must be preserved.
1155 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1156 with proper properties. */
1157 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1158 alias
->address_taken
))
1162 "Wrapper cannot be created because referenced symbol "
1163 "properties mismatch\n");
1165 /* Do not turn function in one comdat group into wrapper to another
1166 comdat group. Other compiler producing the body of the
1167 another comdat group may make opossite decision and with unfortunate
1168 linker choices this may close a loop. */
1169 else if (DECL_COMDAT_GROUP (original
->decl
)
1170 && DECL_COMDAT_GROUP (alias
->decl
)
1171 && (DECL_COMDAT_GROUP (alias
->decl
)
1172 != DECL_COMDAT_GROUP (original
->decl
)))
1176 "Wrapper cannot be created because of COMDAT\n");
1178 else if (DECL_STATIC_CHAIN (alias
->decl
)
1179 || DECL_STATIC_CHAIN (original
->decl
))
1183 "Cannot create wrapper of nested function.\n");
1185 /* TODO: We can also deal with variadic functions never calling
1187 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1191 "can not create wrapper of stdarg function.\n");
1193 else if (inline_summaries
1194 && inline_summaries
->get (alias
)->self_size
<= 2)
1197 fprintf (dump_file
, "Wrapper creation is not "
1198 "profitable (function is too small).\n");
1200 /* If user paid attention to mark function noinline, assume it is
1201 somewhat special and do not try to turn it into a wrapper that can
1202 not be undone by inliner. */
1203 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1206 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1209 create_wrapper
= true;
1211 /* We can redirect local calls in the case both alias and orignal
1212 are not interposable. */
1214 = alias
->get_availability () > AVAIL_INTERPOSABLE
1215 && original
->get_availability () > AVAIL_INTERPOSABLE
1216 && !alias
->instrumented_version
;
1217 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1218 with proper properties. */
1219 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1220 alias
->address_taken
))
1221 redirect_callers
= false;
1223 if (!redirect_callers
&& !create_wrapper
)
1226 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1227 "produce wrapper\n\n");
1231 /* Work out the symbol the wrapper should call.
1232 If ORIGINAL is interposable, we need to call a local alias.
1233 Also produce local alias (if possible) as an optimization.
1235 Local aliases can not be created inside comdat groups because that
1236 prevents inlining. */
1237 if (!original_discardable
&& !original
->get_comdat_group ())
1240 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1242 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1243 local_original
= original
;
1245 /* If we can not use local alias, fallback to the original
1247 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1248 local_original
= original
;
1250 /* If original is COMDAT local, we can not really redirect calls outside
1251 of its comdat group to it. */
1252 if (original
->comdat_local_p ())
1253 redirect_callers
= false;
1254 if (!local_original
)
1257 fprintf (dump_file
, "Not unifying; "
1258 "can not produce local alias.\n\n");
1262 if (!redirect_callers
&& !create_wrapper
)
1265 fprintf (dump_file
, "Not unifying; "
1266 "can not redirect callers nor produce a wrapper\n\n");
1270 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1272 && !alias
->can_remove_if_no_direct_calls_p ())
1275 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1276 "function has other uses than direct calls\n\n");
1281 create_alias
= true;
1283 if (redirect_callers
)
1285 int nredirected
= redirect_all_callers (alias
, local_original
);
1289 alias
->icf_merged
= true;
1290 local_original
->icf_merged
= true;
1292 if (dump_file
&& nredirected
)
1293 fprintf (dump_file
, "%i local calls have been "
1294 "redirected.\n", nredirected
);
1297 /* If all callers was redirected, do not produce wrapper. */
1298 if (alias
->can_remove_if_no_direct_calls_p ()
1299 && !DECL_VIRTUAL_P (alias
->decl
)
1300 && !alias
->has_aliases_p ())
1302 create_wrapper
= false;
1305 gcc_assert (!create_alias
);
1307 else if (create_alias
)
1309 alias
->icf_merged
= true;
1311 /* Remove the function's body. */
1312 ipa_merge_profiles (original
, alias
);
1313 alias
->release_body (true);
1315 /* Notice global symbol possibly produced RTL. */
1316 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1319 /* Create the alias. */
1320 cgraph_node::create_alias (alias_func
->decl
, decl
);
1321 alias
->resolve_alias (original
);
1323 original
->call_for_symbol_thunks_and_aliases
1324 (set_local
, (void *)(size_t) original
->local_p (), true);
1327 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1331 gcc_assert (!create_alias
);
1332 alias
->icf_merged
= true;
1333 local_original
->icf_merged
= true;
1335 ipa_merge_profiles (local_original
, alias
, true);
1336 alias
->create_wrapper (local_original
);
1339 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1342 /* It's possible that redirection can hit thunks that block
1343 redirection opportunities. */
1344 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1345 original
->icf_merged
= true;
1347 /* We use merged flag to track cases where COMDAT function is known to be
1348 compatible its callers. If we merged in non-COMDAT, we need to give up
1349 on this optimization. */
1350 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1353 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1355 local_original
->merged_comdat
= false;
1356 original
->merged_comdat
= false;
1361 ipa_merge_profiles (original
, alias
);
1362 alias
->release_body ();
1364 alias
->body_removed
= true;
1365 alias
->icf_merged
= true;
1367 fprintf (dump_file
, "Unified; Function body was removed.\n");
1373 /* Semantic item initialization function. */
1376 sem_function::init (void)
1379 get_node ()->get_untransformed_body ();
1381 tree fndecl
= node
->decl
;
1382 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1385 gcc_assert (SSANAMES (func
));
1387 ssa_names_size
= SSANAMES (func
)->length ();
1391 region_tree
= func
->eh
->region_tree
;
1393 /* iterating all function arguments. */
1394 arg_count
= count_formal_params (fndecl
);
1396 edge_count
= n_edges_for_fn (func
);
1397 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1398 if (!cnode
->thunk
.thunk_p
)
1400 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1402 inchash::hash hstate
;
1405 FOR_EACH_BB_FN (bb
, func
)
1407 unsigned nondbg_stmt_count
= 0;
1410 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1412 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1415 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1418 gimple
*stmt
= gsi_stmt (gsi
);
1420 if (gimple_code (stmt
) != GIMPLE_DEBUG
1421 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1423 hash_stmt (stmt
, hstate
);
1424 nondbg_stmt_count
++;
1428 gcode_hash
= hstate
.end ();
1429 bb_sizes
.safe_push (nondbg_stmt_count
);
1431 /* Inserting basic block to hash table. */
1432 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1433 EDGE_COUNT (bb
->preds
)
1434 + EDGE_COUNT (bb
->succs
));
1436 bb_sorted
.safe_push (semantic_bb
);
1442 inchash::hash hstate
;
1443 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1444 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1445 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1446 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1447 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1448 gcode_hash
= hstate
.end ();
1452 /* Accumulate to HSTATE a hash of expression EXP.
1453 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1454 and DECL equality classes. */
1457 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1459 if (exp
== NULL_TREE
)
1461 hstate
.merge_hash (0);
1465 /* Handled component can be matched in a cureful way proving equivalence
1466 even if they syntactically differ. Just skip them. */
1468 while (handled_component_p (exp
))
1469 exp
= TREE_OPERAND (exp
, 0);
1471 enum tree_code code
= TREE_CODE (exp
);
1472 hstate
.add_int (code
);
1476 /* Use inchash::add_expr for everything that is LTO stable. */
1484 inchash::add_expr (exp
, hstate
);
1488 unsigned HOST_WIDE_INT idx
;
1491 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1493 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1495 add_expr (value
, hstate
);
1500 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1506 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1509 case POINTER_PLUS_EXPR
:
1512 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1513 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1517 inchash::hash one
, two
;
1518 add_expr (TREE_OPERAND (exp
, 0), one
);
1519 add_expr (TREE_OPERAND (exp
, 1), two
);
1520 hstate
.add_commutative (one
, two
);
1524 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1525 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1531 /* Accumulate to HSTATE a hash of type t.
1532 TYpes that may end up being compatible after LTO type merging needs to have
1536 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1538 if (type
== NULL_TREE
)
1540 hstate
.merge_hash (0);
1544 type
= TYPE_MAIN_VARIANT (type
);
1546 hstate
.add_int (TYPE_MODE (type
));
1548 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1550 hstate
.add_int (COMPLEX_TYPE
);
1551 sem_item::add_type (TREE_TYPE (type
), hstate
);
1553 else if (INTEGRAL_TYPE_P (type
))
1555 hstate
.add_int (INTEGER_TYPE
);
1556 hstate
.add_flag (TYPE_UNSIGNED (type
));
1557 hstate
.add_int (TYPE_PRECISION (type
));
1559 else if (VECTOR_TYPE_P (type
))
1561 hstate
.add_int (VECTOR_TYPE
);
1562 hstate
.add_int (TYPE_PRECISION (type
));
1563 sem_item::add_type (TREE_TYPE (type
), hstate
);
1565 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1567 hstate
.add_int (ARRAY_TYPE
);
1568 /* Do not hash size, so complete and incomplete types can match. */
1569 sem_item::add_type (TREE_TYPE (type
), hstate
);
1571 else if (RECORD_OR_UNION_TYPE_P (type
))
1573 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1574 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1578 inchash::hash hstate2
;
1583 hstate2
.add_int (RECORD_TYPE
);
1584 gcc_assert (COMPLETE_TYPE_P (type
));
1586 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1587 if (TREE_CODE (f
) == FIELD_DECL
)
1589 add_type (TREE_TYPE (f
), hstate2
);
1593 hstate2
.add_int (nf
);
1594 hash
= hstate2
.end ();
1595 hstate
.add_wide_int (hash
);
1596 optimizer
->m_type_hash_cache
.put (type
, hash
);
1599 hstate
.add_wide_int (*val
);
1603 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1606 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1608 enum gimple_code code
= gimple_code (stmt
);
1610 hstate
.add_int (code
);
1615 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1618 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1619 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1620 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1622 inchash::hash one
, two
;
1624 add_expr (gimple_assign_rhs1 (stmt
), one
);
1625 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1626 add_expr (gimple_assign_rhs2 (stmt
), two
);
1627 hstate
.add_commutative (one
, two
);
1628 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1630 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1631 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1633 add_expr (gimple_assign_lhs (stmt
), hstate
);
1634 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1637 /* ... fall through ... */
1643 /* All these statements are equivalent if their operands are. */
1644 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1646 add_expr (gimple_op (stmt
, i
), hstate
);
1647 if (gimple_op (stmt
, i
))
1648 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1656 /* Return true if polymorphic comparison must be processed. */
1659 sem_function::compare_polymorphic_p (void)
1661 struct cgraph_edge
*e
;
1663 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1665 if (get_node ()->indirect_calls
!= NULL
)
1667 /* TODO: We can do simple propagation determining what calls may lead to
1668 a polymorphic call. */
1669 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1670 if (e
->callee
->definition
1671 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1676 /* For a given call graph NODE, the function constructs new
1677 semantic function item. */
1680 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1682 tree fndecl
= node
->decl
;
1683 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1685 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1688 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1692 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1693 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1696 sem_function
*f
= new sem_function (node
, stack
);
1703 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1704 return true if phi nodes are semantically equivalent in these blocks . */
1707 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1709 gphi_iterator si1
, si2
;
1711 unsigned size1
, size2
, i
;
1715 gcc_assert (bb1
!= NULL
);
1716 gcc_assert (bb2
!= NULL
);
1718 si2
= gsi_start_phis (bb2
);
1719 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1722 gsi_next_nonvirtual_phi (&si1
);
1723 gsi_next_nonvirtual_phi (&si2
);
1725 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1728 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1729 return return_false();
1734 tree phi_result1
= gimple_phi_result (phi1
);
1735 tree phi_result2
= gimple_phi_result (phi2
);
1737 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1738 return return_false_with_msg ("PHI results are different");
1740 size1
= gimple_phi_num_args (phi1
);
1741 size2
= gimple_phi_num_args (phi2
);
1744 return return_false ();
1746 for (i
= 0; i
< size1
; ++i
)
1748 t1
= gimple_phi_arg (phi1
, i
)->def
;
1749 t2
= gimple_phi_arg (phi2
, i
)->def
;
1751 if (!m_checker
->compare_operand (t1
, t2
))
1752 return return_false ();
1754 e1
= gimple_phi_arg_edge (phi1
, i
);
1755 e2
= gimple_phi_arg_edge (phi2
, i
);
1757 if (!m_checker
->compare_edge (e1
, e2
))
1758 return return_false ();
1767 /* Returns true if tree T can be compared as a handled component. */
1770 sem_function::icf_handled_component_p (tree t
)
1772 tree_code tc
= TREE_CODE (t
);
1774 return (handled_component_p (t
)
1775 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1778 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1779 corresponds to TARGET. */
1782 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1787 if (bb_dict
->length () <= (unsigned)source
)
1788 bb_dict
->safe_grow_cleared (source
+ 1);
1790 if ((*bb_dict
)[source
] == 0)
1792 (*bb_dict
)[source
] = target
;
1796 return (*bb_dict
)[source
] == target
;
1799 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1803 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1804 : sem_item (VAR
, node
, stack
)
1806 gcc_checking_assert (node
);
1807 gcc_checking_assert (get_node ());
1810 /* Fast equality function based on knowledge known in WPA. */
1813 sem_variable::equals_wpa (sem_item
*item
,
1814 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1816 gcc_assert (item
->type
== VAR
);
1818 if (node
->num_references () != item
->node
->num_references ())
1819 return return_false_with_msg ("different number of references");
1821 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1822 return return_false_with_msg ("TLS model");
1824 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1825 alignment out of all aliases. */
1827 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1828 return return_false_with_msg ("Virtual flag mismatch");
1830 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1831 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1832 || !operand_equal_p (DECL_SIZE (decl
),
1833 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1834 return return_false_with_msg ("size mismatch");
1836 /* Do not attempt to mix data from different user sections;
1837 we do not know what user intends with those. */
1838 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1839 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1840 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1841 return return_false_with_msg ("user section mismatch");
1843 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1844 return return_false_with_msg ("text section");
1846 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1847 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1849 item
->node
->iterate_reference (i
, ref2
);
1851 if (ref
->use
!= ref2
->use
)
1852 return return_false_with_msg ("reference use mismatch");
1854 if (!compare_symbol_references (ignored_nodes
,
1855 ref
->referred
, ref2
->referred
,
1856 ref
->address_matters_p ()))
1863 /* Returns true if the item equals to ITEM given as argument. */
1866 sem_variable::equals (sem_item
*item
,
1867 hash_map
<symtab_node
*, sem_item
*> &)
1869 gcc_assert (item
->type
== VAR
);
1872 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1873 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1874 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1875 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1877 /* As seen in PR ipa/65303 we have to compare variables types. */
1878 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1879 TREE_TYPE (item
->decl
)))
1880 return return_false_with_msg ("variables types are different");
1882 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1883 DECL_INITIAL (item
->node
->decl
));
1884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1886 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1887 xstrdup_for_dump (node
->name()),
1888 xstrdup_for_dump (item
->node
->name ()),
1889 node
->order
, item
->node
->order
,
1890 xstrdup_for_dump (node
->asm_name ()),
1891 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1896 /* Compares trees T1 and T2 for semantic equality. */
1899 sem_variable::equals (tree t1
, tree t2
)
1902 return return_with_debug (t1
== t2
);
1905 tree_code tc1
= TREE_CODE (t1
);
1906 tree_code tc2
= TREE_CODE (t2
);
1909 return return_false_with_msg ("TREE_CODE mismatch");
1915 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1916 unsigned HOST_WIDE_INT idx
;
1918 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1919 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1920 return return_false_with_msg ("constructor type mismatch");
1922 if (typecode
== ARRAY_TYPE
)
1924 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1925 /* For arrays, check that the sizes all match. */
1926 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1928 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1929 return return_false_with_msg ("constructor array size mismatch");
1931 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1933 return return_false_with_msg ("constructor type incompatible");
1935 v1
= CONSTRUCTOR_ELTS (t1
);
1936 v2
= CONSTRUCTOR_ELTS (t2
);
1937 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1938 return return_false_with_msg ("constructor number of elts mismatch");
1940 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1942 constructor_elt
*c1
= &(*v1
)[idx
];
1943 constructor_elt
*c2
= &(*v2
)[idx
];
1945 /* Check that each value is the same... */
1946 if (!sem_variable::equals (c1
->value
, c2
->value
))
1948 /* ... and that they apply to the same fields! */
1949 if (!sem_variable::equals (c1
->index
, c2
->index
))
1956 tree x1
= TREE_OPERAND (t1
, 0);
1957 tree x2
= TREE_OPERAND (t2
, 0);
1958 tree y1
= TREE_OPERAND (t1
, 1);
1959 tree y2
= TREE_OPERAND (t2
, 1);
1961 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1962 return return_false ();
1964 /* Type of the offset on MEM_REF does not matter. */
1965 return return_with_debug (sem_variable::equals (x1
, x2
)
1966 && wi::to_offset (y1
)
1967 == wi::to_offset (y2
));
1972 tree op1
= TREE_OPERAND (t1
, 0);
1973 tree op2
= TREE_OPERAND (t2
, 0);
1974 return sem_variable::equals (op1
, op2
);
1976 /* References to other vars/decls are compared using ipa-ref. */
1979 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1981 return return_false_with_msg ("Declaration mismatch");
1983 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1984 need to process its VAR/FUNCTION references without relying on ipa-ref
1988 return return_false_with_msg ("Declaration mismatch");
1990 /* Integer constants are the same only if the same width of type. */
1991 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1992 return return_false_with_msg ("INTEGER_CST precision mismatch");
1993 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1994 return return_false_with_msg ("INTEGER_CST mode mismatch");
1995 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1997 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1998 return return_false_with_msg ("STRING_CST mode mismatch");
1999 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2000 return return_false_with_msg ("STRING_CST length mismatch");
2001 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2002 TREE_STRING_LENGTH (t1
)))
2003 return return_false_with_msg ("STRING_CST mismatch");
2006 /* Fixed constants are the same only if the same width of type. */
2007 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2008 return return_false_with_msg ("FIXED_CST precision mismatch");
2010 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2011 TREE_FIXED_CST (t2
)));
2013 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2014 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2016 /* Real constants are the same only if the same width of type. */
2017 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2018 return return_false_with_msg ("REAL_CST precision mismatch");
2019 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2020 &TREE_REAL_CST (t2
)));
2025 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2026 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2028 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2029 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2030 VECTOR_CST_ELT (t2
, i
)))
2036 case ARRAY_RANGE_REF
:
2038 tree x1
= TREE_OPERAND (t1
, 0);
2039 tree x2
= TREE_OPERAND (t2
, 0);
2040 tree y1
= TREE_OPERAND (t1
, 1);
2041 tree y2
= TREE_OPERAND (t2
, 1);
2043 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2045 if (!sem_variable::equals (array_ref_low_bound (t1
),
2046 array_ref_low_bound (t2
)))
2048 if (!sem_variable::equals (array_ref_element_size (t1
),
2049 array_ref_element_size (t2
)))
2055 case POINTER_PLUS_EXPR
:
2060 tree x1
= TREE_OPERAND (t1
, 0);
2061 tree x2
= TREE_OPERAND (t2
, 0);
2062 tree y1
= TREE_OPERAND (t1
, 1);
2063 tree y2
= TREE_OPERAND (t2
, 1);
2065 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2069 case VIEW_CONVERT_EXPR
:
2070 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2071 return return_false ();
2072 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2074 return return_false_with_msg ("ERROR_MARK");
2076 return return_false_with_msg ("Unknown TREE code reached");
2080 /* Parser function that visits a varpool NODE. */
2083 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2085 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2089 sem_variable
*v
= new sem_variable (node
, stack
);
2096 /* References independent hash function. */
2099 sem_variable::get_hash (void)
2104 /* All WPA streamed in symbols should have their hashes computed at compile
2105 time. At this point, the constructor may not be in memory at all.
2106 DECL_INITIAL (decl) would be error_mark_node in that case. */
2107 gcc_assert (!node
->lto_file_data
);
2108 tree ctor
= DECL_INITIAL (decl
);
2109 inchash::hash hstate
;
2111 hstate
.add_int (456346417);
2112 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2113 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2114 add_expr (ctor
, hstate
);
2115 set_hash (hstate
.end ());
2120 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2124 sem_variable::merge (sem_item
*alias_item
)
2126 gcc_assert (alias_item
->type
== VAR
);
2128 if (!sem_item::target_supports_symbol_aliases_p ())
2131 fprintf (dump_file
, "Not unifying; "
2132 "Symbol aliases are not supported by target\n\n");
2136 if (DECL_EXTERNAL (alias_item
->decl
))
2139 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2143 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2145 varpool_node
*original
= get_node ();
2146 varpool_node
*alias
= alias_var
->get_node ();
2147 bool original_discardable
= false;
2149 bool original_address_matters
= original
->address_matters_p ();
2150 bool alias_address_matters
= alias
->address_matters_p ();
2152 /* See if original is in a section that can be discarded if the main
2154 Also consider case where we have resolution info and we know that
2155 original's definition is not going to be used. In this case we can not
2156 create alias to original. */
2157 if (original
->can_be_discarded_p ()
2158 || (node
->resolution
!= LDPR_UNKNOWN
2159 && !decl_binds_to_current_def_p (node
->decl
)))
2160 original_discardable
= true;
2162 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2164 /* Constant pool machinery is not quite ready for aliases.
2165 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2166 For LTO merging does not happen that is an important missing feature.
2167 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2168 flag is dropped and non-local symbol name is assigned. */
2169 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2170 || DECL_IN_CONSTANT_POOL (original
->decl
))
2174 "Not unifying; constant pool variables.\n\n");
2178 /* Do not attempt to mix functions from different user sections;
2179 we do not know what user intends with those. */
2180 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2181 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2182 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2187 "original and alias are in different sections.\n\n");
2191 /* We can not merge if address comparsion metters. */
2192 if (original_address_matters
&& alias_address_matters
2193 && flag_merge_constants
< 2)
2198 "adress of original and alias may be compared.\n\n");
2202 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2205 fprintf (dump_file
, "Not unifying; "
2206 "original and alias have incompatible alignments\n\n");
2211 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2214 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2215 "across comdat group boundary\n\n");
2220 if (original_discardable
)
2223 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2224 "target is discardable\n\n");
2230 gcc_assert (!original
->alias
);
2231 gcc_assert (!alias
->alias
);
2233 alias
->analyzed
= false;
2235 DECL_INITIAL (alias
->decl
) = NULL
;
2236 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2238 alias
->need_bounds_init
= false;
2239 alias
->remove_all_references ();
2240 if (TREE_ADDRESSABLE (alias
->decl
))
2241 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2243 varpool_node::create_alias (alias_var
->decl
, decl
);
2244 alias
->resolve_alias (original
);
2245 if (DECL_PT_UID_SET_P (original
->decl
))
2246 SET_DECL_PT_UID (alias
->decl
, DECL_PT_UID (original
->decl
));
2249 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2255 /* Dump symbol to FILE. */
2258 sem_variable::dump_to_file (FILE *file
)
2262 print_node (file
, "", decl
, 0);
2263 fprintf (file
, "\n\n");
2266 unsigned int sem_item_optimizer::class_id
= 0;
2268 sem_item_optimizer::sem_item_optimizer ()
2269 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2270 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 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2391 fn
->set_hash (hash
);
2392 m_items
.safe_push (fn
);
2396 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2398 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2399 var
->set_hash (hash
);
2400 m_items
.safe_push (var
);
2404 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2406 lto_data_in_delete (data_in
);
2409 /* Read IPA ICF summary for symbols. */
2412 sem_item_optimizer::read_summary (void)
2414 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2415 lto_file_decl_data
*file_data
;
2418 while ((file_data
= file_data_vec
[j
++]))
2421 const char *data
= lto_get_section_data (file_data
,
2422 LTO_section_ipa_icf
, NULL
, &len
);
2425 read_section (file_data
, data
, len
);
2429 /* Register callgraph and varpool hooks. */
2432 sem_item_optimizer::register_hooks (void)
2434 if (!m_cgraph_node_hooks
)
2435 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2436 (&sem_item_optimizer::cgraph_removal_hook
, this);
2438 if (!m_varpool_node_hooks
)
2439 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2440 (&sem_item_optimizer::varpool_removal_hook
, this);
2443 /* Unregister callgraph and varpool hooks. */
2446 sem_item_optimizer::unregister_hooks (void)
2448 if (m_cgraph_node_hooks
)
2449 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2451 if (m_varpool_node_hooks
)
2452 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2455 /* Adds a CLS to hashtable associated by hash value. */
2458 sem_item_optimizer::add_class (congruence_class
*cls
)
2460 gcc_assert (cls
->members
.length ());
2462 congruence_class_group
*group
= get_group_by_hash (
2463 cls
->members
[0]->get_hash (),
2464 cls
->members
[0]->type
);
2465 group
->classes
.safe_push (cls
);
2468 /* Gets a congruence class group based on given HASH value and TYPE. */
2470 congruence_class_group
*
2471 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2473 congruence_class_group
*item
= XNEW (congruence_class_group
);
2477 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2483 item
->classes
.create (1);
2490 /* Callgraph removal hook called for a NODE with a custom DATA. */
2493 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2495 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2496 optimizer
->remove_symtab_node (node
);
2499 /* Varpool removal hook called for a NODE with a custom DATA. */
2502 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2504 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2505 optimizer
->remove_symtab_node (node
);
2508 /* Remove symtab NODE triggered by symtab removal hooks. */
2511 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2513 gcc_assert (!m_classes
.elements());
2515 m_removed_items_set
.add (node
);
2519 sem_item_optimizer::remove_item (sem_item
*item
)
2521 if (m_symtab_node_map
.get (item
->node
))
2522 m_symtab_node_map
.remove (item
->node
);
2526 /* Removes all callgraph and varpool nodes that are marked by symtab
2530 sem_item_optimizer::filter_removed_items (void)
2532 auto_vec
<sem_item
*> filtered
;
2534 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2536 sem_item
*item
= m_items
[i
];
2538 if (m_removed_items_set
.contains (item
->node
))
2544 if (item
->type
== FUNC
)
2546 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2548 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2551 filtered
.safe_push (item
);
2555 if (!flag_ipa_icf_variables
)
2559 /* Filter out non-readonly variables. */
2560 tree decl
= item
->decl
;
2561 if (TREE_READONLY (decl
))
2562 filtered
.safe_push (item
);
2569 /* Clean-up of released semantic items. */
2572 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2573 m_items
.safe_push (filtered
[i
]);
2576 /* Optimizer entry point which returns true in case it processes
2577 a merge operation. True is returned if there's a merge operation
2581 sem_item_optimizer::execute (void)
2583 filter_removed_items ();
2584 unregister_hooks ();
2587 update_hash_by_addr_refs ();
2588 build_hash_based_classes ();
2591 fprintf (dump_file
, "Dump after hash based groups\n");
2592 dump_cong_classes ();
2594 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2595 m_items
[i
]->init_wpa ();
2597 subdivide_classes_by_equality (true);
2600 fprintf (dump_file
, "Dump after WPA based types groups\n");
2602 dump_cong_classes ();
2604 process_cong_reduction ();
2605 checking_verify_classes ();
2608 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2610 dump_cong_classes ();
2612 parse_nonsingleton_classes ();
2613 subdivide_classes_by_equality ();
2616 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2618 dump_cong_classes ();
2620 unsigned int prev_class_count
= m_classes_count
;
2622 process_cong_reduction ();
2623 dump_cong_classes ();
2624 checking_verify_classes ();
2625 bool merged_p
= merge_classes (prev_class_count
);
2627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2628 symtab_node::dump_table (dump_file
);
2633 /* Function responsible for visiting all potential functions and
2634 read-only variables that can be merged. */
2637 sem_item_optimizer::parse_funcs_and_vars (void)
2641 if (flag_ipa_icf_functions
)
2642 FOR_EACH_DEFINED_FUNCTION (cnode
)
2644 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2647 m_items
.safe_push (f
);
2648 m_symtab_node_map
.put (cnode
, f
);
2651 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2654 f
->dump_to_file (dump_file
);
2657 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2660 varpool_node
*vnode
;
2662 if (flag_ipa_icf_variables
)
2663 FOR_EACH_DEFINED_VARIABLE (vnode
)
2665 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2669 m_items
.safe_push (v
);
2670 m_symtab_node_map
.put (vnode
, v
);
2675 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2678 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2680 item
->index_in_class
= cls
->members
.length ();
2681 cls
->members
.safe_push (item
);
2685 /* For each semantic item, append hash values of references. */
2688 sem_item_optimizer::update_hash_by_addr_refs ()
2690 /* First, append to hash sensitive references and class type if it need to
2691 be matched for ODR. */
2692 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2694 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2695 if (m_items
[i
]->type
== FUNC
)
2697 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2698 && contains_polymorphic_type_p
2699 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2700 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2701 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2702 && static_cast<sem_function
*> (m_items
[i
])
2703 ->compare_polymorphic_p ())))
2706 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2707 inchash::hash
hstate (m_items
[i
]->get_hash ());
2709 if (TYPE_NAME (class_type
)
2710 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2712 (IDENTIFIER_HASH_VALUE
2713 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2715 m_items
[i
]->set_hash (hstate
.end ());
2720 /* Once all symbols have enhanced hash value, we can append
2721 hash values of symbols that are seen by IPA ICF and are
2722 references by a semantic item. Newly computed values
2723 are saved to global_hash member variable. */
2724 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2725 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2727 /* Global hash value replace current hash values. */
2728 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2729 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2732 /* Congruence classes are built by hash value. */
2735 sem_item_optimizer::build_hash_based_classes (void)
2737 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2739 sem_item
*item
= m_items
[i
];
2741 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2744 if (!group
->classes
.length ())
2747 group
->classes
.safe_push (new congruence_class (class_id
++));
2750 add_item_to_class (group
->classes
[0], item
);
2754 /* Build references according to call graph. */
2757 sem_item_optimizer::build_graph (void)
2759 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2761 sem_item
*item
= m_items
[i
];
2762 m_symtab_node_map
.put (item
->node
, item
);
2764 /* Initialize hash values if we are not in LTO mode. */
2769 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2771 sem_item
*item
= m_items
[i
];
2773 if (item
->type
== FUNC
)
2775 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2777 cgraph_edge
*e
= cnode
->callees
;
2780 sem_item
**slot
= m_symtab_node_map
.get
2781 (e
->callee
->ultimate_alias_target ());
2783 item
->add_reference (*slot
);
2789 ipa_ref
*ref
= NULL
;
2790 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2792 sem_item
**slot
= m_symtab_node_map
.get
2793 (ref
->referred
->ultimate_alias_target ());
2795 item
->add_reference (*slot
);
2800 /* Semantic items in classes having more than one element and initialized.
2801 In case of WPA, we load function body. */
2804 sem_item_optimizer::parse_nonsingleton_classes (void)
2806 unsigned int init_called_count
= 0;
2808 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2809 if (m_items
[i
]->cls
->members
.length () > 1)
2811 m_items
[i
]->init ();
2812 init_called_count
++;
2816 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2817 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2820 /* Equality function for semantic items is used to subdivide existing
2821 classes. If IN_WPA, fast equality function is invoked. */
2824 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2826 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2827 it
!= m_classes
.end (); ++it
)
2829 unsigned int class_count
= (*it
)->classes
.length ();
2831 for (unsigned i
= 0; i
< class_count
; i
++)
2833 congruence_class
*c
= (*it
)->classes
[i
];
2835 if (c
->members
.length() > 1)
2837 auto_vec
<sem_item
*> new_vector
;
2839 sem_item
*first
= c
->members
[0];
2840 new_vector
.safe_push (first
);
2842 unsigned class_split_first
= (*it
)->classes
.length ();
2844 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2846 sem_item
*item
= c
->members
[j
];
2848 bool equals
= in_wpa
? first
->equals_wpa (item
,
2849 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2852 new_vector
.safe_push (item
);
2855 bool integrated
= false;
2857 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2859 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2860 bool equals
= in_wpa
? x
->equals_wpa (item
,
2861 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2866 add_item_to_class ((*it
)->classes
[k
], item
);
2874 congruence_class
*c
= new congruence_class (class_id
++);
2876 add_item_to_class (c
, item
);
2878 (*it
)->classes
.safe_push (c
);
2883 // we replace newly created new_vector for the class we've just splitted
2884 c
->members
.release ();
2885 c
->members
.create (new_vector
.length ());
2887 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2888 add_item_to_class (c
, new_vector
[j
]);
2893 checking_verify_classes ();
2896 /* Subdivide classes by address references that members of the class
2897 reference. Example can be a pair of functions that have an address
2898 taken from a function. If these addresses are different the class
2902 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2904 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2906 unsigned newly_created_classes
= 0;
2908 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2909 it
!= m_classes
.end (); ++it
)
2911 unsigned int class_count
= (*it
)->classes
.length ();
2912 auto_vec
<congruence_class
*> new_classes
;
2914 for (unsigned i
= 0; i
< class_count
; i
++)
2916 congruence_class
*c
= (*it
)->classes
[i
];
2918 if (c
->members
.length() > 1)
2920 subdivide_hash_map split_map
;
2922 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2924 sem_item
*source_node
= c
->members
[j
];
2926 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2929 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2931 gcc_checking_assert (slot
);
2933 slot
->safe_push (source_node
);
2939 /* If the map contains more than one key, we have to split the map
2941 if (split_map
.elements () != 1)
2943 bool first_class
= true;
2945 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2946 it2
!= split_map
.end (); ++it2
)
2948 congruence_class
*new_cls
;
2949 new_cls
= new congruence_class (class_id
++);
2951 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2952 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2954 worklist_push (new_cls
);
2955 newly_created_classes
++;
2959 (*it
)->classes
[i
] = new_cls
;
2960 first_class
= false;
2964 new_classes
.safe_push (new_cls
);
2970 /* Release memory. */
2971 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2972 it2
!= split_map
.end (); ++it2
)
2974 delete (*it2
).first
;
2975 (*it2
).second
.release ();
2980 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2981 (*it
)->classes
.safe_push (new_classes
[i
]);
2984 return newly_created_classes
;
2987 /* Verify congruence classes, if checking is enabled. */
2990 sem_item_optimizer::checking_verify_classes (void)
2996 /* Verify congruence classes. */
2999 sem_item_optimizer::verify_classes (void)
3001 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3002 it
!= m_classes
.end (); ++it
)
3004 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3006 congruence_class
*cls
= (*it
)->classes
[i
];
3009 gcc_assert (cls
->members
.length () > 0);
3011 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3013 sem_item
*item
= cls
->members
[j
];
3016 gcc_assert (item
->cls
== cls
);
3018 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3020 sem_usage_pair
*usage
= item
->usages
[k
];
3021 gcc_assert (usage
->item
->index_in_class
<
3022 usage
->item
->cls
->members
.length ());
3029 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3030 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3031 but unused argument. */
3034 sem_item_optimizer::release_split_map (congruence_class
* const &,
3035 bitmap
const &b
, traverse_split_pair
*)
3044 /* Process split operation for a class given as pointer CLS_PTR,
3045 where bitmap B splits congruence class members. DATA is used
3046 as argument of split pair. */
3049 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3050 bitmap
const &b
, traverse_split_pair
*pair
)
3052 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3053 const congruence_class
*splitter_cls
= pair
->cls
;
3055 /* If counted bits are greater than zero and less than the number of members
3056 a group will be splitted. */
3057 unsigned popcount
= bitmap_count_bits (b
);
3059 if (popcount
> 0 && popcount
< cls
->members
.length ())
3061 auto_vec
<congruence_class
*, 2> newclasses
;
3062 newclasses
.quick_push (new congruence_class (class_id
++));
3063 newclasses
.quick_push (new congruence_class (class_id
++));
3065 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3067 int target
= bitmap_bit_p (b
, i
);
3068 congruence_class
*tc
= newclasses
[target
];
3070 add_item_to_class (tc
, cls
->members
[i
]);
3075 for (unsigned int i
= 0; i
< 2; i
++)
3076 gcc_assert (newclasses
[i
]->members
.length ());
3079 if (splitter_cls
== cls
)
3080 optimizer
->splitter_class_removed
= true;
3082 /* Remove old class from worklist if presented. */
3083 bool in_worklist
= cls
->in_worklist
;
3086 cls
->in_worklist
= false;
3088 congruence_class_group g
;
3089 g
.hash
= cls
->members
[0]->get_hash ();
3090 g
.type
= cls
->members
[0]->type
;
3092 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3094 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3095 if (slot
->classes
[i
] == cls
)
3097 slot
->classes
.ordered_remove (i
);
3101 /* New class will be inserted and integrated to work list. */
3102 for (unsigned int i
= 0; i
< 2; i
++)
3103 optimizer
->add_class (newclasses
[i
]);
3105 /* Two classes replace one, so that increment just by one. */
3106 optimizer
->m_classes_count
++;
3108 /* If OLD class was presented in the worklist, we remove the class
3109 and replace it will both newly created classes. */
3111 for (unsigned int i
= 0; i
< 2; i
++)
3112 optimizer
->worklist_push (newclasses
[i
]);
3113 else /* Just smaller class is inserted. */
3115 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3116 newclasses
[1]->members
.length () ?
3118 optimizer
->worklist_push (newclasses
[smaller_index
]);
3121 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3123 fprintf (dump_file
, " congruence class splitted:\n");
3124 cls
->dump (dump_file
, 4);
3126 fprintf (dump_file
, " newly created groups:\n");
3127 for (unsigned int i
= 0; i
< 2; i
++)
3128 newclasses
[i
]->dump (dump_file
, 4);
3131 /* Release class if not presented in work list. */
3140 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3141 Bitmap stack BMSTACK is used for bitmap allocation. */
3144 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3147 hash_map
<congruence_class
*, bitmap
> split_map
;
3149 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3151 sem_item
*item
= cls
->members
[i
];
3153 /* Iterate all usages that have INDEX as usage of the item. */
3154 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3156 sem_usage_pair
*usage
= item
->usages
[j
];
3158 if (usage
->index
!= index
)
3161 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3166 b
= BITMAP_ALLOC (&m_bmstack
);
3167 split_map
.put (usage
->item
->cls
, b
);
3172 gcc_checking_assert (usage
->item
->cls
);
3173 gcc_checking_assert (usage
->item
->index_in_class
<
3174 usage
->item
->cls
->members
.length ());
3176 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3180 traverse_split_pair pair
;
3181 pair
.optimizer
= this;
3184 splitter_class_removed
= false;
3186 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3188 /* Bitmap clean-up. */
3190 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3193 /* Every usage of a congruence class CLS is a candidate that can split the
3194 collection of classes. Bitmap stack BMSTACK is used for bitmap
3198 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3203 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3205 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3206 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3208 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3211 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3214 do_congruence_step_for_index (cls
, i
);
3216 if (splitter_class_removed
)
3220 BITMAP_FREE (usage
);
3223 /* Adds a newly created congruence class CLS to worklist. */
3226 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3228 /* Return if the class CLS is already presented in work list. */
3229 if (cls
->in_worklist
)
3232 cls
->in_worklist
= true;
3233 worklist
.push_back (cls
);
3236 /* Pops a class from worklist. */
3239 sem_item_optimizer::worklist_pop (void)
3241 congruence_class
*cls
;
3243 while (!worklist
.empty ())
3245 cls
= worklist
.front ();
3246 worklist
.pop_front ();
3247 if (cls
->in_worklist
)
3249 cls
->in_worklist
= false;
3255 /* Work list item was already intended to be removed.
3256 The only reason for doing it is to split a class.
3257 Thus, the class CLS is deleted. */
3265 /* Iterative congruence reduction function. */
3268 sem_item_optimizer::process_cong_reduction (void)
3270 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3271 it
!= m_classes
.end (); ++it
)
3272 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3273 if ((*it
)->classes
[i
]->is_class_used ())
3274 worklist_push ((*it
)->classes
[i
]);
3277 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3278 (unsigned long) worklist
.size ());
3280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3281 fprintf (dump_file
, "Congruence class reduction\n");
3283 congruence_class
*cls
;
3285 /* Process complete congruence reduction. */
3286 while ((cls
= worklist_pop ()) != NULL
)
3287 do_congruence_step (cls
);
3289 /* Subdivide newly created classes according to references. */
3290 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3293 fprintf (dump_file
, "Address reference subdivision created: %u "
3294 "new classes.\n", new_classes
);
3297 /* Debug function prints all informations about congruence classes. */
3300 sem_item_optimizer::dump_cong_classes (void)
3306 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3307 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3309 /* Histogram calculation. */
3310 unsigned int max_index
= 0;
3311 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3313 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3314 it
!= m_classes
.end (); ++it
)
3316 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3318 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3326 "Class size histogram [num of members]: number of classe number of classess\n");
3328 for (unsigned int i
= 0; i
<= max_index
; i
++)
3330 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3332 fprintf (dump_file
, "\n\n");
3335 if (dump_flags
& TDF_DETAILS
)
3336 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3337 it
!= m_classes
.end (); ++it
)
3339 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3341 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3343 (*it
)->classes
[i
]->dump (dump_file
, 4);
3345 if(i
< (*it
)->classes
.length () - 1)
3346 fprintf (dump_file
, " ");
3353 /* After reduction is done, we can declare all items in a group
3354 to be equal. PREV_CLASS_COUNT is start number of classes
3355 before reduction. True is returned if there's a merge operation
3359 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3361 unsigned int item_count
= m_items
.length ();
3362 unsigned int class_count
= m_classes_count
;
3363 unsigned int equal_items
= item_count
- class_count
;
3365 unsigned int non_singular_classes_count
= 0;
3366 unsigned int non_singular_classes_sum
= 0;
3368 bool merged_p
= false;
3370 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3371 it
!= m_classes
.end (); ++it
)
3372 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3374 congruence_class
*c
= (*it
)->classes
[i
];
3375 if (c
->members
.length () > 1)
3377 non_singular_classes_count
++;
3378 non_singular_classes_sum
+= c
->members
.length ();
3384 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3385 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3386 prev_class_count
, class_count
);
3387 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3388 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3389 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3390 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3391 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3392 non_singular_classes_count
: 0.0f
,
3393 non_singular_classes_count
);
3394 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3395 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3396 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3399 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3400 it
!= m_classes
.end (); ++it
)
3401 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3403 congruence_class
*c
= (*it
)->classes
[i
];
3405 if (c
->members
.length () == 1)
3408 sem_item
*source
= c
->members
[0];
3410 if (DECL_NAME (source
->decl
)
3411 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3412 /* If merge via wrappers, picking main as the target can be
3414 source
= c
->members
[1];
3416 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3418 sem_item
*alias
= c
->members
[j
];
3420 if (alias
== source
)
3425 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3426 xstrdup_for_dump (source
->node
->name ()),
3427 xstrdup_for_dump (alias
->node
->name ()));
3428 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3429 xstrdup_for_dump (source
->node
->asm_name ()),
3430 xstrdup_for_dump (alias
->node
->asm_name ()));
3433 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3437 "Merge operation is skipped due to no_icf "
3443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3445 source
->dump_to_file (dump_file
);
3446 alias
->dump_to_file (dump_file
);
3449 if (dbg_cnt (merged_ipa_icf
))
3450 merged_p
|= source
->merge (alias
);
3457 /* Dump function prints all class members to a FILE with an INDENT. */
3460 congruence_class::dump (FILE *file
, unsigned int indent
) const
3462 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3463 id
, members
[0]->get_hash (), members
.length ());
3465 FPUTS_SPACES (file
, indent
+ 2, "");
3466 for (unsigned i
= 0; i
< members
.length (); i
++)
3467 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3468 (void *) members
[i
]->decl
,
3469 members
[i
]->node
->order
);
3471 fprintf (file
, "\n");
3474 /* Returns true if there's a member that is used from another group. */
3477 congruence_class::is_class_used (void)
3479 for (unsigned int i
= 0; i
< members
.length (); i
++)
3480 if (members
[i
]->usages
.length ())
3486 /* Generate pass summary for IPA ICF pass. */
3489 ipa_icf_generate_summary (void)
3492 optimizer
= new sem_item_optimizer ();
3494 optimizer
->register_hooks ();
3495 optimizer
->parse_funcs_and_vars ();
3498 /* Write pass summary for IPA ICF pass. */
3501 ipa_icf_write_summary (void)
3503 gcc_assert (optimizer
);
3505 optimizer
->write_summary ();
3508 /* Read pass summary for IPA ICF pass. */
3511 ipa_icf_read_summary (void)
3514 optimizer
= new sem_item_optimizer ();
3516 optimizer
->read_summary ();
3517 optimizer
->register_hooks ();
3520 /* Semantic equality exection function. */
3523 ipa_icf_driver (void)
3525 gcc_assert (optimizer
);
3527 bool merged_p
= optimizer
->execute ();
3532 return merged_p
? TODO_remove_functions
: 0;
3535 const pass_data pass_data_ipa_icf
=
3537 IPA_PASS
, /* type */
3539 OPTGROUP_IPA
, /* optinfo_flags */
3540 TV_IPA_ICF
, /* tv_id */
3541 0, /* properties_required */
3542 0, /* properties_provided */
3543 0, /* properties_destroyed */
3544 0, /* todo_flags_start */
3545 0, /* todo_flags_finish */
3548 class pass_ipa_icf
: public ipa_opt_pass_d
3551 pass_ipa_icf (gcc::context
*ctxt
)
3552 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3553 ipa_icf_generate_summary
, /* generate_summary */
3554 ipa_icf_write_summary
, /* write_summary */
3555 ipa_icf_read_summary
, /* read_summary */
3557 write_optimization_summary */
3559 read_optimization_summary */
3560 NULL
, /* stmt_fixup */
3561 0, /* function_transform_todo_flags_start */
3562 NULL
, /* function_transform */
3563 NULL
) /* variable_transform */
3566 /* opt_pass methods: */
3567 virtual bool gate (function
*)
3569 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3572 virtual unsigned int execute (function
*)
3574 return ipa_icf_driver();
3576 }; // class pass_ipa_icf
3578 } // ipa_icf namespace
3581 make_pass_ipa_icf (gcc::context
*ctxt
)
3583 return new ipa_icf::pass_ipa_icf (ctxt
);