1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
61 #include "double-int.h"
69 #include "fold-const.h"
72 #include "hard-reg-set.h"
74 #include "dominance.h"
76 #include "basic-block.h"
77 #include "tree-ssa-alias.h"
78 #include "internal-fn.h"
79 #include "gimple-expr.h"
85 #include "statistics.h"
87 #include "fixed-value.h"
88 #include "insn-config.h"
97 #include "gimple-iterator.h"
98 #include "gimple-ssa.h"
100 #include "tree-phinodes.h"
101 #include "stringpool.h"
102 #include "tree-ssanames.h"
103 #include "tree-dfa.h"
104 #include "tree-pass.h"
105 #include "gimple-pretty-print.h"
106 #include "hash-map.h"
107 #include "plugin-api.h"
110 #include "alloc-pool.h"
111 #include "symbol-summary.h"
112 #include "ipa-prop.h"
113 #include "ipa-inline.h"
116 #include "hash-table.h"
117 #include "coverage.h"
119 #include "print-tree.h"
120 #include "lto-streamer.h"
121 #include "data-streamer.h"
122 #include "ipa-utils.h"
123 #include "ipa-icf-gimple.h"
125 #include "stor-layout.h"
127 using namespace ipa_icf_gimple
;
133 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
135 m_references
.create (0);
136 m_interposables
.create (0);
140 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
143 for (unsigned i
= 0; i
< node
->num_references (); i
++)
145 ref
= node
->iterate_reference (i
, ref
);
146 if (ref
->address_matters_p ())
147 m_references
.safe_push (ref
->referred
);
149 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
151 if (ref
->address_matters_p ())
152 m_references
.safe_push (ref
->referred
);
154 m_interposables
.safe_push (ref
->referred
);
158 if (is_a
<cgraph_node
*> (node
))
160 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
162 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
163 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
164 m_interposables
.safe_push (e
->callee
);
168 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
170 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
171 item (_item
), index (_index
)
175 /* Semantic item constructor for a node of _TYPE, where STACK is used
176 for bitmap memory allocation. */
178 sem_item::sem_item (sem_item_type _type
,
179 bitmap_obstack
*stack
): type(_type
), hash(0)
184 /* Semantic item constructor for a node of _TYPE, where STACK is used
185 for bitmap memory allocation. The item is based on symtab node _NODE
186 with computed _HASH. */
188 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
189 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
190 node (_node
), hash (_hash
)
196 /* Add reference to a semantic TARGET. */
199 sem_item::add_reference (sem_item
*target
)
201 refs
.safe_push (target
);
202 unsigned index
= refs
.length ();
203 target
->usages
.safe_push (new sem_usage_pair(this, index
));
204 bitmap_set_bit (target
->usage_index_bitmap
, index
);
205 refs_set
.add (target
->node
);
208 /* Initialize internal data structures. Bitmap STACK is used for
209 bitmap memory allocation process. */
212 sem_item::setup (bitmap_obstack
*stack
)
214 gcc_checking_assert (node
);
217 tree_refs
.create (0);
219 usage_index_bitmap
= BITMAP_ALLOC (stack
);
222 sem_item::~sem_item ()
224 for (unsigned i
= 0; i
< usages
.length (); i
++)
228 tree_refs
.release ();
231 BITMAP_FREE (usage_index_bitmap
);
234 /* Dump function for debugging purpose. */
237 sem_item::dump (void)
241 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
242 name(), node
->order
, (void *) node
->decl
);
243 fprintf (dump_file
, " hash: %u\n", get_hash ());
244 fprintf (dump_file
, " references: ");
246 for (unsigned i
= 0; i
< refs
.length (); i
++)
247 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
248 i
< refs
.length() - 1 ? "," : "");
250 fprintf (dump_file
, "\n");
254 /* Return true if target supports alias symbols. */
257 sem_item::target_supports_symbol_aliases_p (void)
259 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
266 /* Semantic function constructor that uses STACK as bitmap memory stack. */
268 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
269 m_checker (NULL
), m_compared_func (NULL
)
271 arg_types
.create (0);
273 bb_sorted
.create (0);
276 /* Constructor based on callgraph node _NODE with computed hash _HASH.
277 Bitmap STACK is used for memory allocation. */
278 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
279 bitmap_obstack
*stack
):
280 sem_item (FUNC
, node
, hash
, stack
),
281 m_checker (NULL
), m_compared_func (NULL
)
283 arg_types
.create (0);
285 bb_sorted
.create (0);
288 sem_function::~sem_function ()
290 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
291 delete (bb_sorted
[i
]);
293 arg_types
.release ();
295 bb_sorted
.release ();
298 /* Calculates hash value based on a BASIC_BLOCK. */
301 sem_function::get_bb_hash (const sem_bb
*basic_block
)
303 inchash::hash hstate
;
305 hstate
.add_int (basic_block
->nondbg_stmt_count
);
306 hstate
.add_int (basic_block
->edge_count
);
308 return hstate
.end ();
311 /* References independent hash function. */
314 sem_function::get_hash (void)
318 inchash::hash hstate
;
319 hstate
.add_int (177454); /* Random number for function type. */
321 hstate
.add_int (arg_count
);
322 hstate
.add_int (cfg_checksum
);
323 hstate
.add_int (gcode_hash
);
325 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
326 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
328 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
329 hstate
.add_int (bb_sizes
[i
]);
331 hash
= hstate
.end ();
337 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
338 point to a same function. Comparison can be skipped if IGNORED_NODES
339 contains these nodes. ADDRESS indicate if address is taken. */
342 sem_item::compare_cgraph_references (
343 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
344 symtab_node
*n1
, symtab_node
*n2
, bool address
)
346 enum availability avail1
, avail2
;
351 /* Merging two definitions with a reference to equivalent vtables, but
352 belonging to a different type may result in ipa-polymorphic-call analysis
353 giving a wrong answer about the dynamic type of instance. */
354 if (is_a
<varpool_node
*> (n1
)
355 && (DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
356 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
357 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
358 DECL_CONTEXT (n2
->decl
))))
359 return return_false_with_msg
360 ("references to virtual tables can not be merged");
362 if (address
&& n1
->equal_address_to (n2
) == 1)
364 if (!address
&& n1
->semantically_equivalent_p (n2
))
367 n1
= n1
->ultimate_alias_target (&avail1
);
368 n2
= n2
->ultimate_alias_target (&avail2
);
370 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
371 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
374 return return_false_with_msg ("different references");
377 /* If cgraph edges E1 and E2 are indirect calls, verify that
378 ECF flags are the same. */
380 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
382 if (e1
->indirect_info
&& e2
->indirect_info
)
384 int e1_flags
= e1
->indirect_info
->ecf_flags
;
385 int e2_flags
= e2
->indirect_info
->ecf_flags
;
387 if (e1_flags
!= e2_flags
)
388 return return_false_with_msg ("ICF flags are different");
390 else if (e1
->indirect_info
|| e2
->indirect_info
)
396 /* Fast equality function based on knowledge known in WPA. */
399 sem_function::equals_wpa (sem_item
*item
,
400 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
402 gcc_assert (item
->type
== FUNC
);
404 m_compared_func
= static_cast<sem_function
*> (item
);
406 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
407 return return_false_with_msg ("different number of arguments");
409 /* Compare special function DECL attributes. */
410 if (DECL_FUNCTION_PERSONALITY (decl
)
411 != DECL_FUNCTION_PERSONALITY (item
->decl
))
412 return return_false_with_msg ("function personalities are different");
414 if (DECL_DISREGARD_INLINE_LIMITS (decl
)
415 != DECL_DISREGARD_INLINE_LIMITS (item
->decl
))
416 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
418 if (DECL_DECLARED_INLINE_P (decl
) != DECL_DECLARED_INLINE_P (item
->decl
))
419 return return_false_with_msg ("inline attributes are different");
421 if (DECL_IS_OPERATOR_NEW (decl
) != DECL_IS_OPERATOR_NEW (item
->decl
))
422 return return_false_with_msg ("operator new flags are different");
424 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
425 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
426 return return_false_with_msg ("intrument function entry exit "
427 "attributes are different");
429 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
430 return return_false_with_msg ("no stack limit attributes are different");
432 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
433 return return_false_with_msg ("DELC_CXX_CONSTRUCTOR mismatch");
435 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
436 return return_false_with_msg ("DELC_CXX_DESTRUCTOR mismatch");
438 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
439 return return_false_with_msg ("decl_or_type flags are different");
441 /* Do not match polymorphic constructors of different types. They calls
442 type memory location for ipa-polymorphic-call and we do not want
443 it to get confused by wrong type. */
444 if (DECL_CXX_CONSTRUCTOR_P (decl
)
445 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
447 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
448 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
449 else if (!func_checker::compatible_polymorphic_types_p
450 (method_class_type (TREE_TYPE (decl
)),
451 method_class_type (TREE_TYPE (item
->decl
)), false))
452 return return_false_with_msg ("ctor polymorphic type mismatch");
455 /* Checking function TARGET and OPTIMIZATION flags. */
456 cl_target_option
*tar1
= target_opts_for_fn (decl
);
457 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
459 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
463 fprintf (dump_file
, "target flags difference");
464 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
467 return return_false_with_msg ("Target flags are different");
470 cl_optimization
*opt1
= opts_for_fn (decl
);
471 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
473 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
477 fprintf (dump_file
, "optimization flags difference");
478 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
481 return return_false_with_msg ("optimization flags are different");
484 /* Result type checking. */
485 if (!func_checker::compatible_types_p (result_type
,
486 m_compared_func
->result_type
))
487 return return_false_with_msg ("result types are different");
489 /* Checking types of arguments. */
490 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
492 /* This guard is here for function pointer with attributes (pr59927.c). */
493 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
494 return return_false_with_msg ("NULL argument type");
496 if (!func_checker::compatible_types_p (arg_types
[i
],
497 m_compared_func
->arg_types
[i
]))
498 return return_false_with_msg ("argument type is different");
499 if (POINTER_TYPE_P (arg_types
[i
])
500 && (TYPE_RESTRICT (arg_types
[i
])
501 != TYPE_RESTRICT (m_compared_func
->arg_types
[i
])))
502 return return_false_with_msg ("argument restrict flag mismatch");
505 if (node
->num_references () != item
->node
->num_references ())
506 return return_false_with_msg ("different number of references");
508 if (comp_type_attributes (TREE_TYPE (decl
),
509 TREE_TYPE (item
->decl
)) != 1)
510 return return_false_with_msg ("different type attributes");
512 /* The type of THIS pointer type memory location for
513 ipa-polymorphic-call-analysis. */
514 if (opt_for_fn (decl
, flag_devirtualize
)
515 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
516 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
518 || ipa_is_param_used (IPA_NODE_REF (dyn_cast
<cgraph_node
*>(node
)),
520 && compare_polymorphic_p ())
522 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
523 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
524 if (!func_checker::compatible_polymorphic_types_p
525 (method_class_type (TREE_TYPE (decl
)),
526 method_class_type (TREE_TYPE (item
->decl
)), false))
527 return return_false_with_msg ("THIS pointer ODR type mismatch");
530 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
531 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
533 item
->node
->iterate_reference (i
, ref2
);
535 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
,
537 ref
->address_matters_p ()))
541 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
542 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
546 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
,
550 e1
= e1
->next_callee
;
551 e2
= e2
->next_callee
;
555 return return_false_with_msg ("different number of edges");
560 /* Returns true if the item equals to ITEM given as argument. */
563 sem_function::equals (sem_item
*item
,
564 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
566 gcc_assert (item
->type
== FUNC
);
567 bool eq
= equals_private (item
, ignored_nodes
);
569 if (m_checker
!= NULL
)
575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
578 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
579 item
->asm_name (), eq
? "true" : "false");
584 /* Processes function equality comparison. */
587 sem_function::equals_private (sem_item
*item
,
588 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
590 if (item
->type
!= FUNC
)
593 basic_block bb1
, bb2
;
595 edge_iterator ei1
, ei2
;
599 m_compared_func
= static_cast<sem_function
*> (item
);
601 gcc_assert (decl
!= item
->decl
);
603 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
604 || edge_count
!= m_compared_func
->edge_count
605 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
606 return return_false ();
608 if (!equals_wpa (item
, ignored_nodes
))
611 /* Checking function arguments. */
612 tree decl1
= DECL_ATTRIBUTES (decl
);
613 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
615 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
616 compare_polymorphic_p (),
619 &m_compared_func
->refs_set
);
623 return return_false ();
625 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
626 return return_false ();
628 tree attr_value1
= TREE_VALUE (decl1
);
629 tree attr_value2
= TREE_VALUE (decl2
);
631 if (attr_value1
&& attr_value2
)
633 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
634 TREE_VALUE (attr_value2
));
636 return return_false_with_msg ("attribute values are different");
638 else if (!attr_value1
&& !attr_value2
)
641 return return_false ();
643 decl1
= TREE_CHAIN (decl1
);
644 decl2
= TREE_CHAIN (decl2
);
648 return return_false();
650 for (arg1
= DECL_ARGUMENTS (decl
),
651 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
652 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
653 if (!m_checker
->compare_decl (arg1
, arg2
))
654 return return_false ();
656 /* Fill-up label dictionary. */
657 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
659 m_checker
->parse_labels (bb_sorted
[i
]);
660 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
663 /* Checking all basic blocks. */
664 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
665 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
666 return return_false();
668 dump_message ("All BBs are equal\n");
670 auto_vec
<int> bb_dict
;
672 /* Basic block edges check. */
673 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
675 bb1
= bb_sorted
[i
]->bb
;
676 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
678 ei2
= ei_start (bb2
->preds
);
680 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
684 if (e1
->flags
!= e2
->flags
)
685 return return_false_with_msg ("flags comparison returns false");
687 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
688 return return_false_with_msg ("edge comparison returns false");
690 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
691 return return_false_with_msg ("BB comparison returns false");
693 if (!m_checker
->compare_edge (e1
, e2
))
694 return return_false_with_msg ("edge comparison returns false");
700 /* Basic block PHI nodes comparison. */
701 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
702 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
703 return return_false_with_msg ("PHI node comparison returns false");
708 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
709 Helper for call_for_symbol_thunks_and_aliases. */
712 set_local (cgraph_node
*node
, void *data
)
714 node
->local
.local
= data
!= NULL
;
718 /* TREE_ADDRESSABLE of NODE to true.
719 Helper for call_for_symbol_thunks_and_aliases. */
722 set_addressable (varpool_node
*node
, void *)
724 TREE_ADDRESSABLE (node
->decl
) = 1;
728 /* Clear DECL_RTL of NODE.
729 Helper for call_for_symbol_thunks_and_aliases. */
732 clear_decl_rtl (symtab_node
*node
, void *)
734 SET_DECL_RTL (node
->decl
, NULL
);
738 /* Redirect all callers of N and its aliases to TO. Remove aliases if
739 possible. Return number of redirections made. */
742 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
746 cgraph_edge
*e
= n
->callers
;
750 /* Redirecting thunks to interposable symbols or symbols in other sections
751 may not be supported by target output code. Play safe for now and
752 punt on redirection. */
753 if (!e
->caller
->thunk
.thunk_p
)
755 struct cgraph_edge
*nexte
= e
->next_caller
;
756 e
->redirect_callee (to
);
763 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
765 bool removed
= false;
766 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
768 if ((DECL_COMDAT_GROUP (n
->decl
)
769 && (DECL_COMDAT_GROUP (n
->decl
)
770 == DECL_COMDAT_GROUP (n_alias
->decl
)))
771 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
772 && n
->get_availability () > AVAIL_INTERPOSABLE
))
774 nredirected
+= redirect_all_callers (n_alias
, to
);
775 if (n_alias
->can_remove_if_no_direct_calls_p ()
776 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
778 && !n_alias
->has_aliases_p ())
787 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
791 sem_function::merge (sem_item
*alias_item
)
793 gcc_assert (alias_item
->type
== FUNC
);
795 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
797 cgraph_node
*original
= get_node ();
798 cgraph_node
*local_original
= NULL
;
799 cgraph_node
*alias
= alias_func
->get_node ();
801 bool create_wrapper
= false;
802 bool create_alias
= false;
803 bool redirect_callers
= false;
806 bool original_discardable
= false;
807 bool original_discarded
= false;
809 bool original_address_matters
= original
->address_matters_p ();
810 bool alias_address_matters
= alias
->address_matters_p ();
812 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
813 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
818 "DECL_NO_INLINE_WARNING mismatch.\n\n");
822 /* Do not attempt to mix functions from different user sections;
823 we do not know what user intends with those. */
824 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
825 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
826 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
831 "original and alias are in different sections.\n\n");
835 /* See if original is in a section that can be discarded if the main
836 symbol is not used. */
838 if (original
->can_be_discarded_p ())
839 original_discardable
= true;
840 /* Also consider case where we have resolution info and we know that
841 original's definition is not going to be used. In this case we can not
842 create alias to original. */
843 if (node
->resolution
!= LDPR_UNKNOWN
844 && !decl_binds_to_current_def_p (node
->decl
))
845 original_discardable
= original_discarded
= true;
847 /* Creating a symtab alias is the optimal way to merge.
848 It however can not be used in the following cases:
850 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
851 2) if ORIGINAL is in a section that may be discarded by linker or if
852 it is an external functions where we can not create an alias
853 (ORIGINAL_DISCARDABLE)
854 3) if target do not support symbol aliases.
855 4) original and alias lie in different comdat groups.
857 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
858 and/or redirect all callers from ALIAS to ORIGINAL. */
859 if ((original_address_matters
&& alias_address_matters
)
860 || (original_discardable
861 && (!DECL_COMDAT_GROUP (alias
->decl
)
862 || (DECL_COMDAT_GROUP (alias
->decl
)
863 != DECL_COMDAT_GROUP (original
->decl
))))
864 || original_discarded
865 || !sem_item::target_supports_symbol_aliases_p ()
866 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
868 /* First see if we can produce wrapper. */
870 /* Do not turn function in one comdat group into wrapper to another
871 comdat group. Other compiler producing the body of the
872 another comdat group may make opossite decision and with unfortunate
873 linker choices this may close a loop. */
874 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
875 && (DECL_COMDAT_GROUP (alias
->decl
)
876 != DECL_COMDAT_GROUP (original
->decl
)))
880 "Wrapper cannot be created because of COMDAT\n");
882 else if (DECL_STATIC_CHAIN (alias
->decl
))
886 "Can not create wrapper of nested functions.\n");
888 /* TODO: We can also deal with variadic functions never calling
890 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
894 "can not create wrapper of stdarg function.\n");
896 else if (inline_summaries
897 && inline_summaries
->get (alias
)->self_size
<= 2)
900 fprintf (dump_file
, "Wrapper creation is not "
901 "profitable (function is too small).\n");
903 /* If user paid attention to mark function noinline, assume it is
904 somewhat special and do not try to turn it into a wrapper that can
905 not be undone by inliner. */
906 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
909 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
912 create_wrapper
= true;
914 /* We can redirect local calls in the case both alias and orignal
915 are not interposable. */
917 = alias
->get_availability () > AVAIL_INTERPOSABLE
918 && original
->get_availability () > AVAIL_INTERPOSABLE
919 && !alias
->instrumented_version
;
921 if (!redirect_callers
&& !create_wrapper
)
924 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
925 "produce wrapper\n\n");
929 /* Work out the symbol the wrapper should call.
930 If ORIGINAL is interposable, we need to call a local alias.
931 Also produce local alias (if possible) as an optimization.
933 Local aliases can not be created inside comdat groups because that
934 prevents inlining. */
935 if (!original_discardable
&& !original
->get_comdat_group ())
938 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
940 && original
->get_availability () > AVAIL_INTERPOSABLE
)
941 local_original
= original
;
943 /* If we can not use local alias, fallback to the original
945 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
946 local_original
= original
;
948 /* If original is COMDAT local, we can not really redirect calls outside
949 of its comdat group to it. */
950 if (original
->comdat_local_p ())
951 redirect_callers
= false;
955 fprintf (dump_file
, "Not unifying; "
956 "can not produce local alias.\n\n");
960 if (!redirect_callers
&& !create_wrapper
)
963 fprintf (dump_file
, "Not unifying; "
964 "can not redirect callers nor produce a wrapper\n\n");
968 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
970 && !alias
->can_remove_if_no_direct_calls_p ())
973 fprintf (dump_file
, "Not unifying; can not make wrapper and "
974 "function has other uses than direct calls\n\n");
981 if (redirect_callers
)
983 int nredirected
= redirect_all_callers (alias
, local_original
);
987 alias
->icf_merged
= true;
988 local_original
->icf_merged
= true;
990 if (dump_file
&& nredirected
)
991 fprintf (dump_file
, "%i local calls have been "
992 "redirected.\n", nredirected
);
995 /* If all callers was redirected, do not produce wrapper. */
996 if (alias
->can_remove_if_no_direct_calls_p ()
997 && !alias
->has_aliases_p ())
999 create_wrapper
= false;
1002 gcc_assert (!create_alias
);
1004 else if (create_alias
)
1006 alias
->icf_merged
= true;
1008 /* Remove the function's body. */
1009 ipa_merge_profiles (original
, alias
);
1010 alias
->release_body (true);
1012 /* Notice global symbol possibly produced RTL. */
1013 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1016 /* Create the alias. */
1017 cgraph_node::create_alias (alias_func
->decl
, decl
);
1018 alias
->resolve_alias (original
);
1020 original
->call_for_symbol_thunks_and_aliases
1021 (set_local
, (void *)(size_t) original
->local_p (), true);
1024 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1028 gcc_assert (!create_alias
);
1029 alias
->icf_merged
= true;
1030 local_original
->icf_merged
= true;
1032 ipa_merge_profiles (local_original
, alias
, true);
1033 alias
->create_wrapper (local_original
);
1036 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1039 /* It's possible that redirection can hit thunks that block
1040 redirection opportunities. */
1041 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1042 original
->icf_merged
= true;
1044 /* Inform the inliner about cross-module merging. */
1045 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1046 && original
->lto_file_data
!= alias
->lto_file_data
)
1047 local_original
->merged
= original
->merged
= true;
1051 ipa_merge_profiles (original
, alias
);
1052 alias
->release_body ();
1054 alias
->body_removed
= true;
1055 alias
->icf_merged
= true;
1057 fprintf (dump_file
, "Unified; Function body was removed.\n");
1063 /* Semantic item initialization function. */
1066 sem_function::init (void)
1069 get_node ()->get_untransformed_body ();
1071 tree fndecl
= node
->decl
;
1072 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1075 gcc_assert (SSANAMES (func
));
1077 ssa_names_size
= SSANAMES (func
)->length ();
1081 region_tree
= func
->eh
->region_tree
;
1083 /* iterating all function arguments. */
1084 arg_count
= count_formal_params (fndecl
);
1086 edge_count
= n_edges_for_fn (func
);
1087 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1089 inchash::hash hstate
;
1092 FOR_EACH_BB_FN (bb
, func
)
1094 unsigned nondbg_stmt_count
= 0;
1097 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1099 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1102 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1105 gimple stmt
= gsi_stmt (gsi
);
1107 if (gimple_code (stmt
) != GIMPLE_DEBUG
1108 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1110 hash_stmt (stmt
, hstate
);
1111 nondbg_stmt_count
++;
1115 gcode_hash
= hstate
.end ();
1116 bb_sizes
.safe_push (nondbg_stmt_count
);
1118 /* Inserting basic block to hash table. */
1119 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1120 EDGE_COUNT (bb
->preds
)
1121 + EDGE_COUNT (bb
->succs
));
1123 bb_sorted
.safe_push (semantic_bb
);
1129 /* Accumulate to HSTATE a hash of expression EXP.
1130 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1131 and DECL equality classes. */
1134 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1136 if (exp
== NULL_TREE
)
1138 hstate
.merge_hash (0);
1142 /* Handled component can be matched in a cureful way proving equivalence
1143 even if they syntactically differ. Just skip them. */
1145 while (handled_component_p (exp
))
1146 exp
= TREE_OPERAND (exp
, 0);
1148 enum tree_code code
= TREE_CODE (exp
);
1149 hstate
.add_int (code
);
1153 /* Use inchash::add_expr for everything that is LTO stable. */
1161 inchash::add_expr (exp
, hstate
);
1165 unsigned HOST_WIDE_INT idx
;
1168 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1170 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1172 add_expr (value
, hstate
);
1177 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1183 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1186 case POINTER_PLUS_EXPR
:
1189 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1190 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1194 inchash::hash one
, two
;
1195 add_expr (TREE_OPERAND (exp
, 0), one
);
1196 add_expr (TREE_OPERAND (exp
, 1), two
);
1197 hstate
.add_commutative (one
, two
);
1201 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1202 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1208 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1211 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1213 enum gimple_code code
= gimple_code (stmt
);
1215 hstate
.add_int (code
);
1220 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1221 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1223 inchash::hash one
, two
;
1225 add_expr (gimple_assign_rhs1 (stmt
), one
);
1226 add_expr (gimple_assign_rhs2 (stmt
), two
);
1227 hstate
.add_commutative (one
, two
);
1228 add_expr (gimple_assign_lhs (stmt
), hstate
);
1231 /* ... fall through ... */
1237 /* All these statements are equivalent if their operands are. */
1238 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1239 add_expr (gimple_op (stmt
, i
), hstate
);
1246 /* Return true if polymorphic comparison must be processed. */
1249 sem_function::compare_polymorphic_p (void)
1251 struct cgraph_edge
*e
;
1253 if (!opt_for_fn (decl
, flag_devirtualize
))
1255 if (get_node ()->indirect_calls
!= NULL
1256 || m_compared_func
->get_node ()->indirect_calls
!= NULL
)
1258 /* TODO: We can do simple propagation determining what calls may lead to
1259 a polymorphic call. */
1260 for (e
= m_compared_func
->get_node ()->callees
; e
; e
= e
->next_callee
)
1261 if (e
->callee
->definition
1262 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1267 /* For a given call graph NODE, the function constructs new
1268 semantic function item. */
1271 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1273 tree fndecl
= node
->decl
;
1274 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1276 /* TODO: add support for thunks. */
1278 if (!func
|| !node
->has_gimple_body_p ())
1281 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1284 sem_function
*f
= new sem_function (node
, 0, stack
);
1291 /* Parses function arguments and result type. */
1294 sem_function::parse_tree_args (void)
1298 if (arg_types
.exists ())
1299 arg_types
.release ();
1301 arg_types
.create (4);
1302 tree fnargs
= DECL_ARGUMENTS (decl
);
1304 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1305 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1307 /* Function result type. */
1308 result
= DECL_RESULT (decl
);
1309 result_type
= result
? TREE_TYPE (result
) : NULL
;
1311 /* During WPA, we can get arguments by following method. */
1314 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1315 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1316 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1318 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1322 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1323 return true if phi nodes are semantically equivalent in these blocks . */
1326 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1328 gphi_iterator si1
, si2
;
1330 unsigned size1
, size2
, i
;
1334 gcc_assert (bb1
!= NULL
);
1335 gcc_assert (bb2
!= NULL
);
1337 si2
= gsi_start_phis (bb2
);
1338 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1341 gsi_next_nonvirtual_phi (&si1
);
1342 gsi_next_nonvirtual_phi (&si2
);
1344 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1347 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1348 return return_false();
1353 tree phi_result1
= gimple_phi_result (phi1
);
1354 tree phi_result2
= gimple_phi_result (phi2
);
1356 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1357 return return_false_with_msg ("PHI results are different");
1359 size1
= gimple_phi_num_args (phi1
);
1360 size2
= gimple_phi_num_args (phi2
);
1363 return return_false ();
1365 for (i
= 0; i
< size1
; ++i
)
1367 t1
= gimple_phi_arg (phi1
, i
)->def
;
1368 t2
= gimple_phi_arg (phi2
, i
)->def
;
1370 if (!m_checker
->compare_operand (t1
, t2
))
1371 return return_false ();
1373 e1
= gimple_phi_arg_edge (phi1
, i
);
1374 e2
= gimple_phi_arg_edge (phi2
, i
);
1376 if (!m_checker
->compare_edge (e1
, e2
))
1377 return return_false ();
1386 /* Returns true if tree T can be compared as a handled component. */
1389 sem_function::icf_handled_component_p (tree t
)
1391 tree_code tc
= TREE_CODE (t
);
1393 return ((handled_component_p (t
))
1394 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1395 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1398 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1399 corresponds to TARGET. */
1402 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1407 if (bb_dict
->length () <= (unsigned)source
)
1408 bb_dict
->safe_grow_cleared (source
+ 1);
1410 if ((*bb_dict
)[source
] == 0)
1412 (*bb_dict
)[source
] = target
;
1416 return (*bb_dict
)[source
] == target
;
1420 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1422 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1426 /* Constructor based on varpool node _NODE with computed hash _HASH.
1427 Bitmap STACK is used for memory allocation. */
1429 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1430 bitmap_obstack
*stack
): sem_item(VAR
,
1433 gcc_checking_assert (node
);
1434 gcc_checking_assert (get_node ());
1437 /* Fast equality function based on knowledge known in WPA. */
1440 sem_variable::equals_wpa (sem_item
*item
,
1441 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1443 gcc_assert (item
->type
== VAR
);
1445 if (node
->num_references () != item
->node
->num_references ())
1446 return return_false_with_msg ("different number of references");
1448 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1449 return return_false_with_msg ("TLS model");
1451 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1452 return return_false_with_msg ("alignment mismatch");
1454 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1455 return return_false_with_msg ("Virtual flag mismatch");
1457 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1458 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1459 || !operand_equal_p (DECL_SIZE (decl
),
1460 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1461 return return_false_with_msg ("size mismatch");
1463 /* Do not attempt to mix data from different user sections;
1464 we do not know what user intends with those. */
1465 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1466 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1467 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1468 return return_false_with_msg ("user section mismatch");
1470 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1471 return return_false_with_msg ("text section");
1473 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1474 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1476 item
->node
->iterate_reference (i
, ref2
);
1478 if (!compare_cgraph_references (ignored_nodes
,
1479 ref
->referred
, ref2
->referred
,
1480 ref
->address_matters_p ()))
1483 /* DECL_FINAL_P flag on methods referred by virtual tables is used
1484 to decide on completeness possible_polymorphic_call_targets lists
1485 and therefore it must match. */
1486 if ((DECL_VIRTUAL_P (decl
) || DECL_VIRTUAL_P (item
->decl
))
1487 && (DECL_VIRTUAL_P (ref
->referred
->decl
)
1488 || DECL_VIRTUAL_P (ref2
->referred
->decl
))
1489 && ((DECL_VIRTUAL_P (ref
->referred
->decl
)
1490 != DECL_VIRTUAL_P (ref2
->referred
->decl
))
1491 || (DECL_FINAL_P (ref
->referred
->decl
)
1492 != DECL_FINAL_P (ref2
->referred
->decl
))))
1493 return return_false_with_msg ("virtual or final flag mismatch");
1499 /* Returns true if the item equals to ITEM given as argument. */
1501 /* Returns true if the item equals to ITEM given as argument. */
1504 sem_variable::equals (sem_item
*item
,
1505 hash_map
<symtab_node
*, sem_item
*> &)
1507 gcc_assert (item
->type
== VAR
);
1510 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1511 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1512 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1513 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1515 /* As seen in PR ipa/65303 we have to compare variables types. */
1516 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1517 TREE_TYPE (item
->decl
)))
1518 return return_false_with_msg ("variables types are different");
1520 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1521 DECL_INITIAL (item
->node
->decl
));
1522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1524 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1525 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
1526 item
->asm_name (), ret
? "true" : "false");
1531 /* Compares trees T1 and T2 for semantic equality. */
1534 sem_variable::equals (tree t1
, tree t2
)
1537 return return_with_debug (t1
== t2
);
1540 tree_code tc1
= TREE_CODE (t1
);
1541 tree_code tc2
= TREE_CODE (t2
);
1544 return return_false_with_msg ("TREE_CODE mismatch");
1550 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1551 unsigned HOST_WIDE_INT idx
;
1553 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1554 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1555 return return_false_with_msg ("constructor type mismatch");
1557 if (typecode
== ARRAY_TYPE
)
1559 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1560 /* For arrays, check that the sizes all match. */
1561 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1563 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1564 return return_false_with_msg ("constructor array size mismatch");
1566 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1568 return return_false_with_msg ("constructor type incompatible");
1570 v1
= CONSTRUCTOR_ELTS (t1
);
1571 v2
= CONSTRUCTOR_ELTS (t2
);
1572 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1573 return return_false_with_msg ("constructor number of elts mismatch");
1575 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1577 constructor_elt
*c1
= &(*v1
)[idx
];
1578 constructor_elt
*c2
= &(*v2
)[idx
];
1580 /* Check that each value is the same... */
1581 if (!sem_variable::equals (c1
->value
, c2
->value
))
1583 /* ... and that they apply to the same fields! */
1584 if (!sem_variable::equals (c1
->index
, c2
->index
))
1591 tree x1
= TREE_OPERAND (t1
, 0);
1592 tree x2
= TREE_OPERAND (t2
, 0);
1593 tree y1
= TREE_OPERAND (t1
, 1);
1594 tree y2
= TREE_OPERAND (t2
, 1);
1596 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1597 return return_false ();
1599 /* Type of the offset on MEM_REF does not matter. */
1600 return return_with_debug (sem_variable::equals (x1
, x2
)
1601 && wi::to_offset (y1
)
1602 == wi::to_offset (y2
));
1607 tree op1
= TREE_OPERAND (t1
, 0);
1608 tree op2
= TREE_OPERAND (t2
, 0);
1609 return sem_variable::equals (op1
, op2
);
1611 /* References to other vars/decls are compared using ipa-ref. */
1614 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1616 return return_false_with_msg ("Declaration mismatch");
1618 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1619 need to process its VAR/FUNCTION references without relying on ipa-ref
1623 return return_false_with_msg ("Declaration mismatch");
1625 /* Integer constants are the same only if the same width of type. */
1626 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1627 return return_false_with_msg ("INTEGER_CST precision mismatch");
1628 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1629 return return_false_with_msg ("INTEGER_CST mode mismatch");
1630 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1632 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1633 return return_false_with_msg ("STRING_CST mode mismatch");
1634 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1635 return return_false_with_msg ("STRING_CST length mismatch");
1636 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1637 TREE_STRING_LENGTH (t1
)))
1638 return return_false_with_msg ("STRING_CST mismatch");
1641 /* Fixed constants are the same only if the same width of type. */
1642 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1643 return return_false_with_msg ("FIXED_CST precision mismatch");
1645 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1646 TREE_FIXED_CST (t2
)));
1648 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1649 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1651 /* Real constants are the same only if the same width of type. */
1652 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1653 return return_false_with_msg ("REAL_CST precision mismatch");
1654 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1655 TREE_REAL_CST (t2
)));
1660 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1661 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1663 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1664 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1665 VECTOR_CST_ELT (t2
, i
)))
1671 case ARRAY_RANGE_REF
:
1673 tree x1
= TREE_OPERAND (t1
, 0);
1674 tree x2
= TREE_OPERAND (t2
, 0);
1675 tree y1
= TREE_OPERAND (t1
, 1);
1676 tree y2
= TREE_OPERAND (t2
, 1);
1678 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1680 if (!sem_variable::equals (array_ref_low_bound (t1
),
1681 array_ref_low_bound (t2
)))
1683 if (!sem_variable::equals (array_ref_element_size (t1
),
1684 array_ref_element_size (t2
)))
1690 case POINTER_PLUS_EXPR
:
1695 tree x1
= TREE_OPERAND (t1
, 0);
1696 tree x2
= TREE_OPERAND (t2
, 0);
1697 tree y1
= TREE_OPERAND (t1
, 1);
1698 tree y2
= TREE_OPERAND (t2
, 1);
1700 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1704 case VIEW_CONVERT_EXPR
:
1705 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1706 return return_false ();
1707 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1709 return return_false_with_msg ("ERROR_MARK");
1711 return return_false_with_msg ("Unknown TREE code reached");
1715 /* Parser function that visits a varpool NODE. */
1718 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1720 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1724 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1731 /* References independent hash function. */
1734 sem_variable::get_hash (void)
1739 /* All WPA streamed in symbols should have their hashes computed at compile
1740 time. At this point, the constructor may not be in memory at all.
1741 DECL_INITIAL (decl) would be error_mark_node in that case. */
1742 gcc_assert (!node
->lto_file_data
);
1743 tree ctor
= DECL_INITIAL (decl
);
1744 inchash::hash hstate
;
1746 hstate
.add_int (456346417);
1747 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1748 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1749 add_expr (ctor
, hstate
);
1750 hash
= hstate
.end ();
1755 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1759 sem_variable::merge (sem_item
*alias_item
)
1761 gcc_assert (alias_item
->type
== VAR
);
1763 if (!sem_item::target_supports_symbol_aliases_p ())
1766 fprintf (dump_file
, "Not unifying; "
1767 "Symbol aliases are not supported by target\n\n");
1771 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1773 varpool_node
*original
= get_node ();
1774 varpool_node
*alias
= alias_var
->get_node ();
1775 bool original_discardable
= false;
1777 bool original_address_matters
= original
->address_matters_p ();
1778 bool alias_address_matters
= alias
->address_matters_p ();
1780 /* See if original is in a section that can be discarded if the main
1782 Also consider case where we have resolution info and we know that
1783 original's definition is not going to be used. In this case we can not
1784 create alias to original. */
1785 if (original
->can_be_discarded_p ()
1786 || (node
->resolution
!= LDPR_UNKNOWN
1787 && !decl_binds_to_current_def_p (node
->decl
)))
1788 original_discardable
= true;
1790 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1792 /* Constant pool machinery is not quite ready for aliases.
1793 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1794 For LTO merging does not happen that is an important missing feature.
1795 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1796 flag is dropped and non-local symbol name is assigned. */
1797 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1798 || DECL_IN_CONSTANT_POOL (original
->decl
))
1802 "Not unifying; constant pool variables.\n\n");
1806 /* Do not attempt to mix functions from different user sections;
1807 we do not know what user intends with those. */
1808 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1809 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1810 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1815 "original and alias are in different sections.\n\n");
1819 /* We can not merge if address comparsion metters. */
1820 if (original_address_matters
&& alias_address_matters
1821 && flag_merge_constants
< 2)
1826 "adress of original and alias may be compared.\n\n");
1829 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
1832 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1833 "across comdat group boundary\n\n");
1838 if (original_discardable
)
1841 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1842 "target is discardable\n\n");
1848 gcc_assert (!original
->alias
);
1849 gcc_assert (!alias
->alias
);
1851 alias
->analyzed
= false;
1853 DECL_INITIAL (alias
->decl
) = NULL
;
1854 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1856 alias
->need_bounds_init
= false;
1857 alias
->remove_all_references ();
1858 if (TREE_ADDRESSABLE (alias
->decl
))
1859 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1861 varpool_node::create_alias (alias_var
->decl
, decl
);
1862 alias
->resolve_alias (original
);
1865 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1871 /* Dump symbol to FILE. */
1874 sem_variable::dump_to_file (FILE *file
)
1878 print_node (file
, "", decl
, 0);
1879 fprintf (file
, "\n\n");
1882 unsigned int sem_item_optimizer::class_id
= 0;
1884 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1885 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1888 bitmap_obstack_initialize (&m_bmstack
);
1891 sem_item_optimizer::~sem_item_optimizer ()
1893 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1896 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1897 it
!= m_classes
.end (); ++it
)
1899 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1900 delete (*it
)->classes
[i
];
1902 (*it
)->classes
.release ();
1908 bitmap_obstack_release (&m_bmstack
);
1911 /* Write IPA ICF summary for symbols. */
1914 sem_item_optimizer::write_summary (void)
1916 unsigned int count
= 0;
1918 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1919 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1922 /* Calculate number of symbols to be serialized. */
1923 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1925 lsei_next_in_partition (&lsei
))
1927 symtab_node
*node
= lsei_node (lsei
);
1929 if (m_symtab_node_map
.get (node
))
1933 streamer_write_uhwi (ob
, count
);
1935 /* Process all of the symbols. */
1936 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1938 lsei_next_in_partition (&lsei
))
1940 symtab_node
*node
= lsei_node (lsei
);
1942 sem_item
**item
= m_symtab_node_map
.get (node
);
1946 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1947 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1949 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1953 streamer_write_char_stream (ob
->main_stream
, 0);
1954 produce_asm (ob
, NULL
);
1955 destroy_output_block (ob
);
1958 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1959 contains LEN bytes. */
1962 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1963 const char *data
, size_t len
)
1965 const lto_function_header
*header
=
1966 (const lto_function_header
*) data
;
1967 const int cfg_offset
= sizeof (lto_function_header
);
1968 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1969 const int string_offset
= main_offset
+ header
->main_size
;
1974 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1975 header
->main_size
, file_data
->mode_table
);
1978 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1979 header
->string_size
, vNULL
);
1981 count
= streamer_read_uhwi (&ib_main
);
1983 for (i
= 0; i
< count
; i
++)
1987 lto_symtab_encoder_t encoder
;
1989 index
= streamer_read_uhwi (&ib_main
);
1990 encoder
= file_data
->symtab_node_encoder
;
1991 node
= lto_symtab_encoder_deref (encoder
, index
);
1993 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1995 gcc_assert (node
->definition
);
1998 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1999 (void *) node
->decl
, node
->order
);
2001 if (is_a
<cgraph_node
*> (node
))
2003 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2005 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2009 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2011 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2015 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2017 lto_data_in_delete (data_in
);
2020 /* Read IPA IPA ICF summary for symbols. */
2023 sem_item_optimizer::read_summary (void)
2025 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2026 lto_file_decl_data
*file_data
;
2029 while ((file_data
= file_data_vec
[j
++]))
2032 const char *data
= lto_get_section_data (file_data
,
2033 LTO_section_ipa_icf
, NULL
, &len
);
2036 read_section (file_data
, data
, len
);
2040 /* Register callgraph and varpool hooks. */
2043 sem_item_optimizer::register_hooks (void)
2045 if (!m_cgraph_node_hooks
)
2046 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2047 (&sem_item_optimizer::cgraph_removal_hook
, this);
2049 if (!m_varpool_node_hooks
)
2050 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2051 (&sem_item_optimizer::varpool_removal_hook
, this);
2054 /* Unregister callgraph and varpool hooks. */
2057 sem_item_optimizer::unregister_hooks (void)
2059 if (m_cgraph_node_hooks
)
2060 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2062 if (m_varpool_node_hooks
)
2063 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2066 /* Adds a CLS to hashtable associated by hash value. */
2069 sem_item_optimizer::add_class (congruence_class
*cls
)
2071 gcc_assert (cls
->members
.length ());
2073 congruence_class_group
*group
= get_group_by_hash (
2074 cls
->members
[0]->get_hash (),
2075 cls
->members
[0]->type
);
2076 group
->classes
.safe_push (cls
);
2079 /* Gets a congruence class group based on given HASH value and TYPE. */
2081 congruence_class_group
*
2082 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2084 congruence_class_group
*item
= XNEW (congruence_class_group
);
2088 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2094 item
->classes
.create (1);
2101 /* Callgraph removal hook called for a NODE with a custom DATA. */
2104 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2106 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2107 optimizer
->remove_symtab_node (node
);
2110 /* Varpool removal hook called for a NODE with a custom DATA. */
2113 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2115 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2116 optimizer
->remove_symtab_node (node
);
2119 /* Remove symtab NODE triggered by symtab removal hooks. */
2122 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2124 gcc_assert (!m_classes
.elements());
2126 m_removed_items_set
.add (node
);
2130 sem_item_optimizer::remove_item (sem_item
*item
)
2132 if (m_symtab_node_map
.get (item
->node
))
2133 m_symtab_node_map
.remove (item
->node
);
2137 /* Removes all callgraph and varpool nodes that are marked by symtab
2141 sem_item_optimizer::filter_removed_items (void)
2143 auto_vec
<sem_item
*> filtered
;
2145 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2147 sem_item
*item
= m_items
[i
];
2149 if (m_removed_items_set
.contains (item
->node
))
2155 if (item
->type
== FUNC
)
2157 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2159 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2162 filtered
.safe_push (item
);
2166 if (!flag_ipa_icf_variables
)
2170 /* Filter out non-readonly variables. */
2171 tree decl
= item
->decl
;
2172 if (TREE_READONLY (decl
))
2173 filtered
.safe_push (item
);
2180 /* Clean-up of released semantic items. */
2183 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2184 m_items
.safe_push (filtered
[i
]);
2187 /* Optimizer entry point which returns true in case it processes
2188 a merge operation. True is returned if there's a merge operation
2192 sem_item_optimizer::execute (void)
2194 filter_removed_items ();
2195 unregister_hooks ();
2197 build_hash_based_classes ();
2200 fprintf (dump_file
, "Dump after hash based groups\n");
2201 dump_cong_classes ();
2203 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2204 m_items
[i
]->init_wpa ();
2208 subdivide_classes_by_equality (true);
2211 fprintf (dump_file
, "Dump after WPA based types groups\n");
2213 dump_cong_classes ();
2215 process_cong_reduction ();
2219 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2221 dump_cong_classes ();
2223 parse_nonsingleton_classes ();
2224 subdivide_classes_by_equality ();
2227 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2229 dump_cong_classes ();
2231 unsigned int prev_class_count
= m_classes_count
;
2233 process_cong_reduction ();
2234 dump_cong_classes ();
2236 bool merged_p
= merge_classes (prev_class_count
);
2238 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2239 symtab_node::dump_table (dump_file
);
2244 /* Function responsible for visiting all potential functions and
2245 read-only variables that can be merged. */
2248 sem_item_optimizer::parse_funcs_and_vars (void)
2252 if (flag_ipa_icf_functions
)
2253 FOR_EACH_DEFINED_FUNCTION (cnode
)
2255 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2258 m_items
.safe_push (f
);
2259 m_symtab_node_map
.put (cnode
, f
);
2262 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
2264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2265 f
->dump_to_file (dump_file
);
2268 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2271 varpool_node
*vnode
;
2273 if (flag_ipa_icf_variables
)
2274 FOR_EACH_DEFINED_VARIABLE (vnode
)
2276 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2280 m_items
.safe_push (v
);
2281 m_symtab_node_map
.put (vnode
, v
);
2286 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2289 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2291 item
->index_in_class
= cls
->members
.length ();
2292 cls
->members
.safe_push (item
);
2296 /* Congruence classes are built by hash value. */
2299 sem_item_optimizer::build_hash_based_classes (void)
2301 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2303 sem_item
*item
= m_items
[i
];
2305 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2308 if (!group
->classes
.length ())
2311 group
->classes
.safe_push (new congruence_class (class_id
++));
2314 add_item_to_class (group
->classes
[0], item
);
2318 /* Build references according to call graph. */
2321 sem_item_optimizer::build_graph (void)
2323 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2325 sem_item
*item
= m_items
[i
];
2326 m_symtab_node_map
.put (item
->node
, item
);
2329 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2331 sem_item
*item
= m_items
[i
];
2333 if (item
->type
== FUNC
)
2335 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2337 cgraph_edge
*e
= cnode
->callees
;
2340 sem_item
**slot
= m_symtab_node_map
.get
2341 (e
->callee
->ultimate_alias_target ());
2343 item
->add_reference (*slot
);
2349 ipa_ref
*ref
= NULL
;
2350 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2352 sem_item
**slot
= m_symtab_node_map
.get
2353 (ref
->referred
->ultimate_alias_target ());
2355 item
->add_reference (*slot
);
2360 /* Semantic items in classes having more than one element and initialized.
2361 In case of WPA, we load function body. */
2364 sem_item_optimizer::parse_nonsingleton_classes (void)
2366 unsigned int init_called_count
= 0;
2368 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2369 if (m_items
[i
]->cls
->members
.length () > 1)
2371 m_items
[i
]->init ();
2372 init_called_count
++;
2376 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2377 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2380 /* Equality function for semantic items is used to subdivide existing
2381 classes. If IN_WPA, fast equality function is invoked. */
2384 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2386 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2387 it
!= m_classes
.end (); ++it
)
2389 unsigned int class_count
= (*it
)->classes
.length ();
2391 for (unsigned i
= 0; i
< class_count
; i
++)
2393 congruence_class
*c
= (*it
)->classes
[i
];
2395 if (c
->members
.length() > 1)
2397 auto_vec
<sem_item
*> new_vector
;
2399 sem_item
*first
= c
->members
[0];
2400 new_vector
.safe_push (first
);
2402 unsigned class_split_first
= (*it
)->classes
.length ();
2404 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2406 sem_item
*item
= c
->members
[j
];
2408 bool equals
= in_wpa
? first
->equals_wpa (item
,
2409 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2412 new_vector
.safe_push (item
);
2415 bool integrated
= false;
2417 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2419 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2420 bool equals
= in_wpa
? x
->equals_wpa (item
,
2421 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2426 add_item_to_class ((*it
)->classes
[k
], item
);
2434 congruence_class
*c
= new congruence_class (class_id
++);
2436 add_item_to_class (c
, item
);
2438 (*it
)->classes
.safe_push (c
);
2443 // we replace newly created new_vector for the class we've just splitted
2444 c
->members
.release ();
2445 c
->members
.create (new_vector
.length ());
2447 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2448 add_item_to_class (c
, new_vector
[j
]);
2456 /* Subdivide classes by address references that members of the class
2457 reference. Example can be a pair of functions that have an address
2458 taken from a function. If these addresses are different the class
2462 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2464 unsigned newly_created_classes
= 0;
2466 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2467 it
!= m_classes
.end (); ++it
)
2469 unsigned int class_count
= (*it
)->classes
.length ();
2470 auto_vec
<congruence_class
*> new_classes
;
2472 for (unsigned i
= 0; i
< class_count
; i
++)
2474 congruence_class
*c
= (*it
)->classes
[i
];
2476 if (c
->members
.length() > 1)
2478 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2479 symbol_compare_hashmap_traits
> split_map
;
2481 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2483 sem_item
*source_node
= c
->members
[j
];
2485 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2487 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2488 gcc_checking_assert (slot
);
2490 slot
->safe_push (source_node
);
2493 /* If the map contains more than one key, we have to split the map
2495 if (split_map
.elements () != 1)
2497 bool first_class
= true;
2499 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2500 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2501 for (; it2
!= split_map
.end (); ++it2
)
2503 congruence_class
*new_cls
;
2504 new_cls
= new congruence_class (class_id
++);
2506 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2507 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2509 worklist_push (new_cls
);
2510 newly_created_classes
++;
2514 (*it
)->classes
[i
] = new_cls
;
2515 first_class
= false;
2519 new_classes
.safe_push (new_cls
);
2527 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2528 (*it
)->classes
.safe_push (new_classes
[i
]);
2531 return newly_created_classes
;
2534 /* Verify congruence classes if checking is enabled. */
2537 sem_item_optimizer::verify_classes (void)
2540 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2541 it
!= m_classes
.end (); ++it
)
2543 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2545 congruence_class
*cls
= (*it
)->classes
[i
];
2547 gcc_checking_assert (cls
);
2548 gcc_checking_assert (cls
->members
.length () > 0);
2550 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2552 sem_item
*item
= cls
->members
[j
];
2554 gcc_checking_assert (item
);
2555 gcc_checking_assert (item
->cls
== cls
);
2557 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2559 sem_usage_pair
*usage
= item
->usages
[k
];
2560 gcc_checking_assert (usage
->item
->index_in_class
<
2561 usage
->item
->cls
->members
.length ());
2569 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2570 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2571 but unused argument. */
2574 sem_item_optimizer::release_split_map (congruence_class
* const &,
2575 bitmap
const &b
, traverse_split_pair
*)
2584 /* Process split operation for a class given as pointer CLS_PTR,
2585 where bitmap B splits congruence class members. DATA is used
2586 as argument of split pair. */
2589 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2590 bitmap
const &b
, traverse_split_pair
*pair
)
2592 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2593 const congruence_class
*splitter_cls
= pair
->cls
;
2595 /* If counted bits are greater than zero and less than the number of members
2596 a group will be splitted. */
2597 unsigned popcount
= bitmap_count_bits (b
);
2599 if (popcount
> 0 && popcount
< cls
->members
.length ())
2601 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2603 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2605 int target
= bitmap_bit_p (b
, i
);
2606 congruence_class
*tc
= newclasses
[target
];
2608 add_item_to_class (tc
, cls
->members
[i
]);
2611 #ifdef ENABLE_CHECKING
2612 for (unsigned int i
= 0; i
< 2; i
++)
2613 gcc_checking_assert (newclasses
[i
]->members
.length ());
2616 if (splitter_cls
== cls
)
2617 optimizer
->splitter_class_removed
= true;
2619 /* Remove old class from worklist if presented. */
2620 bool in_worklist
= cls
->in_worklist
;
2623 cls
->in_worklist
= false;
2625 congruence_class_group g
;
2626 g
.hash
= cls
->members
[0]->get_hash ();
2627 g
.type
= cls
->members
[0]->type
;
2629 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2631 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2632 if (slot
->classes
[i
] == cls
)
2634 slot
->classes
.ordered_remove (i
);
2638 /* New class will be inserted and integrated to work list. */
2639 for (unsigned int i
= 0; i
< 2; i
++)
2640 optimizer
->add_class (newclasses
[i
]);
2642 /* Two classes replace one, so that increment just by one. */
2643 optimizer
->m_classes_count
++;
2645 /* If OLD class was presented in the worklist, we remove the class
2646 and replace it will both newly created classes. */
2648 for (unsigned int i
= 0; i
< 2; i
++)
2649 optimizer
->worklist_push (newclasses
[i
]);
2650 else /* Just smaller class is inserted. */
2652 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2653 newclasses
[1]->members
.length () ?
2655 optimizer
->worklist_push (newclasses
[smaller_index
]);
2658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2660 fprintf (dump_file
, " congruence class splitted:\n");
2661 cls
->dump (dump_file
, 4);
2663 fprintf (dump_file
, " newly created groups:\n");
2664 for (unsigned int i
= 0; i
< 2; i
++)
2665 newclasses
[i
]->dump (dump_file
, 4);
2668 /* Release class if not presented in work list. */
2677 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2678 Bitmap stack BMSTACK is used for bitmap allocation. */
2681 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2684 hash_map
<congruence_class
*, bitmap
> split_map
;
2686 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2688 sem_item
*item
= cls
->members
[i
];
2690 /* Iterate all usages that have INDEX as usage of the item. */
2691 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2693 sem_usage_pair
*usage
= item
->usages
[j
];
2695 if (usage
->index
!= index
)
2698 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2703 b
= BITMAP_ALLOC (&m_bmstack
);
2704 split_map
.put (usage
->item
->cls
, b
);
2710 gcc_checking_assert (usage
->item
->cls
);
2711 gcc_checking_assert (usage
->item
->index_in_class
<
2712 usage
->item
->cls
->members
.length ());
2715 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2719 traverse_split_pair pair
;
2720 pair
.optimizer
= this;
2723 splitter_class_removed
= false;
2725 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2727 /* Bitmap clean-up. */
2729 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2732 /* Every usage of a congruence class CLS is a candidate that can split the
2733 collection of classes. Bitmap stack BMSTACK is used for bitmap
2737 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2742 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2744 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2745 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2747 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2750 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2753 do_congruence_step_for_index (cls
, i
);
2755 if (splitter_class_removed
)
2759 BITMAP_FREE (usage
);
2762 /* Adds a newly created congruence class CLS to worklist. */
2765 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2767 /* Return if the class CLS is already presented in work list. */
2768 if (cls
->in_worklist
)
2771 cls
->in_worklist
= true;
2772 worklist
.push_back (cls
);
2775 /* Pops a class from worklist. */
2778 sem_item_optimizer::worklist_pop (void)
2780 congruence_class
*cls
;
2782 while (!worklist
.empty ())
2784 cls
= worklist
.front ();
2785 worklist
.pop_front ();
2786 if (cls
->in_worklist
)
2788 cls
->in_worklist
= false;
2794 /* Work list item was already intended to be removed.
2795 The only reason for doing it is to split a class.
2796 Thus, the class CLS is deleted. */
2804 /* Iterative congruence reduction function. */
2807 sem_item_optimizer::process_cong_reduction (void)
2809 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2810 it
!= m_classes
.end (); ++it
)
2811 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2812 if ((*it
)->classes
[i
]->is_class_used ())
2813 worklist_push ((*it
)->classes
[i
]);
2816 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2817 (unsigned long) worklist
.size ());
2819 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2820 fprintf (dump_file
, "Congruence class reduction\n");
2822 congruence_class
*cls
;
2824 /* Process complete congruence reduction. */
2825 while ((cls
= worklist_pop ()) != NULL
)
2826 do_congruence_step (cls
);
2828 /* Subdivide newly created classes according to references. */
2829 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2832 fprintf (dump_file
, "Address reference subdivision created: %u "
2833 "new classes.\n", new_classes
);
2836 /* Debug function prints all informations about congruence classes. */
2839 sem_item_optimizer::dump_cong_classes (void)
2845 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2846 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2848 /* Histogram calculation. */
2849 unsigned int max_index
= 0;
2850 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2852 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2853 it
!= m_classes
.end (); ++it
)
2855 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2857 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2865 "Class size histogram [num of members]: number of classe number of classess\n");
2867 for (unsigned int i
= 0; i
<= max_index
; i
++)
2869 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2871 fprintf (dump_file
, "\n\n");
2874 if (dump_flags
& TDF_DETAILS
)
2875 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2876 it
!= m_classes
.end (); ++it
)
2878 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2880 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2882 (*it
)->classes
[i
]->dump (dump_file
, 4);
2884 if(i
< (*it
)->classes
.length () - 1)
2885 fprintf (dump_file
, " ");
2892 /* After reduction is done, we can declare all items in a group
2893 to be equal. PREV_CLASS_COUNT is start number of classes
2894 before reduction. True is returned if there's a merge operation
2898 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2900 unsigned int item_count
= m_items
.length ();
2901 unsigned int class_count
= m_classes_count
;
2902 unsigned int equal_items
= item_count
- class_count
;
2904 unsigned int non_singular_classes_count
= 0;
2905 unsigned int non_singular_classes_sum
= 0;
2907 bool merged_p
= false;
2909 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2910 it
!= m_classes
.end (); ++it
)
2911 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2913 congruence_class
*c
= (*it
)->classes
[i
];
2914 if (c
->members
.length () > 1)
2916 non_singular_classes_count
++;
2917 non_singular_classes_sum
+= c
->members
.length ();
2923 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2924 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2925 prev_class_count
, class_count
);
2926 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2927 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2928 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2929 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2930 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2931 non_singular_classes_count
: 0.0f
,
2932 non_singular_classes_count
);
2933 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2934 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2935 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2938 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2939 it
!= m_classes
.end (); ++it
)
2940 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2942 congruence_class
*c
= (*it
)->classes
[i
];
2944 if (c
->members
.length () == 1)
2947 gcc_assert (c
->members
.length ());
2949 sem_item
*source
= c
->members
[0];
2951 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2953 sem_item
*alias
= c
->members
[j
];
2957 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2958 source
->name (), alias
->name ());
2959 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2960 source
->asm_name (), alias
->asm_name ());
2963 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2967 "Merge operation is skipped due to no_icf "
2973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2975 source
->dump_to_file (dump_file
);
2976 alias
->dump_to_file (dump_file
);
2979 merged_p
|= source
->merge (alias
);
2986 /* Dump function prints all class members to a FILE with an INDENT. */
2989 congruence_class::dump (FILE *file
, unsigned int indent
) const
2991 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2992 id
, members
[0]->get_hash (), members
.length ());
2994 FPUTS_SPACES (file
, indent
+ 2, "");
2995 for (unsigned i
= 0; i
< members
.length (); i
++)
2996 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2997 members
[i
]->node
->order
);
2999 fprintf (file
, "\n");
3002 /* Returns true if there's a member that is used from another group. */
3005 congruence_class::is_class_used (void)
3007 for (unsigned int i
= 0; i
< members
.length (); i
++)
3008 if (members
[i
]->usages
.length ())
3014 /* Initialization and computation of symtab node hash, there data
3015 are propagated later on. */
3017 static sem_item_optimizer
*optimizer
= NULL
;
3019 /* Generate pass summary for IPA ICF pass. */
3022 ipa_icf_generate_summary (void)
3025 optimizer
= new sem_item_optimizer ();
3027 optimizer
->register_hooks ();
3028 optimizer
->parse_funcs_and_vars ();
3031 /* Write pass summary for IPA ICF pass. */
3034 ipa_icf_write_summary (void)
3036 gcc_assert (optimizer
);
3038 optimizer
->write_summary ();
3041 /* Read pass summary for IPA ICF pass. */
3044 ipa_icf_read_summary (void)
3047 optimizer
= new sem_item_optimizer ();
3049 optimizer
->read_summary ();
3050 optimizer
->register_hooks ();
3053 /* Semantic equality exection function. */
3056 ipa_icf_driver (void)
3058 gcc_assert (optimizer
);
3060 bool merged_p
= optimizer
->execute ();
3065 return merged_p
? TODO_remove_functions
: 0;
3068 const pass_data pass_data_ipa_icf
=
3070 IPA_PASS
, /* type */
3072 OPTGROUP_IPA
, /* optinfo_flags */
3073 TV_IPA_ICF
, /* tv_id */
3074 0, /* properties_required */
3075 0, /* properties_provided */
3076 0, /* properties_destroyed */
3077 0, /* todo_flags_start */
3078 0, /* todo_flags_finish */
3081 class pass_ipa_icf
: public ipa_opt_pass_d
3084 pass_ipa_icf (gcc::context
*ctxt
)
3085 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3086 ipa_icf_generate_summary
, /* generate_summary */
3087 ipa_icf_write_summary
, /* write_summary */
3088 ipa_icf_read_summary
, /* read_summary */
3090 write_optimization_summary */
3092 read_optimization_summary */
3093 NULL
, /* stmt_fixup */
3094 0, /* function_transform_todo_flags_start */
3095 NULL
, /* function_transform */
3096 NULL
) /* variable_transform */
3099 /* opt_pass methods: */
3100 virtual bool gate (function
*)
3102 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3105 virtual unsigned int execute (function
*)
3107 return ipa_icf_driver();
3109 }; // class pass_ipa_icf
3111 } // ipa_icf namespace
3114 make_pass_ipa_icf (gcc::context
*ctxt
)
3116 return new ipa_icf::pass_ipa_icf (ctxt
);