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"
64 #include "hard-reg-set.h"
67 #include "dominance.h"
69 #include "basic-block.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
76 #include "gimple-iterator.h"
77 #include "gimple-ssa.h"
79 #include "tree-phinodes.h"
80 #include "stringpool.h"
81 #include "tree-ssanames.h"
83 #include "tree-pass.h"
84 #include "gimple-pretty-print.h"
86 #include "plugin-api.h"
89 #include "alloc-pool.h"
90 #include "symbol-summary.h"
92 #include "ipa-inline.h"
95 #include "hash-table.h"
98 #include "print-tree.h"
99 #include "lto-streamer.h"
100 #include "data-streamer.h"
101 #include "ipa-utils.h"
103 #include "ipa-icf-gimple.h"
107 using namespace ipa_icf_gimple
;
110 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
112 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
113 item (_item
), index (_index
)
117 /* Semantic item constructor for a node of _TYPE, where STACK is used
118 for bitmap memory allocation. */
120 sem_item::sem_item (sem_item_type _type
,
121 bitmap_obstack
*stack
): type(_type
), hash(0)
126 /* Semantic item constructor for a node of _TYPE, where STACK is used
127 for bitmap memory allocation. The item is based on symtab node _NODE
128 with computed _HASH. */
130 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
131 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
132 node (_node
), hash (_hash
)
138 /* Add reference to a semantic TARGET. */
141 sem_item::add_reference (sem_item
*target
)
143 refs
.safe_push (target
);
144 unsigned index
= refs
.length ();
145 target
->usages
.safe_push (new sem_usage_pair(this, index
));
146 bitmap_set_bit (target
->usage_index_bitmap
, index
);
147 refs_set
.add (target
->node
);
150 /* Initialize internal data structures. Bitmap STACK is used for
151 bitmap memory allocation process. */
154 sem_item::setup (bitmap_obstack
*stack
)
156 gcc_checking_assert (node
);
159 tree_refs
.create (0);
161 usage_index_bitmap
= BITMAP_ALLOC (stack
);
164 sem_item::~sem_item ()
166 for (unsigned i
= 0; i
< usages
.length (); i
++)
170 tree_refs
.release ();
173 BITMAP_FREE (usage_index_bitmap
);
176 /* Dump function for debugging purpose. */
179 sem_item::dump (void)
183 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
184 name(), node
->order
, (void *) node
->decl
);
185 fprintf (dump_file
, " hash: %u\n", get_hash ());
186 fprintf (dump_file
, " references: ");
188 for (unsigned i
= 0; i
< refs
.length (); i
++)
189 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
190 i
< refs
.length() - 1 ? "," : "");
192 fprintf (dump_file
, "\n");
196 /* Return true if target supports alias symbols. */
199 sem_item::target_supports_symbol_aliases_p (void)
201 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
208 /* Semantic function constructor that uses STACK as bitmap memory stack. */
210 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
211 m_checker (NULL
), m_compared_func (NULL
)
213 arg_types
.create (0);
215 bb_sorted
.create (0);
218 /* Constructor based on callgraph node _NODE with computed hash _HASH.
219 Bitmap STACK is used for memory allocation. */
220 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
221 bitmap_obstack
*stack
):
222 sem_item (FUNC
, node
, hash
, stack
),
223 m_checker (NULL
), m_compared_func (NULL
)
225 arg_types
.create (0);
227 bb_sorted
.create (0);
230 sem_function::~sem_function ()
232 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
233 delete (bb_sorted
[i
]);
235 arg_types
.release ();
237 bb_sorted
.release ();
240 /* Calculates hash value based on a BASIC_BLOCK. */
243 sem_function::get_bb_hash (const sem_bb
*basic_block
)
245 inchash::hash hstate
;
247 hstate
.add_int (basic_block
->nondbg_stmt_count
);
248 hstate
.add_int (basic_block
->edge_count
);
250 return hstate
.end ();
253 /* References independent hash function. */
256 sem_function::get_hash (void)
260 inchash::hash hstate
;
261 hstate
.add_int (177454); /* Random number for function type. */
263 hstate
.add_int (arg_count
);
264 hstate
.add_int (cfg_checksum
);
265 hstate
.add_int (gcode_hash
);
267 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
268 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
270 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
271 hstate
.add_int (bb_sizes
[i
]);
273 hash
= hstate
.end ();
279 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
280 point to a same function. Comparison can be skipped if IGNORED_NODES
281 contains these nodes. */
284 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
286 symtab_node
*n1
, symtab_node
*n2
)
288 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
291 /* TODO: add more precise comparison for weakrefs, etc. */
293 return return_false_with_msg ("different references");
296 /* If cgraph edges E1 and E2 are indirect calls, verify that
297 ECF flags are the same. */
299 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
301 if (e1
->indirect_info
&& e2
->indirect_info
)
303 int e1_flags
= e1
->indirect_info
->ecf_flags
;
304 int e2_flags
= e2
->indirect_info
->ecf_flags
;
306 if (e1_flags
!= e2_flags
)
307 return return_false_with_msg ("ICF flags are different");
309 else if (e1
->indirect_info
|| e2
->indirect_info
)
315 /* Fast equality function based on knowledge known in WPA. */
318 sem_function::equals_wpa (sem_item
*item
,
319 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
321 gcc_assert (item
->type
== FUNC
);
323 m_compared_func
= static_cast<sem_function
*> (item
);
325 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
326 return return_false_with_msg ("different number of arguments");
328 /* Checking types of arguments. */
329 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
331 /* This guard is here for function pointer with attributes (pr59927.c). */
332 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
333 return return_false_with_msg ("NULL argument type");
335 /* Polymorphic comparison is executed just for non-leaf functions. */
336 bool is_not_leaf
= get_node ()->callees
!= NULL
;
338 if (!func_checker::compatible_types_p (arg_types
[i
],
339 m_compared_func
->arg_types
[i
],
340 is_not_leaf
, i
== 0))
341 return return_false_with_msg ("argument type is different");
344 /* Result type checking. */
345 if (!func_checker::compatible_types_p (result_type
,
346 m_compared_func
->result_type
))
347 return return_false_with_msg ("result types are different");
349 if (node
->num_references () != item
->node
->num_references ())
350 return return_false_with_msg ("different number of references");
352 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
353 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
355 item
->node
->iterate_reference (i
, ref2
);
357 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
361 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
362 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
366 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
369 e1
= e1
->next_callee
;
370 e2
= e2
->next_callee
;
374 return return_false_with_msg ("different number of edges");
379 /* Returns true if the item equals to ITEM given as argument. */
382 sem_function::equals (sem_item
*item
,
383 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
385 gcc_assert (item
->type
== FUNC
);
386 bool eq
= equals_private (item
, ignored_nodes
);
388 if (m_checker
!= NULL
)
394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
396 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
397 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
398 item
->asm_name (), eq
? "true" : "false");
403 /* Processes function equality comparison. */
406 sem_function::equals_private (sem_item
*item
,
407 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
409 if (item
->type
!= FUNC
)
412 basic_block bb1
, bb2
;
414 edge_iterator ei1
, ei2
;
418 m_compared_func
= static_cast<sem_function
*> (item
);
420 gcc_assert (decl
!= item
->decl
);
422 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
423 || edge_count
!= m_compared_func
->edge_count
424 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
425 return return_false ();
427 if (!equals_wpa (item
, ignored_nodes
))
430 /* Checking function TARGET and OPTIMIZATION flags. */
431 cl_target_option
*tar1
= target_opts_for_fn (decl
);
432 cl_target_option
*tar2
= target_opts_for_fn (m_compared_func
->decl
);
434 if (tar1
!= NULL
|| tar2
!= NULL
)
436 if (!cl_target_option_eq (tar1
, tar2
))
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
440 fprintf (dump_file
, "Source target flags\n");
441 cl_target_option_print (dump_file
, 2, tar1
);
442 fprintf (dump_file
, "Target target flags\n");
443 cl_target_option_print (dump_file
, 2, tar2
);
446 return return_false_with_msg ("Target flags are different");
449 else if (tar1
!= NULL
|| tar2
!= NULL
)
450 return return_false_with_msg ("Target flags are different");
452 cl_optimization
*opt1
= opts_for_fn (decl
);
453 cl_optimization
*opt2
= opts_for_fn (m_compared_func
->decl
);
455 if (opt1
!= NULL
&& opt2
!= NULL
)
457 if (memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
461 fprintf (dump_file
, "Source optimization flags\n");
462 cl_optimization_print (dump_file
, 2, opt1
);
463 fprintf (dump_file
, "Target optimization flags\n");
464 cl_optimization_print (dump_file
, 2, opt2
);
467 return return_false_with_msg ("optimization flags are different");
470 else if (opt1
!= NULL
|| opt2
!= NULL
)
471 return return_false_with_msg ("optimization flags are different");
473 /* Checking function arguments. */
474 tree decl1
= DECL_ATTRIBUTES (decl
);
475 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
477 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
478 compare_polymorphic_p (),
481 &m_compared_func
->refs_set
);
485 return return_false ();
487 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
488 return return_false ();
490 tree attr_value1
= TREE_VALUE (decl1
);
491 tree attr_value2
= TREE_VALUE (decl2
);
493 if (attr_value1
&& attr_value2
)
495 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
496 TREE_VALUE (attr_value2
));
498 return return_false_with_msg ("attribute values are different");
500 else if (!attr_value1
&& !attr_value2
)
503 return return_false ();
505 decl1
= TREE_CHAIN (decl1
);
506 decl2
= TREE_CHAIN (decl2
);
510 return return_false();
513 for (arg1
= DECL_ARGUMENTS (decl
),
514 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
515 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
516 if (!m_checker
->compare_decl (arg1
, arg2
))
517 return return_false ();
519 /* Fill-up label dictionary. */
520 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
522 m_checker
->parse_labels (bb_sorted
[i
]);
523 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
526 /* Checking all basic blocks. */
527 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
528 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
529 return return_false();
531 dump_message ("All BBs are equal\n");
533 auto_vec
<int> bb_dict
;
535 /* Basic block edges check. */
536 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
538 bb1
= bb_sorted
[i
]->bb
;
539 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
541 ei2
= ei_start (bb2
->preds
);
543 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
547 if (e1
->flags
!= e2
->flags
)
548 return return_false_with_msg ("flags comparison returns false");
550 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
551 return return_false_with_msg ("edge comparison returns false");
553 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
554 return return_false_with_msg ("BB comparison returns false");
556 if (!m_checker
->compare_edge (e1
, e2
))
557 return return_false_with_msg ("edge comparison returns false");
563 /* Basic block PHI nodes comparison. */
564 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
565 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
566 return return_false_with_msg ("PHI node comparison returns false");
571 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
574 sem_function::merge (sem_item
*alias_item
)
576 gcc_assert (alias_item
->type
== FUNC
);
578 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
580 cgraph_node
*original
= get_node ();
581 cgraph_node
*local_original
= original
;
582 cgraph_node
*alias
= alias_func
->get_node ();
583 bool original_address_matters
;
584 bool alias_address_matters
;
586 bool create_thunk
= false;
587 bool create_alias
= false;
588 bool redirect_callers
= false;
589 bool original_discardable
= false;
591 /* Do not attempt to mix functions from different user sections;
592 we do not know what user intends with those. */
593 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
594 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
595 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
599 "Not unifying; original and alias are in different sections.\n\n");
603 /* See if original is in a section that can be discarded if the main
604 symbol is not used. */
605 if (DECL_EXTERNAL (original
->decl
))
606 original_discardable
= true;
607 if (original
->resolution
== LDPR_PREEMPTED_REG
608 || original
->resolution
== LDPR_PREEMPTED_IR
)
609 original_discardable
= true;
610 if (original
->can_be_discarded_p ())
611 original_discardable
= true;
613 /* See if original and/or alias address can be compared for equality. */
614 original_address_matters
615 = (!DECL_VIRTUAL_P (original
->decl
)
616 && (original
->externally_visible
617 || original
->address_taken_from_non_vtable_p ()));
618 alias_address_matters
619 = (!DECL_VIRTUAL_P (alias
->decl
)
620 && (alias
->externally_visible
621 || alias
->address_taken_from_non_vtable_p ()));
623 /* If alias and original can be compared for address equality, we need
624 to create a thunk. Also we can not create extra aliases into discardable
625 section (or we risk link failures when section is discarded). */
626 if ((original_address_matters
627 && alias_address_matters
)
628 || original_discardable
)
630 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
631 create_alias
= false;
632 /* When both alias and original are not overwritable, we can save
633 the extra thunk wrapper for direct calls. */
635 = (!original_discardable
636 && alias
->get_availability () > AVAIL_INTERPOSABLE
637 && original
->get_availability () > AVAIL_INTERPOSABLE
638 && !alias
->instrumented_version
);
643 create_thunk
= false;
644 redirect_callers
= false;
647 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
648 || !sem_item::target_supports_symbol_aliases_p ()))
650 create_alias
= false;
654 /* We want thunk to always jump to the local function body
655 unless the body is comdat and may be optimized out. */
656 if ((create_thunk
|| redirect_callers
)
657 && (!original_discardable
658 || (DECL_COMDAT_GROUP (original
->decl
)
659 && (DECL_COMDAT_GROUP (original
->decl
)
660 == DECL_COMDAT_GROUP (alias
->decl
)))))
662 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
667 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
672 if (!decl_binds_to_current_def_p (alias
->decl
))
675 fprintf (dump_file
, "Declaration does not bind to currect definition.\n\n");
679 if (redirect_callers
)
681 /* If alias is non-overwritable then
682 all direct calls are safe to be redirected to the original. */
683 bool redirected
= false;
684 while (alias
->callers
)
686 cgraph_edge
*e
= alias
->callers
;
687 e
->redirect_callee (local_original
);
688 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
691 e
->redirect_call_stmt_to_callee ();
697 alias
->icf_merged
= true;
699 /* The alias function is removed if symbol address
701 if (!alias_address_matters
)
704 if (dump_file
&& redirected
)
705 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
707 /* If the condtion above is not met, we are lucky and can turn the
708 function into real alias. */
709 else if (create_alias
)
711 alias
->icf_merged
= true;
713 /* Remove the function's body. */
714 ipa_merge_profiles (original
, alias
);
715 alias
->release_body (true);
718 /* Create the alias. */
719 cgraph_node::create_alias (alias_func
->decl
, decl
);
720 alias
->resolve_alias (original
);
722 /* Workaround for PR63566 that forces equal calling convention
724 alias
->local
.local
= false;
725 original
->local
.local
= false;
728 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
730 else if (create_thunk
)
732 if (DECL_COMDAT_GROUP (alias
->decl
))
735 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
740 if (DECL_STATIC_CHAIN (alias
->decl
))
743 fprintf (dump_file
, "Thunk creation is risky for static-chain functions.\n\n");
748 alias
->icf_merged
= true;
749 ipa_merge_profiles (local_original
, alias
);
750 alias
->create_wrapper (local_original
);
753 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
756 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
761 /* Semantic item initialization function. */
764 sem_function::init (void)
767 get_node ()->get_untransformed_body ();
769 tree fndecl
= node
->decl
;
770 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
773 gcc_assert (SSANAMES (func
));
775 ssa_names_size
= SSANAMES (func
)->length ();
779 region_tree
= func
->eh
->region_tree
;
781 /* iterating all function arguments. */
782 arg_count
= count_formal_params (fndecl
);
784 edge_count
= n_edges_for_fn (func
);
785 cfg_checksum
= coverage_compute_cfg_checksum (func
);
787 inchash::hash hstate
;
790 FOR_EACH_BB_FN (bb
, func
)
792 unsigned nondbg_stmt_count
= 0;
795 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
796 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
799 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
802 gimple stmt
= gsi_stmt (gsi
);
804 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
806 hash_stmt (&hstate
, stmt
);
811 gcode_hash
= hstate
.end ();
812 bb_sizes
.safe_push (nondbg_stmt_count
);
814 /* Inserting basic block to hash table. */
815 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
816 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
818 bb_sorted
.safe_push (semantic_bb
);
824 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
827 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
829 enum gimple_code code
= gimple_code (stmt
);
831 hstate
->add_int (code
);
833 if (code
== GIMPLE_CALL
)
835 /* Checking of argument. */
836 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
838 tree argument
= gimple_call_arg (stmt
, i
);
840 switch (TREE_CODE (argument
))
843 if (tree_fits_shwi_p (argument
))
844 hstate
->add_wide_int (tree_to_shwi (argument
));
845 else if (tree_fits_uhwi_p (argument
))
846 hstate
->add_wide_int (tree_to_uhwi (argument
));
852 c
= TREE_REAL_CST (argument
);
853 n
= real_to_integer (&c
);
855 hstate
->add_wide_int (n
);
859 tree addr_operand
= TREE_OPERAND (argument
, 0);
861 if (TREE_CODE (addr_operand
) == STRING_CST
)
862 hstate
->add (TREE_STRING_POINTER (addr_operand
),
863 TREE_STRING_LENGTH (addr_operand
));
874 /* Return true if polymorphic comparison must be processed. */
877 sem_function::compare_polymorphic_p (void)
879 return get_node ()->callees
!= NULL
880 || m_compared_func
->get_node ()->callees
!= NULL
;
883 /* For a given call graph NODE, the function constructs new
884 semantic function item. */
887 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
889 tree fndecl
= node
->decl
;
890 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
892 /* TODO: add support for thunks and aliases. */
894 if (!func
|| !node
->has_gimple_body_p ())
897 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
900 sem_function
*f
= new sem_function (node
, 0, stack
);
907 /* Parses function arguments and result type. */
910 sem_function::parse_tree_args (void)
914 if (arg_types
.exists ())
915 arg_types
.release ();
917 arg_types
.create (4);
918 tree fnargs
= DECL_ARGUMENTS (decl
);
920 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
921 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
923 /* Function result type. */
924 result
= DECL_RESULT (decl
);
925 result_type
= result
? TREE_TYPE (result
) : NULL
;
927 /* During WPA, we can get arguments by following method. */
930 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
931 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
932 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
934 result_type
= TREE_TYPE (TREE_TYPE (decl
));
938 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
939 return true if phi nodes are semantically equivalent in these blocks . */
942 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
944 gphi_iterator si1
, si2
;
946 unsigned size1
, size2
, i
;
950 gcc_assert (bb1
!= NULL
);
951 gcc_assert (bb2
!= NULL
);
953 si2
= gsi_start_phis (bb2
);
954 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
957 gsi_next_nonvirtual_phi (&si1
);
958 gsi_next_nonvirtual_phi (&si2
);
960 if (gsi_end_p (si1
) && gsi_end_p (si2
))
963 if (gsi_end_p (si1
) || gsi_end_p (si2
))
964 return return_false();
969 tree phi_result1
= gimple_phi_result (phi1
);
970 tree phi_result2
= gimple_phi_result (phi2
);
972 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
973 return return_false_with_msg ("PHI results are different");
975 size1
= gimple_phi_num_args (phi1
);
976 size2
= gimple_phi_num_args (phi2
);
979 return return_false ();
981 for (i
= 0; i
< size1
; ++i
)
983 t1
= gimple_phi_arg (phi1
, i
)->def
;
984 t2
= gimple_phi_arg (phi2
, i
)->def
;
986 if (!m_checker
->compare_operand (t1
, t2
))
987 return return_false ();
989 e1
= gimple_phi_arg_edge (phi1
, i
);
990 e2
= gimple_phi_arg_edge (phi2
, i
);
992 if (!m_checker
->compare_edge (e1
, e2
))
993 return return_false ();
1002 /* Returns true if tree T can be compared as a handled component. */
1005 sem_function::icf_handled_component_p (tree t
)
1007 tree_code tc
= TREE_CODE (t
);
1009 return ((handled_component_p (t
))
1010 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1011 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1014 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1015 corresponds to TARGET. */
1018 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
1023 if (bb_dict
.length () <= (unsigned)source
)
1024 bb_dict
.safe_grow_cleared (source
+ 1);
1026 if (bb_dict
[source
] == 0)
1028 bb_dict
[source
] = target
;
1032 return bb_dict
[source
] == target
;
1035 /* Iterates all tree types in T1 and T2 and returns true if all types
1036 are compatible. If COMPARE_POLYMORPHIC is set to true,
1037 more strict comparison is executed. */
1040 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1048 while (t1
!= NULL
&& t2
!= NULL
)
1050 tv1
= TREE_VALUE (t1
);
1051 tv2
= TREE_VALUE (t2
);
1053 tc1
= TREE_CODE (tv1
);
1054 tc2
= TREE_CODE (tv2
);
1056 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1058 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1060 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1063 t1
= TREE_CHAIN (t1
);
1064 t2
= TREE_CHAIN (t2
);
1071 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1073 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1077 /* Constructor based on varpool node _NODE with computed hash _HASH.
1078 Bitmap STACK is used for memory allocation. */
1080 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1081 bitmap_obstack
*stack
): sem_item(VAR
,
1084 gcc_checking_assert (node
);
1085 gcc_checking_assert (get_node ());
1088 /* Returns true if the item equals to ITEM given as argument. */
1091 sem_variable::equals (sem_item
*item
,
1092 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1094 gcc_assert (item
->type
== VAR
);
1096 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1098 if (!ctor
|| !v
->ctor
)
1099 return return_false_with_msg ("ctor is missing for semantic variable");
1101 return sem_variable::equals (ctor
, v
->ctor
);
1104 /* Compares trees T1 and T2 for semantic equality. */
1107 sem_variable::equals (tree t1
, tree t2
)
1109 tree_code tc1
= TREE_CODE (t1
);
1110 tree_code tc2
= TREE_CODE (t2
);
1119 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1120 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1125 for (unsigned i
= 0; i
< len1
; i
++)
1126 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1127 CONSTRUCTOR_ELT (t2
, i
)->value
)
1128 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1135 tree x1
= TREE_OPERAND (t1
, 0);
1136 tree x2
= TREE_OPERAND (t2
, 0);
1137 tree y1
= TREE_OPERAND (t1
, 1);
1138 tree y2
= TREE_OPERAND (t2
, 1);
1140 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1142 return return_false ();
1144 /* Type of the offset on MEM_REF does not matter. */
1145 return sem_variable::equals (x1
, x2
)
1146 && wi::to_offset (y1
) == wi::to_offset (y2
);
1151 tree op1
= TREE_OPERAND (t1
, 0);
1152 tree op2
= TREE_OPERAND (t2
, 0);
1153 return sem_variable::equals (op1
, op2
);
1161 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1163 && wi::to_offset (t1
) == wi::to_offset (t2
);
1167 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1170 case POINTER_PLUS_EXPR
:
1172 tree x1
= TREE_OPERAND (t1
, 0);
1173 tree x2
= TREE_OPERAND (t2
, 0);
1174 tree y1
= TREE_OPERAND (t1
, 1);
1175 tree y2
= TREE_OPERAND (t2
, 1);
1177 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1180 return return_false_with_msg ("ERROR_MARK");
1182 return return_false_with_msg ("Unknown TREE code reached");
1186 /* Parser function that visits a varpool NODE. */
1189 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1191 tree decl
= node
->decl
;
1193 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1197 bool can_handle
= DECL_VIRTUAL_P (decl
)
1198 || flag_merge_constants
>= 2
1199 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1201 if (!can_handle
|| DECL_EXTERNAL (decl
))
1204 tree ctor
= ctor_for_folding (decl
);
1208 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1215 /* References independent hash function. */
1218 sem_variable::get_hash (void)
1223 inchash::hash hstate
;
1225 hstate
.add_int (456346417);
1226 hstate
.add_int (TREE_CODE (ctor
));
1228 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1230 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1231 hstate
.add_int (length
);
1234 hash
= hstate
.end ();
1239 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1243 sem_variable::merge (sem_item
*alias_item
)
1245 gcc_assert (alias_item
->type
== VAR
);
1247 if (!sem_item::target_supports_symbol_aliases_p ())
1250 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1254 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1256 varpool_node
*original
= get_node ();
1257 varpool_node
*alias
= alias_var
->get_node ();
1258 bool original_discardable
= false;
1260 /* See if original is in a section that can be discarded if the main
1261 symbol is not used. */
1262 if (DECL_EXTERNAL (original
->decl
))
1263 original_discardable
= true;
1264 if (original
->resolution
== LDPR_PREEMPTED_REG
1265 || original
->resolution
== LDPR_PREEMPTED_IR
)
1266 original_discardable
= true;
1267 if (original
->can_be_discarded_p ())
1268 original_discardable
= true;
1270 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1272 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1273 !compare_sections (alias_var
))
1276 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1282 // alias cycle creation check
1283 varpool_node
*n
= original
;
1287 n
= n
->get_alias_target ();
1291 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1297 alias
->analyzed
= false;
1299 DECL_INITIAL (alias
->decl
) = NULL
;
1300 alias
->need_bounds_init
= false;
1301 alias
->remove_all_references ();
1303 varpool_node::create_alias (alias_var
->decl
, decl
);
1304 alias
->resolve_alias (original
);
1307 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1314 sem_variable::compare_sections (sem_variable
*alias
)
1316 const char *source
= node
->get_section ();
1317 const char *target
= alias
->node
->get_section();
1319 if (source
== NULL
&& target
== NULL
)
1321 else if(!source
|| !target
)
1324 return strcmp (source
, target
) == 0;
1327 /* Dump symbol to FILE. */
1330 sem_variable::dump_to_file (FILE *file
)
1334 print_node (file
, "", decl
, 0);
1335 fprintf (file
, "\n\n");
1338 /* Iterates though a constructor and identifies tree references
1339 we are interested in semantic function equality. */
1342 sem_variable::parse_tree_refs (tree t
)
1344 switch (TREE_CODE (t
))
1348 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1350 for (unsigned i
= 0; i
< length
; i
++)
1351 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1358 tree op
= TREE_OPERAND (t
, 0);
1359 parse_tree_refs (op
);
1364 tree_refs
.safe_push (t
);
1372 unsigned int sem_item_optimizer::class_id
= 0;
1374 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1375 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1378 bitmap_obstack_initialize (&m_bmstack
);
1381 sem_item_optimizer::~sem_item_optimizer ()
1383 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1386 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1387 it
!= m_classes
.end (); ++it
)
1389 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1390 delete (*it
)->classes
[i
];
1392 (*it
)->classes
.release ();
1398 bitmap_obstack_release (&m_bmstack
);
1401 /* Write IPA ICF summary for symbols. */
1404 sem_item_optimizer::write_summary (void)
1406 unsigned int count
= 0;
1408 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1409 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1412 /* Calculate number of symbols to be serialized. */
1413 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1415 lsei_next_in_partition (&lsei
))
1417 symtab_node
*node
= lsei_node (lsei
);
1419 if (m_symtab_node_map
.get (node
))
1423 streamer_write_uhwi (ob
, count
);
1425 /* Process all of the symbols. */
1426 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1428 lsei_next_in_partition (&lsei
))
1430 symtab_node
*node
= lsei_node (lsei
);
1432 sem_item
**item
= m_symtab_node_map
.get (node
);
1436 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1437 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1439 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1443 streamer_write_char_stream (ob
->main_stream
, 0);
1444 produce_asm (ob
, NULL
);
1445 destroy_output_block (ob
);
1448 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1449 contains LEN bytes. */
1452 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1453 const char *data
, size_t len
)
1455 const lto_function_header
*header
=
1456 (const lto_function_header
*) data
;
1457 const int cfg_offset
= sizeof (lto_function_header
);
1458 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1459 const int string_offset
= main_offset
+ header
->main_size
;
1464 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1468 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1469 header
->string_size
, vNULL
);
1471 count
= streamer_read_uhwi (&ib_main
);
1473 for (i
= 0; i
< count
; i
++)
1477 lto_symtab_encoder_t encoder
;
1479 index
= streamer_read_uhwi (&ib_main
);
1480 encoder
= file_data
->symtab_node_encoder
;
1481 node
= lto_symtab_encoder_deref (encoder
, index
);
1483 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1485 gcc_assert (node
->definition
);
1488 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1489 (void *) node
->decl
, node
->order
);
1491 if (is_a
<cgraph_node
*> (node
))
1493 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1495 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1499 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1501 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1505 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1507 lto_data_in_delete (data_in
);
1510 /* Read IPA IPA ICF summary for symbols. */
1513 sem_item_optimizer::read_summary (void)
1515 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1516 lto_file_decl_data
*file_data
;
1519 while ((file_data
= file_data_vec
[j
++]))
1522 const char *data
= lto_get_section_data (file_data
,
1523 LTO_section_ipa_icf
, NULL
, &len
);
1526 read_section (file_data
, data
, len
);
1530 /* Register callgraph and varpool hooks. */
1533 sem_item_optimizer::register_hooks (void)
1535 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1536 (&sem_item_optimizer::cgraph_removal_hook
, this);
1538 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1539 (&sem_item_optimizer::varpool_removal_hook
, this);
1542 /* Unregister callgraph and varpool hooks. */
1545 sem_item_optimizer::unregister_hooks (void)
1547 if (m_cgraph_node_hooks
)
1548 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1550 if (m_varpool_node_hooks
)
1551 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1554 /* Adds a CLS to hashtable associated by hash value. */
1557 sem_item_optimizer::add_class (congruence_class
*cls
)
1559 gcc_assert (cls
->members
.length ());
1561 congruence_class_group
*group
= get_group_by_hash (
1562 cls
->members
[0]->get_hash (),
1563 cls
->members
[0]->type
);
1564 group
->classes
.safe_push (cls
);
1567 /* Gets a congruence class group based on given HASH value and TYPE. */
1569 congruence_class_group
*
1570 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1572 congruence_class_group
*item
= XNEW (congruence_class_group
);
1576 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1582 item
->classes
.create (1);
1589 /* Callgraph removal hook called for a NODE with a custom DATA. */
1592 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1594 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1595 optimizer
->remove_symtab_node (node
);
1598 /* Varpool removal hook called for a NODE with a custom DATA. */
1601 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1603 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1604 optimizer
->remove_symtab_node (node
);
1607 /* Remove symtab NODE triggered by symtab removal hooks. */
1610 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1612 gcc_assert (!m_classes
.elements());
1614 m_removed_items_set
.add (node
);
1618 sem_item_optimizer::remove_item (sem_item
*item
)
1620 if (m_symtab_node_map
.get (item
->node
))
1621 m_symtab_node_map
.remove (item
->node
);
1625 /* Removes all callgraph and varpool nodes that are marked by symtab
1629 sem_item_optimizer::filter_removed_items (void)
1631 auto_vec
<sem_item
*> filtered
;
1633 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1635 sem_item
*item
= m_items
[i
];
1637 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1643 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1649 bool no_body_function
= false;
1651 if (item
->type
== FUNC
)
1653 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1655 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1658 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1659 && !no_body_function
)
1661 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1662 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1664 filtered
.safe_push (m_items
[i
]);
1672 /* Clean-up of released semantic items. */
1675 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1676 m_items
.safe_push (filtered
[i
]);
1679 /* Optimizer entry point. */
1682 sem_item_optimizer::execute (void)
1684 filter_removed_items ();
1685 build_hash_based_classes ();
1688 fprintf (dump_file
, "Dump after hash based groups\n");
1689 dump_cong_classes ();
1691 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1692 m_items
[i
]->init_wpa ();
1696 subdivide_classes_by_equality (true);
1699 fprintf (dump_file
, "Dump after WPA based types groups\n");
1701 dump_cong_classes ();
1703 process_cong_reduction ();
1707 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1709 dump_cong_classes ();
1711 parse_nonsingleton_classes ();
1712 subdivide_classes_by_equality ();
1715 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1717 dump_cong_classes ();
1719 unsigned int prev_class_count
= m_classes_count
;
1721 process_cong_reduction ();
1722 dump_cong_classes ();
1724 merge_classes (prev_class_count
);
1726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1727 symtab_node::dump_table (dump_file
);
1730 /* Function responsible for visiting all potential functions and
1731 read-only variables that can be merged. */
1734 sem_item_optimizer::parse_funcs_and_vars (void)
1738 if (flag_ipa_icf_functions
)
1739 FOR_EACH_DEFINED_FUNCTION (cnode
)
1741 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1744 m_items
.safe_push (f
);
1745 m_symtab_node_map
.put (cnode
, f
);
1748 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1751 f
->dump_to_file (dump_file
);
1754 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1757 varpool_node
*vnode
;
1759 if (flag_ipa_icf_variables
)
1760 FOR_EACH_DEFINED_VARIABLE (vnode
)
1762 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1766 m_items
.safe_push (v
);
1767 m_symtab_node_map
.put (vnode
, v
);
1772 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1775 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1777 item
->index_in_class
= cls
->members
.length ();
1778 cls
->members
.safe_push (item
);
1782 /* Congruence classes are built by hash value. */
1785 sem_item_optimizer::build_hash_based_classes (void)
1787 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1789 sem_item
*item
= m_items
[i
];
1791 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1794 if (!group
->classes
.length ())
1797 group
->classes
.safe_push (new congruence_class (class_id
++));
1800 add_item_to_class (group
->classes
[0], item
);
1804 /* Build references according to call graph. */
1807 sem_item_optimizer::build_graph (void)
1809 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1811 sem_item
*item
= m_items
[i
];
1812 m_symtab_node_map
.put (item
->node
, item
);
1815 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1817 sem_item
*item
= m_items
[i
];
1819 if (item
->type
== FUNC
)
1821 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1823 cgraph_edge
*e
= cnode
->callees
;
1826 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1828 item
->add_reference (*slot
);
1834 ipa_ref
*ref
= NULL
;
1835 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1837 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1839 item
->add_reference (*slot
);
1844 /* Semantic items in classes having more than one element and initialized.
1845 In case of WPA, we load function body. */
1848 sem_item_optimizer::parse_nonsingleton_classes (void)
1850 unsigned int init_called_count
= 0;
1852 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1853 if (m_items
[i
]->cls
->members
.length () > 1)
1855 m_items
[i
]->init ();
1856 init_called_count
++;
1860 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1861 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1864 /* Equality function for semantic items is used to subdivide existing
1865 classes. If IN_WPA, fast equality function is invoked. */
1868 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1870 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1871 it
!= m_classes
.end (); ++it
)
1873 unsigned int class_count
= (*it
)->classes
.length ();
1875 for (unsigned i
= 0; i
< class_count
; i
++)
1877 congruence_class
*c
= (*it
)->classes
[i
];
1879 if (c
->members
.length() > 1)
1881 auto_vec
<sem_item
*> new_vector
;
1883 sem_item
*first
= c
->members
[0];
1884 new_vector
.safe_push (first
);
1886 unsigned class_split_first
= (*it
)->classes
.length ();
1888 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1890 sem_item
*item
= c
->members
[j
];
1892 bool equals
= in_wpa
? first
->equals_wpa (item
,
1893 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1896 new_vector
.safe_push (item
);
1899 bool integrated
= false;
1901 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1903 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1904 bool equals
= in_wpa
? x
->equals_wpa (item
,
1905 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1910 add_item_to_class ((*it
)->classes
[k
], item
);
1918 congruence_class
*c
= new congruence_class (class_id
++);
1920 add_item_to_class (c
, item
);
1922 (*it
)->classes
.safe_push (c
);
1927 // we replace newly created new_vector for the class we've just splitted
1928 c
->members
.release ();
1929 c
->members
.create (new_vector
.length ());
1931 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1932 add_item_to_class (c
, new_vector
[j
]);
1940 /* Verify congruence classes if checking is enabled. */
1943 sem_item_optimizer::verify_classes (void)
1946 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1947 it
!= m_classes
.end (); ++it
)
1949 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1951 congruence_class
*cls
= (*it
)->classes
[i
];
1953 gcc_checking_assert (cls
);
1954 gcc_checking_assert (cls
->members
.length () > 0);
1956 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1958 sem_item
*item
= cls
->members
[j
];
1960 gcc_checking_assert (item
);
1961 gcc_checking_assert (item
->cls
== cls
);
1963 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1965 sem_usage_pair
*usage
= item
->usages
[k
];
1966 gcc_checking_assert (usage
->item
->index_in_class
<
1967 usage
->item
->cls
->members
.length ());
1975 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1976 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1977 but unused argument. */
1980 sem_item_optimizer::release_split_map (congruence_class
* const &,
1981 bitmap
const &b
, traverse_split_pair
*)
1990 /* Process split operation for a class given as pointer CLS_PTR,
1991 where bitmap B splits congruence class members. DATA is used
1992 as argument of split pair. */
1995 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1996 bitmap
const &b
, traverse_split_pair
*pair
)
1998 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1999 const congruence_class
*splitter_cls
= pair
->cls
;
2001 /* If counted bits are greater than zero and less than the number of members
2002 a group will be splitted. */
2003 unsigned popcount
= bitmap_count_bits (b
);
2005 if (popcount
> 0 && popcount
< cls
->members
.length ())
2007 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2009 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2011 int target
= bitmap_bit_p (b
, i
);
2012 congruence_class
*tc
= newclasses
[target
];
2014 add_item_to_class (tc
, cls
->members
[i
]);
2017 #ifdef ENABLE_CHECKING
2018 for (unsigned int i
= 0; i
< 2; i
++)
2019 gcc_checking_assert (newclasses
[i
]->members
.length ());
2022 if (splitter_cls
== cls
)
2023 optimizer
->splitter_class_removed
= true;
2025 /* Remove old class from worklist if presented. */
2026 bool in_worklist
= cls
->in_worklist
;
2029 cls
->in_worklist
= false;
2031 congruence_class_group g
;
2032 g
.hash
= cls
->members
[0]->get_hash ();
2033 g
.type
= cls
->members
[0]->type
;
2035 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2037 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2038 if (slot
->classes
[i
] == cls
)
2040 slot
->classes
.ordered_remove (i
);
2044 /* New class will be inserted and integrated to work list. */
2045 for (unsigned int i
= 0; i
< 2; i
++)
2046 optimizer
->add_class (newclasses
[i
]);
2048 /* Two classes replace one, so that increment just by one. */
2049 optimizer
->m_classes_count
++;
2051 /* If OLD class was presented in the worklist, we remove the class
2052 and replace it will both newly created classes. */
2054 for (unsigned int i
= 0; i
< 2; i
++)
2055 optimizer
->worklist_push (newclasses
[i
]);
2056 else /* Just smaller class is inserted. */
2058 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2059 newclasses
[1]->members
.length () ?
2061 optimizer
->worklist_push (newclasses
[smaller_index
]);
2064 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2066 fprintf (dump_file
, " congruence class splitted:\n");
2067 cls
->dump (dump_file
, 4);
2069 fprintf (dump_file
, " newly created groups:\n");
2070 for (unsigned int i
= 0; i
< 2; i
++)
2071 newclasses
[i
]->dump (dump_file
, 4);
2074 /* Release class if not presented in work list. */
2083 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2084 Bitmap stack BMSTACK is used for bitmap allocation. */
2087 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2090 hash_map
<congruence_class
*, bitmap
> split_map
;
2092 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2094 sem_item
*item
= cls
->members
[i
];
2096 /* Iterate all usages that have INDEX as usage of the item. */
2097 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2099 sem_usage_pair
*usage
= item
->usages
[j
];
2101 if (usage
->index
!= index
)
2104 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2109 b
= BITMAP_ALLOC (&m_bmstack
);
2110 split_map
.put (usage
->item
->cls
, b
);
2116 gcc_checking_assert (usage
->item
->cls
);
2117 gcc_checking_assert (usage
->item
->index_in_class
<
2118 usage
->item
->cls
->members
.length ());
2121 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2125 traverse_split_pair pair
;
2126 pair
.optimizer
= this;
2129 splitter_class_removed
= false;
2131 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2133 /* Bitmap clean-up. */
2135 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2138 /* Every usage of a congruence class CLS is a candidate that can split the
2139 collection of classes. Bitmap stack BMSTACK is used for bitmap
2143 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2148 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2150 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2151 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2153 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2156 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2159 do_congruence_step_for_index (cls
, i
);
2161 if (splitter_class_removed
)
2165 BITMAP_FREE (usage
);
2168 /* Adds a newly created congruence class CLS to worklist. */
2171 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2173 /* Return if the class CLS is already presented in work list. */
2174 if (cls
->in_worklist
)
2177 cls
->in_worklist
= true;
2178 worklist
.push_back (cls
);
2181 /* Pops a class from worklist. */
2184 sem_item_optimizer::worklist_pop (void)
2186 congruence_class
*cls
;
2188 while (!worklist
.empty ())
2190 cls
= worklist
.front ();
2191 worklist
.pop_front ();
2192 if (cls
->in_worklist
)
2194 cls
->in_worklist
= false;
2200 /* Work list item was already intended to be removed.
2201 The only reason for doing it is to split a class.
2202 Thus, the class CLS is deleted. */
2210 /* Iterative congruence reduction function. */
2213 sem_item_optimizer::process_cong_reduction (void)
2215 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2216 it
!= m_classes
.end (); ++it
)
2217 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2218 if ((*it
)->classes
[i
]->is_class_used ())
2219 worklist_push ((*it
)->classes
[i
]);
2222 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2223 (unsigned long) worklist
.size ());
2225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2226 fprintf (dump_file
, "Congruence class reduction\n");
2228 congruence_class
*cls
;
2229 while ((cls
= worklist_pop ()) != NULL
)
2230 do_congruence_step (cls
);
2233 /* Debug function prints all informations about congruence classes. */
2236 sem_item_optimizer::dump_cong_classes (void)
2242 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2243 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2245 /* Histogram calculation. */
2246 unsigned int max_index
= 0;
2247 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2249 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2250 it
!= m_classes
.end (); ++it
)
2252 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2254 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2262 "Class size histogram [num of members]: number of classe number of classess\n");
2264 for (unsigned int i
= 0; i
<= max_index
; i
++)
2266 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2268 fprintf (dump_file
, "\n\n");
2271 if (dump_flags
& TDF_DETAILS
)
2272 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2273 it
!= m_classes
.end (); ++it
)
2275 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2277 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2279 (*it
)->classes
[i
]->dump (dump_file
, 4);
2281 if(i
< (*it
)->classes
.length () - 1)
2282 fprintf (dump_file
, " ");
2289 /* After reduction is done, we can declare all items in a group
2290 to be equal. PREV_CLASS_COUNT is start number of classes
2291 before reduction. */
2294 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2296 unsigned int item_count
= m_items
.length ();
2297 unsigned int class_count
= m_classes_count
;
2298 unsigned int equal_items
= item_count
- class_count
;
2300 unsigned int non_singular_classes_count
= 0;
2301 unsigned int non_singular_classes_sum
= 0;
2303 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2304 it
!= m_classes
.end (); ++it
)
2305 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2307 congruence_class
*c
= (*it
)->classes
[i
];
2308 if (c
->members
.length () > 1)
2310 non_singular_classes_count
++;
2311 non_singular_classes_sum
+= c
->members
.length ();
2317 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2318 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2319 prev_class_count
, class_count
);
2320 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2321 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2322 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2323 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2324 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2325 non_singular_classes_count
: 0.0f
,
2326 non_singular_classes_count
);
2327 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2328 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2329 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2332 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2333 it
!= m_classes
.end (); ++it
)
2334 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2336 congruence_class
*c
= (*it
)->classes
[i
];
2338 if (c
->members
.length () == 1)
2341 gcc_assert (c
->members
.length ());
2343 sem_item
*source
= c
->members
[0];
2345 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2347 sem_item
*alias
= c
->members
[j
];
2351 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2352 source
->name (), alias
->name ());
2353 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2354 source
->asm_name (), alias
->asm_name ());
2357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2359 source
->dump_to_file (dump_file
);
2360 alias
->dump_to_file (dump_file
);
2363 source
->merge (alias
);
2368 /* Dump function prints all class members to a FILE with an INDENT. */
2371 congruence_class::dump (FILE *file
, unsigned int indent
) const
2373 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2374 id
, members
[0]->get_hash (), members
.length ());
2376 FPUTS_SPACES (file
, indent
+ 2, "");
2377 for (unsigned i
= 0; i
< members
.length (); i
++)
2378 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2379 members
[i
]->node
->order
);
2381 fprintf (file
, "\n");
2384 /* Returns true if there's a member that is used from another group. */
2387 congruence_class::is_class_used (void)
2389 for (unsigned int i
= 0; i
< members
.length (); i
++)
2390 if (members
[i
]->usages
.length ())
2396 /* Initialization and computation of symtab node hash, there data
2397 are propagated later on. */
2399 static sem_item_optimizer
*optimizer
= NULL
;
2401 /* Generate pass summary for IPA ICF pass. */
2404 ipa_icf_generate_summary (void)
2407 optimizer
= new sem_item_optimizer ();
2409 optimizer
->parse_funcs_and_vars ();
2412 /* Write pass summary for IPA ICF pass. */
2415 ipa_icf_write_summary (void)
2417 gcc_assert (optimizer
);
2419 optimizer
->write_summary ();
2422 /* Read pass summary for IPA ICF pass. */
2425 ipa_icf_read_summary (void)
2428 optimizer
= new sem_item_optimizer ();
2430 optimizer
->read_summary ();
2431 optimizer
->register_hooks ();
2434 /* Semantic equality exection function. */
2437 ipa_icf_driver (void)
2439 gcc_assert (optimizer
);
2441 optimizer
->execute ();
2442 optimizer
->unregister_hooks ();
2450 const pass_data pass_data_ipa_icf
=
2452 IPA_PASS
, /* type */
2454 OPTGROUP_IPA
, /* optinfo_flags */
2455 TV_IPA_ICF
, /* tv_id */
2456 0, /* properties_required */
2457 0, /* properties_provided */
2458 0, /* properties_destroyed */
2459 0, /* todo_flags_start */
2460 0, /* todo_flags_finish */
2463 class pass_ipa_icf
: public ipa_opt_pass_d
2466 pass_ipa_icf (gcc::context
*ctxt
)
2467 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2468 ipa_icf_generate_summary
, /* generate_summary */
2469 ipa_icf_write_summary
, /* write_summary */
2470 ipa_icf_read_summary
, /* read_summary */
2472 write_optimization_summary */
2474 read_optimization_summary */
2475 NULL
, /* stmt_fixup */
2476 0, /* function_transform_todo_flags_start */
2477 NULL
, /* function_transform */
2478 NULL
) /* variable_transform */
2481 /* opt_pass methods: */
2482 virtual bool gate (function
*)
2484 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2487 virtual unsigned int execute (function
*)
2489 return ipa_icf_driver();
2491 }; // class pass_ipa_icf
2493 } // ipa_icf namespace
2496 make_pass_ipa_icf (gcc::context
*ctxt
)
2498 return new ipa_icf::pass_ipa_icf (ctxt
);