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
;
417 m_compared_func
= static_cast<sem_function
*> (item
);
419 gcc_assert (decl
!= item
->decl
);
421 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
422 || edge_count
!= m_compared_func
->edge_count
423 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
424 return return_false ();
426 if (!equals_wpa (item
, ignored_nodes
))
429 /* Checking function arguments. */
430 tree decl1
= DECL_ATTRIBUTES (decl
);
431 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
433 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
434 compare_polymorphic_p (),
437 &m_compared_func
->refs_set
);
441 return return_false ();
443 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
444 return return_false ();
446 tree attr_value1
= TREE_VALUE (decl1
);
447 tree attr_value2
= TREE_VALUE (decl2
);
449 if (attr_value1
&& attr_value2
)
451 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
452 TREE_VALUE (attr_value2
));
454 return return_false_with_msg ("attribute values are different");
456 else if (!attr_value1
&& !attr_value2
)
459 return return_false ();
461 decl1
= TREE_CHAIN (decl1
);
462 decl2
= TREE_CHAIN (decl2
);
466 return return_false();
469 for (arg1
= DECL_ARGUMENTS (decl
),
470 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
471 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
472 if (!m_checker
->compare_decl (arg1
, arg2
))
473 return return_false ();
475 /* Fill-up label dictionary. */
476 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
478 m_checker
->parse_labels (bb_sorted
[i
]);
479 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
482 /* Checking all basic blocks. */
483 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
484 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
485 return return_false();
487 dump_message ("All BBs are equal\n");
489 /* Basic block edges check. */
490 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
492 bb_dict
= XNEWVEC (int, bb_sorted
.length () + 2);
493 memset (bb_dict
, -1, (bb_sorted
.length () + 2) * sizeof (int));
495 bb1
= bb_sorted
[i
]->bb
;
496 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
498 ei2
= ei_start (bb2
->preds
);
500 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
504 if (e1
->flags
!= e2
->flags
)
505 return return_false_with_msg ("flags comparison returns false");
507 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
508 return return_false_with_msg ("edge comparison returns false");
510 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
511 return return_false_with_msg ("BB comparison returns false");
513 if (!m_checker
->compare_edge (e1
, e2
))
514 return return_false_with_msg ("edge comparison returns false");
520 /* Basic block PHI nodes comparison. */
521 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
522 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
523 return return_false_with_msg ("PHI node comparison returns false");
528 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
531 sem_function::merge (sem_item
*alias_item
)
533 gcc_assert (alias_item
->type
== FUNC
);
535 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
537 cgraph_node
*original
= get_node ();
538 cgraph_node
*local_original
= original
;
539 cgraph_node
*alias
= alias_func
->get_node ();
540 bool original_address_matters
;
541 bool alias_address_matters
;
543 bool create_thunk
= false;
544 bool create_alias
= false;
545 bool redirect_callers
= false;
546 bool original_discardable
= false;
548 /* Do not attempt to mix functions from different user sections;
549 we do not know what user intends with those. */
550 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
551 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
552 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
556 "Not unifying; original and alias are in different sections.\n\n");
560 /* See if original is in a section that can be discarded if the main
561 symbol is not used. */
562 if (DECL_EXTERNAL (original
->decl
))
563 original_discardable
= true;
564 if (original
->resolution
== LDPR_PREEMPTED_REG
565 || original
->resolution
== LDPR_PREEMPTED_IR
)
566 original_discardable
= true;
567 if (original
->can_be_discarded_p ())
568 original_discardable
= true;
570 /* See if original and/or alias address can be compared for equality. */
571 original_address_matters
572 = (!DECL_VIRTUAL_P (original
->decl
)
573 && (original
->externally_visible
574 || original
->address_taken_from_non_vtable_p ()));
575 alias_address_matters
576 = (!DECL_VIRTUAL_P (alias
->decl
)
577 && (alias
->externally_visible
578 || alias
->address_taken_from_non_vtable_p ()));
580 /* If alias and original can be compared for address equality, we need
581 to create a thunk. Also we can not create extra aliases into discardable
582 section (or we risk link failures when section is discarded). */
583 if ((original_address_matters
584 && alias_address_matters
)
585 || original_discardable
)
587 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
588 create_alias
= false;
589 /* When both alias and original are not overwritable, we can save
590 the extra thunk wrapper for direct calls. */
592 = (!original_discardable
593 && alias
->get_availability () > AVAIL_INTERPOSABLE
594 && original
->get_availability () > AVAIL_INTERPOSABLE
595 && !alias
->instrumented_version
);
600 create_thunk
= false;
601 redirect_callers
= false;
604 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
605 || !sem_item::target_supports_symbol_aliases_p ()))
607 create_alias
= false;
611 /* We want thunk to always jump to the local function body
612 unless the body is comdat and may be optimized out. */
613 if ((create_thunk
|| redirect_callers
)
614 && (!original_discardable
615 || (DECL_COMDAT_GROUP (original
->decl
)
616 && (DECL_COMDAT_GROUP (original
->decl
)
617 == DECL_COMDAT_GROUP (alias
->decl
)))))
619 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
624 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
629 if (redirect_callers
)
631 /* If alias is non-overwritable then
632 all direct calls are safe to be redirected to the original. */
633 bool redirected
= false;
634 while (alias
->callers
)
636 cgraph_edge
*e
= alias
->callers
;
637 e
->redirect_callee (local_original
);
638 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
641 e
->redirect_call_stmt_to_callee ();
647 alias
->icf_merged
= true;
649 /* The alias function is removed if symbol address
651 if (!alias_address_matters
)
654 if (dump_file
&& redirected
)
655 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
657 /* If the condtion above is not met, we are lucky and can turn the
658 function into real alias. */
659 else if (create_alias
)
661 alias
->icf_merged
= true;
663 /* Remove the function's body. */
664 ipa_merge_profiles (original
, alias
);
665 alias
->release_body (true);
668 /* Create the alias. */
669 cgraph_node::create_alias (alias_func
->decl
, decl
);
670 alias
->resolve_alias (original
);
672 /* Workaround for PR63566 that forces equal calling convention
674 alias
->local
.local
= false;
675 original
->local
.local
= false;
678 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
680 else if (create_thunk
)
682 if (DECL_COMDAT_GROUP (alias
->decl
))
685 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
690 alias
->icf_merged
= true;
691 ipa_merge_profiles (local_original
, alias
);
692 alias
->create_wrapper (local_original
);
695 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
698 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
703 /* Semantic item initialization function. */
706 sem_function::init (void)
709 get_node ()->get_untransformed_body ();
711 tree fndecl
= node
->decl
;
712 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
715 gcc_assert (SSANAMES (func
));
717 ssa_names_size
= SSANAMES (func
)->length ();
721 region_tree
= func
->eh
->region_tree
;
723 /* iterating all function arguments. */
724 arg_count
= count_formal_params (fndecl
);
726 edge_count
= n_edges_for_fn (func
);
727 cfg_checksum
= coverage_compute_cfg_checksum (func
);
729 inchash::hash hstate
;
732 FOR_EACH_BB_FN (bb
, func
)
734 unsigned nondbg_stmt_count
= 0;
737 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
738 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
741 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
744 gimple stmt
= gsi_stmt (gsi
);
746 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
748 hash_stmt (&hstate
, stmt
);
753 gcode_hash
= hstate
.end ();
754 bb_sizes
.safe_push (nondbg_stmt_count
);
756 /* Inserting basic block to hash table. */
757 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
758 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
760 bb_sorted
.safe_push (semantic_bb
);
766 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
769 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
771 enum gimple_code code
= gimple_code (stmt
);
773 hstate
->add_int (code
);
775 if (code
== GIMPLE_CALL
)
777 /* Checking of argument. */
778 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
780 tree argument
= gimple_call_arg (stmt
, i
);
782 switch (TREE_CODE (argument
))
785 if (tree_fits_shwi_p (argument
))
786 hstate
->add_wide_int (tree_to_shwi (argument
));
787 else if (tree_fits_uhwi_p (argument
))
788 hstate
->add_wide_int (tree_to_uhwi (argument
));
794 c
= TREE_REAL_CST (argument
);
795 n
= real_to_integer (&c
);
797 hstate
->add_wide_int (n
);
801 tree addr_operand
= TREE_OPERAND (argument
, 0);
803 if (TREE_CODE (addr_operand
) == STRING_CST
)
804 hstate
->add (TREE_STRING_POINTER (addr_operand
),
805 TREE_STRING_LENGTH (addr_operand
));
816 /* Return true if polymorphic comparison must be processed. */
819 sem_function::compare_polymorphic_p (void)
821 return get_node ()->callees
!= NULL
822 || m_compared_func
->get_node ()->callees
!= NULL
;
825 /* For a given call graph NODE, the function constructs new
826 semantic function item. */
829 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
831 tree fndecl
= node
->decl
;
832 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
834 /* TODO: add support for thunks and aliases. */
836 if (!func
|| !node
->has_gimple_body_p ())
839 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
842 sem_function
*f
= new sem_function (node
, 0, stack
);
849 /* Parses function arguments and result type. */
852 sem_function::parse_tree_args (void)
856 if (arg_types
.exists ())
857 arg_types
.release ();
859 arg_types
.create (4);
860 tree fnargs
= DECL_ARGUMENTS (decl
);
862 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
863 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
865 /* Function result type. */
866 result
= DECL_RESULT (decl
);
867 result_type
= result
? TREE_TYPE (result
) : NULL
;
869 /* During WPA, we can get arguments by following method. */
872 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
873 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
874 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
876 result_type
= TREE_TYPE (TREE_TYPE (decl
));
880 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
881 return true if phi nodes are semantically equivalent in these blocks . */
884 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
886 gphi_iterator si1
, si2
;
888 unsigned size1
, size2
, i
;
892 gcc_assert (bb1
!= NULL
);
893 gcc_assert (bb2
!= NULL
);
895 si2
= gsi_start_phis (bb2
);
896 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
899 gsi_next_nonvirtual_phi (&si1
);
900 gsi_next_nonvirtual_phi (&si2
);
902 if (gsi_end_p (si1
) && gsi_end_p (si2
))
905 if (gsi_end_p (si1
) || gsi_end_p (si2
))
906 return return_false();
911 tree phi_result1
= gimple_phi_result (phi1
);
912 tree phi_result2
= gimple_phi_result (phi2
);
914 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
915 return return_false_with_msg ("PHI results are different");
917 size1
= gimple_phi_num_args (phi1
);
918 size2
= gimple_phi_num_args (phi2
);
921 return return_false ();
923 for (i
= 0; i
< size1
; ++i
)
925 t1
= gimple_phi_arg (phi1
, i
)->def
;
926 t2
= gimple_phi_arg (phi2
, i
)->def
;
928 if (!m_checker
->compare_operand (t1
, t2
))
929 return return_false ();
931 e1
= gimple_phi_arg_edge (phi1
, i
);
932 e2
= gimple_phi_arg_edge (phi2
, i
);
934 if (!m_checker
->compare_edge (e1
, e2
))
935 return return_false ();
944 /* Returns true if tree T can be compared as a handled component. */
947 sem_function::icf_handled_component_p (tree t
)
949 tree_code tc
= TREE_CODE (t
);
951 return ((handled_component_p (t
))
952 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
953 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
956 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
957 corresponds to TARGET. */
960 sem_function::bb_dict_test (int* bb_dict
, int source
, int target
)
962 if (bb_dict
[source
] == -1)
964 bb_dict
[source
] = target
;
968 return bb_dict
[source
] == target
;
971 /* Iterates all tree types in T1 and T2 and returns true if all types
972 are compatible. If COMPARE_POLYMORPHIC is set to true,
973 more strict comparison is executed. */
976 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
984 while (t1
!= NULL
&& t2
!= NULL
)
986 tv1
= TREE_VALUE (t1
);
987 tv2
= TREE_VALUE (t2
);
989 tc1
= TREE_CODE (tv1
);
990 tc2
= TREE_CODE (tv2
);
992 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
994 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
996 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
999 t1
= TREE_CHAIN (t1
);
1000 t2
= TREE_CHAIN (t2
);
1007 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1009 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1013 /* Constructor based on varpool node _NODE with computed hash _HASH.
1014 Bitmap STACK is used for memory allocation. */
1016 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1017 bitmap_obstack
*stack
): sem_item(VAR
,
1020 gcc_checking_assert (node
);
1021 gcc_checking_assert (get_node ());
1024 /* Returns true if the item equals to ITEM given as argument. */
1027 sem_variable::equals (sem_item
*item
,
1028 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1030 gcc_assert (item
->type
== VAR
);
1032 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1034 if (!ctor
|| !v
->ctor
)
1035 return return_false_with_msg ("ctor is missing for semantic variable");
1037 return sem_variable::equals (ctor
, v
->ctor
);
1040 /* Compares trees T1 and T2 for semantic equality. */
1043 sem_variable::equals (tree t1
, tree t2
)
1045 tree_code tc1
= TREE_CODE (t1
);
1046 tree_code tc2
= TREE_CODE (t2
);
1055 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1056 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1061 for (unsigned i
= 0; i
< len1
; i
++)
1062 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1063 CONSTRUCTOR_ELT (t2
, i
)->value
)
1064 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1071 tree x1
= TREE_OPERAND (t1
, 0);
1072 tree x2
= TREE_OPERAND (t2
, 0);
1073 tree y1
= TREE_OPERAND (t1
, 1);
1074 tree y2
= TREE_OPERAND (t2
, 1);
1076 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1078 return return_false ();
1080 /* Type of the offset on MEM_REF does not matter. */
1081 return sem_variable::equals (x1
, x2
)
1082 && wi::to_offset (y1
) == wi::to_offset (y2
);
1087 tree op1
= TREE_OPERAND (t1
, 0);
1088 tree op2
= TREE_OPERAND (t2
, 0);
1089 return sem_variable::equals (op1
, op2
);
1097 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1099 && wi::to_offset (t1
) == wi::to_offset (t2
);
1103 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1106 case POINTER_PLUS_EXPR
:
1108 tree x1
= TREE_OPERAND (t1
, 0);
1109 tree x2
= TREE_OPERAND (t2
, 0);
1110 tree y1
= TREE_OPERAND (t1
, 1);
1111 tree y2
= TREE_OPERAND (t2
, 1);
1113 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1116 return return_false_with_msg ("ERROR_MARK");
1118 return return_false_with_msg ("Unknown TREE code reached");
1122 /* Parser function that visits a varpool NODE. */
1125 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1127 tree decl
= node
->decl
;
1129 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1130 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1131 || !TREE_ADDRESSABLE (decl
));
1136 tree ctor
= ctor_for_folding (decl
);
1140 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1147 /* References independent hash function. */
1150 sem_variable::get_hash (void)
1155 inchash::hash hstate
;
1157 hstate
.add_int (456346417);
1158 hstate
.add_int (TREE_CODE (ctor
));
1160 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1162 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1163 hstate
.add_int (length
);
1166 hash
= hstate
.end ();
1171 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1175 sem_variable::merge (sem_item
*alias_item
)
1177 gcc_assert (alias_item
->type
== VAR
);
1179 if (!sem_item::target_supports_symbol_aliases_p ())
1182 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1186 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1188 varpool_node
*original
= get_node ();
1189 varpool_node
*alias
= alias_var
->get_node ();
1190 bool original_discardable
= false;
1192 /* See if original is in a section that can be discarded if the main
1193 symbol is not used. */
1194 if (DECL_EXTERNAL (original
->decl
))
1195 original_discardable
= true;
1196 if (original
->resolution
== LDPR_PREEMPTED_REG
1197 || original
->resolution
== LDPR_PREEMPTED_IR
)
1198 original_discardable
= true;
1199 if (original
->can_be_discarded_p ())
1200 original_discardable
= true;
1202 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1204 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1205 !compare_sections (alias_var
))
1208 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1214 // alias cycle creation check
1215 varpool_node
*n
= original
;
1219 n
= n
->get_alias_target ();
1223 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1229 alias
->analyzed
= false;
1231 DECL_INITIAL (alias
->decl
) = NULL
;
1232 alias
->need_bounds_init
= false;
1233 alias
->remove_all_references ();
1235 varpool_node::create_alias (alias_var
->decl
, decl
);
1236 alias
->resolve_alias (original
);
1239 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1246 sem_variable::compare_sections (sem_variable
*alias
)
1248 const char *source
= node
->get_section ();
1249 const char *target
= alias
->node
->get_section();
1251 if (source
== NULL
&& target
== NULL
)
1253 else if(!source
|| !target
)
1256 return strcmp (source
, target
) == 0;
1259 /* Dump symbol to FILE. */
1262 sem_variable::dump_to_file (FILE *file
)
1266 print_node (file
, "", decl
, 0);
1267 fprintf (file
, "\n\n");
1270 /* Iterates though a constructor and identifies tree references
1271 we are interested in semantic function equality. */
1274 sem_variable::parse_tree_refs (tree t
)
1276 switch (TREE_CODE (t
))
1280 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1282 for (unsigned i
= 0; i
< length
; i
++)
1283 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1290 tree op
= TREE_OPERAND (t
, 0);
1291 parse_tree_refs (op
);
1296 tree_refs
.safe_push (t
);
1304 unsigned int sem_item_optimizer::class_id
= 0;
1306 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1307 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1310 bitmap_obstack_initialize (&m_bmstack
);
1313 sem_item_optimizer::~sem_item_optimizer ()
1315 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1318 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1319 it
!= m_classes
.end (); ++it
)
1321 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1322 delete (*it
)->classes
[i
];
1324 (*it
)->classes
.release ();
1330 bitmap_obstack_release (&m_bmstack
);
1333 /* Write IPA ICF summary for symbols. */
1336 sem_item_optimizer::write_summary (void)
1338 unsigned int count
= 0;
1340 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1341 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1344 /* Calculate number of symbols to be serialized. */
1345 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1347 lsei_next_in_partition (&lsei
))
1349 symtab_node
*node
= lsei_node (lsei
);
1351 if (m_symtab_node_map
.get (node
))
1355 streamer_write_uhwi (ob
, count
);
1357 /* Process all of the symbols. */
1358 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1360 lsei_next_in_partition (&lsei
))
1362 symtab_node
*node
= lsei_node (lsei
);
1364 sem_item
**item
= m_symtab_node_map
.get (node
);
1368 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1369 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1371 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1375 streamer_write_char_stream (ob
->main_stream
, 0);
1376 produce_asm (ob
, NULL
);
1377 destroy_output_block (ob
);
1380 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1381 contains LEN bytes. */
1384 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1385 const char *data
, size_t len
)
1387 const lto_function_header
*header
=
1388 (const lto_function_header
*) data
;
1389 const int cfg_offset
= sizeof (lto_function_header
);
1390 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1391 const int string_offset
= main_offset
+ header
->main_size
;
1396 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1400 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1401 header
->string_size
, vNULL
);
1403 count
= streamer_read_uhwi (&ib_main
);
1405 for (i
= 0; i
< count
; i
++)
1409 lto_symtab_encoder_t encoder
;
1411 index
= streamer_read_uhwi (&ib_main
);
1412 encoder
= file_data
->symtab_node_encoder
;
1413 node
= lto_symtab_encoder_deref (encoder
, index
);
1415 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1417 gcc_assert (node
->definition
);
1420 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1421 (void *) node
->decl
, node
->order
);
1423 if (is_a
<cgraph_node
*> (node
))
1425 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1427 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1431 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1433 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1437 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1439 lto_data_in_delete (data_in
);
1442 /* Read IPA IPA ICF summary for symbols. */
1445 sem_item_optimizer::read_summary (void)
1447 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1448 lto_file_decl_data
*file_data
;
1451 while ((file_data
= file_data_vec
[j
++]))
1454 const char *data
= lto_get_section_data (file_data
,
1455 LTO_section_ipa_icf
, NULL
, &len
);
1458 read_section (file_data
, data
, len
);
1462 /* Register callgraph and varpool hooks. */
1465 sem_item_optimizer::register_hooks (void)
1467 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1468 (&sem_item_optimizer::cgraph_removal_hook
, this);
1470 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1471 (&sem_item_optimizer::varpool_removal_hook
, this);
1474 /* Unregister callgraph and varpool hooks. */
1477 sem_item_optimizer::unregister_hooks (void)
1479 if (m_cgraph_node_hooks
)
1480 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1482 if (m_varpool_node_hooks
)
1483 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1486 /* Adds a CLS to hashtable associated by hash value. */
1489 sem_item_optimizer::add_class (congruence_class
*cls
)
1491 gcc_assert (cls
->members
.length ());
1493 congruence_class_group
*group
= get_group_by_hash (
1494 cls
->members
[0]->get_hash (),
1495 cls
->members
[0]->type
);
1496 group
->classes
.safe_push (cls
);
1499 /* Gets a congruence class group based on given HASH value and TYPE. */
1501 congruence_class_group
*
1502 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1504 congruence_class_group
*item
= XNEW (congruence_class_group
);
1508 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1514 item
->classes
.create (1);
1521 /* Callgraph removal hook called for a NODE with a custom DATA. */
1524 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1526 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1527 optimizer
->remove_symtab_node (node
);
1530 /* Varpool removal hook called for a NODE with a custom DATA. */
1533 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1535 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1536 optimizer
->remove_symtab_node (node
);
1539 /* Remove symtab NODE triggered by symtab removal hooks. */
1542 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1544 gcc_assert (!m_classes
.elements());
1546 m_removed_items_set
.add (node
);
1550 sem_item_optimizer::remove_item (sem_item
*item
)
1552 if (m_symtab_node_map
.get (item
->node
))
1553 m_symtab_node_map
.remove (item
->node
);
1557 /* Removes all callgraph and varpool nodes that are marked by symtab
1561 sem_item_optimizer::filter_removed_items (void)
1563 auto_vec
<sem_item
*> filtered
;
1565 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1567 sem_item
*item
= m_items
[i
];
1569 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1575 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1581 bool no_body_function
= false;
1583 if (item
->type
== FUNC
)
1585 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1587 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1590 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1591 && !no_body_function
)
1593 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1594 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1596 filtered
.safe_push (m_items
[i
]);
1604 /* Clean-up of released semantic items. */
1607 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1608 m_items
.safe_push (filtered
[i
]);
1611 /* Optimizer entry point. */
1614 sem_item_optimizer::execute (void)
1616 filter_removed_items ();
1617 build_hash_based_classes ();
1620 fprintf (dump_file
, "Dump after hash based groups\n");
1621 dump_cong_classes ();
1623 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1624 m_items
[i
]->init_wpa ();
1628 subdivide_classes_by_equality (true);
1631 fprintf (dump_file
, "Dump after WPA based types groups\n");
1633 dump_cong_classes ();
1635 process_cong_reduction ();
1639 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1641 dump_cong_classes ();
1643 parse_nonsingleton_classes ();
1644 subdivide_classes_by_equality ();
1647 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1649 dump_cong_classes ();
1651 unsigned int prev_class_count
= m_classes_count
;
1653 process_cong_reduction ();
1654 dump_cong_classes ();
1656 merge_classes (prev_class_count
);
1658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1659 symtab_node::dump_table (dump_file
);
1662 /* Function responsible for visiting all potential functions and
1663 read-only variables that can be merged. */
1666 sem_item_optimizer::parse_funcs_and_vars (void)
1670 if (flag_ipa_icf_functions
)
1671 FOR_EACH_DEFINED_FUNCTION (cnode
)
1673 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1676 m_items
.safe_push (f
);
1677 m_symtab_node_map
.put (cnode
, f
);
1680 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1683 f
->dump_to_file (dump_file
);
1686 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1689 varpool_node
*vnode
;
1691 if (flag_ipa_icf_variables
)
1692 FOR_EACH_DEFINED_VARIABLE (vnode
)
1694 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1698 m_items
.safe_push (v
);
1699 m_symtab_node_map
.put (vnode
, v
);
1704 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1707 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1709 item
->index_in_class
= cls
->members
.length ();
1710 cls
->members
.safe_push (item
);
1714 /* Congruence classes are built by hash value. */
1717 sem_item_optimizer::build_hash_based_classes (void)
1719 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1721 sem_item
*item
= m_items
[i
];
1723 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1726 if (!group
->classes
.length ())
1729 group
->classes
.safe_push (new congruence_class (class_id
++));
1732 add_item_to_class (group
->classes
[0], item
);
1736 /* Build references according to call graph. */
1739 sem_item_optimizer::build_graph (void)
1741 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1743 sem_item
*item
= m_items
[i
];
1744 m_symtab_node_map
.put (item
->node
, item
);
1747 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1749 sem_item
*item
= m_items
[i
];
1751 if (item
->type
== FUNC
)
1753 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1755 cgraph_edge
*e
= cnode
->callees
;
1758 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1760 item
->add_reference (*slot
);
1766 ipa_ref
*ref
= NULL
;
1767 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1769 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1771 item
->add_reference (*slot
);
1776 /* Semantic items in classes having more than one element and initialized.
1777 In case of WPA, we load function body. */
1780 sem_item_optimizer::parse_nonsingleton_classes (void)
1782 unsigned int init_called_count
= 0;
1784 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1785 if (m_items
[i
]->cls
->members
.length () > 1)
1787 m_items
[i
]->init ();
1788 init_called_count
++;
1792 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1793 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1796 /* Equality function for semantic items is used to subdivide existing
1797 classes. If IN_WPA, fast equality function is invoked. */
1800 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1802 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1803 it
!= m_classes
.end (); ++it
)
1805 unsigned int class_count
= (*it
)->classes
.length ();
1807 for (unsigned i
= 0; i
< class_count
; i
++)
1809 congruence_class
*c
= (*it
)->classes
[i
];
1811 if (c
->members
.length() > 1)
1813 auto_vec
<sem_item
*> new_vector
;
1815 sem_item
*first
= c
->members
[0];
1816 new_vector
.safe_push (first
);
1818 unsigned class_split_first
= (*it
)->classes
.length ();
1820 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1822 sem_item
*item
= c
->members
[j
];
1824 bool equals
= in_wpa
? first
->equals_wpa (item
,
1825 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1828 new_vector
.safe_push (item
);
1831 bool integrated
= false;
1833 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1835 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1836 bool equals
= in_wpa
? x
->equals_wpa (item
,
1837 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1842 add_item_to_class ((*it
)->classes
[k
], item
);
1850 congruence_class
*c
= new congruence_class (class_id
++);
1852 add_item_to_class (c
, item
);
1854 (*it
)->classes
.safe_push (c
);
1859 // we replace newly created new_vector for the class we've just splitted
1860 c
->members
.release ();
1861 c
->members
.create (new_vector
.length ());
1863 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1864 add_item_to_class (c
, new_vector
[j
]);
1872 /* Verify congruence classes if checking is enabled. */
1875 sem_item_optimizer::verify_classes (void)
1878 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1879 it
!= m_classes
.end (); ++it
)
1881 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1883 congruence_class
*cls
= (*it
)->classes
[i
];
1885 gcc_checking_assert (cls
);
1886 gcc_checking_assert (cls
->members
.length () > 0);
1888 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1890 sem_item
*item
= cls
->members
[j
];
1892 gcc_checking_assert (item
);
1893 gcc_checking_assert (item
->cls
== cls
);
1895 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1897 sem_usage_pair
*usage
= item
->usages
[k
];
1898 gcc_checking_assert (usage
->item
->index_in_class
<
1899 usage
->item
->cls
->members
.length ());
1907 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1908 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1909 but unused argument. */
1912 sem_item_optimizer::release_split_map (congruence_class
* const &,
1913 bitmap
const &b
, traverse_split_pair
*)
1922 /* Process split operation for a class given as pointer CLS_PTR,
1923 where bitmap B splits congruence class members. DATA is used
1924 as argument of split pair. */
1927 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1928 bitmap
const &b
, traverse_split_pair
*pair
)
1930 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1931 const congruence_class
*splitter_cls
= pair
->cls
;
1933 /* If counted bits are greater than zero and less than the number of members
1934 a group will be splitted. */
1935 unsigned popcount
= bitmap_count_bits (b
);
1937 if (popcount
> 0 && popcount
< cls
->members
.length ())
1939 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1941 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1943 int target
= bitmap_bit_p (b
, i
);
1944 congruence_class
*tc
= newclasses
[target
];
1946 add_item_to_class (tc
, cls
->members
[i
]);
1949 #ifdef ENABLE_CHECKING
1950 for (unsigned int i
= 0; i
< 2; i
++)
1951 gcc_checking_assert (newclasses
[i
]->members
.length ());
1954 if (splitter_cls
== cls
)
1955 optimizer
->splitter_class_removed
= true;
1957 /* Remove old class from worklist if presented. */
1958 bool in_worklist
= cls
->in_worklist
;
1961 cls
->in_worklist
= false;
1963 congruence_class_group g
;
1964 g
.hash
= cls
->members
[0]->get_hash ();
1965 g
.type
= cls
->members
[0]->type
;
1967 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1969 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1970 if (slot
->classes
[i
] == cls
)
1972 slot
->classes
.ordered_remove (i
);
1976 /* New class will be inserted and integrated to work list. */
1977 for (unsigned int i
= 0; i
< 2; i
++)
1978 optimizer
->add_class (newclasses
[i
]);
1980 /* Two classes replace one, so that increment just by one. */
1981 optimizer
->m_classes_count
++;
1983 /* If OLD class was presented in the worklist, we remove the class
1984 and replace it will both newly created classes. */
1986 for (unsigned int i
= 0; i
< 2; i
++)
1987 optimizer
->worklist_push (newclasses
[i
]);
1988 else /* Just smaller class is inserted. */
1990 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1991 newclasses
[1]->members
.length () ?
1993 optimizer
->worklist_push (newclasses
[smaller_index
]);
1996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1998 fprintf (dump_file
, " congruence class splitted:\n");
1999 cls
->dump (dump_file
, 4);
2001 fprintf (dump_file
, " newly created groups:\n");
2002 for (unsigned int i
= 0; i
< 2; i
++)
2003 newclasses
[i
]->dump (dump_file
, 4);
2006 /* Release class if not presented in work list. */
2015 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2016 Bitmap stack BMSTACK is used for bitmap allocation. */
2019 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2022 hash_map
<congruence_class
*, bitmap
> split_map
;
2024 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2026 sem_item
*item
= cls
->members
[i
];
2028 /* Iterate all usages that have INDEX as usage of the item. */
2029 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2031 sem_usage_pair
*usage
= item
->usages
[j
];
2033 if (usage
->index
!= index
)
2036 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2041 b
= BITMAP_ALLOC (&m_bmstack
);
2042 split_map
.put (usage
->item
->cls
, b
);
2048 gcc_checking_assert (usage
->item
->cls
);
2049 gcc_checking_assert (usage
->item
->index_in_class
<
2050 usage
->item
->cls
->members
.length ());
2053 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2057 traverse_split_pair pair
;
2058 pair
.optimizer
= this;
2061 splitter_class_removed
= false;
2063 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2065 /* Bitmap clean-up. */
2067 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2070 /* Every usage of a congruence class CLS is a candidate that can split the
2071 collection of classes. Bitmap stack BMSTACK is used for bitmap
2075 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2080 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2082 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2083 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2085 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2087 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2088 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2091 do_congruence_step_for_index (cls
, i
);
2093 if (splitter_class_removed
)
2097 BITMAP_FREE (usage
);
2100 /* Adds a newly created congruence class CLS to worklist. */
2103 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2105 /* Return if the class CLS is already presented in work list. */
2106 if (cls
->in_worklist
)
2109 cls
->in_worklist
= true;
2110 worklist
.push_back (cls
);
2113 /* Pops a class from worklist. */
2116 sem_item_optimizer::worklist_pop (void)
2118 congruence_class
*cls
;
2120 while (!worklist
.empty ())
2122 cls
= worklist
.front ();
2123 worklist
.pop_front ();
2124 if (cls
->in_worklist
)
2126 cls
->in_worklist
= false;
2132 /* Work list item was already intended to be removed.
2133 The only reason for doing it is to split a class.
2134 Thus, the class CLS is deleted. */
2142 /* Iterative congruence reduction function. */
2145 sem_item_optimizer::process_cong_reduction (void)
2147 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2148 it
!= m_classes
.end (); ++it
)
2149 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2150 if ((*it
)->classes
[i
]->is_class_used ())
2151 worklist_push ((*it
)->classes
[i
]);
2154 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2155 (unsigned long) worklist
.size ());
2157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2158 fprintf (dump_file
, "Congruence class reduction\n");
2160 congruence_class
*cls
;
2161 while ((cls
= worklist_pop ()) != NULL
)
2162 do_congruence_step (cls
);
2165 /* Debug function prints all informations about congruence classes. */
2168 sem_item_optimizer::dump_cong_classes (void)
2174 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2175 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2177 /* Histogram calculation. */
2178 unsigned int max_index
= 0;
2179 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2181 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2182 it
!= m_classes
.end (); ++it
)
2184 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2186 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2194 "Class size histogram [num of members]: number of classe number of classess\n");
2196 for (unsigned int i
= 0; i
<= max_index
; i
++)
2198 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2200 fprintf (dump_file
, "\n\n");
2203 if (dump_flags
& TDF_DETAILS
)
2204 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2205 it
!= m_classes
.end (); ++it
)
2207 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2209 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2211 (*it
)->classes
[i
]->dump (dump_file
, 4);
2213 if(i
< (*it
)->classes
.length () - 1)
2214 fprintf (dump_file
, " ");
2221 /* After reduction is done, we can declare all items in a group
2222 to be equal. PREV_CLASS_COUNT is start number of classes
2223 before reduction. */
2226 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2228 unsigned int item_count
= m_items
.length ();
2229 unsigned int class_count
= m_classes_count
;
2230 unsigned int equal_items
= item_count
- class_count
;
2232 unsigned int non_singular_classes_count
= 0;
2233 unsigned int non_singular_classes_sum
= 0;
2235 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2236 it
!= m_classes
.end (); ++it
)
2237 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2239 congruence_class
*c
= (*it
)->classes
[i
];
2240 if (c
->members
.length () > 1)
2242 non_singular_classes_count
++;
2243 non_singular_classes_sum
+= c
->members
.length ();
2249 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2250 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2251 prev_class_count
, class_count
);
2252 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2253 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2254 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2255 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2256 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2257 non_singular_classes_count
: 0.0f
,
2258 non_singular_classes_count
);
2259 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2260 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2261 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2264 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2265 it
!= m_classes
.end (); ++it
)
2266 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2268 congruence_class
*c
= (*it
)->classes
[i
];
2270 if (c
->members
.length () == 1)
2273 gcc_assert (c
->members
.length ());
2275 sem_item
*source
= c
->members
[0];
2277 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2279 sem_item
*alias
= c
->members
[j
];
2280 source
->equals (alias
, m_symtab_node_map
);
2284 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2285 source
->name (), alias
->name ());
2286 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2287 source
->asm_name (), alias
->asm_name ());
2290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2292 source
->dump_to_file (dump_file
);
2293 alias
->dump_to_file (dump_file
);
2296 source
->merge (alias
);
2301 /* Dump function prints all class members to a FILE with an INDENT. */
2304 congruence_class::dump (FILE *file
, unsigned int indent
) const
2306 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2307 id
, members
[0]->get_hash (), members
.length ());
2309 FPUTS_SPACES (file
, indent
+ 2, "");
2310 for (unsigned i
= 0; i
< members
.length (); i
++)
2311 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2312 members
[i
]->node
->order
);
2314 fprintf (file
, "\n");
2317 /* Returns true if there's a member that is used from another group. */
2320 congruence_class::is_class_used (void)
2322 for (unsigned int i
= 0; i
< members
.length (); i
++)
2323 if (members
[i
]->usages
.length ())
2329 /* Initialization and computation of symtab node hash, there data
2330 are propagated later on. */
2332 static sem_item_optimizer
*optimizer
= NULL
;
2334 /* Generate pass summary for IPA ICF pass. */
2337 ipa_icf_generate_summary (void)
2340 optimizer
= new sem_item_optimizer ();
2342 optimizer
->parse_funcs_and_vars ();
2345 /* Write pass summary for IPA ICF pass. */
2348 ipa_icf_write_summary (void)
2350 gcc_assert (optimizer
);
2352 optimizer
->write_summary ();
2355 /* Read pass summary for IPA ICF pass. */
2358 ipa_icf_read_summary (void)
2361 optimizer
= new sem_item_optimizer ();
2363 optimizer
->read_summary ();
2364 optimizer
->register_hooks ();
2367 /* Semantic equality exection function. */
2370 ipa_icf_driver (void)
2372 gcc_assert (optimizer
);
2374 optimizer
->execute ();
2375 optimizer
->unregister_hooks ();
2383 const pass_data pass_data_ipa_icf
=
2385 IPA_PASS
, /* type */
2387 OPTGROUP_IPA
, /* optinfo_flags */
2388 TV_IPA_ICF
, /* tv_id */
2389 0, /* properties_required */
2390 0, /* properties_provided */
2391 0, /* properties_destroyed */
2392 0, /* todo_flags_start */
2393 0, /* todo_flags_finish */
2396 class pass_ipa_icf
: public ipa_opt_pass_d
2399 pass_ipa_icf (gcc::context
*ctxt
)
2400 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2401 ipa_icf_generate_summary
, /* generate_summary */
2402 ipa_icf_write_summary
, /* write_summary */
2403 ipa_icf_read_summary
, /* read_summary */
2405 write_optimization_summary */
2407 read_optimization_summary */
2408 NULL
, /* stmt_fixup */
2409 0, /* function_transform_todo_flags_start */
2410 NULL
, /* function_transform */
2411 NULL
) /* variable_transform */
2414 /* opt_pass methods: */
2415 virtual bool gate (function
*)
2417 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2420 virtual unsigned int execute (function
*)
2422 return ipa_icf_driver();
2424 }; // class pass_ipa_icf
2426 } // ipa_icf namespace
2429 make_pass_ipa_icf (gcc::context
*ctxt
)
2431 return new ipa_icf::pass_ipa_icf (ctxt
);