1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014 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"
91 #include "ipa-inline.h"
94 #include "hash-table.h"
97 #include "print-tree.h"
98 #include "lto-streamer.h"
99 #include "data-streamer.h"
100 #include "ipa-utils.h"
102 #include "ipa-icf-gimple.h"
105 using namespace ipa_icf_gimple
;
108 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
110 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
111 item (_item
), index (_index
)
115 /* Semantic item constructor for a node of _TYPE, where STACK is used
116 for bitmap memory allocation. */
118 sem_item::sem_item (sem_item_type _type
,
119 bitmap_obstack
*stack
): type(_type
), hash(0)
124 /* Semantic item constructor for a node of _TYPE, where STACK is used
125 for bitmap memory allocation. The item is based on symtab node _NODE
126 with computed _HASH. */
128 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
129 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
130 node (_node
), hash (_hash
)
136 /* Add reference to a semantic TARGET. */
139 sem_item::add_reference (sem_item
*target
)
141 refs
.safe_push (target
);
142 unsigned index
= refs
.length ();
143 target
->usages
.safe_push (new sem_usage_pair(this, index
));
144 bitmap_set_bit (target
->usage_index_bitmap
, index
);
145 refs_set
.add (target
->node
);
148 /* Initialize internal data structures. Bitmap STACK is used for
149 bitmap memory allocation process. */
152 sem_item::setup (bitmap_obstack
*stack
)
154 gcc_checking_assert (node
);
157 tree_refs
.create (0);
159 usage_index_bitmap
= BITMAP_ALLOC (stack
);
162 sem_item::~sem_item ()
164 for (unsigned i
= 0; i
< usages
.length (); i
++)
168 tree_refs
.release ();
171 BITMAP_FREE (usage_index_bitmap
);
174 /* Dump function for debugging purpose. */
177 sem_item::dump (void)
181 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
182 name(), node
->order
, (void *) node
->decl
);
183 fprintf (dump_file
, " hash: %u\n", get_hash ());
184 fprintf (dump_file
, " references: ");
186 for (unsigned i
= 0; i
< refs
.length (); i
++)
187 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
188 i
< refs
.length() - 1 ? "," : "");
190 fprintf (dump_file
, "\n");
194 /* Return true if target supports alias symbols. */
197 sem_item::target_supports_symbol_aliases_p (void)
199 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
206 /* Semantic function constructor that uses STACK as bitmap memory stack. */
208 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
209 m_checker (NULL
), m_compared_func (NULL
)
211 arg_types
.create (0);
213 bb_sorted
.create (0);
216 /* Constructor based on callgraph node _NODE with computed hash _HASH.
217 Bitmap STACK is used for memory allocation. */
218 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
219 bitmap_obstack
*stack
):
220 sem_item (FUNC
, node
, hash
, stack
),
221 m_checker (NULL
), m_compared_func (NULL
)
223 arg_types
.create (0);
225 bb_sorted
.create (0);
228 sem_function::~sem_function ()
230 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
231 delete (bb_sorted
[i
]);
233 arg_types
.release ();
235 bb_sorted
.release ();
238 /* Calculates hash value based on a BASIC_BLOCK. */
241 sem_function::get_bb_hash (const sem_bb
*basic_block
)
243 inchash::hash hstate
;
245 hstate
.add_int (basic_block
->nondbg_stmt_count
);
246 hstate
.add_int (basic_block
->edge_count
);
248 return hstate
.end ();
251 /* References independent hash function. */
254 sem_function::get_hash (void)
258 inchash::hash hstate
;
259 hstate
.add_int (177454); /* Random number for function type. */
261 hstate
.add_int (arg_count
);
262 hstate
.add_int (cfg_checksum
);
263 hstate
.add_int (gcode_hash
);
265 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
266 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
268 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
269 hstate
.add_int (bb_sizes
[i
]);
271 hash
= hstate
.end ();
277 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
278 point to a same function. Comparison can be skipped if IGNORED_NODES
279 contains these nodes. */
282 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
284 symtab_node
*n1
, symtab_node
*n2
)
286 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
289 /* TODO: add more precise comparison for weakrefs, etc. */
291 return return_false_with_msg ("different references");
294 /* If cgraph edges E1 and E2 are indirect calls, verify that
295 ECF flags are the same. */
297 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
299 if (e1
->indirect_info
&& e2
->indirect_info
)
301 int e1_flags
= e1
->indirect_info
->ecf_flags
;
302 int e2_flags
= e2
->indirect_info
->ecf_flags
;
304 if (e1_flags
!= e2_flags
)
305 return return_false_with_msg ("ICF flags are different");
307 else if (e1
->indirect_info
|| e2
->indirect_info
)
313 /* Fast equality function based on knowledge known in WPA. */
316 sem_function::equals_wpa (sem_item
*item
,
317 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
319 gcc_assert (item
->type
== FUNC
);
321 m_compared_func
= static_cast<sem_function
*> (item
);
323 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
324 return return_false_with_msg ("different number of arguments");
326 /* Checking types of arguments. */
327 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
329 /* This guard is here for function pointer with attributes (pr59927.c). */
330 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
331 return return_false_with_msg ("NULL argument type");
333 /* Polymorphic comparison is executed just for non-leaf functions. */
334 bool is_not_leaf
= get_node ()->callees
!= NULL
;
336 if (!func_checker::compatible_types_p (arg_types
[i
],
337 m_compared_func
->arg_types
[i
],
338 is_not_leaf
, i
== 0))
339 return return_false_with_msg ("argument type is different");
342 /* Result type checking. */
343 if (!func_checker::compatible_types_p (result_type
,
344 m_compared_func
->result_type
))
345 return return_false_with_msg ("result types are different");
347 if (node
->num_references () != item
->node
->num_references ())
348 return return_false_with_msg ("different number of references");
350 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
351 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
353 item
->node
->iterate_reference (i
, ref2
);
355 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
359 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
360 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
364 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
367 e1
= e1
->next_callee
;
368 e2
= e2
->next_callee
;
372 return return_false_with_msg ("different number of edges");
377 /* Returns true if the item equals to ITEM given as argument. */
380 sem_function::equals (sem_item
*item
,
381 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
383 gcc_assert (item
->type
== FUNC
);
384 bool eq
= equals_private (item
, ignored_nodes
);
386 if (m_checker
!= NULL
)
392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
394 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
395 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
396 item
->asm_name (), eq
? "true" : "false");
401 /* Processes function equality comparison. */
404 sem_function::equals_private (sem_item
*item
,
405 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
407 if (item
->type
!= FUNC
)
410 basic_block bb1
, bb2
;
412 edge_iterator ei1
, ei2
;
416 m_compared_func
= static_cast<sem_function
*> (item
);
418 gcc_assert (decl
!= item
->decl
);
420 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
421 || edge_count
!= m_compared_func
->edge_count
422 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
423 return return_false ();
425 if (!equals_wpa (item
, ignored_nodes
))
428 /* Checking function arguments. */
429 tree decl1
= DECL_ATTRIBUTES (decl
);
430 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
432 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
433 compare_polymorphic_p (),
436 &m_compared_func
->refs_set
);
440 return return_false ();
442 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
443 return return_false ();
445 tree attr_value1
= TREE_VALUE (decl1
);
446 tree attr_value2
= TREE_VALUE (decl2
);
448 if (attr_value1
&& attr_value2
)
450 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
451 TREE_VALUE (attr_value2
));
453 return return_false_with_msg ("attribute values are different");
455 else if (!attr_value1
&& !attr_value2
)
458 return return_false ();
460 decl1
= TREE_CHAIN (decl1
);
461 decl2
= TREE_CHAIN (decl2
);
465 return return_false();
468 for (arg1
= DECL_ARGUMENTS (decl
),
469 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
470 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
471 if (!m_checker
->compare_decl (arg1
, arg2
))
472 return return_false ();
474 /* Fill-up label dictionary. */
475 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
477 m_checker
->parse_labels (bb_sorted
[i
]);
478 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
481 /* Checking all basic blocks. */
482 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
483 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
484 return return_false();
486 dump_message ("All BBs are equal\n");
488 auto_vec
<int> bb_dict
;
490 /* Basic block edges check. */
491 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
493 bb1
= bb_sorted
[i
]->bb
;
494 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
496 ei2
= ei_start (bb2
->preds
);
498 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
502 if (e1
->flags
!= e2
->flags
)
503 return return_false_with_msg ("flags comparison returns false");
505 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
506 return return_false_with_msg ("edge comparison returns false");
508 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
509 return return_false_with_msg ("BB comparison returns false");
511 if (!m_checker
->compare_edge (e1
, e2
))
512 return return_false_with_msg ("edge comparison returns false");
518 /* Basic block PHI nodes comparison. */
519 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
520 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
521 return return_false_with_msg ("PHI node comparison returns false");
526 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
529 sem_function::merge (sem_item
*alias_item
)
531 gcc_assert (alias_item
->type
== FUNC
);
533 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
535 cgraph_node
*original
= get_node ();
536 cgraph_node
*local_original
= original
;
537 cgraph_node
*alias
= alias_func
->get_node ();
538 bool original_address_matters
;
539 bool alias_address_matters
;
541 bool create_thunk
= false;
542 bool create_alias
= false;
543 bool redirect_callers
= false;
544 bool original_discardable
= false;
546 /* Do not attempt to mix functions from different user sections;
547 we do not know what user intends with those. */
548 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
549 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
550 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
554 "Not unifying; original and alias are in different sections.\n\n");
558 /* See if original is in a section that can be discarded if the main
559 symbol is not used. */
560 if (DECL_EXTERNAL (original
->decl
))
561 original_discardable
= true;
562 if (original
->resolution
== LDPR_PREEMPTED_REG
563 || original
->resolution
== LDPR_PREEMPTED_IR
)
564 original_discardable
= true;
565 if (original
->can_be_discarded_p ())
566 original_discardable
= true;
568 /* See if original and/or alias address can be compared for equality. */
569 original_address_matters
570 = (!DECL_VIRTUAL_P (original
->decl
)
571 && (original
->externally_visible
572 || original
->address_taken_from_non_vtable_p ()));
573 alias_address_matters
574 = (!DECL_VIRTUAL_P (alias
->decl
)
575 && (alias
->externally_visible
576 || alias
->address_taken_from_non_vtable_p ()));
578 /* If alias and original can be compared for address equality, we need
579 to create a thunk. Also we can not create extra aliases into discardable
580 section (or we risk link failures when section is discarded). */
581 if ((original_address_matters
582 && alias_address_matters
)
583 || original_discardable
)
585 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
586 create_alias
= false;
587 /* When both alias and original are not overwritable, we can save
588 the extra thunk wrapper for direct calls. */
590 = (!original_discardable
591 && alias
->get_availability () > AVAIL_INTERPOSABLE
592 && original
->get_availability () > AVAIL_INTERPOSABLE
593 && !alias
->instrumented_version
);
598 create_thunk
= false;
599 redirect_callers
= false;
602 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
603 || !sem_item::target_supports_symbol_aliases_p ()))
605 create_alias
= false;
609 /* We want thunk to always jump to the local function body
610 unless the body is comdat and may be optimized out. */
611 if ((create_thunk
|| redirect_callers
)
612 && (!original_discardable
613 || (DECL_COMDAT_GROUP (original
->decl
)
614 && (DECL_COMDAT_GROUP (original
->decl
)
615 == DECL_COMDAT_GROUP (alias
->decl
)))))
617 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
622 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
627 if (redirect_callers
)
629 /* If alias is non-overwritable then
630 all direct calls are safe to be redirected to the original. */
631 bool redirected
= false;
632 while (alias
->callers
)
634 cgraph_edge
*e
= alias
->callers
;
635 e
->redirect_callee (local_original
);
636 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
639 e
->redirect_call_stmt_to_callee ();
645 alias
->icf_merged
= true;
647 /* The alias function is removed if symbol address
649 if (!alias_address_matters
)
652 if (dump_file
&& redirected
)
653 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
655 /* If the condtion above is not met, we are lucky and can turn the
656 function into real alias. */
657 else if (create_alias
)
659 alias
->icf_merged
= true;
661 /* Remove the function's body. */
662 ipa_merge_profiles (original
, alias
);
663 alias
->release_body (true);
666 /* Create the alias. */
667 cgraph_node::create_alias (alias_func
->decl
, decl
);
668 alias
->resolve_alias (original
);
670 /* Workaround for PR63566 that forces equal calling convention
672 alias
->local
.local
= false;
673 original
->local
.local
= false;
676 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
678 else if (create_thunk
)
680 if (DECL_COMDAT_GROUP (alias
->decl
))
683 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
688 alias
->icf_merged
= true;
689 ipa_merge_profiles (local_original
, alias
);
690 alias
->create_wrapper (local_original
);
693 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
696 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
701 /* Semantic item initialization function. */
704 sem_function::init (void)
707 get_node ()->get_untransformed_body ();
709 tree fndecl
= node
->decl
;
710 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
713 gcc_assert (SSANAMES (func
));
715 ssa_names_size
= SSANAMES (func
)->length ();
719 region_tree
= func
->eh
->region_tree
;
721 /* iterating all function arguments. */
722 arg_count
= count_formal_params (fndecl
);
724 edge_count
= n_edges_for_fn (func
);
725 cfg_checksum
= coverage_compute_cfg_checksum (func
);
727 inchash::hash hstate
;
730 FOR_EACH_BB_FN (bb
, func
)
732 unsigned nondbg_stmt_count
= 0;
735 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
736 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
739 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
742 gimple stmt
= gsi_stmt (gsi
);
744 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
746 hash_stmt (&hstate
, stmt
);
751 gcode_hash
= hstate
.end ();
752 bb_sizes
.safe_push (nondbg_stmt_count
);
754 /* Inserting basic block to hash table. */
755 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
756 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
758 bb_sorted
.safe_push (semantic_bb
);
764 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
767 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
769 enum gimple_code code
= gimple_code (stmt
);
771 hstate
->add_int (code
);
773 if (code
== GIMPLE_CALL
)
775 /* Checking of argument. */
776 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
778 tree argument
= gimple_call_arg (stmt
, i
);
780 switch (TREE_CODE (argument
))
783 if (tree_fits_shwi_p (argument
))
784 hstate
->add_wide_int (tree_to_shwi (argument
));
785 else if (tree_fits_uhwi_p (argument
))
786 hstate
->add_wide_int (tree_to_uhwi (argument
));
792 c
= TREE_REAL_CST (argument
);
793 n
= real_to_integer (&c
);
795 hstate
->add_wide_int (n
);
799 tree addr_operand
= TREE_OPERAND (argument
, 0);
801 if (TREE_CODE (addr_operand
) == STRING_CST
)
802 hstate
->add (TREE_STRING_POINTER (addr_operand
),
803 TREE_STRING_LENGTH (addr_operand
));
814 /* Return true if polymorphic comparison must be processed. */
817 sem_function::compare_polymorphic_p (void)
819 return get_node ()->callees
!= NULL
820 || m_compared_func
->get_node ()->callees
!= NULL
;
823 /* For a given call graph NODE, the function constructs new
824 semantic function item. */
827 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
829 tree fndecl
= node
->decl
;
830 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
832 /* TODO: add support for thunks and aliases. */
834 if (!func
|| !node
->has_gimple_body_p ())
837 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
840 sem_function
*f
= new sem_function (node
, 0, stack
);
847 /* Parses function arguments and result type. */
850 sem_function::parse_tree_args (void)
854 if (arg_types
.exists ())
855 arg_types
.release ();
857 arg_types
.create (4);
858 tree fnargs
= DECL_ARGUMENTS (decl
);
860 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
861 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
863 /* Function result type. */
864 result
= DECL_RESULT (decl
);
865 result_type
= result
? TREE_TYPE (result
) : NULL
;
867 /* During WPA, we can get arguments by following method. */
870 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
871 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
872 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
874 result_type
= TREE_TYPE (TREE_TYPE (decl
));
878 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
879 return true if phi nodes are semantically equivalent in these blocks . */
882 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
884 gphi_iterator si1
, si2
;
886 unsigned size1
, size2
, i
;
890 gcc_assert (bb1
!= NULL
);
891 gcc_assert (bb2
!= NULL
);
893 si2
= gsi_start_phis (bb2
);
894 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
897 gsi_next_nonvirtual_phi (&si1
);
898 gsi_next_nonvirtual_phi (&si2
);
900 if (gsi_end_p (si1
) && gsi_end_p (si2
))
903 if (gsi_end_p (si1
) || gsi_end_p (si2
))
904 return return_false();
909 tree phi_result1
= gimple_phi_result (phi1
);
910 tree phi_result2
= gimple_phi_result (phi2
);
912 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
913 return return_false_with_msg ("PHI results are different");
915 size1
= gimple_phi_num_args (phi1
);
916 size2
= gimple_phi_num_args (phi2
);
919 return return_false ();
921 for (i
= 0; i
< size1
; ++i
)
923 t1
= gimple_phi_arg (phi1
, i
)->def
;
924 t2
= gimple_phi_arg (phi2
, i
)->def
;
926 if (!m_checker
->compare_operand (t1
, t2
))
927 return return_false ();
929 e1
= gimple_phi_arg_edge (phi1
, i
);
930 e2
= gimple_phi_arg_edge (phi2
, i
);
932 if (!m_checker
->compare_edge (e1
, e2
))
933 return return_false ();
942 /* Returns true if tree T can be compared as a handled component. */
945 sem_function::icf_handled_component_p (tree t
)
947 tree_code tc
= TREE_CODE (t
);
949 return ((handled_component_p (t
))
950 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
951 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
954 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
955 corresponds to TARGET. */
958 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
963 if (bb_dict
.length () <= (unsigned)source
)
964 bb_dict
.safe_grow_cleared (source
+ 1);
966 if (bb_dict
[source
] == 0)
968 bb_dict
[source
] = target
;
972 return bb_dict
[source
] == target
;
975 /* Iterates all tree types in T1 and T2 and returns true if all types
976 are compatible. If COMPARE_POLYMORPHIC is set to true,
977 more strict comparison is executed. */
980 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
988 while (t1
!= NULL
&& t2
!= NULL
)
990 tv1
= TREE_VALUE (t1
);
991 tv2
= TREE_VALUE (t2
);
993 tc1
= TREE_CODE (tv1
);
994 tc2
= TREE_CODE (tv2
);
996 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
998 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1000 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1003 t1
= TREE_CHAIN (t1
);
1004 t2
= TREE_CHAIN (t2
);
1011 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1013 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1017 /* Constructor based on varpool node _NODE with computed hash _HASH.
1018 Bitmap STACK is used for memory allocation. */
1020 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1021 bitmap_obstack
*stack
): sem_item(VAR
,
1024 gcc_checking_assert (node
);
1025 gcc_checking_assert (get_node ());
1028 /* Returns true if the item equals to ITEM given as argument. */
1031 sem_variable::equals (sem_item
*item
,
1032 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1034 gcc_assert (item
->type
== VAR
);
1036 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1038 if (!ctor
|| !v
->ctor
)
1039 return return_false_with_msg ("ctor is missing for semantic variable");
1041 return sem_variable::equals (ctor
, v
->ctor
);
1044 /* Compares trees T1 and T2 for semantic equality. */
1047 sem_variable::equals (tree t1
, tree t2
)
1049 tree_code tc1
= TREE_CODE (t1
);
1050 tree_code tc2
= TREE_CODE (t2
);
1059 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1060 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1065 for (unsigned i
= 0; i
< len1
; i
++)
1066 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1067 CONSTRUCTOR_ELT (t2
, i
)->value
)
1068 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1075 tree x1
= TREE_OPERAND (t1
, 0);
1076 tree x2
= TREE_OPERAND (t2
, 0);
1077 tree y1
= TREE_OPERAND (t1
, 1);
1078 tree y2
= TREE_OPERAND (t2
, 1);
1080 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1082 return return_false ();
1084 /* Type of the offset on MEM_REF does not matter. */
1085 return sem_variable::equals (x1
, x2
)
1086 && wi::to_offset (y1
) == wi::to_offset (y2
);
1091 tree op1
= TREE_OPERAND (t1
, 0);
1092 tree op2
= TREE_OPERAND (t2
, 0);
1093 return sem_variable::equals (op1
, op2
);
1101 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1103 && wi::to_offset (t1
) == wi::to_offset (t2
);
1107 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1110 case POINTER_PLUS_EXPR
:
1112 tree x1
= TREE_OPERAND (t1
, 0);
1113 tree x2
= TREE_OPERAND (t2
, 0);
1114 tree y1
= TREE_OPERAND (t1
, 1);
1115 tree y2
= TREE_OPERAND (t2
, 1);
1117 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1120 return return_false_with_msg ("ERROR_MARK");
1122 return return_false_with_msg ("Unknown TREE code reached");
1126 /* Parser function that visits a varpool NODE. */
1129 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1131 tree decl
= node
->decl
;
1133 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1134 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1135 || !TREE_ADDRESSABLE (decl
));
1140 tree ctor
= ctor_for_folding (decl
);
1144 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1151 /* References independent hash function. */
1154 sem_variable::get_hash (void)
1159 inchash::hash hstate
;
1161 hstate
.add_int (456346417);
1162 hstate
.add_int (TREE_CODE (ctor
));
1164 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1166 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1167 hstate
.add_int (length
);
1170 hash
= hstate
.end ();
1175 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1179 sem_variable::merge (sem_item
*alias_item
)
1181 gcc_assert (alias_item
->type
== VAR
);
1183 if (!sem_item::target_supports_symbol_aliases_p ())
1186 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1190 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1192 varpool_node
*original
= get_node ();
1193 varpool_node
*alias
= alias_var
->get_node ();
1194 bool original_discardable
= false;
1196 /* See if original is in a section that can be discarded if the main
1197 symbol is not used. */
1198 if (DECL_EXTERNAL (original
->decl
))
1199 original_discardable
= true;
1200 if (original
->resolution
== LDPR_PREEMPTED_REG
1201 || original
->resolution
== LDPR_PREEMPTED_IR
)
1202 original_discardable
= true;
1203 if (original
->can_be_discarded_p ())
1204 original_discardable
= true;
1206 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1208 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1209 !compare_sections (alias_var
))
1212 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1218 // alias cycle creation check
1219 varpool_node
*n
= original
;
1223 n
= n
->get_alias_target ();
1227 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1233 alias
->analyzed
= false;
1235 DECL_INITIAL (alias
->decl
) = NULL
;
1236 alias
->need_bounds_init
= false;
1237 alias
->remove_all_references ();
1239 varpool_node::create_alias (alias_var
->decl
, decl
);
1240 alias
->resolve_alias (original
);
1243 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1250 sem_variable::compare_sections (sem_variable
*alias
)
1252 const char *source
= node
->get_section ();
1253 const char *target
= alias
->node
->get_section();
1255 if (source
== NULL
&& target
== NULL
)
1257 else if(!source
|| !target
)
1260 return strcmp (source
, target
) == 0;
1263 /* Dump symbol to FILE. */
1266 sem_variable::dump_to_file (FILE *file
)
1270 print_node (file
, "", decl
, 0);
1271 fprintf (file
, "\n\n");
1274 /* Iterates though a constructor and identifies tree references
1275 we are interested in semantic function equality. */
1278 sem_variable::parse_tree_refs (tree t
)
1280 switch (TREE_CODE (t
))
1284 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1286 for (unsigned i
= 0; i
< length
; i
++)
1287 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1294 tree op
= TREE_OPERAND (t
, 0);
1295 parse_tree_refs (op
);
1300 tree_refs
.safe_push (t
);
1308 unsigned int sem_item_optimizer::class_id
= 0;
1310 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1311 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1314 bitmap_obstack_initialize (&m_bmstack
);
1317 sem_item_optimizer::~sem_item_optimizer ()
1319 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1322 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1323 it
!= m_classes
.end (); ++it
)
1325 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1326 delete (*it
)->classes
[i
];
1328 (*it
)->classes
.release ();
1334 bitmap_obstack_release (&m_bmstack
);
1337 /* Write IPA ICF summary for symbols. */
1340 sem_item_optimizer::write_summary (void)
1342 unsigned int count
= 0;
1344 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1345 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1348 /* Calculate number of symbols to be serialized. */
1349 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1351 lsei_next_in_partition (&lsei
))
1353 symtab_node
*node
= lsei_node (lsei
);
1355 if (m_symtab_node_map
.get (node
))
1359 streamer_write_uhwi (ob
, count
);
1361 /* Process all of the symbols. */
1362 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1364 lsei_next_in_partition (&lsei
))
1366 symtab_node
*node
= lsei_node (lsei
);
1368 sem_item
**item
= m_symtab_node_map
.get (node
);
1372 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1373 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1375 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1379 streamer_write_char_stream (ob
->main_stream
, 0);
1380 produce_asm (ob
, NULL
);
1381 destroy_output_block (ob
);
1384 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1385 contains LEN bytes. */
1388 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1389 const char *data
, size_t len
)
1391 const lto_function_header
*header
=
1392 (const lto_function_header
*) data
;
1393 const int cfg_offset
= sizeof (lto_function_header
);
1394 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1395 const int string_offset
= main_offset
+ header
->main_size
;
1400 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1404 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1405 header
->string_size
, vNULL
);
1407 count
= streamer_read_uhwi (&ib_main
);
1409 for (i
= 0; i
< count
; i
++)
1413 lto_symtab_encoder_t encoder
;
1415 index
= streamer_read_uhwi (&ib_main
);
1416 encoder
= file_data
->symtab_node_encoder
;
1417 node
= lto_symtab_encoder_deref (encoder
, index
);
1419 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1421 gcc_assert (node
->definition
);
1424 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1425 (void *) node
->decl
, node
->order
);
1427 if (is_a
<cgraph_node
*> (node
))
1429 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1431 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1435 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1437 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1441 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1443 lto_data_in_delete (data_in
);
1446 /* Read IPA IPA ICF summary for symbols. */
1449 sem_item_optimizer::read_summary (void)
1451 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1452 lto_file_decl_data
*file_data
;
1455 while ((file_data
= file_data_vec
[j
++]))
1458 const char *data
= lto_get_section_data (file_data
,
1459 LTO_section_ipa_icf
, NULL
, &len
);
1462 read_section (file_data
, data
, len
);
1466 /* Register callgraph and varpool hooks. */
1469 sem_item_optimizer::register_hooks (void)
1471 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1472 (&sem_item_optimizer::cgraph_removal_hook
, this);
1474 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1475 (&sem_item_optimizer::varpool_removal_hook
, this);
1478 /* Unregister callgraph and varpool hooks. */
1481 sem_item_optimizer::unregister_hooks (void)
1483 if (m_cgraph_node_hooks
)
1484 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1486 if (m_varpool_node_hooks
)
1487 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1490 /* Adds a CLS to hashtable associated by hash value. */
1493 sem_item_optimizer::add_class (congruence_class
*cls
)
1495 gcc_assert (cls
->members
.length ());
1497 congruence_class_group
*group
= get_group_by_hash (
1498 cls
->members
[0]->get_hash (),
1499 cls
->members
[0]->type
);
1500 group
->classes
.safe_push (cls
);
1503 /* Gets a congruence class group based on given HASH value and TYPE. */
1505 congruence_class_group
*
1506 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1508 congruence_class_group
*item
= XNEW (congruence_class_group
);
1512 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1518 item
->classes
.create (1);
1525 /* Callgraph removal hook called for a NODE with a custom DATA. */
1528 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1530 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1531 optimizer
->remove_symtab_node (node
);
1534 /* Varpool removal hook called for a NODE with a custom DATA. */
1537 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1539 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1540 optimizer
->remove_symtab_node (node
);
1543 /* Remove symtab NODE triggered by symtab removal hooks. */
1546 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1548 gcc_assert (!m_classes
.elements());
1550 m_removed_items_set
.add (node
);
1554 sem_item_optimizer::remove_item (sem_item
*item
)
1556 if (m_symtab_node_map
.get (item
->node
))
1557 m_symtab_node_map
.remove (item
->node
);
1561 /* Removes all callgraph and varpool nodes that are marked by symtab
1565 sem_item_optimizer::filter_removed_items (void)
1567 auto_vec
<sem_item
*> filtered
;
1569 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1571 sem_item
*item
= m_items
[i
];
1573 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1579 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1585 bool no_body_function
= false;
1587 if (item
->type
== FUNC
)
1589 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1591 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1594 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1595 && !no_body_function
)
1597 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1598 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1600 filtered
.safe_push (m_items
[i
]);
1608 /* Clean-up of released semantic items. */
1611 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1612 m_items
.safe_push (filtered
[i
]);
1615 /* Optimizer entry point. */
1618 sem_item_optimizer::execute (void)
1620 filter_removed_items ();
1621 build_hash_based_classes ();
1624 fprintf (dump_file
, "Dump after hash based groups\n");
1625 dump_cong_classes ();
1627 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1628 m_items
[i
]->init_wpa ();
1632 subdivide_classes_by_equality (true);
1635 fprintf (dump_file
, "Dump after WPA based types groups\n");
1637 dump_cong_classes ();
1639 process_cong_reduction ();
1643 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1645 dump_cong_classes ();
1647 parse_nonsingleton_classes ();
1648 subdivide_classes_by_equality ();
1651 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1653 dump_cong_classes ();
1655 unsigned int prev_class_count
= m_classes_count
;
1657 process_cong_reduction ();
1658 dump_cong_classes ();
1660 merge_classes (prev_class_count
);
1662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1663 symtab_node::dump_table (dump_file
);
1666 /* Function responsible for visiting all potential functions and
1667 read-only variables that can be merged. */
1670 sem_item_optimizer::parse_funcs_and_vars (void)
1674 if (flag_ipa_icf_functions
)
1675 FOR_EACH_DEFINED_FUNCTION (cnode
)
1677 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1680 m_items
.safe_push (f
);
1681 m_symtab_node_map
.put (cnode
, f
);
1684 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1687 f
->dump_to_file (dump_file
);
1690 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1693 varpool_node
*vnode
;
1695 if (flag_ipa_icf_variables
)
1696 FOR_EACH_DEFINED_VARIABLE (vnode
)
1698 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1702 m_items
.safe_push (v
);
1703 m_symtab_node_map
.put (vnode
, v
);
1708 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1711 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1713 item
->index_in_class
= cls
->members
.length ();
1714 cls
->members
.safe_push (item
);
1718 /* Congruence classes are built by hash value. */
1721 sem_item_optimizer::build_hash_based_classes (void)
1723 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1725 sem_item
*item
= m_items
[i
];
1727 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1730 if (!group
->classes
.length ())
1733 group
->classes
.safe_push (new congruence_class (class_id
++));
1736 add_item_to_class (group
->classes
[0], item
);
1740 /* Build references according to call graph. */
1743 sem_item_optimizer::build_graph (void)
1745 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1747 sem_item
*item
= m_items
[i
];
1748 m_symtab_node_map
.put (item
->node
, item
);
1751 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1753 sem_item
*item
= m_items
[i
];
1755 if (item
->type
== FUNC
)
1757 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1759 cgraph_edge
*e
= cnode
->callees
;
1762 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1764 item
->add_reference (*slot
);
1770 ipa_ref
*ref
= NULL
;
1771 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1773 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1775 item
->add_reference (*slot
);
1780 /* Semantic items in classes having more than one element and initialized.
1781 In case of WPA, we load function body. */
1784 sem_item_optimizer::parse_nonsingleton_classes (void)
1786 unsigned int init_called_count
= 0;
1788 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1789 if (m_items
[i
]->cls
->members
.length () > 1)
1791 m_items
[i
]->init ();
1792 init_called_count
++;
1796 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1797 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1800 /* Equality function for semantic items is used to subdivide existing
1801 classes. If IN_WPA, fast equality function is invoked. */
1804 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1806 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1807 it
!= m_classes
.end (); ++it
)
1809 unsigned int class_count
= (*it
)->classes
.length ();
1811 for (unsigned i
= 0; i
< class_count
; i
++)
1813 congruence_class
*c
= (*it
)->classes
[i
];
1815 if (c
->members
.length() > 1)
1817 auto_vec
<sem_item
*> new_vector
;
1819 sem_item
*first
= c
->members
[0];
1820 new_vector
.safe_push (first
);
1822 unsigned class_split_first
= (*it
)->classes
.length ();
1824 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1826 sem_item
*item
= c
->members
[j
];
1828 bool equals
= in_wpa
? first
->equals_wpa (item
,
1829 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1832 new_vector
.safe_push (item
);
1835 bool integrated
= false;
1837 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1839 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1840 bool equals
= in_wpa
? x
->equals_wpa (item
,
1841 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1846 add_item_to_class ((*it
)->classes
[k
], item
);
1854 congruence_class
*c
= new congruence_class (class_id
++);
1856 add_item_to_class (c
, item
);
1858 (*it
)->classes
.safe_push (c
);
1863 // we replace newly created new_vector for the class we've just splitted
1864 c
->members
.release ();
1865 c
->members
.create (new_vector
.length ());
1867 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1868 add_item_to_class (c
, new_vector
[j
]);
1876 /* Verify congruence classes if checking is enabled. */
1879 sem_item_optimizer::verify_classes (void)
1882 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1883 it
!= m_classes
.end (); ++it
)
1885 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1887 congruence_class
*cls
= (*it
)->classes
[i
];
1889 gcc_checking_assert (cls
);
1890 gcc_checking_assert (cls
->members
.length () > 0);
1892 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1894 sem_item
*item
= cls
->members
[j
];
1896 gcc_checking_assert (item
);
1897 gcc_checking_assert (item
->cls
== cls
);
1899 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1901 sem_usage_pair
*usage
= item
->usages
[k
];
1902 gcc_checking_assert (usage
->item
->index_in_class
<
1903 usage
->item
->cls
->members
.length ());
1911 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1912 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1913 but unused argument. */
1916 sem_item_optimizer::release_split_map (congruence_class
* const &,
1917 bitmap
const &b
, traverse_split_pair
*)
1926 /* Process split operation for a class given as pointer CLS_PTR,
1927 where bitmap B splits congruence class members. DATA is used
1928 as argument of split pair. */
1931 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1932 bitmap
const &b
, traverse_split_pair
*pair
)
1934 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1935 const congruence_class
*splitter_cls
= pair
->cls
;
1937 /* If counted bits are greater than zero and less than the number of members
1938 a group will be splitted. */
1939 unsigned popcount
= bitmap_count_bits (b
);
1941 if (popcount
> 0 && popcount
< cls
->members
.length ())
1943 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1945 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1947 int target
= bitmap_bit_p (b
, i
);
1948 congruence_class
*tc
= newclasses
[target
];
1950 add_item_to_class (tc
, cls
->members
[i
]);
1953 #ifdef ENABLE_CHECKING
1954 for (unsigned int i
= 0; i
< 2; i
++)
1955 gcc_checking_assert (newclasses
[i
]->members
.length ());
1958 if (splitter_cls
== cls
)
1959 optimizer
->splitter_class_removed
= true;
1961 /* Remove old class from worklist if presented. */
1962 bool in_worklist
= cls
->in_worklist
;
1965 cls
->in_worklist
= false;
1967 congruence_class_group g
;
1968 g
.hash
= cls
->members
[0]->get_hash ();
1969 g
.type
= cls
->members
[0]->type
;
1971 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1973 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1974 if (slot
->classes
[i
] == cls
)
1976 slot
->classes
.ordered_remove (i
);
1980 /* New class will be inserted and integrated to work list. */
1981 for (unsigned int i
= 0; i
< 2; i
++)
1982 optimizer
->add_class (newclasses
[i
]);
1984 /* Two classes replace one, so that increment just by one. */
1985 optimizer
->m_classes_count
++;
1987 /* If OLD class was presented in the worklist, we remove the class
1988 and replace it will both newly created classes. */
1990 for (unsigned int i
= 0; i
< 2; i
++)
1991 optimizer
->worklist_push (newclasses
[i
]);
1992 else /* Just smaller class is inserted. */
1994 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1995 newclasses
[1]->members
.length () ?
1997 optimizer
->worklist_push (newclasses
[smaller_index
]);
2000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2002 fprintf (dump_file
, " congruence class splitted:\n");
2003 cls
->dump (dump_file
, 4);
2005 fprintf (dump_file
, " newly created groups:\n");
2006 for (unsigned int i
= 0; i
< 2; i
++)
2007 newclasses
[i
]->dump (dump_file
, 4);
2010 /* Release class if not presented in work list. */
2019 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2020 Bitmap stack BMSTACK is used for bitmap allocation. */
2023 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2026 hash_map
<congruence_class
*, bitmap
> split_map
;
2028 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2030 sem_item
*item
= cls
->members
[i
];
2032 /* Iterate all usages that have INDEX as usage of the item. */
2033 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2035 sem_usage_pair
*usage
= item
->usages
[j
];
2037 if (usage
->index
!= index
)
2040 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2045 b
= BITMAP_ALLOC (&m_bmstack
);
2046 split_map
.put (usage
->item
->cls
, b
);
2052 gcc_checking_assert (usage
->item
->cls
);
2053 gcc_checking_assert (usage
->item
->index_in_class
<
2054 usage
->item
->cls
->members
.length ());
2057 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2061 traverse_split_pair pair
;
2062 pair
.optimizer
= this;
2065 splitter_class_removed
= false;
2067 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2069 /* Bitmap clean-up. */
2071 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2074 /* Every usage of a congruence class CLS is a candidate that can split the
2075 collection of classes. Bitmap stack BMSTACK is used for bitmap
2079 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2084 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2086 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2087 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2089 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2091 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2092 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2095 do_congruence_step_for_index (cls
, i
);
2097 if (splitter_class_removed
)
2101 BITMAP_FREE (usage
);
2104 /* Adds a newly created congruence class CLS to worklist. */
2107 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2109 /* Return if the class CLS is already presented in work list. */
2110 if (cls
->in_worklist
)
2113 cls
->in_worklist
= true;
2114 worklist
.push_back (cls
);
2117 /* Pops a class from worklist. */
2120 sem_item_optimizer::worklist_pop (void)
2122 congruence_class
*cls
;
2124 while (!worklist
.empty ())
2126 cls
= worklist
.front ();
2127 worklist
.pop_front ();
2128 if (cls
->in_worklist
)
2130 cls
->in_worklist
= false;
2136 /* Work list item was already intended to be removed.
2137 The only reason for doing it is to split a class.
2138 Thus, the class CLS is deleted. */
2146 /* Iterative congruence reduction function. */
2149 sem_item_optimizer::process_cong_reduction (void)
2151 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2152 it
!= m_classes
.end (); ++it
)
2153 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2154 if ((*it
)->classes
[i
]->is_class_used ())
2155 worklist_push ((*it
)->classes
[i
]);
2158 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2159 (unsigned long) worklist
.size ());
2161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2162 fprintf (dump_file
, "Congruence class reduction\n");
2164 congruence_class
*cls
;
2165 while ((cls
= worklist_pop ()) != NULL
)
2166 do_congruence_step (cls
);
2169 /* Debug function prints all informations about congruence classes. */
2172 sem_item_optimizer::dump_cong_classes (void)
2178 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2179 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2181 /* Histogram calculation. */
2182 unsigned int max_index
= 0;
2183 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2185 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2186 it
!= m_classes
.end (); ++it
)
2188 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2190 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2198 "Class size histogram [num of members]: number of classe number of classess\n");
2200 for (unsigned int i
= 0; i
<= max_index
; i
++)
2202 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2204 fprintf (dump_file
, "\n\n");
2207 if (dump_flags
& TDF_DETAILS
)
2208 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2209 it
!= m_classes
.end (); ++it
)
2211 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2213 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2215 (*it
)->classes
[i
]->dump (dump_file
, 4);
2217 if(i
< (*it
)->classes
.length () - 1)
2218 fprintf (dump_file
, " ");
2225 /* After reduction is done, we can declare all items in a group
2226 to be equal. PREV_CLASS_COUNT is start number of classes
2227 before reduction. */
2230 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2232 unsigned int item_count
= m_items
.length ();
2233 unsigned int class_count
= m_classes_count
;
2234 unsigned int equal_items
= item_count
- class_count
;
2236 unsigned int non_singular_classes_count
= 0;
2237 unsigned int non_singular_classes_sum
= 0;
2239 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2240 it
!= m_classes
.end (); ++it
)
2241 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2243 congruence_class
*c
= (*it
)->classes
[i
];
2244 if (c
->members
.length () > 1)
2246 non_singular_classes_count
++;
2247 non_singular_classes_sum
+= c
->members
.length ();
2253 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2254 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2255 prev_class_count
, class_count
);
2256 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2257 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2258 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2259 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2260 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2261 non_singular_classes_count
: 0.0f
,
2262 non_singular_classes_count
);
2263 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2264 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2265 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2268 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2269 it
!= m_classes
.end (); ++it
)
2270 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2272 congruence_class
*c
= (*it
)->classes
[i
];
2274 if (c
->members
.length () == 1)
2277 gcc_assert (c
->members
.length ());
2279 sem_item
*source
= c
->members
[0];
2281 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2283 sem_item
*alias
= c
->members
[j
];
2284 source
->equals (alias
, m_symtab_node_map
);
2288 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2289 source
->name (), alias
->name ());
2290 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2291 source
->asm_name (), alias
->asm_name ());
2294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2296 source
->dump_to_file (dump_file
);
2297 alias
->dump_to_file (dump_file
);
2300 source
->merge (alias
);
2305 /* Dump function prints all class members to a FILE with an INDENT. */
2308 congruence_class::dump (FILE *file
, unsigned int indent
) const
2310 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2311 id
, members
[0]->get_hash (), members
.length ());
2313 FPUTS_SPACES (file
, indent
+ 2, "");
2314 for (unsigned i
= 0; i
< members
.length (); i
++)
2315 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2316 members
[i
]->node
->order
);
2318 fprintf (file
, "\n");
2321 /* Returns true if there's a member that is used from another group. */
2324 congruence_class::is_class_used (void)
2326 for (unsigned int i
= 0; i
< members
.length (); i
++)
2327 if (members
[i
]->usages
.length ())
2333 /* Initialization and computation of symtab node hash, there data
2334 are propagated later on. */
2336 static sem_item_optimizer
*optimizer
= NULL
;
2338 /* Generate pass summary for IPA ICF pass. */
2341 ipa_icf_generate_summary (void)
2344 optimizer
= new sem_item_optimizer ();
2346 optimizer
->parse_funcs_and_vars ();
2349 /* Write pass summary for IPA ICF pass. */
2352 ipa_icf_write_summary (void)
2354 gcc_assert (optimizer
);
2356 optimizer
->write_summary ();
2359 /* Read pass summary for IPA ICF pass. */
2362 ipa_icf_read_summary (void)
2365 optimizer
= new sem_item_optimizer ();
2367 optimizer
->read_summary ();
2368 optimizer
->register_hooks ();
2371 /* Semantic equality exection function. */
2374 ipa_icf_driver (void)
2376 gcc_assert (optimizer
);
2378 optimizer
->execute ();
2379 optimizer
->unregister_hooks ();
2387 const pass_data pass_data_ipa_icf
=
2389 IPA_PASS
, /* type */
2391 OPTGROUP_IPA
, /* optinfo_flags */
2392 TV_IPA_ICF
, /* tv_id */
2393 0, /* properties_required */
2394 0, /* properties_provided */
2395 0, /* properties_destroyed */
2396 0, /* todo_flags_start */
2397 0, /* todo_flags_finish */
2400 class pass_ipa_icf
: public ipa_opt_pass_d
2403 pass_ipa_icf (gcc::context
*ctxt
)
2404 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2405 ipa_icf_generate_summary
, /* generate_summary */
2406 ipa_icf_write_summary
, /* write_summary */
2407 ipa_icf_read_summary
, /* read_summary */
2409 write_optimization_summary */
2411 read_optimization_summary */
2412 NULL
, /* stmt_fixup */
2413 0, /* function_transform_todo_flags_start */
2414 NULL
, /* function_transform */
2415 NULL
) /* variable_transform */
2418 /* opt_pass methods: */
2419 virtual bool gate (function
*)
2421 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2424 virtual unsigned int execute (function
*)
2426 return ipa_icf_driver();
2428 }; // class pass_ipa_icf
2430 } // ipa_icf namespace
2433 make_pass_ipa_icf (gcc::context
*ctxt
)
2435 return new ipa_icf::pass_ipa_icf (ctxt
);