1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
56 #include "coretypes.h"
60 #include "double-int.h"
68 #include "fold-const.h"
71 #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"
83 #include "gimple-iterator.h"
84 #include "gimple-ssa.h"
86 #include "tree-phinodes.h"
87 #include "stringpool.h"
88 #include "tree-ssanames.h"
90 #include "tree-pass.h"
91 #include "gimple-pretty-print.h"
93 #include "plugin-api.h"
96 #include "alloc-pool.h"
97 #include "symbol-summary.h"
99 #include "ipa-inline.h"
102 #include "hash-table.h"
103 #include "coverage.h"
105 #include "print-tree.h"
106 #include "lto-streamer.h"
107 #include "data-streamer.h"
108 #include "ipa-utils.h"
110 #include "ipa-icf-gimple.h"
114 using namespace ipa_icf_gimple
;
117 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
119 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
120 item (_item
), index (_index
)
124 /* Semantic item constructor for a node of _TYPE, where STACK is used
125 for bitmap memory allocation. */
127 sem_item::sem_item (sem_item_type _type
,
128 bitmap_obstack
*stack
): type(_type
), hash(0)
133 /* Semantic item constructor for a node of _TYPE, where STACK is used
134 for bitmap memory allocation. The item is based on symtab node _NODE
135 with computed _HASH. */
137 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
138 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
139 node (_node
), hash (_hash
)
145 /* Add reference to a semantic TARGET. */
148 sem_item::add_reference (sem_item
*target
)
150 refs
.safe_push (target
);
151 unsigned index
= refs
.length ();
152 target
->usages
.safe_push (new sem_usage_pair(this, index
));
153 bitmap_set_bit (target
->usage_index_bitmap
, index
);
154 refs_set
.add (target
->node
);
157 /* Initialize internal data structures. Bitmap STACK is used for
158 bitmap memory allocation process. */
161 sem_item::setup (bitmap_obstack
*stack
)
163 gcc_checking_assert (node
);
166 tree_refs
.create (0);
168 usage_index_bitmap
= BITMAP_ALLOC (stack
);
171 sem_item::~sem_item ()
173 for (unsigned i
= 0; i
< usages
.length (); i
++)
177 tree_refs
.release ();
180 BITMAP_FREE (usage_index_bitmap
);
183 /* Dump function for debugging purpose. */
186 sem_item::dump (void)
190 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
191 name(), node
->order
, (void *) node
->decl
);
192 fprintf (dump_file
, " hash: %u\n", get_hash ());
193 fprintf (dump_file
, " references: ");
195 for (unsigned i
= 0; i
< refs
.length (); i
++)
196 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
197 i
< refs
.length() - 1 ? "," : "");
199 fprintf (dump_file
, "\n");
203 /* Return true if target supports alias symbols. */
206 sem_item::target_supports_symbol_aliases_p (void)
208 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
215 /* Semantic function constructor that uses STACK as bitmap memory stack. */
217 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
218 m_checker (NULL
), m_compared_func (NULL
)
220 arg_types
.create (0);
222 bb_sorted
.create (0);
225 /* Constructor based on callgraph node _NODE with computed hash _HASH.
226 Bitmap STACK is used for memory allocation. */
227 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
228 bitmap_obstack
*stack
):
229 sem_item (FUNC
, node
, hash
, stack
),
230 m_checker (NULL
), m_compared_func (NULL
)
232 arg_types
.create (0);
234 bb_sorted
.create (0);
237 sem_function::~sem_function ()
239 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
240 delete (bb_sorted
[i
]);
242 arg_types
.release ();
244 bb_sorted
.release ();
247 /* Calculates hash value based on a BASIC_BLOCK. */
250 sem_function::get_bb_hash (const sem_bb
*basic_block
)
252 inchash::hash hstate
;
254 hstate
.add_int (basic_block
->nondbg_stmt_count
);
255 hstate
.add_int (basic_block
->edge_count
);
257 return hstate
.end ();
260 /* References independent hash function. */
263 sem_function::get_hash (void)
267 inchash::hash hstate
;
268 hstate
.add_int (177454); /* Random number for function type. */
270 hstate
.add_int (arg_count
);
271 hstate
.add_int (cfg_checksum
);
272 hstate
.add_int (gcode_hash
);
274 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
275 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
277 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
278 hstate
.add_int (bb_sizes
[i
]);
280 hash
= hstate
.end ();
286 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
287 point to a same function. Comparison can be skipped if IGNORED_NODES
288 contains these nodes. */
291 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
293 symtab_node
*n1
, symtab_node
*n2
)
295 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
298 /* TODO: add more precise comparison for weakrefs, etc. */
300 return return_false_with_msg ("different references");
303 /* If cgraph edges E1 and E2 are indirect calls, verify that
304 ECF flags are the same. */
306 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
308 if (e1
->indirect_info
&& e2
->indirect_info
)
310 int e1_flags
= e1
->indirect_info
->ecf_flags
;
311 int e2_flags
= e2
->indirect_info
->ecf_flags
;
313 if (e1_flags
!= e2_flags
)
314 return return_false_with_msg ("ICF flags are different");
316 else if (e1
->indirect_info
|| e2
->indirect_info
)
322 /* Fast equality function based on knowledge known in WPA. */
325 sem_function::equals_wpa (sem_item
*item
,
326 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
328 gcc_assert (item
->type
== FUNC
);
330 m_compared_func
= static_cast<sem_function
*> (item
);
332 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
333 return return_false_with_msg ("different number of arguments");
335 /* Checking types of arguments. */
336 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
338 /* This guard is here for function pointer with attributes (pr59927.c). */
339 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
340 return return_false_with_msg ("NULL argument type");
342 /* Polymorphic comparison is executed just for non-leaf functions. */
343 bool is_not_leaf
= get_node ()->callees
!= NULL
344 || get_node ()->indirect_calls
!= NULL
;
346 if (!func_checker::compatible_types_p (arg_types
[i
],
347 m_compared_func
->arg_types
[i
],
348 is_not_leaf
, i
== 0))
349 return return_false_with_msg ("argument type is different");
352 /* Result type checking. */
353 if (!func_checker::compatible_types_p (result_type
,
354 m_compared_func
->result_type
))
355 return return_false_with_msg ("result types are different");
357 if (node
->num_references () != item
->node
->num_references ())
358 return return_false_with_msg ("different number of references");
360 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
361 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
363 item
->node
->iterate_reference (i
, ref2
);
365 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
369 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
370 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
374 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
377 e1
= e1
->next_callee
;
378 e2
= e2
->next_callee
;
382 return return_false_with_msg ("different number of edges");
387 /* Returns true if the item equals to ITEM given as argument. */
390 sem_function::equals (sem_item
*item
,
391 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
393 gcc_assert (item
->type
== FUNC
);
394 bool eq
= equals_private (item
, ignored_nodes
);
396 if (m_checker
!= NULL
)
402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
404 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
405 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
406 item
->asm_name (), eq
? "true" : "false");
411 /* Processes function equality comparison. */
414 sem_function::equals_private (sem_item
*item
,
415 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
417 if (item
->type
!= FUNC
)
420 basic_block bb1
, bb2
;
422 edge_iterator ei1
, ei2
;
426 m_compared_func
= static_cast<sem_function
*> (item
);
428 gcc_assert (decl
!= item
->decl
);
430 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
431 || edge_count
!= m_compared_func
->edge_count
432 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
433 return return_false ();
435 if (!equals_wpa (item
, ignored_nodes
))
438 /* Checking function TARGET and OPTIMIZATION flags. */
439 cl_target_option
*tar1
= target_opts_for_fn (decl
);
440 cl_target_option
*tar2
= target_opts_for_fn (m_compared_func
->decl
);
442 if (tar1
!= NULL
&& tar2
!= NULL
)
444 if (!cl_target_option_eq (tar1
, tar2
))
446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
448 fprintf (dump_file
, "target flags difference");
449 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
452 return return_false_with_msg ("Target flags are different");
455 else if (tar1
!= NULL
|| tar2
!= NULL
)
456 return return_false_with_msg ("Target flags are different");
458 cl_optimization
*opt1
= opts_for_fn (decl
);
459 cl_optimization
*opt2
= opts_for_fn (m_compared_func
->decl
);
461 if (opt1
!= NULL
&& opt2
!= NULL
)
463 if (memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
467 fprintf (dump_file
, "optimization flags difference");
468 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
471 return return_false_with_msg ("optimization flags are different");
474 else if (opt1
!= NULL
|| opt2
!= NULL
)
475 return return_false_with_msg ("optimization flags are different");
477 /* Checking function arguments. */
478 tree decl1
= DECL_ATTRIBUTES (decl
);
479 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
481 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
482 compare_polymorphic_p (),
485 &m_compared_func
->refs_set
);
489 return return_false ();
491 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
492 return return_false ();
494 tree attr_value1
= TREE_VALUE (decl1
);
495 tree attr_value2
= TREE_VALUE (decl2
);
497 if (attr_value1
&& attr_value2
)
499 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
500 TREE_VALUE (attr_value2
));
502 return return_false_with_msg ("attribute values are different");
504 else if (!attr_value1
&& !attr_value2
)
507 return return_false ();
509 decl1
= TREE_CHAIN (decl1
);
510 decl2
= TREE_CHAIN (decl2
);
514 return return_false();
517 for (arg1
= DECL_ARGUMENTS (decl
),
518 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
519 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
520 if (!m_checker
->compare_decl (arg1
, arg2
))
521 return return_false ();
523 /* Fill-up label dictionary. */
524 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
526 m_checker
->parse_labels (bb_sorted
[i
]);
527 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
530 /* Checking all basic blocks. */
531 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
532 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
533 return return_false();
535 dump_message ("All BBs are equal\n");
537 auto_vec
<int> bb_dict
;
539 /* Basic block edges check. */
540 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
542 bb1
= bb_sorted
[i
]->bb
;
543 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
545 ei2
= ei_start (bb2
->preds
);
547 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
551 if (e1
->flags
!= e2
->flags
)
552 return return_false_with_msg ("flags comparison returns false");
554 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
555 return return_false_with_msg ("edge comparison returns false");
557 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
558 return return_false_with_msg ("BB comparison returns false");
560 if (!m_checker
->compare_edge (e1
, e2
))
561 return return_false_with_msg ("edge comparison returns false");
567 /* Basic block PHI nodes comparison. */
568 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
569 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
570 return return_false_with_msg ("PHI node comparison returns false");
575 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
578 sem_function::merge (sem_item
*alias_item
)
580 gcc_assert (alias_item
->type
== FUNC
);
582 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
584 cgraph_node
*original
= get_node ();
585 cgraph_node
*local_original
= original
;
586 cgraph_node
*alias
= alias_func
->get_node ();
587 bool original_address_matters
;
588 bool alias_address_matters
;
590 bool create_thunk
= false;
591 bool create_alias
= false;
592 bool redirect_callers
= false;
593 bool original_discardable
= false;
595 /* Do not attempt to mix functions from different user sections;
596 we do not know what user intends with those. */
597 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
598 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
599 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
603 "Not unifying; original and alias are in different sections.\n\n");
607 /* See if original is in a section that can be discarded if the main
608 symbol is not used. */
609 if (DECL_EXTERNAL (original
->decl
))
610 original_discardable
= true;
611 if (original
->resolution
== LDPR_PREEMPTED_REG
612 || original
->resolution
== LDPR_PREEMPTED_IR
)
613 original_discardable
= true;
614 if (original
->can_be_discarded_p ())
615 original_discardable
= true;
617 /* See if original and/or alias address can be compared for equality. */
618 original_address_matters
619 = (!DECL_VIRTUAL_P (original
->decl
)
620 && (original
->externally_visible
621 || original
->address_taken_from_non_vtable_p ()));
622 alias_address_matters
623 = (!DECL_VIRTUAL_P (alias
->decl
)
624 && (alias
->externally_visible
625 || alias
->address_taken_from_non_vtable_p ()));
627 /* If alias and original can be compared for address equality, we need
628 to create a thunk. Also we can not create extra aliases into discardable
629 section (or we risk link failures when section is discarded). */
630 if ((original_address_matters
631 && alias_address_matters
)
632 || original_discardable
)
634 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
635 create_alias
= false;
636 /* When both alias and original are not overwritable, we can save
637 the extra thunk wrapper for direct calls. */
639 = (!original_discardable
640 && alias
->get_availability () > AVAIL_INTERPOSABLE
641 && original
->get_availability () > AVAIL_INTERPOSABLE
642 && !alias
->instrumented_version
);
647 create_thunk
= false;
648 redirect_callers
= false;
651 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
652 || !sem_item::target_supports_symbol_aliases_p ()))
654 create_alias
= false;
658 /* We want thunk to always jump to the local function body
659 unless the body is comdat and may be optimized out. */
660 if ((create_thunk
|| redirect_callers
)
661 && (!original_discardable
662 || (DECL_COMDAT_GROUP (original
->decl
)
663 && (DECL_COMDAT_GROUP (original
->decl
)
664 == DECL_COMDAT_GROUP (alias
->decl
)))))
666 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
671 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
676 if (!decl_binds_to_current_def_p (alias
->decl
))
679 fprintf (dump_file
, "Declaration does not bind to currect definition.\n\n");
683 if (redirect_callers
)
685 /* If alias is non-overwritable then
686 all direct calls are safe to be redirected to the original. */
687 bool redirected
= false;
688 while (alias
->callers
)
690 cgraph_edge
*e
= alias
->callers
;
691 e
->redirect_callee (local_original
);
692 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
695 e
->redirect_call_stmt_to_callee ();
701 alias
->icf_merged
= true;
703 /* The alias function is removed if symbol address
705 if (!alias_address_matters
)
708 if (dump_file
&& redirected
)
709 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
711 /* If the condtion above is not met, we are lucky and can turn the
712 function into real alias. */
713 else if (create_alias
)
715 alias
->icf_merged
= true;
717 /* Remove the function's body. */
718 ipa_merge_profiles (original
, alias
);
719 alias
->release_body (true);
722 /* Create the alias. */
723 cgraph_node::create_alias (alias_func
->decl
, decl
);
724 alias
->resolve_alias (original
);
726 /* Workaround for PR63566 that forces equal calling convention
728 alias
->local
.local
= false;
729 original
->local
.local
= false;
732 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
734 else if (create_thunk
)
736 if (DECL_COMDAT_GROUP (alias
->decl
))
739 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
744 if (DECL_STATIC_CHAIN (alias
->decl
))
747 fprintf (dump_file
, "Thunk creation is risky for static-chain functions.\n\n");
752 alias
->icf_merged
= true;
753 ipa_merge_profiles (local_original
, alias
);
754 alias
->create_wrapper (local_original
);
757 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
760 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
765 /* Semantic item initialization function. */
768 sem_function::init (void)
771 get_node ()->get_untransformed_body ();
773 tree fndecl
= node
->decl
;
774 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
777 gcc_assert (SSANAMES (func
));
779 ssa_names_size
= SSANAMES (func
)->length ();
783 region_tree
= func
->eh
->region_tree
;
785 /* iterating all function arguments. */
786 arg_count
= count_formal_params (fndecl
);
788 edge_count
= n_edges_for_fn (func
);
789 cfg_checksum
= coverage_compute_cfg_checksum (func
);
791 inchash::hash hstate
;
794 FOR_EACH_BB_FN (bb
, func
)
796 unsigned nondbg_stmt_count
= 0;
799 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
800 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
803 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
806 gimple stmt
= gsi_stmt (gsi
);
808 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
810 hash_stmt (&hstate
, stmt
);
815 gcode_hash
= hstate
.end ();
816 bb_sizes
.safe_push (nondbg_stmt_count
);
818 /* Inserting basic block to hash table. */
819 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
820 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
822 bb_sorted
.safe_push (semantic_bb
);
828 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
831 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
833 enum gimple_code code
= gimple_code (stmt
);
835 hstate
->add_int (code
);
837 if (code
== GIMPLE_CALL
)
839 /* Checking of argument. */
840 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
842 tree argument
= gimple_call_arg (stmt
, i
);
844 switch (TREE_CODE (argument
))
847 if (tree_fits_shwi_p (argument
))
848 hstate
->add_wide_int (tree_to_shwi (argument
));
849 else if (tree_fits_uhwi_p (argument
))
850 hstate
->add_wide_int (tree_to_uhwi (argument
));
856 c
= TREE_REAL_CST (argument
);
857 n
= real_to_integer (&c
);
859 hstate
->add_wide_int (n
);
863 tree addr_operand
= TREE_OPERAND (argument
, 0);
865 if (TREE_CODE (addr_operand
) == STRING_CST
)
866 hstate
->add (TREE_STRING_POINTER (addr_operand
),
867 TREE_STRING_LENGTH (addr_operand
));
878 /* Return true if polymorphic comparison must be processed. */
881 sem_function::compare_polymorphic_p (void)
883 return get_node ()->callees
!= NULL
884 || get_node ()->indirect_calls
!= NULL
885 || m_compared_func
->get_node ()->callees
!= NULL
886 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
889 /* For a given call graph NODE, the function constructs new
890 semantic function item. */
893 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
895 tree fndecl
= node
->decl
;
896 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
898 /* TODO: add support for thunks and aliases. */
900 if (!func
|| !node
->has_gimple_body_p ())
903 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
906 sem_function
*f
= new sem_function (node
, 0, stack
);
913 /* Parses function arguments and result type. */
916 sem_function::parse_tree_args (void)
920 if (arg_types
.exists ())
921 arg_types
.release ();
923 arg_types
.create (4);
924 tree fnargs
= DECL_ARGUMENTS (decl
);
926 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
927 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
929 /* Function result type. */
930 result
= DECL_RESULT (decl
);
931 result_type
= result
? TREE_TYPE (result
) : NULL
;
933 /* During WPA, we can get arguments by following method. */
936 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
937 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
938 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
940 result_type
= TREE_TYPE (TREE_TYPE (decl
));
944 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
945 return true if phi nodes are semantically equivalent in these blocks . */
948 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
950 gphi_iterator si1
, si2
;
952 unsigned size1
, size2
, i
;
956 gcc_assert (bb1
!= NULL
);
957 gcc_assert (bb2
!= NULL
);
959 si2
= gsi_start_phis (bb2
);
960 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
963 gsi_next_nonvirtual_phi (&si1
);
964 gsi_next_nonvirtual_phi (&si2
);
966 if (gsi_end_p (si1
) && gsi_end_p (si2
))
969 if (gsi_end_p (si1
) || gsi_end_p (si2
))
970 return return_false();
975 tree phi_result1
= gimple_phi_result (phi1
);
976 tree phi_result2
= gimple_phi_result (phi2
);
978 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
979 return return_false_with_msg ("PHI results are different");
981 size1
= gimple_phi_num_args (phi1
);
982 size2
= gimple_phi_num_args (phi2
);
985 return return_false ();
987 for (i
= 0; i
< size1
; ++i
)
989 t1
= gimple_phi_arg (phi1
, i
)->def
;
990 t2
= gimple_phi_arg (phi2
, i
)->def
;
992 if (!m_checker
->compare_operand (t1
, t2
))
993 return return_false ();
995 e1
= gimple_phi_arg_edge (phi1
, i
);
996 e2
= gimple_phi_arg_edge (phi2
, i
);
998 if (!m_checker
->compare_edge (e1
, e2
))
999 return return_false ();
1008 /* Returns true if tree T can be compared as a handled component. */
1011 sem_function::icf_handled_component_p (tree t
)
1013 tree_code tc
= TREE_CODE (t
);
1015 return ((handled_component_p (t
))
1016 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1017 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1020 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1021 corresponds to TARGET. */
1024 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
1029 if (bb_dict
.length () <= (unsigned)source
)
1030 bb_dict
.safe_grow_cleared (source
+ 1);
1032 if (bb_dict
[source
] == 0)
1034 bb_dict
[source
] = target
;
1038 return bb_dict
[source
] == target
;
1041 /* Iterates all tree types in T1 and T2 and returns true if all types
1042 are compatible. If COMPARE_POLYMORPHIC is set to true,
1043 more strict comparison is executed. */
1046 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1054 while (t1
!= NULL
&& t2
!= NULL
)
1056 tv1
= TREE_VALUE (t1
);
1057 tv2
= TREE_VALUE (t2
);
1059 tc1
= TREE_CODE (tv1
);
1060 tc2
= TREE_CODE (tv2
);
1062 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1064 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1066 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1069 t1
= TREE_CHAIN (t1
);
1070 t2
= TREE_CHAIN (t2
);
1077 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1079 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1083 /* Constructor based on varpool node _NODE with computed hash _HASH.
1084 Bitmap STACK is used for memory allocation. */
1086 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1087 bitmap_obstack
*stack
): sem_item(VAR
,
1090 gcc_checking_assert (node
);
1091 gcc_checking_assert (get_node ());
1094 /* Returns true if the item equals to ITEM given as argument. */
1097 sem_variable::equals (sem_item
*item
,
1098 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1100 gcc_assert (item
->type
== VAR
);
1102 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1104 if (!ctor
|| !v
->ctor
)
1105 return return_false_with_msg ("ctor is missing for semantic variable");
1107 return sem_variable::equals (ctor
, v
->ctor
);
1110 /* Compares trees T1 and T2 for semantic equality. */
1113 sem_variable::equals (tree t1
, tree t2
)
1115 tree_code tc1
= TREE_CODE (t1
);
1116 tree_code tc2
= TREE_CODE (t2
);
1125 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1126 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1131 for (unsigned i
= 0; i
< len1
; i
++)
1132 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1133 CONSTRUCTOR_ELT (t2
, i
)->value
)
1134 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1141 tree x1
= TREE_OPERAND (t1
, 0);
1142 tree x2
= TREE_OPERAND (t2
, 0);
1143 tree y1
= TREE_OPERAND (t1
, 1);
1144 tree y2
= TREE_OPERAND (t2
, 1);
1146 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1148 return return_false ();
1150 /* Type of the offset on MEM_REF does not matter. */
1151 return sem_variable::equals (x1
, x2
)
1152 && wi::to_offset (y1
) == wi::to_offset (y2
);
1157 tree op1
= TREE_OPERAND (t1
, 0);
1158 tree op2
= TREE_OPERAND (t2
, 0);
1159 return sem_variable::equals (op1
, op2
);
1167 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1169 && wi::to_offset (t1
) == wi::to_offset (t2
);
1173 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1176 case POINTER_PLUS_EXPR
:
1178 tree x1
= TREE_OPERAND (t1
, 0);
1179 tree x2
= TREE_OPERAND (t2
, 0);
1180 tree y1
= TREE_OPERAND (t1
, 1);
1181 tree y2
= TREE_OPERAND (t2
, 1);
1183 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1186 return return_false_with_msg ("ERROR_MARK");
1188 return return_false_with_msg ("Unknown TREE code reached");
1192 /* Parser function that visits a varpool NODE. */
1195 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1197 tree decl
= node
->decl
;
1199 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1203 bool can_handle
= DECL_VIRTUAL_P (decl
)
1204 || flag_merge_constants
>= 2
1205 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1207 if (!can_handle
|| DECL_EXTERNAL (decl
))
1210 tree ctor
= ctor_for_folding (decl
);
1214 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1221 /* References independent hash function. */
1224 sem_variable::get_hash (void)
1229 inchash::hash hstate
;
1231 hstate
.add_int (456346417);
1232 hstate
.add_int (TREE_CODE (ctor
));
1234 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1236 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1237 hstate
.add_int (length
);
1240 hash
= hstate
.end ();
1245 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1249 sem_variable::merge (sem_item
*alias_item
)
1251 gcc_assert (alias_item
->type
== VAR
);
1253 if (!sem_item::target_supports_symbol_aliases_p ())
1256 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1260 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1262 varpool_node
*original
= get_node ();
1263 varpool_node
*alias
= alias_var
->get_node ();
1264 bool original_discardable
= false;
1266 /* See if original is in a section that can be discarded if the main
1267 symbol is not used. */
1268 if (DECL_EXTERNAL (original
->decl
))
1269 original_discardable
= true;
1270 if (original
->resolution
== LDPR_PREEMPTED_REG
1271 || original
->resolution
== LDPR_PREEMPTED_IR
)
1272 original_discardable
= true;
1273 if (original
->can_be_discarded_p ())
1274 original_discardable
= true;
1276 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1278 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1279 !compare_sections (alias_var
))
1282 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1288 // alias cycle creation check
1289 varpool_node
*n
= original
;
1293 n
= n
->get_alias_target ();
1297 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1303 alias
->analyzed
= false;
1305 DECL_INITIAL (alias
->decl
) = NULL
;
1306 alias
->need_bounds_init
= false;
1307 alias
->remove_all_references ();
1309 varpool_node::create_alias (alias_var
->decl
, decl
);
1310 alias
->resolve_alias (original
);
1313 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1320 sem_variable::compare_sections (sem_variable
*alias
)
1322 const char *source
= node
->get_section ();
1323 const char *target
= alias
->node
->get_section();
1325 if (source
== NULL
&& target
== NULL
)
1327 else if(!source
|| !target
)
1330 return strcmp (source
, target
) == 0;
1333 /* Dump symbol to FILE. */
1336 sem_variable::dump_to_file (FILE *file
)
1340 print_node (file
, "", decl
, 0);
1341 fprintf (file
, "\n\n");
1344 /* Iterates though a constructor and identifies tree references
1345 we are interested in semantic function equality. */
1348 sem_variable::parse_tree_refs (tree t
)
1350 switch (TREE_CODE (t
))
1354 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1356 for (unsigned i
= 0; i
< length
; i
++)
1357 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1364 tree op
= TREE_OPERAND (t
, 0);
1365 parse_tree_refs (op
);
1370 tree_refs
.safe_push (t
);
1378 unsigned int sem_item_optimizer::class_id
= 0;
1380 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1381 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1384 bitmap_obstack_initialize (&m_bmstack
);
1387 sem_item_optimizer::~sem_item_optimizer ()
1389 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1392 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1393 it
!= m_classes
.end (); ++it
)
1395 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1396 delete (*it
)->classes
[i
];
1398 (*it
)->classes
.release ();
1404 bitmap_obstack_release (&m_bmstack
);
1407 /* Write IPA ICF summary for symbols. */
1410 sem_item_optimizer::write_summary (void)
1412 unsigned int count
= 0;
1414 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1415 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1418 /* Calculate number of symbols to be serialized. */
1419 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1421 lsei_next_in_partition (&lsei
))
1423 symtab_node
*node
= lsei_node (lsei
);
1425 if (m_symtab_node_map
.get (node
))
1429 streamer_write_uhwi (ob
, count
);
1431 /* Process all of the symbols. */
1432 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1434 lsei_next_in_partition (&lsei
))
1436 symtab_node
*node
= lsei_node (lsei
);
1438 sem_item
**item
= m_symtab_node_map
.get (node
);
1442 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1443 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1445 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1449 streamer_write_char_stream (ob
->main_stream
, 0);
1450 produce_asm (ob
, NULL
);
1451 destroy_output_block (ob
);
1454 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1455 contains LEN bytes. */
1458 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1459 const char *data
, size_t len
)
1461 const lto_function_header
*header
=
1462 (const lto_function_header
*) data
;
1463 const int cfg_offset
= sizeof (lto_function_header
);
1464 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1465 const int string_offset
= main_offset
+ header
->main_size
;
1470 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1474 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1475 header
->string_size
, vNULL
);
1477 count
= streamer_read_uhwi (&ib_main
);
1479 for (i
= 0; i
< count
; i
++)
1483 lto_symtab_encoder_t encoder
;
1485 index
= streamer_read_uhwi (&ib_main
);
1486 encoder
= file_data
->symtab_node_encoder
;
1487 node
= lto_symtab_encoder_deref (encoder
, index
);
1489 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1491 gcc_assert (node
->definition
);
1494 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1495 (void *) node
->decl
, node
->order
);
1497 if (is_a
<cgraph_node
*> (node
))
1499 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1501 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1505 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1507 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1511 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1513 lto_data_in_delete (data_in
);
1516 /* Read IPA IPA ICF summary for symbols. */
1519 sem_item_optimizer::read_summary (void)
1521 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1522 lto_file_decl_data
*file_data
;
1525 while ((file_data
= file_data_vec
[j
++]))
1528 const char *data
= lto_get_section_data (file_data
,
1529 LTO_section_ipa_icf
, NULL
, &len
);
1532 read_section (file_data
, data
, len
);
1536 /* Register callgraph and varpool hooks. */
1539 sem_item_optimizer::register_hooks (void)
1541 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1542 (&sem_item_optimizer::cgraph_removal_hook
, this);
1544 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1545 (&sem_item_optimizer::varpool_removal_hook
, this);
1548 /* Unregister callgraph and varpool hooks. */
1551 sem_item_optimizer::unregister_hooks (void)
1553 if (m_cgraph_node_hooks
)
1554 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1556 if (m_varpool_node_hooks
)
1557 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1560 /* Adds a CLS to hashtable associated by hash value. */
1563 sem_item_optimizer::add_class (congruence_class
*cls
)
1565 gcc_assert (cls
->members
.length ());
1567 congruence_class_group
*group
= get_group_by_hash (
1568 cls
->members
[0]->get_hash (),
1569 cls
->members
[0]->type
);
1570 group
->classes
.safe_push (cls
);
1573 /* Gets a congruence class group based on given HASH value and TYPE. */
1575 congruence_class_group
*
1576 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1578 congruence_class_group
*item
= XNEW (congruence_class_group
);
1582 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1588 item
->classes
.create (1);
1595 /* Callgraph removal hook called for a NODE with a custom DATA. */
1598 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1600 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1601 optimizer
->remove_symtab_node (node
);
1604 /* Varpool removal hook called for a NODE with a custom DATA. */
1607 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1609 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1610 optimizer
->remove_symtab_node (node
);
1613 /* Remove symtab NODE triggered by symtab removal hooks. */
1616 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1618 gcc_assert (!m_classes
.elements());
1620 m_removed_items_set
.add (node
);
1624 sem_item_optimizer::remove_item (sem_item
*item
)
1626 if (m_symtab_node_map
.get (item
->node
))
1627 m_symtab_node_map
.remove (item
->node
);
1631 /* Removes all callgraph and varpool nodes that are marked by symtab
1635 sem_item_optimizer::filter_removed_items (void)
1637 auto_vec
<sem_item
*> filtered
;
1639 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1641 sem_item
*item
= m_items
[i
];
1643 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1649 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1655 bool no_body_function
= false;
1657 if (item
->type
== FUNC
)
1659 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1661 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1664 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1665 && !no_body_function
)
1667 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1668 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1670 filtered
.safe_push (m_items
[i
]);
1678 /* Clean-up of released semantic items. */
1681 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1682 m_items
.safe_push (filtered
[i
]);
1685 /* Optimizer entry point. */
1688 sem_item_optimizer::execute (void)
1690 filter_removed_items ();
1691 build_hash_based_classes ();
1694 fprintf (dump_file
, "Dump after hash based groups\n");
1695 dump_cong_classes ();
1697 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1698 m_items
[i
]->init_wpa ();
1702 subdivide_classes_by_equality (true);
1705 fprintf (dump_file
, "Dump after WPA based types groups\n");
1707 dump_cong_classes ();
1709 process_cong_reduction ();
1713 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1715 dump_cong_classes ();
1717 parse_nonsingleton_classes ();
1718 subdivide_classes_by_equality ();
1721 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1723 dump_cong_classes ();
1725 unsigned int prev_class_count
= m_classes_count
;
1727 process_cong_reduction ();
1728 dump_cong_classes ();
1730 merge_classes (prev_class_count
);
1732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1733 symtab_node::dump_table (dump_file
);
1736 /* Function responsible for visiting all potential functions and
1737 read-only variables that can be merged. */
1740 sem_item_optimizer::parse_funcs_and_vars (void)
1744 if (flag_ipa_icf_functions
)
1745 FOR_EACH_DEFINED_FUNCTION (cnode
)
1747 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1750 m_items
.safe_push (f
);
1751 m_symtab_node_map
.put (cnode
, f
);
1754 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1757 f
->dump_to_file (dump_file
);
1760 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1763 varpool_node
*vnode
;
1765 if (flag_ipa_icf_variables
)
1766 FOR_EACH_DEFINED_VARIABLE (vnode
)
1768 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1772 m_items
.safe_push (v
);
1773 m_symtab_node_map
.put (vnode
, v
);
1778 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1781 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1783 item
->index_in_class
= cls
->members
.length ();
1784 cls
->members
.safe_push (item
);
1788 /* Congruence classes are built by hash value. */
1791 sem_item_optimizer::build_hash_based_classes (void)
1793 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1795 sem_item
*item
= m_items
[i
];
1797 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1800 if (!group
->classes
.length ())
1803 group
->classes
.safe_push (new congruence_class (class_id
++));
1806 add_item_to_class (group
->classes
[0], item
);
1810 /* Build references according to call graph. */
1813 sem_item_optimizer::build_graph (void)
1815 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1817 sem_item
*item
= m_items
[i
];
1818 m_symtab_node_map
.put (item
->node
, item
);
1821 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1823 sem_item
*item
= m_items
[i
];
1825 if (item
->type
== FUNC
)
1827 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1829 cgraph_edge
*e
= cnode
->callees
;
1832 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1834 item
->add_reference (*slot
);
1840 ipa_ref
*ref
= NULL
;
1841 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1843 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1845 item
->add_reference (*slot
);
1850 /* Semantic items in classes having more than one element and initialized.
1851 In case of WPA, we load function body. */
1854 sem_item_optimizer::parse_nonsingleton_classes (void)
1856 unsigned int init_called_count
= 0;
1858 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1859 if (m_items
[i
]->cls
->members
.length () > 1)
1861 m_items
[i
]->init ();
1862 init_called_count
++;
1866 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1867 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1870 /* Equality function for semantic items is used to subdivide existing
1871 classes. If IN_WPA, fast equality function is invoked. */
1874 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1876 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1877 it
!= m_classes
.end (); ++it
)
1879 unsigned int class_count
= (*it
)->classes
.length ();
1881 for (unsigned i
= 0; i
< class_count
; i
++)
1883 congruence_class
*c
= (*it
)->classes
[i
];
1885 if (c
->members
.length() > 1)
1887 auto_vec
<sem_item
*> new_vector
;
1889 sem_item
*first
= c
->members
[0];
1890 new_vector
.safe_push (first
);
1892 unsigned class_split_first
= (*it
)->classes
.length ();
1894 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1896 sem_item
*item
= c
->members
[j
];
1898 bool equals
= in_wpa
? first
->equals_wpa (item
,
1899 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1902 new_vector
.safe_push (item
);
1905 bool integrated
= false;
1907 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1909 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1910 bool equals
= in_wpa
? x
->equals_wpa (item
,
1911 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1916 add_item_to_class ((*it
)->classes
[k
], item
);
1924 congruence_class
*c
= new congruence_class (class_id
++);
1926 add_item_to_class (c
, item
);
1928 (*it
)->classes
.safe_push (c
);
1933 // we replace newly created new_vector for the class we've just splitted
1934 c
->members
.release ();
1935 c
->members
.create (new_vector
.length ());
1937 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1938 add_item_to_class (c
, new_vector
[j
]);
1946 /* Verify congruence classes if checking is enabled. */
1949 sem_item_optimizer::verify_classes (void)
1952 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1953 it
!= m_classes
.end (); ++it
)
1955 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1957 congruence_class
*cls
= (*it
)->classes
[i
];
1959 gcc_checking_assert (cls
);
1960 gcc_checking_assert (cls
->members
.length () > 0);
1962 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1964 sem_item
*item
= cls
->members
[j
];
1966 gcc_checking_assert (item
);
1967 gcc_checking_assert (item
->cls
== cls
);
1969 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1971 sem_usage_pair
*usage
= item
->usages
[k
];
1972 gcc_checking_assert (usage
->item
->index_in_class
<
1973 usage
->item
->cls
->members
.length ());
1981 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1982 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1983 but unused argument. */
1986 sem_item_optimizer::release_split_map (congruence_class
* const &,
1987 bitmap
const &b
, traverse_split_pair
*)
1996 /* Process split operation for a class given as pointer CLS_PTR,
1997 where bitmap B splits congruence class members. DATA is used
1998 as argument of split pair. */
2001 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2002 bitmap
const &b
, traverse_split_pair
*pair
)
2004 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2005 const congruence_class
*splitter_cls
= pair
->cls
;
2007 /* If counted bits are greater than zero and less than the number of members
2008 a group will be splitted. */
2009 unsigned popcount
= bitmap_count_bits (b
);
2011 if (popcount
> 0 && popcount
< cls
->members
.length ())
2013 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2015 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2017 int target
= bitmap_bit_p (b
, i
);
2018 congruence_class
*tc
= newclasses
[target
];
2020 add_item_to_class (tc
, cls
->members
[i
]);
2023 #ifdef ENABLE_CHECKING
2024 for (unsigned int i
= 0; i
< 2; i
++)
2025 gcc_checking_assert (newclasses
[i
]->members
.length ());
2028 if (splitter_cls
== cls
)
2029 optimizer
->splitter_class_removed
= true;
2031 /* Remove old class from worklist if presented. */
2032 bool in_worklist
= cls
->in_worklist
;
2035 cls
->in_worklist
= false;
2037 congruence_class_group g
;
2038 g
.hash
= cls
->members
[0]->get_hash ();
2039 g
.type
= cls
->members
[0]->type
;
2041 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2043 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2044 if (slot
->classes
[i
] == cls
)
2046 slot
->classes
.ordered_remove (i
);
2050 /* New class will be inserted and integrated to work list. */
2051 for (unsigned int i
= 0; i
< 2; i
++)
2052 optimizer
->add_class (newclasses
[i
]);
2054 /* Two classes replace one, so that increment just by one. */
2055 optimizer
->m_classes_count
++;
2057 /* If OLD class was presented in the worklist, we remove the class
2058 and replace it will both newly created classes. */
2060 for (unsigned int i
= 0; i
< 2; i
++)
2061 optimizer
->worklist_push (newclasses
[i
]);
2062 else /* Just smaller class is inserted. */
2064 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2065 newclasses
[1]->members
.length () ?
2067 optimizer
->worklist_push (newclasses
[smaller_index
]);
2070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2072 fprintf (dump_file
, " congruence class splitted:\n");
2073 cls
->dump (dump_file
, 4);
2075 fprintf (dump_file
, " newly created groups:\n");
2076 for (unsigned int i
= 0; i
< 2; i
++)
2077 newclasses
[i
]->dump (dump_file
, 4);
2080 /* Release class if not presented in work list. */
2089 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2090 Bitmap stack BMSTACK is used for bitmap allocation. */
2093 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2096 hash_map
<congruence_class
*, bitmap
> split_map
;
2098 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2100 sem_item
*item
= cls
->members
[i
];
2102 /* Iterate all usages that have INDEX as usage of the item. */
2103 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2105 sem_usage_pair
*usage
= item
->usages
[j
];
2107 if (usage
->index
!= index
)
2110 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2115 b
= BITMAP_ALLOC (&m_bmstack
);
2116 split_map
.put (usage
->item
->cls
, b
);
2122 gcc_checking_assert (usage
->item
->cls
);
2123 gcc_checking_assert (usage
->item
->index_in_class
<
2124 usage
->item
->cls
->members
.length ());
2127 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2131 traverse_split_pair pair
;
2132 pair
.optimizer
= this;
2135 splitter_class_removed
= false;
2137 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2139 /* Bitmap clean-up. */
2141 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2144 /* Every usage of a congruence class CLS is a candidate that can split the
2145 collection of classes. Bitmap stack BMSTACK is used for bitmap
2149 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2154 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2156 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2157 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2159 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2162 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2165 do_congruence_step_for_index (cls
, i
);
2167 if (splitter_class_removed
)
2171 BITMAP_FREE (usage
);
2174 /* Adds a newly created congruence class CLS to worklist. */
2177 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2179 /* Return if the class CLS is already presented in work list. */
2180 if (cls
->in_worklist
)
2183 cls
->in_worklist
= true;
2184 worklist
.push_back (cls
);
2187 /* Pops a class from worklist. */
2190 sem_item_optimizer::worklist_pop (void)
2192 congruence_class
*cls
;
2194 while (!worklist
.empty ())
2196 cls
= worklist
.front ();
2197 worklist
.pop_front ();
2198 if (cls
->in_worklist
)
2200 cls
->in_worklist
= false;
2206 /* Work list item was already intended to be removed.
2207 The only reason for doing it is to split a class.
2208 Thus, the class CLS is deleted. */
2216 /* Iterative congruence reduction function. */
2219 sem_item_optimizer::process_cong_reduction (void)
2221 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2222 it
!= m_classes
.end (); ++it
)
2223 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2224 if ((*it
)->classes
[i
]->is_class_used ())
2225 worklist_push ((*it
)->classes
[i
]);
2228 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2229 (unsigned long) worklist
.size ());
2231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2232 fprintf (dump_file
, "Congruence class reduction\n");
2234 congruence_class
*cls
;
2235 while ((cls
= worklist_pop ()) != NULL
)
2236 do_congruence_step (cls
);
2239 /* Debug function prints all informations about congruence classes. */
2242 sem_item_optimizer::dump_cong_classes (void)
2248 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2249 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2251 /* Histogram calculation. */
2252 unsigned int max_index
= 0;
2253 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2255 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2256 it
!= m_classes
.end (); ++it
)
2258 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2260 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2268 "Class size histogram [num of members]: number of classe number of classess\n");
2270 for (unsigned int i
= 0; i
<= max_index
; i
++)
2272 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2274 fprintf (dump_file
, "\n\n");
2277 if (dump_flags
& TDF_DETAILS
)
2278 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2279 it
!= m_classes
.end (); ++it
)
2281 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2283 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2285 (*it
)->classes
[i
]->dump (dump_file
, 4);
2287 if(i
< (*it
)->classes
.length () - 1)
2288 fprintf (dump_file
, " ");
2295 /* After reduction is done, we can declare all items in a group
2296 to be equal. PREV_CLASS_COUNT is start number of classes
2297 before reduction. */
2300 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2302 unsigned int item_count
= m_items
.length ();
2303 unsigned int class_count
= m_classes_count
;
2304 unsigned int equal_items
= item_count
- class_count
;
2306 unsigned int non_singular_classes_count
= 0;
2307 unsigned int non_singular_classes_sum
= 0;
2309 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2310 it
!= m_classes
.end (); ++it
)
2311 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2313 congruence_class
*c
= (*it
)->classes
[i
];
2314 if (c
->members
.length () > 1)
2316 non_singular_classes_count
++;
2317 non_singular_classes_sum
+= c
->members
.length ();
2323 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2324 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2325 prev_class_count
, class_count
);
2326 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2327 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2328 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2329 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2330 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2331 non_singular_classes_count
: 0.0f
,
2332 non_singular_classes_count
);
2333 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2334 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2335 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2338 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2339 it
!= m_classes
.end (); ++it
)
2340 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2342 congruence_class
*c
= (*it
)->classes
[i
];
2344 if (c
->members
.length () == 1)
2347 gcc_assert (c
->members
.length ());
2349 sem_item
*source
= c
->members
[0];
2351 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2353 sem_item
*alias
= c
->members
[j
];
2357 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2358 source
->name (), alias
->name ());
2359 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2360 source
->asm_name (), alias
->asm_name ());
2363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2365 source
->dump_to_file (dump_file
);
2366 alias
->dump_to_file (dump_file
);
2369 source
->merge (alias
);
2374 /* Dump function prints all class members to a FILE with an INDENT. */
2377 congruence_class::dump (FILE *file
, unsigned int indent
) const
2379 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2380 id
, members
[0]->get_hash (), members
.length ());
2382 FPUTS_SPACES (file
, indent
+ 2, "");
2383 for (unsigned i
= 0; i
< members
.length (); i
++)
2384 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2385 members
[i
]->node
->order
);
2387 fprintf (file
, "\n");
2390 /* Returns true if there's a member that is used from another group. */
2393 congruence_class::is_class_used (void)
2395 for (unsigned int i
= 0; i
< members
.length (); i
++)
2396 if (members
[i
]->usages
.length ())
2402 /* Initialization and computation of symtab node hash, there data
2403 are propagated later on. */
2405 static sem_item_optimizer
*optimizer
= NULL
;
2407 /* Generate pass summary for IPA ICF pass. */
2410 ipa_icf_generate_summary (void)
2413 optimizer
= new sem_item_optimizer ();
2415 optimizer
->parse_funcs_and_vars ();
2418 /* Write pass summary for IPA ICF pass. */
2421 ipa_icf_write_summary (void)
2423 gcc_assert (optimizer
);
2425 optimizer
->write_summary ();
2428 /* Read pass summary for IPA ICF pass. */
2431 ipa_icf_read_summary (void)
2434 optimizer
= new sem_item_optimizer ();
2436 optimizer
->read_summary ();
2437 optimizer
->register_hooks ();
2440 /* Semantic equality exection function. */
2443 ipa_icf_driver (void)
2445 gcc_assert (optimizer
);
2447 optimizer
->execute ();
2448 optimizer
->unregister_hooks ();
2456 const pass_data pass_data_ipa_icf
=
2458 IPA_PASS
, /* type */
2460 OPTGROUP_IPA
, /* optinfo_flags */
2461 TV_IPA_ICF
, /* tv_id */
2462 0, /* properties_required */
2463 0, /* properties_provided */
2464 0, /* properties_destroyed */
2465 0, /* todo_flags_start */
2466 0, /* todo_flags_finish */
2469 class pass_ipa_icf
: public ipa_opt_pass_d
2472 pass_ipa_icf (gcc::context
*ctxt
)
2473 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2474 ipa_icf_generate_summary
, /* generate_summary */
2475 ipa_icf_write_summary
, /* write_summary */
2476 ipa_icf_read_summary
, /* read_summary */
2478 write_optimization_summary */
2480 read_optimization_summary */
2481 NULL
, /* stmt_fixup */
2482 0, /* function_transform_todo_flags_start */
2483 NULL
, /* function_transform */
2484 NULL
) /* variable_transform */
2487 /* opt_pass methods: */
2488 virtual bool gate (function
*)
2490 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2493 virtual unsigned int execute (function
*)
2495 return ipa_icf_driver();
2497 }; // class pass_ipa_icf
2499 } // ipa_icf namespace
2502 make_pass_ipa_icf (gcc::context
*ctxt
)
2504 return new ipa_icf::pass_ipa_icf (ctxt
);