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 node
->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
]->node
->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 /* Update hash by address sensitive references. We iterate over all
561 sensitive references (address_matters_p) and we hash ultime alias
562 target of these nodes, which can improve a semantic item hash.
563 TODO: stronger SCC based hashing would be desirable here. */
566 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
567 sem_item
*> &m_symtab_node_map
)
569 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
573 inchash::hash
hstate (hash
);
574 for (unsigned i
= 0; i
< node
->num_references (); i
++)
576 ref
= node
->iterate_reference (i
, ref
);
577 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
578 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
581 if (is_a
<cgraph_node
*> (node
))
583 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
586 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
588 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
592 hash
= hstate
.end ();
595 /* Update hash by computed local hash values taken from different
599 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
600 sem_item
*> &m_symtab_node_map
)
602 inchash::hash
state (hash
);
603 for (unsigned j
= 0; j
< node
->num_references (); j
++)
606 ref
= node
->iterate_reference (j
, ref
);
607 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
609 state
.merge_hash ((*result
)->hash
);
614 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
617 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
619 state
.merge_hash ((*result
)->hash
);
623 global_hash
= state
.end ();
626 /* Returns true if the item equals to ITEM given as argument. */
629 sem_function::equals (sem_item
*item
,
630 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
632 gcc_assert (item
->type
== FUNC
);
633 bool eq
= equals_private (item
, ignored_nodes
);
635 if (m_checker
!= NULL
)
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
644 xstrdup_for_dump (node
->name()),
645 xstrdup_for_dump (item
->node
->name ()),
648 xstrdup_for_dump (node
->asm_name ()),
649 xstrdup_for_dump (item
->node
->asm_name ()),
650 eq
? "true" : "false");
655 /* Processes function equality comparison. */
658 sem_function::equals_private (sem_item
*item
,
659 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
661 if (item
->type
!= FUNC
)
664 basic_block bb1
, bb2
;
666 edge_iterator ei1
, ei2
;
670 m_compared_func
= static_cast<sem_function
*> (item
);
672 gcc_assert (decl
!= item
->decl
);
674 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
675 || edge_count
!= m_compared_func
->edge_count
676 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
677 return return_false ();
679 if (!equals_wpa (item
, ignored_nodes
))
682 /* Checking function arguments. */
683 tree decl1
= DECL_ATTRIBUTES (decl
);
684 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
686 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
687 compare_polymorphic_p (),
690 &m_compared_func
->refs_set
);
694 return return_false ();
696 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
697 return return_false ();
699 tree attr_value1
= TREE_VALUE (decl1
);
700 tree attr_value2
= TREE_VALUE (decl2
);
702 if (attr_value1
&& attr_value2
)
704 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
705 TREE_VALUE (attr_value2
));
707 return return_false_with_msg ("attribute values are different");
709 else if (!attr_value1
&& !attr_value2
)
712 return return_false ();
714 decl1
= TREE_CHAIN (decl1
);
715 decl2
= TREE_CHAIN (decl2
);
719 return return_false();
721 for (arg1
= DECL_ARGUMENTS (decl
),
722 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
723 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
724 if (!m_checker
->compare_decl (arg1
, arg2
))
725 return return_false ();
727 /* Fill-up label dictionary. */
728 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
730 m_checker
->parse_labels (bb_sorted
[i
]);
731 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
734 /* Checking all basic blocks. */
735 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
736 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
737 return return_false();
739 dump_message ("All BBs are equal\n");
741 auto_vec
<int> bb_dict
;
743 /* Basic block edges check. */
744 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
746 bb1
= bb_sorted
[i
]->bb
;
747 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
749 ei2
= ei_start (bb2
->preds
);
751 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
755 if (e1
->flags
!= e2
->flags
)
756 return return_false_with_msg ("flags comparison returns false");
758 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
759 return return_false_with_msg ("edge comparison returns false");
761 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
762 return return_false_with_msg ("BB comparison returns false");
764 if (!m_checker
->compare_edge (e1
, e2
))
765 return return_false_with_msg ("edge comparison returns false");
771 /* Basic block PHI nodes comparison. */
772 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
773 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
774 return return_false_with_msg ("PHI node comparison returns false");
779 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
780 Helper for call_for_symbol_thunks_and_aliases. */
783 set_local (cgraph_node
*node
, void *data
)
785 node
->local
.local
= data
!= NULL
;
789 /* TREE_ADDRESSABLE of NODE to true.
790 Helper for call_for_symbol_thunks_and_aliases. */
793 set_addressable (varpool_node
*node
, void *)
795 TREE_ADDRESSABLE (node
->decl
) = 1;
799 /* Clear DECL_RTL of NODE.
800 Helper for call_for_symbol_thunks_and_aliases. */
803 clear_decl_rtl (symtab_node
*node
, void *)
805 SET_DECL_RTL (node
->decl
, NULL
);
809 /* Redirect all callers of N and its aliases to TO. Remove aliases if
810 possible. Return number of redirections made. */
813 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
817 cgraph_edge
*e
= n
->callers
;
821 /* Redirecting thunks to interposable symbols or symbols in other sections
822 may not be supported by target output code. Play safe for now and
823 punt on redirection. */
824 if (!e
->caller
->thunk
.thunk_p
)
826 struct cgraph_edge
*nexte
= e
->next_caller
;
827 e
->redirect_callee (to
);
834 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
836 bool removed
= false;
837 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
839 if ((DECL_COMDAT_GROUP (n
->decl
)
840 && (DECL_COMDAT_GROUP (n
->decl
)
841 == DECL_COMDAT_GROUP (n_alias
->decl
)))
842 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
843 && n
->get_availability () > AVAIL_INTERPOSABLE
))
845 nredirected
+= redirect_all_callers (n_alias
, to
);
846 if (n_alias
->can_remove_if_no_direct_calls_p ()
847 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
849 && !n_alias
->has_aliases_p ())
858 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
862 sem_function::merge (sem_item
*alias_item
)
864 gcc_assert (alias_item
->type
== FUNC
);
866 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
868 cgraph_node
*original
= get_node ();
869 cgraph_node
*local_original
= NULL
;
870 cgraph_node
*alias
= alias_func
->get_node ();
872 bool create_wrapper
= false;
873 bool create_alias
= false;
874 bool redirect_callers
= false;
877 bool original_discardable
= false;
878 bool original_discarded
= false;
880 bool original_address_matters
= original
->address_matters_p ();
881 bool alias_address_matters
= alias
->address_matters_p ();
883 if (DECL_EXTERNAL (alias
->decl
))
886 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
890 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
891 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
896 "DECL_NO_INLINE_WARNING mismatch.\n\n");
900 /* Do not attempt to mix functions from different user sections;
901 we do not know what user intends with those. */
902 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
903 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
904 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
909 "original and alias are in different sections.\n\n");
913 /* See if original is in a section that can be discarded if the main
914 symbol is not used. */
916 if (original
->can_be_discarded_p ())
917 original_discardable
= true;
918 /* Also consider case where we have resolution info and we know that
919 original's definition is not going to be used. In this case we can not
920 create alias to original. */
921 if (node
->resolution
!= LDPR_UNKNOWN
922 && !decl_binds_to_current_def_p (node
->decl
))
923 original_discardable
= original_discarded
= true;
925 /* Creating a symtab alias is the optimal way to merge.
926 It however can not be used in the following cases:
928 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
929 2) if ORIGINAL is in a section that may be discarded by linker or if
930 it is an external functions where we can not create an alias
931 (ORIGINAL_DISCARDABLE)
932 3) if target do not support symbol aliases.
933 4) original and alias lie in different comdat groups.
935 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
936 and/or redirect all callers from ALIAS to ORIGINAL. */
937 if ((original_address_matters
&& alias_address_matters
)
938 || (original_discardable
939 && (!DECL_COMDAT_GROUP (alias
->decl
)
940 || (DECL_COMDAT_GROUP (alias
->decl
)
941 != DECL_COMDAT_GROUP (original
->decl
))))
942 || original_discarded
943 || !sem_item::target_supports_symbol_aliases_p ()
944 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
946 /* First see if we can produce wrapper. */
948 /* Do not turn function in one comdat group into wrapper to another
949 comdat group. Other compiler producing the body of the
950 another comdat group may make opossite decision and with unfortunate
951 linker choices this may close a loop. */
952 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
953 && (DECL_COMDAT_GROUP (alias
->decl
)
954 != DECL_COMDAT_GROUP (original
->decl
)))
958 "Wrapper cannot be created because of COMDAT\n");
960 else if (DECL_STATIC_CHAIN (alias
->decl
))
964 "Can not create wrapper of nested functions.\n");
966 /* TODO: We can also deal with variadic functions never calling
968 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
972 "can not create wrapper of stdarg function.\n");
974 else if (inline_summaries
975 && inline_summaries
->get (alias
)->self_size
<= 2)
978 fprintf (dump_file
, "Wrapper creation is not "
979 "profitable (function is too small).\n");
981 /* If user paid attention to mark function noinline, assume it is
982 somewhat special and do not try to turn it into a wrapper that can
983 not be undone by inliner. */
984 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
987 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
990 create_wrapper
= true;
992 /* We can redirect local calls in the case both alias and orignal
993 are not interposable. */
995 = alias
->get_availability () > AVAIL_INTERPOSABLE
996 && original
->get_availability () > AVAIL_INTERPOSABLE
997 && !alias
->instrumented_version
;
999 if (!redirect_callers
&& !create_wrapper
)
1002 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1003 "produce wrapper\n\n");
1007 /* Work out the symbol the wrapper should call.
1008 If ORIGINAL is interposable, we need to call a local alias.
1009 Also produce local alias (if possible) as an optimization.
1011 Local aliases can not be created inside comdat groups because that
1012 prevents inlining. */
1013 if (!original_discardable
&& !original
->get_comdat_group ())
1016 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1018 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1019 local_original
= original
;
1021 /* If we can not use local alias, fallback to the original
1023 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1024 local_original
= original
;
1026 /* If original is COMDAT local, we can not really redirect calls outside
1027 of its comdat group to it. */
1028 if (original
->comdat_local_p ())
1029 redirect_callers
= false;
1030 if (!local_original
)
1033 fprintf (dump_file
, "Not unifying; "
1034 "can not produce local alias.\n\n");
1038 if (!redirect_callers
&& !create_wrapper
)
1041 fprintf (dump_file
, "Not unifying; "
1042 "can not redirect callers nor produce a wrapper\n\n");
1046 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1048 && !alias
->can_remove_if_no_direct_calls_p ())
1051 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1052 "function has other uses than direct calls\n\n");
1057 create_alias
= true;
1059 if (redirect_callers
)
1061 int nredirected
= redirect_all_callers (alias
, local_original
);
1065 alias
->icf_merged
= true;
1066 local_original
->icf_merged
= true;
1068 if (dump_file
&& nredirected
)
1069 fprintf (dump_file
, "%i local calls have been "
1070 "redirected.\n", nredirected
);
1073 /* If all callers was redirected, do not produce wrapper. */
1074 if (alias
->can_remove_if_no_direct_calls_p ()
1075 && !alias
->has_aliases_p ())
1077 create_wrapper
= false;
1080 gcc_assert (!create_alias
);
1082 else if (create_alias
)
1084 alias
->icf_merged
= true;
1086 /* Remove the function's body. */
1087 ipa_merge_profiles (original
, alias
);
1088 alias
->release_body (true);
1090 /* Notice global symbol possibly produced RTL. */
1091 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1094 /* Create the alias. */
1095 cgraph_node::create_alias (alias_func
->decl
, decl
);
1096 alias
->resolve_alias (original
);
1098 original
->call_for_symbol_thunks_and_aliases
1099 (set_local
, (void *)(size_t) original
->local_p (), true);
1102 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1106 gcc_assert (!create_alias
);
1107 alias
->icf_merged
= true;
1108 local_original
->icf_merged
= true;
1110 ipa_merge_profiles (local_original
, alias
, true);
1111 alias
->create_wrapper (local_original
);
1114 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1117 /* It's possible that redirection can hit thunks that block
1118 redirection opportunities. */
1119 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1120 original
->icf_merged
= true;
1122 /* Inform the inliner about cross-module merging. */
1123 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1124 && original
->lto_file_data
!= alias
->lto_file_data
)
1125 local_original
->merged
= original
->merged
= true;
1129 ipa_merge_profiles (original
, alias
);
1130 alias
->release_body ();
1132 alias
->body_removed
= true;
1133 alias
->icf_merged
= true;
1135 fprintf (dump_file
, "Unified; Function body was removed.\n");
1141 /* Semantic item initialization function. */
1144 sem_function::init (void)
1147 get_node ()->get_untransformed_body ();
1149 tree fndecl
= node
->decl
;
1150 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1153 gcc_assert (SSANAMES (func
));
1155 ssa_names_size
= SSANAMES (func
)->length ();
1159 region_tree
= func
->eh
->region_tree
;
1161 /* iterating all function arguments. */
1162 arg_count
= count_formal_params (fndecl
);
1164 edge_count
= n_edges_for_fn (func
);
1165 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1167 inchash::hash hstate
;
1170 FOR_EACH_BB_FN (bb
, func
)
1172 unsigned nondbg_stmt_count
= 0;
1175 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1177 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1180 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1183 gimple stmt
= gsi_stmt (gsi
);
1185 if (gimple_code (stmt
) != GIMPLE_DEBUG
1186 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1188 hash_stmt (stmt
, hstate
);
1189 nondbg_stmt_count
++;
1193 gcode_hash
= hstate
.end ();
1194 bb_sizes
.safe_push (nondbg_stmt_count
);
1196 /* Inserting basic block to hash table. */
1197 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1198 EDGE_COUNT (bb
->preds
)
1199 + EDGE_COUNT (bb
->succs
));
1201 bb_sorted
.safe_push (semantic_bb
);
1207 /* Accumulate to HSTATE a hash of expression EXP.
1208 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1209 and DECL equality classes. */
1212 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1214 if (exp
== NULL_TREE
)
1216 hstate
.merge_hash (0);
1220 /* Handled component can be matched in a cureful way proving equivalence
1221 even if they syntactically differ. Just skip them. */
1223 while (handled_component_p (exp
))
1224 exp
= TREE_OPERAND (exp
, 0);
1226 enum tree_code code
= TREE_CODE (exp
);
1227 hstate
.add_int (code
);
1231 /* Use inchash::add_expr for everything that is LTO stable. */
1239 inchash::add_expr (exp
, hstate
);
1243 unsigned HOST_WIDE_INT idx
;
1246 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1248 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1250 add_expr (value
, hstate
);
1255 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1261 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1264 case POINTER_PLUS_EXPR
:
1267 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1268 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1272 inchash::hash one
, two
;
1273 add_expr (TREE_OPERAND (exp
, 0), one
);
1274 add_expr (TREE_OPERAND (exp
, 1), two
);
1275 hstate
.add_commutative (one
, two
);
1279 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1280 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1286 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1289 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1291 enum gimple_code code
= gimple_code (stmt
);
1293 hstate
.add_int (code
);
1298 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1299 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1301 inchash::hash one
, two
;
1303 add_expr (gimple_assign_rhs1 (stmt
), one
);
1304 add_expr (gimple_assign_rhs2 (stmt
), two
);
1305 hstate
.add_commutative (one
, two
);
1306 add_expr (gimple_assign_lhs (stmt
), hstate
);
1309 /* ... fall through ... */
1315 /* All these statements are equivalent if their operands are. */
1316 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1317 add_expr (gimple_op (stmt
, i
), hstate
);
1324 /* Return true if polymorphic comparison must be processed. */
1327 sem_function::compare_polymorphic_p (void)
1329 struct cgraph_edge
*e
;
1331 if (!opt_for_fn (decl
, flag_devirtualize
))
1333 if (get_node ()->indirect_calls
!= NULL
1334 || m_compared_func
->get_node ()->indirect_calls
!= NULL
)
1336 /* TODO: We can do simple propagation determining what calls may lead to
1337 a polymorphic call. */
1338 for (e
= m_compared_func
->get_node ()->callees
; e
; e
= e
->next_callee
)
1339 if (e
->callee
->definition
1340 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1345 /* For a given call graph NODE, the function constructs new
1346 semantic function item. */
1349 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1351 tree fndecl
= node
->decl
;
1352 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1354 /* TODO: add support for thunks. */
1356 if (!func
|| !node
->has_gimple_body_p ())
1359 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1362 sem_function
*f
= new sem_function (node
, 0, stack
);
1369 /* Parses function arguments and result type. */
1372 sem_function::parse_tree_args (void)
1376 if (arg_types
.exists ())
1377 arg_types
.release ();
1379 arg_types
.create (4);
1380 tree fnargs
= DECL_ARGUMENTS (decl
);
1382 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1383 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1385 /* Function result type. */
1386 result
= DECL_RESULT (decl
);
1387 result_type
= result
? TREE_TYPE (result
) : NULL
;
1389 /* During WPA, we can get arguments by following method. */
1392 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1393 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1394 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1396 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1400 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1401 return true if phi nodes are semantically equivalent in these blocks . */
1404 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1406 gphi_iterator si1
, si2
;
1408 unsigned size1
, size2
, i
;
1412 gcc_assert (bb1
!= NULL
);
1413 gcc_assert (bb2
!= NULL
);
1415 si2
= gsi_start_phis (bb2
);
1416 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1419 gsi_next_nonvirtual_phi (&si1
);
1420 gsi_next_nonvirtual_phi (&si2
);
1422 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1425 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1426 return return_false();
1431 tree phi_result1
= gimple_phi_result (phi1
);
1432 tree phi_result2
= gimple_phi_result (phi2
);
1434 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1435 return return_false_with_msg ("PHI results are different");
1437 size1
= gimple_phi_num_args (phi1
);
1438 size2
= gimple_phi_num_args (phi2
);
1441 return return_false ();
1443 for (i
= 0; i
< size1
; ++i
)
1445 t1
= gimple_phi_arg (phi1
, i
)->def
;
1446 t2
= gimple_phi_arg (phi2
, i
)->def
;
1448 if (!m_checker
->compare_operand (t1
, t2
))
1449 return return_false ();
1451 e1
= gimple_phi_arg_edge (phi1
, i
);
1452 e2
= gimple_phi_arg_edge (phi2
, i
);
1454 if (!m_checker
->compare_edge (e1
, e2
))
1455 return return_false ();
1464 /* Returns true if tree T can be compared as a handled component. */
1467 sem_function::icf_handled_component_p (tree t
)
1469 tree_code tc
= TREE_CODE (t
);
1471 return ((handled_component_p (t
))
1472 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1473 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1476 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1477 corresponds to TARGET. */
1480 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1485 if (bb_dict
->length () <= (unsigned)source
)
1486 bb_dict
->safe_grow_cleared (source
+ 1);
1488 if ((*bb_dict
)[source
] == 0)
1490 (*bb_dict
)[source
] = target
;
1494 return (*bb_dict
)[source
] == target
;
1498 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1500 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1504 /* Constructor based on varpool node _NODE with computed hash _HASH.
1505 Bitmap STACK is used for memory allocation. */
1507 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1508 bitmap_obstack
*stack
): sem_item(VAR
,
1511 gcc_checking_assert (node
);
1512 gcc_checking_assert (get_node ());
1515 /* Fast equality function based on knowledge known in WPA. */
1518 sem_variable::equals_wpa (sem_item
*item
,
1519 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1521 gcc_assert (item
->type
== VAR
);
1523 if (node
->num_references () != item
->node
->num_references ())
1524 return return_false_with_msg ("different number of references");
1526 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1527 return return_false_with_msg ("TLS model");
1529 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1530 return return_false_with_msg ("alignment mismatch");
1532 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1533 return return_false_with_msg ("Virtual flag mismatch");
1535 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1536 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1537 || !operand_equal_p (DECL_SIZE (decl
),
1538 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1539 return return_false_with_msg ("size mismatch");
1541 /* Do not attempt to mix data from different user sections;
1542 we do not know what user intends with those. */
1543 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1544 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1545 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1546 return return_false_with_msg ("user section mismatch");
1548 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1549 return return_false_with_msg ("text section");
1551 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1552 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1554 item
->node
->iterate_reference (i
, ref2
);
1556 if (!compare_cgraph_references (ignored_nodes
,
1557 ref
->referred
, ref2
->referred
,
1558 ref
->address_matters_p ()))
1561 /* DECL_FINAL_P flag on methods referred by virtual tables is used
1562 to decide on completeness possible_polymorphic_call_targets lists
1563 and therefore it must match. */
1564 if ((DECL_VIRTUAL_P (decl
) || DECL_VIRTUAL_P (item
->decl
))
1565 && (DECL_VIRTUAL_P (ref
->referred
->decl
)
1566 || DECL_VIRTUAL_P (ref2
->referred
->decl
))
1567 && ((DECL_VIRTUAL_P (ref
->referred
->decl
)
1568 != DECL_VIRTUAL_P (ref2
->referred
->decl
))
1569 || (DECL_FINAL_P (ref
->referred
->decl
)
1570 != DECL_FINAL_P (ref2
->referred
->decl
))))
1571 return return_false_with_msg ("virtual or final flag mismatch");
1577 /* Returns true if the item equals to ITEM given as argument. */
1579 /* Returns true if the item equals to ITEM given as argument. */
1582 sem_variable::equals (sem_item
*item
,
1583 hash_map
<symtab_node
*, sem_item
*> &)
1585 gcc_assert (item
->type
== VAR
);
1588 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1589 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1590 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1591 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1593 /* As seen in PR ipa/65303 we have to compare variables types. */
1594 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1595 TREE_TYPE (item
->decl
)))
1596 return return_false_with_msg ("variables types are different");
1598 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1599 DECL_INITIAL (item
->node
->decl
));
1600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1602 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1603 xstrdup_for_dump (node
->name()),
1604 xstrdup_for_dump (item
->node
->name ()),
1605 node
->order
, item
->node
->order
,
1606 xstrdup_for_dump (node
->asm_name ()),
1607 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1612 /* Compares trees T1 and T2 for semantic equality. */
1615 sem_variable::equals (tree t1
, tree t2
)
1618 return return_with_debug (t1
== t2
);
1621 tree_code tc1
= TREE_CODE (t1
);
1622 tree_code tc2
= TREE_CODE (t2
);
1625 return return_false_with_msg ("TREE_CODE mismatch");
1631 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1632 unsigned HOST_WIDE_INT idx
;
1634 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1635 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1636 return return_false_with_msg ("constructor type mismatch");
1638 if (typecode
== ARRAY_TYPE
)
1640 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1641 /* For arrays, check that the sizes all match. */
1642 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1644 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1645 return return_false_with_msg ("constructor array size mismatch");
1647 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1649 return return_false_with_msg ("constructor type incompatible");
1651 v1
= CONSTRUCTOR_ELTS (t1
);
1652 v2
= CONSTRUCTOR_ELTS (t2
);
1653 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1654 return return_false_with_msg ("constructor number of elts mismatch");
1656 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1658 constructor_elt
*c1
= &(*v1
)[idx
];
1659 constructor_elt
*c2
= &(*v2
)[idx
];
1661 /* Check that each value is the same... */
1662 if (!sem_variable::equals (c1
->value
, c2
->value
))
1664 /* ... and that they apply to the same fields! */
1665 if (!sem_variable::equals (c1
->index
, c2
->index
))
1672 tree x1
= TREE_OPERAND (t1
, 0);
1673 tree x2
= TREE_OPERAND (t2
, 0);
1674 tree y1
= TREE_OPERAND (t1
, 1);
1675 tree y2
= TREE_OPERAND (t2
, 1);
1677 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1678 return return_false ();
1680 /* Type of the offset on MEM_REF does not matter. */
1681 return return_with_debug (sem_variable::equals (x1
, x2
)
1682 && wi::to_offset (y1
)
1683 == wi::to_offset (y2
));
1688 tree op1
= TREE_OPERAND (t1
, 0);
1689 tree op2
= TREE_OPERAND (t2
, 0);
1690 return sem_variable::equals (op1
, op2
);
1692 /* References to other vars/decls are compared using ipa-ref. */
1695 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1697 return return_false_with_msg ("Declaration mismatch");
1699 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1700 need to process its VAR/FUNCTION references without relying on ipa-ref
1704 return return_false_with_msg ("Declaration mismatch");
1706 /* Integer constants are the same only if the same width of type. */
1707 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1708 return return_false_with_msg ("INTEGER_CST precision mismatch");
1709 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1710 return return_false_with_msg ("INTEGER_CST mode mismatch");
1711 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1713 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1714 return return_false_with_msg ("STRING_CST mode mismatch");
1715 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1716 return return_false_with_msg ("STRING_CST length mismatch");
1717 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1718 TREE_STRING_LENGTH (t1
)))
1719 return return_false_with_msg ("STRING_CST mismatch");
1722 /* Fixed constants are the same only if the same width of type. */
1723 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1724 return return_false_with_msg ("FIXED_CST precision mismatch");
1726 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1727 TREE_FIXED_CST (t2
)));
1729 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1730 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1732 /* Real constants are the same only if the same width of type. */
1733 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1734 return return_false_with_msg ("REAL_CST precision mismatch");
1735 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1736 TREE_REAL_CST (t2
)));
1741 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1742 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1744 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1745 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1746 VECTOR_CST_ELT (t2
, i
)))
1752 case ARRAY_RANGE_REF
:
1754 tree x1
= TREE_OPERAND (t1
, 0);
1755 tree x2
= TREE_OPERAND (t2
, 0);
1756 tree y1
= TREE_OPERAND (t1
, 1);
1757 tree y2
= TREE_OPERAND (t2
, 1);
1759 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1761 if (!sem_variable::equals (array_ref_low_bound (t1
),
1762 array_ref_low_bound (t2
)))
1764 if (!sem_variable::equals (array_ref_element_size (t1
),
1765 array_ref_element_size (t2
)))
1771 case POINTER_PLUS_EXPR
:
1776 tree x1
= TREE_OPERAND (t1
, 0);
1777 tree x2
= TREE_OPERAND (t2
, 0);
1778 tree y1
= TREE_OPERAND (t1
, 1);
1779 tree y2
= TREE_OPERAND (t2
, 1);
1781 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1785 case VIEW_CONVERT_EXPR
:
1786 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1787 return return_false ();
1788 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1790 return return_false_with_msg ("ERROR_MARK");
1792 return return_false_with_msg ("Unknown TREE code reached");
1796 /* Parser function that visits a varpool NODE. */
1799 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1801 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1805 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1812 /* References independent hash function. */
1815 sem_variable::get_hash (void)
1820 /* All WPA streamed in symbols should have their hashes computed at compile
1821 time. At this point, the constructor may not be in memory at all.
1822 DECL_INITIAL (decl) would be error_mark_node in that case. */
1823 gcc_assert (!node
->lto_file_data
);
1824 tree ctor
= DECL_INITIAL (decl
);
1825 inchash::hash hstate
;
1827 hstate
.add_int (456346417);
1828 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1829 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1830 add_expr (ctor
, hstate
);
1831 hash
= hstate
.end ();
1836 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1840 sem_variable::merge (sem_item
*alias_item
)
1842 gcc_assert (alias_item
->type
== VAR
);
1844 if (!sem_item::target_supports_symbol_aliases_p ())
1847 fprintf (dump_file
, "Not unifying; "
1848 "Symbol aliases are not supported by target\n\n");
1852 if (DECL_EXTERNAL (alias_item
->decl
))
1855 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1859 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1861 varpool_node
*original
= get_node ();
1862 varpool_node
*alias
= alias_var
->get_node ();
1863 bool original_discardable
= false;
1865 bool original_address_matters
= original
->address_matters_p ();
1866 bool alias_address_matters
= alias
->address_matters_p ();
1868 /* See if original is in a section that can be discarded if the main
1870 Also consider case where we have resolution info and we know that
1871 original's definition is not going to be used. In this case we can not
1872 create alias to original. */
1873 if (original
->can_be_discarded_p ()
1874 || (node
->resolution
!= LDPR_UNKNOWN
1875 && !decl_binds_to_current_def_p (node
->decl
)))
1876 original_discardable
= true;
1878 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1880 /* Constant pool machinery is not quite ready for aliases.
1881 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1882 For LTO merging does not happen that is an important missing feature.
1883 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1884 flag is dropped and non-local symbol name is assigned. */
1885 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1886 || DECL_IN_CONSTANT_POOL (original
->decl
))
1890 "Not unifying; constant pool variables.\n\n");
1894 /* Do not attempt to mix functions from different user sections;
1895 we do not know what user intends with those. */
1896 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1897 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1898 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1903 "original and alias are in different sections.\n\n");
1907 /* We can not merge if address comparsion metters. */
1908 if (original_address_matters
&& alias_address_matters
1909 && flag_merge_constants
< 2)
1914 "adress of original and alias may be compared.\n\n");
1917 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
1920 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1921 "across comdat group boundary\n\n");
1926 if (original_discardable
)
1929 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1930 "target is discardable\n\n");
1936 gcc_assert (!original
->alias
);
1937 gcc_assert (!alias
->alias
);
1939 alias
->analyzed
= false;
1941 DECL_INITIAL (alias
->decl
) = NULL
;
1942 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1944 alias
->need_bounds_init
= false;
1945 alias
->remove_all_references ();
1946 if (TREE_ADDRESSABLE (alias
->decl
))
1947 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1949 varpool_node::create_alias (alias_var
->decl
, decl
);
1950 alias
->resolve_alias (original
);
1953 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1959 /* Dump symbol to FILE. */
1962 sem_variable::dump_to_file (FILE *file
)
1966 print_node (file
, "", decl
, 0);
1967 fprintf (file
, "\n\n");
1970 unsigned int sem_item_optimizer::class_id
= 0;
1972 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1973 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1976 bitmap_obstack_initialize (&m_bmstack
);
1979 sem_item_optimizer::~sem_item_optimizer ()
1981 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1984 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1985 it
!= m_classes
.end (); ++it
)
1987 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1988 delete (*it
)->classes
[i
];
1990 (*it
)->classes
.release ();
1996 bitmap_obstack_release (&m_bmstack
);
1999 /* Write IPA ICF summary for symbols. */
2002 sem_item_optimizer::write_summary (void)
2004 unsigned int count
= 0;
2006 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2007 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2010 /* Calculate number of symbols to be serialized. */
2011 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2013 lsei_next_in_partition (&lsei
))
2015 symtab_node
*node
= lsei_node (lsei
);
2017 if (m_symtab_node_map
.get (node
))
2021 streamer_write_uhwi (ob
, count
);
2023 /* Process all of the symbols. */
2024 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2026 lsei_next_in_partition (&lsei
))
2028 symtab_node
*node
= lsei_node (lsei
);
2030 sem_item
**item
= m_symtab_node_map
.get (node
);
2034 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2035 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2037 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2041 streamer_write_char_stream (ob
->main_stream
, 0);
2042 produce_asm (ob
, NULL
);
2043 destroy_output_block (ob
);
2046 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2047 contains LEN bytes. */
2050 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2051 const char *data
, size_t len
)
2053 const lto_function_header
*header
=
2054 (const lto_function_header
*) data
;
2055 const int cfg_offset
= sizeof (lto_function_header
);
2056 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2057 const int string_offset
= main_offset
+ header
->main_size
;
2062 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2063 header
->main_size
, file_data
->mode_table
);
2066 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2067 header
->string_size
, vNULL
);
2069 count
= streamer_read_uhwi (&ib_main
);
2071 for (i
= 0; i
< count
; i
++)
2075 lto_symtab_encoder_t encoder
;
2077 index
= streamer_read_uhwi (&ib_main
);
2078 encoder
= file_data
->symtab_node_encoder
;
2079 node
= lto_symtab_encoder_deref (encoder
, index
);
2081 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2083 gcc_assert (node
->definition
);
2086 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2087 node
->asm_name (), (void *) node
->decl
, node
->order
);
2089 if (is_a
<cgraph_node
*> (node
))
2091 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2093 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2097 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2099 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2103 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2105 lto_data_in_delete (data_in
);
2108 /* Read IPA IPA ICF summary for symbols. */
2111 sem_item_optimizer::read_summary (void)
2113 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2114 lto_file_decl_data
*file_data
;
2117 while ((file_data
= file_data_vec
[j
++]))
2120 const char *data
= lto_get_section_data (file_data
,
2121 LTO_section_ipa_icf
, NULL
, &len
);
2124 read_section (file_data
, data
, len
);
2128 /* Register callgraph and varpool hooks. */
2131 sem_item_optimizer::register_hooks (void)
2133 if (!m_cgraph_node_hooks
)
2134 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2135 (&sem_item_optimizer::cgraph_removal_hook
, this);
2137 if (!m_varpool_node_hooks
)
2138 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2139 (&sem_item_optimizer::varpool_removal_hook
, this);
2142 /* Unregister callgraph and varpool hooks. */
2145 sem_item_optimizer::unregister_hooks (void)
2147 if (m_cgraph_node_hooks
)
2148 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2150 if (m_varpool_node_hooks
)
2151 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2154 /* Adds a CLS to hashtable associated by hash value. */
2157 sem_item_optimizer::add_class (congruence_class
*cls
)
2159 gcc_assert (cls
->members
.length ());
2161 congruence_class_group
*group
= get_group_by_hash (
2162 cls
->members
[0]->get_hash (),
2163 cls
->members
[0]->type
);
2164 group
->classes
.safe_push (cls
);
2167 /* Gets a congruence class group based on given HASH value and TYPE. */
2169 congruence_class_group
*
2170 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2172 congruence_class_group
*item
= XNEW (congruence_class_group
);
2176 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2182 item
->classes
.create (1);
2189 /* Callgraph removal hook called for a NODE with a custom DATA. */
2192 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2194 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2195 optimizer
->remove_symtab_node (node
);
2198 /* Varpool removal hook called for a NODE with a custom DATA. */
2201 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2203 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2204 optimizer
->remove_symtab_node (node
);
2207 /* Remove symtab NODE triggered by symtab removal hooks. */
2210 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2212 gcc_assert (!m_classes
.elements());
2214 m_removed_items_set
.add (node
);
2218 sem_item_optimizer::remove_item (sem_item
*item
)
2220 if (m_symtab_node_map
.get (item
->node
))
2221 m_symtab_node_map
.remove (item
->node
);
2225 /* Removes all callgraph and varpool nodes that are marked by symtab
2229 sem_item_optimizer::filter_removed_items (void)
2231 auto_vec
<sem_item
*> filtered
;
2233 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2235 sem_item
*item
= m_items
[i
];
2237 if (m_removed_items_set
.contains (item
->node
))
2243 if (item
->type
== FUNC
)
2245 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2247 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2250 filtered
.safe_push (item
);
2254 if (!flag_ipa_icf_variables
)
2258 /* Filter out non-readonly variables. */
2259 tree decl
= item
->decl
;
2260 if (TREE_READONLY (decl
))
2261 filtered
.safe_push (item
);
2268 /* Clean-up of released semantic items. */
2271 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2272 m_items
.safe_push (filtered
[i
]);
2275 /* Optimizer entry point which returns true in case it processes
2276 a merge operation. True is returned if there's a merge operation
2280 sem_item_optimizer::execute (void)
2282 filter_removed_items ();
2283 unregister_hooks ();
2286 update_hash_by_addr_refs ();
2287 build_hash_based_classes ();
2290 fprintf (dump_file
, "Dump after hash based groups\n");
2291 dump_cong_classes ();
2293 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2294 m_items
[i
]->init_wpa ();
2296 subdivide_classes_by_equality (true);
2299 fprintf (dump_file
, "Dump after WPA based types groups\n");
2301 dump_cong_classes ();
2303 process_cong_reduction ();
2307 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2309 dump_cong_classes ();
2311 parse_nonsingleton_classes ();
2312 subdivide_classes_by_equality ();
2315 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2317 dump_cong_classes ();
2319 unsigned int prev_class_count
= m_classes_count
;
2321 process_cong_reduction ();
2322 dump_cong_classes ();
2324 bool merged_p
= merge_classes (prev_class_count
);
2326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2327 symtab_node::dump_table (dump_file
);
2332 /* Function responsible for visiting all potential functions and
2333 read-only variables that can be merged. */
2336 sem_item_optimizer::parse_funcs_and_vars (void)
2340 if (flag_ipa_icf_functions
)
2341 FOR_EACH_DEFINED_FUNCTION (cnode
)
2343 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2346 m_items
.safe_push (f
);
2347 m_symtab_node_map
.put (cnode
, f
);
2350 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2353 f
->dump_to_file (dump_file
);
2356 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2359 varpool_node
*vnode
;
2361 if (flag_ipa_icf_variables
)
2362 FOR_EACH_DEFINED_VARIABLE (vnode
)
2364 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2368 m_items
.safe_push (v
);
2369 m_symtab_node_map
.put (vnode
, v
);
2374 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2377 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2379 item
->index_in_class
= cls
->members
.length ();
2380 cls
->members
.safe_push (item
);
2384 /* For each semantic item, append hash values of references. */
2387 sem_item_optimizer::update_hash_by_addr_refs ()
2389 /* First, append to hash sensitive references. */
2390 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2391 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2393 /* Once all symbols have enhanced hash value, we can append
2394 hash values of symbols that are seen by IPA ICF and are
2395 references by a semantic item. Newly computed values
2396 are saved to global_hash member variable. */
2397 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2398 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2400 /* Global hash value replace current hash values. */
2401 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2402 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2405 /* Congruence classes are built by hash value. */
2408 sem_item_optimizer::build_hash_based_classes (void)
2410 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2412 sem_item
*item
= m_items
[i
];
2414 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2417 if (!group
->classes
.length ())
2420 group
->classes
.safe_push (new congruence_class (class_id
++));
2423 add_item_to_class (group
->classes
[0], item
);
2427 /* Build references according to call graph. */
2430 sem_item_optimizer::build_graph (void)
2432 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2434 sem_item
*item
= m_items
[i
];
2435 m_symtab_node_map
.put (item
->node
, item
);
2438 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2440 sem_item
*item
= m_items
[i
];
2442 if (item
->type
== FUNC
)
2444 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2446 cgraph_edge
*e
= cnode
->callees
;
2449 sem_item
**slot
= m_symtab_node_map
.get
2450 (e
->callee
->ultimate_alias_target ());
2452 item
->add_reference (*slot
);
2458 ipa_ref
*ref
= NULL
;
2459 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2461 sem_item
**slot
= m_symtab_node_map
.get
2462 (ref
->referred
->ultimate_alias_target ());
2464 item
->add_reference (*slot
);
2469 /* Semantic items in classes having more than one element and initialized.
2470 In case of WPA, we load function body. */
2473 sem_item_optimizer::parse_nonsingleton_classes (void)
2475 unsigned int init_called_count
= 0;
2477 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2478 if (m_items
[i
]->cls
->members
.length () > 1)
2480 m_items
[i
]->init ();
2481 init_called_count
++;
2485 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2486 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2489 /* Equality function for semantic items is used to subdivide existing
2490 classes. If IN_WPA, fast equality function is invoked. */
2493 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2495 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2496 it
!= m_classes
.end (); ++it
)
2498 unsigned int class_count
= (*it
)->classes
.length ();
2500 for (unsigned i
= 0; i
< class_count
; i
++)
2502 congruence_class
*c
= (*it
)->classes
[i
];
2504 if (c
->members
.length() > 1)
2506 auto_vec
<sem_item
*> new_vector
;
2508 sem_item
*first
= c
->members
[0];
2509 new_vector
.safe_push (first
);
2511 unsigned class_split_first
= (*it
)->classes
.length ();
2513 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2515 sem_item
*item
= c
->members
[j
];
2517 bool equals
= in_wpa
? first
->equals_wpa (item
,
2518 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2521 new_vector
.safe_push (item
);
2524 bool integrated
= false;
2526 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2528 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2529 bool equals
= in_wpa
? x
->equals_wpa (item
,
2530 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2535 add_item_to_class ((*it
)->classes
[k
], item
);
2543 congruence_class
*c
= new congruence_class (class_id
++);
2545 add_item_to_class (c
, item
);
2547 (*it
)->classes
.safe_push (c
);
2552 // we replace newly created new_vector for the class we've just splitted
2553 c
->members
.release ();
2554 c
->members
.create (new_vector
.length ());
2556 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2557 add_item_to_class (c
, new_vector
[j
]);
2565 /* Subdivide classes by address references that members of the class
2566 reference. Example can be a pair of functions that have an address
2567 taken from a function. If these addresses are different the class
2571 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2573 unsigned newly_created_classes
= 0;
2575 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2576 it
!= m_classes
.end (); ++it
)
2578 unsigned int class_count
= (*it
)->classes
.length ();
2579 auto_vec
<congruence_class
*> new_classes
;
2581 for (unsigned i
= 0; i
< class_count
; i
++)
2583 congruence_class
*c
= (*it
)->classes
[i
];
2585 if (c
->members
.length() > 1)
2587 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2588 symbol_compare_hashmap_traits
> split_map
;
2590 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2592 sem_item
*source_node
= c
->members
[j
];
2594 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2596 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2597 gcc_checking_assert (slot
);
2599 slot
->safe_push (source_node
);
2602 /* If the map contains more than one key, we have to split the map
2604 if (split_map
.elements () != 1)
2606 bool first_class
= true;
2608 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2609 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2610 for (; it2
!= split_map
.end (); ++it2
)
2612 congruence_class
*new_cls
;
2613 new_cls
= new congruence_class (class_id
++);
2615 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2616 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2618 worklist_push (new_cls
);
2619 newly_created_classes
++;
2623 (*it
)->classes
[i
] = new_cls
;
2624 first_class
= false;
2628 new_classes
.safe_push (new_cls
);
2636 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2637 (*it
)->classes
.safe_push (new_classes
[i
]);
2640 return newly_created_classes
;
2643 /* Verify congruence classes if checking is enabled. */
2646 sem_item_optimizer::verify_classes (void)
2649 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2650 it
!= m_classes
.end (); ++it
)
2652 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2654 congruence_class
*cls
= (*it
)->classes
[i
];
2656 gcc_checking_assert (cls
);
2657 gcc_checking_assert (cls
->members
.length () > 0);
2659 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2661 sem_item
*item
= cls
->members
[j
];
2663 gcc_checking_assert (item
);
2664 gcc_checking_assert (item
->cls
== cls
);
2666 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2668 sem_usage_pair
*usage
= item
->usages
[k
];
2669 gcc_checking_assert (usage
->item
->index_in_class
<
2670 usage
->item
->cls
->members
.length ());
2678 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2679 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2680 but unused argument. */
2683 sem_item_optimizer::release_split_map (congruence_class
* const &,
2684 bitmap
const &b
, traverse_split_pair
*)
2693 /* Process split operation for a class given as pointer CLS_PTR,
2694 where bitmap B splits congruence class members. DATA is used
2695 as argument of split pair. */
2698 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2699 bitmap
const &b
, traverse_split_pair
*pair
)
2701 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2702 const congruence_class
*splitter_cls
= pair
->cls
;
2704 /* If counted bits are greater than zero and less than the number of members
2705 a group will be splitted. */
2706 unsigned popcount
= bitmap_count_bits (b
);
2708 if (popcount
> 0 && popcount
< cls
->members
.length ())
2710 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2712 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2714 int target
= bitmap_bit_p (b
, i
);
2715 congruence_class
*tc
= newclasses
[target
];
2717 add_item_to_class (tc
, cls
->members
[i
]);
2720 #ifdef ENABLE_CHECKING
2721 for (unsigned int i
= 0; i
< 2; i
++)
2722 gcc_checking_assert (newclasses
[i
]->members
.length ());
2725 if (splitter_cls
== cls
)
2726 optimizer
->splitter_class_removed
= true;
2728 /* Remove old class from worklist if presented. */
2729 bool in_worklist
= cls
->in_worklist
;
2732 cls
->in_worklist
= false;
2734 congruence_class_group g
;
2735 g
.hash
= cls
->members
[0]->get_hash ();
2736 g
.type
= cls
->members
[0]->type
;
2738 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2740 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2741 if (slot
->classes
[i
] == cls
)
2743 slot
->classes
.ordered_remove (i
);
2747 /* New class will be inserted and integrated to work list. */
2748 for (unsigned int i
= 0; i
< 2; i
++)
2749 optimizer
->add_class (newclasses
[i
]);
2751 /* Two classes replace one, so that increment just by one. */
2752 optimizer
->m_classes_count
++;
2754 /* If OLD class was presented in the worklist, we remove the class
2755 and replace it will both newly created classes. */
2757 for (unsigned int i
= 0; i
< 2; i
++)
2758 optimizer
->worklist_push (newclasses
[i
]);
2759 else /* Just smaller class is inserted. */
2761 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2762 newclasses
[1]->members
.length () ?
2764 optimizer
->worklist_push (newclasses
[smaller_index
]);
2767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2769 fprintf (dump_file
, " congruence class splitted:\n");
2770 cls
->dump (dump_file
, 4);
2772 fprintf (dump_file
, " newly created groups:\n");
2773 for (unsigned int i
= 0; i
< 2; i
++)
2774 newclasses
[i
]->dump (dump_file
, 4);
2777 /* Release class if not presented in work list. */
2786 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2787 Bitmap stack BMSTACK is used for bitmap allocation. */
2790 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2793 hash_map
<congruence_class
*, bitmap
> split_map
;
2795 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2797 sem_item
*item
= cls
->members
[i
];
2799 /* Iterate all usages that have INDEX as usage of the item. */
2800 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2802 sem_usage_pair
*usage
= item
->usages
[j
];
2804 if (usage
->index
!= index
)
2807 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2812 b
= BITMAP_ALLOC (&m_bmstack
);
2813 split_map
.put (usage
->item
->cls
, b
);
2819 gcc_checking_assert (usage
->item
->cls
);
2820 gcc_checking_assert (usage
->item
->index_in_class
<
2821 usage
->item
->cls
->members
.length ());
2824 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2828 traverse_split_pair pair
;
2829 pair
.optimizer
= this;
2832 splitter_class_removed
= false;
2834 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2836 /* Bitmap clean-up. */
2838 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2841 /* Every usage of a congruence class CLS is a candidate that can split the
2842 collection of classes. Bitmap stack BMSTACK is used for bitmap
2846 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2851 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2853 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2854 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2856 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2859 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2862 do_congruence_step_for_index (cls
, i
);
2864 if (splitter_class_removed
)
2868 BITMAP_FREE (usage
);
2871 /* Adds a newly created congruence class CLS to worklist. */
2874 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2876 /* Return if the class CLS is already presented in work list. */
2877 if (cls
->in_worklist
)
2880 cls
->in_worklist
= true;
2881 worklist
.push_back (cls
);
2884 /* Pops a class from worklist. */
2887 sem_item_optimizer::worklist_pop (void)
2889 congruence_class
*cls
;
2891 while (!worklist
.empty ())
2893 cls
= worklist
.front ();
2894 worklist
.pop_front ();
2895 if (cls
->in_worklist
)
2897 cls
->in_worklist
= false;
2903 /* Work list item was already intended to be removed.
2904 The only reason for doing it is to split a class.
2905 Thus, the class CLS is deleted. */
2913 /* Iterative congruence reduction function. */
2916 sem_item_optimizer::process_cong_reduction (void)
2918 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2919 it
!= m_classes
.end (); ++it
)
2920 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2921 if ((*it
)->classes
[i
]->is_class_used ())
2922 worklist_push ((*it
)->classes
[i
]);
2925 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2926 (unsigned long) worklist
.size ());
2928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2929 fprintf (dump_file
, "Congruence class reduction\n");
2931 congruence_class
*cls
;
2933 /* Process complete congruence reduction. */
2934 while ((cls
= worklist_pop ()) != NULL
)
2935 do_congruence_step (cls
);
2937 /* Subdivide newly created classes according to references. */
2938 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2941 fprintf (dump_file
, "Address reference subdivision created: %u "
2942 "new classes.\n", new_classes
);
2945 /* Debug function prints all informations about congruence classes. */
2948 sem_item_optimizer::dump_cong_classes (void)
2954 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2955 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2957 /* Histogram calculation. */
2958 unsigned int max_index
= 0;
2959 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2961 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2962 it
!= m_classes
.end (); ++it
)
2964 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2966 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2974 "Class size histogram [num of members]: number of classe number of classess\n");
2976 for (unsigned int i
= 0; i
<= max_index
; i
++)
2978 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2980 fprintf (dump_file
, "\n\n");
2983 if (dump_flags
& TDF_DETAILS
)
2984 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2985 it
!= m_classes
.end (); ++it
)
2987 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2989 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2991 (*it
)->classes
[i
]->dump (dump_file
, 4);
2993 if(i
< (*it
)->classes
.length () - 1)
2994 fprintf (dump_file
, " ");
3001 /* After reduction is done, we can declare all items in a group
3002 to be equal. PREV_CLASS_COUNT is start number of classes
3003 before reduction. True is returned if there's a merge operation
3007 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3009 unsigned int item_count
= m_items
.length ();
3010 unsigned int class_count
= m_classes_count
;
3011 unsigned int equal_items
= item_count
- class_count
;
3013 unsigned int non_singular_classes_count
= 0;
3014 unsigned int non_singular_classes_sum
= 0;
3016 bool merged_p
= false;
3018 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3019 it
!= m_classes
.end (); ++it
)
3020 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3022 congruence_class
*c
= (*it
)->classes
[i
];
3023 if (c
->members
.length () > 1)
3025 non_singular_classes_count
++;
3026 non_singular_classes_sum
+= c
->members
.length ();
3032 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3033 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3034 prev_class_count
, class_count
);
3035 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3036 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3037 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3038 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3039 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3040 non_singular_classes_count
: 0.0f
,
3041 non_singular_classes_count
);
3042 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3043 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3044 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3047 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3048 it
!= m_classes
.end (); ++it
)
3049 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3051 congruence_class
*c
= (*it
)->classes
[i
];
3053 if (c
->members
.length () == 1)
3056 gcc_assert (c
->members
.length ());
3058 sem_item
*source
= c
->members
[0];
3060 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3062 sem_item
*alias
= c
->members
[j
];
3066 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3067 xstrdup_for_dump (source
->node
->name ()),
3068 xstrdup_for_dump (alias
->node
->name ()));
3069 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3070 xstrdup_for_dump (source
->node
->asm_name ()),
3071 xstrdup_for_dump (alias
->node
->asm_name ()));
3074 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3078 "Merge operation is skipped due to no_icf "
3084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3086 source
->dump_to_file (dump_file
);
3087 alias
->dump_to_file (dump_file
);
3090 merged_p
|= source
->merge (alias
);
3097 /* Dump function prints all class members to a FILE with an INDENT. */
3100 congruence_class::dump (FILE *file
, unsigned int indent
) const
3102 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3103 id
, members
[0]->get_hash (), members
.length ());
3105 FPUTS_SPACES (file
, indent
+ 2, "");
3106 for (unsigned i
= 0; i
< members
.length (); i
++)
3107 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3108 (void *) members
[i
]->decl
,
3109 members
[i
]->node
->order
);
3111 fprintf (file
, "\n");
3114 /* Returns true if there's a member that is used from another group. */
3117 congruence_class::is_class_used (void)
3119 for (unsigned int i
= 0; i
< members
.length (); i
++)
3120 if (members
[i
]->usages
.length ())
3126 /* Initialization and computation of symtab node hash, there data
3127 are propagated later on. */
3129 static sem_item_optimizer
*optimizer
= NULL
;
3131 /* Generate pass summary for IPA ICF pass. */
3134 ipa_icf_generate_summary (void)
3137 optimizer
= new sem_item_optimizer ();
3139 optimizer
->register_hooks ();
3140 optimizer
->parse_funcs_and_vars ();
3143 /* Write pass summary for IPA ICF pass. */
3146 ipa_icf_write_summary (void)
3148 gcc_assert (optimizer
);
3150 optimizer
->write_summary ();
3153 /* Read pass summary for IPA ICF pass. */
3156 ipa_icf_read_summary (void)
3159 optimizer
= new sem_item_optimizer ();
3161 optimizer
->read_summary ();
3162 optimizer
->register_hooks ();
3165 /* Semantic equality exection function. */
3168 ipa_icf_driver (void)
3170 gcc_assert (optimizer
);
3172 bool merged_p
= optimizer
->execute ();
3177 return merged_p
? TODO_remove_functions
: 0;
3180 const pass_data pass_data_ipa_icf
=
3182 IPA_PASS
, /* type */
3184 OPTGROUP_IPA
, /* optinfo_flags */
3185 TV_IPA_ICF
, /* tv_id */
3186 0, /* properties_required */
3187 0, /* properties_provided */
3188 0, /* properties_destroyed */
3189 0, /* todo_flags_start */
3190 0, /* todo_flags_finish */
3193 class pass_ipa_icf
: public ipa_opt_pass_d
3196 pass_ipa_icf (gcc::context
*ctxt
)
3197 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3198 ipa_icf_generate_summary
, /* generate_summary */
3199 ipa_icf_write_summary
, /* write_summary */
3200 ipa_icf_read_summary
, /* read_summary */
3202 write_optimization_summary */
3204 read_optimization_summary */
3205 NULL
, /* stmt_fixup */
3206 0, /* function_transform_todo_flags_start */
3207 NULL
, /* function_transform */
3208 NULL
) /* variable_transform */
3211 /* opt_pass methods: */
3212 virtual bool gate (function
*)
3214 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3217 virtual unsigned int execute (function
*)
3219 return ipa_icf_driver();
3221 }; // class pass_ipa_icf
3223 } // ipa_icf namespace
3226 make_pass_ipa_icf (gcc::context
*ctxt
)
3228 return new ipa_icf::pass_ipa_icf (ctxt
);