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"
85 #include "ipa-inline.h"
88 #include "hash-table.h"
91 #include "print-tree.h"
92 #include "lto-streamer.h"
93 #include "data-streamer.h"
94 #include "ipa-utils.h"
96 #include "ipa-icf-gimple.h"
99 using namespace ipa_icf_gimple
;
102 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
104 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
105 item (_item
), index (_index
)
109 /* Semantic item constructor for a node of _TYPE, where STACK is used
110 for bitmap memory allocation. */
112 sem_item::sem_item (sem_item_type _type
,
113 bitmap_obstack
*stack
): type(_type
), hash(0)
118 /* Semantic item constructor for a node of _TYPE, where STACK is used
119 for bitmap memory allocation. The item is based on symtab node _NODE
120 with computed _HASH. */
122 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
123 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
124 node (_node
), hash (_hash
)
130 /* Add reference to a semantic TARGET. */
133 sem_item::add_reference (sem_item
*target
)
135 refs
.safe_push (target
);
136 unsigned index
= refs
.length ();
137 target
->usages
.safe_push (new sem_usage_pair(this, index
));
138 bitmap_set_bit (target
->usage_index_bitmap
, index
);
139 refs_set
.add (target
->node
);
142 /* Initialize internal data structures. Bitmap STACK is used for
143 bitmap memory allocation process. */
146 sem_item::setup (bitmap_obstack
*stack
)
148 gcc_checking_assert (node
);
151 tree_refs
.create (0);
153 usage_index_bitmap
= BITMAP_ALLOC (stack
);
156 sem_item::~sem_item ()
158 for (unsigned i
= 0; i
< usages
.length (); i
++)
162 tree_refs
.release ();
165 BITMAP_FREE (usage_index_bitmap
);
168 /* Dump function for debugging purpose. */
171 sem_item::dump (void)
175 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
176 name(), node
->order
, (void *) node
->decl
);
177 fprintf (dump_file
, " hash: %u\n", get_hash ());
178 fprintf (dump_file
, " references: ");
180 for (unsigned i
= 0; i
< refs
.length (); i
++)
181 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
182 i
< refs
.length() - 1 ? "," : "");
184 fprintf (dump_file
, "\n");
188 /* Semantic function constructor that uses STACK as bitmap memory stack. */
190 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
191 m_checker (NULL
), m_compared_func (NULL
)
193 arg_types
.create (0);
195 bb_sorted
.create (0);
198 /* Constructor based on callgraph node _NODE with computed hash _HASH.
199 Bitmap STACK is used for memory allocation. */
200 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
201 bitmap_obstack
*stack
):
202 sem_item (FUNC
, node
, hash
, stack
),
203 m_checker (NULL
), m_compared_func (NULL
)
205 arg_types
.create (0);
207 bb_sorted
.create (0);
210 sem_function::~sem_function ()
212 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
215 arg_types
.release ();
217 bb_sorted
.release ();
220 /* Calculates hash value based on a BASIC_BLOCK. */
223 sem_function::get_bb_hash (const sem_bb
*basic_block
)
225 inchash::hash hstate
;
227 hstate
.add_int (basic_block
->nondbg_stmt_count
);
228 hstate
.add_int (basic_block
->edge_count
);
230 return hstate
.end ();
233 /* References independent hash function. */
236 sem_function::get_hash (void)
240 inchash::hash hstate
;
241 hstate
.add_int (177454); /* Random number for function type. */
243 hstate
.add_int (arg_count
);
244 hstate
.add_int (cfg_checksum
);
245 hstate
.add_int (gcode_hash
);
247 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
248 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
250 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
251 hstate
.add_int (bb_sizes
[i
]);
253 hash
= hstate
.end ();
259 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
260 point to a same function. Comparison can be skipped if IGNORED_NODES
261 contains these nodes. */
264 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
266 symtab_node
*n1
, symtab_node
*n2
)
268 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
271 /* TODO: add more precise comparison for weakrefs, etc. */
273 return return_false_with_msg ("different references");
276 /* If cgraph edges E1 and E2 are indirect calls, verify that
277 ECF flags are the same. */
279 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
281 if (e1
->indirect_info
&& e2
->indirect_info
)
283 int e1_flags
= e1
->indirect_info
->ecf_flags
;
284 int e2_flags
= e2
->indirect_info
->ecf_flags
;
286 if (e1_flags
!= e2_flags
)
287 return return_false_with_msg ("ICF flags are different");
289 else if (e1
->indirect_info
|| e2
->indirect_info
)
295 /* Fast equality function based on knowledge known in WPA. */
298 sem_function::equals_wpa (sem_item
*item
,
299 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
301 gcc_assert (item
->type
== FUNC
);
303 m_compared_func
= static_cast<sem_function
*> (item
);
305 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
306 return return_false_with_msg ("different number of arguments");
308 /* Checking types of arguments. */
309 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
311 /* This guard is here for function pointer with attributes (pr59927.c). */
312 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
313 return return_false_with_msg ("NULL argument type");
315 /* Polymorphic comparison is executed just for non-leaf functions. */
316 bool is_not_leaf
= get_node ()->callees
!= NULL
;
318 if (!func_checker::compatible_types_p (arg_types
[i
],
319 m_compared_func
->arg_types
[i
],
320 is_not_leaf
, i
== 0))
321 return return_false_with_msg ("argument type is different");
324 /* Result type checking. */
325 if (!func_checker::compatible_types_p (result_type
,
326 m_compared_func
->result_type
))
327 return return_false_with_msg ("result types are different");
329 if (node
->num_references () != item
->node
->num_references ())
330 return return_false_with_msg ("different number of references");
332 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
333 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
335 item
->node
->iterate_reference (i
, ref2
);
337 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
341 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
342 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
346 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
349 e1
= e1
->next_callee
;
350 e2
= e2
->next_callee
;
354 return return_false_with_msg ("different number of edges");
359 /* Returns true if the item equals to ITEM given as argument. */
362 sem_function::equals (sem_item
*item
,
363 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
365 gcc_assert (item
->type
== FUNC
);
366 bool eq
= equals_private (item
, ignored_nodes
);
368 if (m_checker
!= NULL
)
374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
376 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
377 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
378 item
->asm_name (), eq
? "true" : "false");
383 /* Processes function equality comparison. */
386 sem_function::equals_private (sem_item
*item
,
387 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
389 if (item
->type
!= FUNC
)
392 basic_block bb1
, bb2
;
394 edge_iterator ei1
, ei2
;
399 m_compared_func
= static_cast<sem_function
*> (item
);
401 gcc_assert (decl
!= item
->decl
);
403 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
404 || edge_count
!= m_compared_func
->edge_count
405 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
406 return return_false ();
408 if (!equals_wpa (item
, ignored_nodes
))
411 /* Checking function arguments. */
412 tree decl1
= DECL_ATTRIBUTES (decl
);
413 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
415 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
416 compare_polymorphic_p (),
419 &m_compared_func
->refs_set
);
423 return return_false ();
425 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
426 return return_false ();
428 tree attr_value1
= TREE_VALUE (decl1
);
429 tree attr_value2
= TREE_VALUE (decl2
);
431 if (attr_value1
&& attr_value2
)
433 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
434 TREE_VALUE (attr_value2
));
436 return return_false_with_msg ("attribute values are different");
438 else if (!attr_value1
&& !attr_value2
)
441 return return_false ();
443 decl1
= TREE_CHAIN (decl1
);
444 decl2
= TREE_CHAIN (decl2
);
448 return return_false();
451 for (arg1
= DECL_ARGUMENTS (decl
),
452 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
453 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
454 if (!m_checker
->compare_decl (arg1
, arg2
))
455 return return_false ();
457 /* Fill-up label dictionary. */
458 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
460 m_checker
->parse_labels (bb_sorted
[i
]);
461 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
464 /* Checking all basic blocks. */
465 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
466 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
467 return return_false();
469 dump_message ("All BBs are equal\n");
471 /* Basic block edges check. */
472 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
474 bb_dict
= XNEWVEC (int, bb_sorted
.length () + 2);
475 memset (bb_dict
, -1, (bb_sorted
.length () + 2) * sizeof (int));
477 bb1
= bb_sorted
[i
]->bb
;
478 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
480 ei2
= ei_start (bb2
->preds
);
482 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
486 if (e1
->flags
!= e2
->flags
)
487 return return_false_with_msg ("flags comparison returns false");
489 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
490 return return_false_with_msg ("edge comparison returns false");
492 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
493 return return_false_with_msg ("BB comparison returns false");
495 if (!m_checker
->compare_edge (e1
, e2
))
496 return return_false_with_msg ("edge comparison returns false");
502 /* Basic block PHI nodes comparison. */
503 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
504 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
505 return return_false_with_msg ("PHI node comparison returns false");
510 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
513 sem_function::merge (sem_item
*alias_item
)
515 gcc_assert (alias_item
->type
== FUNC
);
517 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
519 cgraph_node
*original
= get_node ();
520 cgraph_node
*local_original
= original
;
521 cgraph_node
*alias
= alias_func
->get_node ();
522 bool original_address_matters
;
523 bool alias_address_matters
;
525 bool create_thunk
= false;
526 bool create_alias
= false;
527 bool redirect_callers
= false;
528 bool original_discardable
= false;
530 /* Do not attempt to mix functions from different user sections;
531 we do not know what user intends with those. */
532 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
533 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
534 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
538 "Not unifying; original and alias are in different sections.\n\n");
542 /* See if original is in a section that can be discarded if the main
543 symbol is not used. */
544 if (DECL_EXTERNAL (original
->decl
))
545 original_discardable
= true;
546 if (original
->resolution
== LDPR_PREEMPTED_REG
547 || original
->resolution
== LDPR_PREEMPTED_IR
)
548 original_discardable
= true;
549 if (original
->can_be_discarded_p ())
550 original_discardable
= true;
552 /* See if original and/or alias address can be compared for equality. */
553 original_address_matters
554 = (!DECL_VIRTUAL_P (original
->decl
)
555 && (original
->externally_visible
556 || original
->address_taken_from_non_vtable_p ()));
557 alias_address_matters
558 = (!DECL_VIRTUAL_P (alias
->decl
)
559 && (alias
->externally_visible
560 || alias
->address_taken_from_non_vtable_p ()));
562 /* If alias and original can be compared for address equality, we need
563 to create a thunk. Also we can not create extra aliases into discardable
564 section (or we risk link failures when section is discarded). */
565 if ((original_address_matters
566 && alias_address_matters
)
567 || original_discardable
)
569 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
570 create_alias
= false;
571 /* When both alias and original are not overwritable, we can save
572 the extra thunk wrapper for direct calls. */
574 = (!original_discardable
575 && alias
->get_availability () > AVAIL_INTERPOSABLE
576 && original
->get_availability () > AVAIL_INTERPOSABLE
);
581 create_thunk
= false;
582 redirect_callers
= false;
585 if (create_alias
&& DECL_COMDAT_GROUP (alias
->decl
))
587 create_alias
= false;
591 /* We want thunk to always jump to the local function body
592 unless the body is comdat and may be optimized out. */
593 if ((create_thunk
|| redirect_callers
)
594 && (!original_discardable
595 || (DECL_COMDAT_GROUP (original
->decl
)
596 && (DECL_COMDAT_GROUP (original
->decl
)
597 == DECL_COMDAT_GROUP (alias
->decl
)))))
599 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
601 if (redirect_callers
)
603 /* If alias is non-overwritable then
604 all direct calls are safe to be redirected to the original. */
605 bool redirected
= false;
606 while (alias
->callers
)
608 cgraph_edge
*e
= alias
->callers
;
609 e
->redirect_callee (local_original
);
610 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
613 e
->redirect_call_stmt_to_callee ();
619 alias
->icf_merged
= true;
621 /* The alias function is removed if symbol address
623 if (!alias_address_matters
)
626 if (dump_file
&& redirected
)
627 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
629 /* If the condtion above is not met, we are lucky and can turn the
630 function into real alias. */
631 else if (create_alias
)
633 alias
->icf_merged
= true;
635 /* Remove the function's body. */
636 ipa_merge_profiles (original
, alias
);
637 alias
->release_body (true);
640 /* Create the alias. */
641 cgraph_node::create_alias (alias_func
->decl
, decl
);
642 alias
->resolve_alias (original
);
644 /* Workaround for PR63566 that forces equal calling convention
646 alias
->local
.local
= false;
647 original
->local
.local
= false;
650 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
652 else if (create_thunk
)
654 if (DECL_COMDAT_GROUP (alias
->decl
))
657 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
662 alias
->icf_merged
= true;
663 ipa_merge_profiles (local_original
, alias
);
664 alias
->create_wrapper (local_original
);
667 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
670 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
675 /* Semantic item initialization function. */
678 sem_function::init (void)
681 get_node ()->get_body ();
683 tree fndecl
= node
->decl
;
684 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
687 gcc_assert (SSANAMES (func
));
689 ssa_names_size
= SSANAMES (func
)->length ();
693 region_tree
= func
->eh
->region_tree
;
695 /* iterating all function arguments. */
696 arg_count
= count_formal_params (fndecl
);
698 edge_count
= n_edges_for_fn (func
);
699 cfg_checksum
= coverage_compute_cfg_checksum (func
);
701 inchash::hash hstate
;
704 FOR_EACH_BB_FN (bb
, func
)
706 unsigned nondbg_stmt_count
= 0;
709 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
710 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
713 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
716 gimple stmt
= gsi_stmt (gsi
);
718 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
720 hash_stmt (&hstate
, stmt
);
725 gcode_hash
= hstate
.end ();
726 bb_sizes
.safe_push (nondbg_stmt_count
);
728 /* Inserting basic block to hash table. */
729 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
730 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
732 bb_sorted
.safe_push (semantic_bb
);
738 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
741 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
743 enum gimple_code code
= gimple_code (stmt
);
745 hstate
->add_int (code
);
747 if (code
== GIMPLE_CALL
)
749 /* Checking of argument. */
750 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
752 tree argument
= gimple_call_arg (stmt
, i
);
754 switch (TREE_CODE (argument
))
757 if (tree_fits_shwi_p (argument
))
758 hstate
->add_wide_int (tree_to_shwi (argument
));
759 else if (tree_fits_uhwi_p (argument
))
760 hstate
->add_wide_int (tree_to_uhwi (argument
));
766 c
= TREE_REAL_CST (argument
);
767 n
= real_to_integer (&c
);
769 hstate
->add_wide_int (n
);
773 tree addr_operand
= TREE_OPERAND (argument
, 0);
775 if (TREE_CODE (addr_operand
) == STRING_CST
)
776 hstate
->add (TREE_STRING_POINTER (addr_operand
),
777 TREE_STRING_LENGTH (addr_operand
));
788 /* Return true if polymorphic comparison must be processed. */
791 sem_function::compare_polymorphic_p (void)
793 return get_node ()->callees
!= NULL
794 || m_compared_func
->get_node ()->callees
!= NULL
;
797 /* For a given call graph NODE, the function constructs new
798 semantic function item. */
801 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
803 tree fndecl
= node
->decl
;
804 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
806 /* TODO: add support for thunks and aliases. */
808 if (!func
|| !node
->has_gimple_body_p ())
811 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
814 sem_function
*f
= new sem_function (node
, 0, stack
);
821 /* Parses function arguments and result type. */
824 sem_function::parse_tree_args (void)
828 if (arg_types
.exists ())
829 arg_types
.release ();
831 arg_types
.create (4);
832 tree fnargs
= DECL_ARGUMENTS (decl
);
834 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
835 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
837 /* Function result type. */
838 result
= DECL_RESULT (decl
);
839 result_type
= result
? TREE_TYPE (result
) : NULL
;
841 /* During WPA, we can get arguments by following method. */
844 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
845 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
846 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
848 result_type
= TREE_TYPE (TREE_TYPE (decl
));
852 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
853 return true if phi nodes are semantically equivalent in these blocks . */
856 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
858 gphi_iterator si1
, si2
;
860 unsigned size1
, size2
, i
;
864 gcc_assert (bb1
!= NULL
);
865 gcc_assert (bb2
!= NULL
);
867 si2
= gsi_start_phis (bb2
);
868 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
871 gsi_next_nonvirtual_phi (&si1
);
872 gsi_next_nonvirtual_phi (&si2
);
874 if (gsi_end_p (si1
) && gsi_end_p (si2
))
877 if (gsi_end_p (si1
) || gsi_end_p (si2
))
878 return return_false();
883 tree phi_result1
= gimple_phi_result (phi1
);
884 tree phi_result2
= gimple_phi_result (phi2
);
886 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
887 return return_false_with_msg ("PHI results are different");
889 size1
= gimple_phi_num_args (phi1
);
890 size2
= gimple_phi_num_args (phi2
);
893 return return_false ();
895 for (i
= 0; i
< size1
; ++i
)
897 t1
= gimple_phi_arg (phi1
, i
)->def
;
898 t2
= gimple_phi_arg (phi2
, i
)->def
;
900 if (!m_checker
->compare_operand (t1
, t2
))
901 return return_false ();
903 e1
= gimple_phi_arg_edge (phi1
, i
);
904 e2
= gimple_phi_arg_edge (phi2
, i
);
906 if (!m_checker
->compare_edge (e1
, e2
))
907 return return_false ();
916 /* Returns true if tree T can be compared as a handled component. */
919 sem_function::icf_handled_component_p (tree t
)
921 tree_code tc
= TREE_CODE (t
);
923 return ((handled_component_p (t
))
924 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
925 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
928 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
929 corresponds to TARGET. */
932 sem_function::bb_dict_test (int* bb_dict
, int source
, int target
)
934 if (bb_dict
[source
] == -1)
936 bb_dict
[source
] = target
;
940 return bb_dict
[source
] == target
;
943 /* Iterates all tree types in T1 and T2 and returns true if all types
944 are compatible. If COMPARE_POLYMORPHIC is set to true,
945 more strict comparison is executed. */
948 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
956 while (t1
!= NULL
&& t2
!= NULL
)
958 tv1
= TREE_VALUE (t1
);
959 tv2
= TREE_VALUE (t2
);
961 tc1
= TREE_CODE (tv1
);
962 tc2
= TREE_CODE (tv2
);
964 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
966 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
968 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
971 t1
= TREE_CHAIN (t1
);
972 t2
= TREE_CHAIN (t2
);
979 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
981 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
985 /* Constructor based on varpool node _NODE with computed hash _HASH.
986 Bitmap STACK is used for memory allocation. */
988 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
989 bitmap_obstack
*stack
): sem_item(VAR
,
992 gcc_checking_assert (node
);
993 gcc_checking_assert (get_node ());
996 /* Returns true if the item equals to ITEM given as argument. */
999 sem_variable::equals (sem_item
*item
,
1000 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1002 gcc_assert (item
->type
== VAR
);
1004 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1006 if (!ctor
|| !v
->ctor
)
1007 return return_false_with_msg ("ctor is missing for semantic variable");
1009 return sem_variable::equals (ctor
, v
->ctor
);
1012 /* Compares trees T1 and T2 for semantic equality. */
1015 sem_variable::equals (tree t1
, tree t2
)
1017 tree_code tc1
= TREE_CODE (t1
);
1018 tree_code tc2
= TREE_CODE (t2
);
1027 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1028 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1033 for (unsigned i
= 0; i
< len1
; i
++)
1034 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1035 CONSTRUCTOR_ELT (t2
, i
)->value
)
1036 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1043 tree x1
= TREE_OPERAND (t1
, 0);
1044 tree x2
= TREE_OPERAND (t2
, 0);
1045 tree y1
= TREE_OPERAND (t1
, 1);
1046 tree y2
= TREE_OPERAND (t2
, 1);
1048 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1050 return return_false ();
1052 /* Type of the offset on MEM_REF does not matter. */
1053 return sem_variable::equals (x1
, x2
)
1054 && wi::to_offset (y1
) == wi::to_offset (y2
);
1059 tree op1
= TREE_OPERAND (t1
, 0);
1060 tree op2
= TREE_OPERAND (t2
, 0);
1061 return sem_variable::equals (op1
, op2
);
1069 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1071 && wi::to_offset (t1
) == wi::to_offset (t2
);
1075 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1078 case POINTER_PLUS_EXPR
:
1080 tree x1
= TREE_OPERAND (t1
, 0);
1081 tree x2
= TREE_OPERAND (t2
, 0);
1082 tree y1
= TREE_OPERAND (t1
, 1);
1083 tree y2
= TREE_OPERAND (t2
, 1);
1085 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1088 return return_false_with_msg ("ERROR_MARK");
1090 return return_false_with_msg ("Unknown TREE code reached");
1094 /* Parser function that visits a varpool NODE. */
1097 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1099 tree decl
= node
->decl
;
1101 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1102 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1103 || !TREE_ADDRESSABLE (decl
));
1108 tree ctor
= ctor_for_folding (decl
);
1112 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1119 /* References independent hash function. */
1122 sem_variable::get_hash (void)
1127 inchash::hash hstate
;
1129 hstate
.add_int (456346417);
1130 hstate
.add_int (TREE_CODE (ctor
));
1132 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1134 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1135 hstate
.add_int (length
);
1138 hash
= hstate
.end ();
1143 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1147 sem_variable::merge (sem_item
*alias_item
)
1149 gcc_assert (alias_item
->type
== VAR
);
1151 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1153 varpool_node
*original
= get_node ();
1154 varpool_node
*alias
= alias_var
->get_node ();
1155 bool original_discardable
= false;
1157 /* See if original is in a section that can be discarded if the main
1158 symbol is not used. */
1159 if (DECL_EXTERNAL (original
->decl
))
1160 original_discardable
= true;
1161 if (original
->resolution
== LDPR_PREEMPTED_REG
1162 || original
->resolution
== LDPR_PREEMPTED_IR
)
1163 original_discardable
= true;
1164 if (original
->can_be_discarded_p ())
1165 original_discardable
= true;
1167 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1169 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1170 !compare_sections (alias_var
))
1173 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1179 // alias cycle creation check
1180 varpool_node
*n
= original
;
1184 n
= n
->get_alias_target ();
1188 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1194 alias
->analyzed
= false;
1196 DECL_INITIAL (alias
->decl
) = NULL
;
1197 alias
->remove_all_references ();
1199 varpool_node::create_alias (alias_var
->decl
, decl
);
1200 alias
->resolve_alias (original
);
1203 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1210 sem_variable::compare_sections (sem_variable
*alias
)
1212 const char *source
= node
->get_section ();
1213 const char *target
= alias
->node
->get_section();
1215 if (source
== NULL
&& target
== NULL
)
1217 else if(!source
|| !target
)
1220 return strcmp (source
, target
) == 0;
1223 /* Dump symbol to FILE. */
1226 sem_variable::dump_to_file (FILE *file
)
1230 print_node (file
, "", decl
, 0);
1231 fprintf (file
, "\n\n");
1234 /* Iterates though a constructor and identifies tree references
1235 we are interested in semantic function equality. */
1238 sem_variable::parse_tree_refs (tree t
)
1240 switch (TREE_CODE (t
))
1244 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1246 for (unsigned i
= 0; i
< length
; i
++)
1247 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1254 tree op
= TREE_OPERAND (t
, 0);
1255 parse_tree_refs (op
);
1260 tree_refs
.safe_push (t
);
1268 unsigned int sem_item_optimizer::class_id
= 0;
1270 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1271 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1274 bitmap_obstack_initialize (&m_bmstack
);
1277 sem_item_optimizer::~sem_item_optimizer ()
1279 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1282 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1283 it
!= m_classes
.end (); ++it
)
1285 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1286 delete (*it
)->classes
[i
];
1288 (*it
)->classes
.release ();
1293 bitmap_obstack_release (&m_bmstack
);
1296 /* Write IPA ICF summary for symbols. */
1299 sem_item_optimizer::write_summary (void)
1301 unsigned int count
= 0;
1303 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1304 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1307 /* Calculate number of symbols to be serialized. */
1308 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1310 lsei_next_in_partition (&lsei
))
1312 symtab_node
*node
= lsei_node (lsei
);
1314 if (m_symtab_node_map
.get (node
))
1318 streamer_write_uhwi (ob
, count
);
1320 /* Process all of the symbols. */
1321 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1323 lsei_next_in_partition (&lsei
))
1325 symtab_node
*node
= lsei_node (lsei
);
1327 sem_item
**item
= m_symtab_node_map
.get (node
);
1331 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1332 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1334 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1338 streamer_write_char_stream (ob
->main_stream
, 0);
1339 produce_asm (ob
, NULL
);
1340 destroy_output_block (ob
);
1343 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1344 contains LEN bytes. */
1347 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1348 const char *data
, size_t len
)
1350 const lto_function_header
*header
=
1351 (const lto_function_header
*) data
;
1352 const int cfg_offset
= sizeof (lto_function_header
);
1353 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1354 const int string_offset
= main_offset
+ header
->main_size
;
1359 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1363 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1364 header
->string_size
, vNULL
);
1366 count
= streamer_read_uhwi (&ib_main
);
1368 for (i
= 0; i
< count
; i
++)
1372 lto_symtab_encoder_t encoder
;
1374 index
= streamer_read_uhwi (&ib_main
);
1375 encoder
= file_data
->symtab_node_encoder
;
1376 node
= lto_symtab_encoder_deref (encoder
, index
);
1378 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1380 gcc_assert (node
->definition
);
1383 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1384 (void *) node
->decl
, node
->order
);
1386 if (is_a
<cgraph_node
*> (node
))
1388 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1390 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1394 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1396 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1400 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1402 lto_data_in_delete (data_in
);
1405 /* Read IPA IPA ICF summary for symbols. */
1408 sem_item_optimizer::read_summary (void)
1410 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1411 lto_file_decl_data
*file_data
;
1414 while ((file_data
= file_data_vec
[j
++]))
1417 const char *data
= lto_get_section_data (file_data
,
1418 LTO_section_ipa_icf
, NULL
, &len
);
1421 read_section (file_data
, data
, len
);
1425 /* Register callgraph and varpool hooks. */
1428 sem_item_optimizer::register_hooks (void)
1430 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1431 (&sem_item_optimizer::cgraph_removal_hook
, this);
1433 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1434 (&sem_item_optimizer::varpool_removal_hook
, this);
1437 /* Unregister callgraph and varpool hooks. */
1440 sem_item_optimizer::unregister_hooks (void)
1442 if (m_cgraph_node_hooks
)
1443 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1445 if (m_varpool_node_hooks
)
1446 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1449 /* Adds a CLS to hashtable associated by hash value. */
1452 sem_item_optimizer::add_class (congruence_class
*cls
)
1454 gcc_assert (cls
->members
.length ());
1456 congruence_class_group
*group
= get_group_by_hash (
1457 cls
->members
[0]->get_hash (),
1458 cls
->members
[0]->type
);
1459 group
->classes
.safe_push (cls
);
1462 /* Gets a congruence class group based on given HASH value and TYPE. */
1464 congruence_class_group
*
1465 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1467 congruence_class_group
*item
= XNEW (congruence_class_group
);
1471 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1477 item
->classes
.create (1);
1484 /* Callgraph removal hook called for a NODE with a custom DATA. */
1487 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1489 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1490 optimizer
->remove_symtab_node (node
);
1493 /* Varpool removal hook called for a NODE with a custom DATA. */
1496 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1498 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1499 optimizer
->remove_symtab_node (node
);
1502 /* Remove symtab NODE triggered by symtab removal hooks. */
1505 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1507 gcc_assert (!m_classes
.elements());
1509 m_removed_items_set
.add (node
);
1513 sem_item_optimizer::remove_item (sem_item
*item
)
1515 if (m_symtab_node_map
.get (item
->node
))
1516 m_symtab_node_map
.remove (item
->node
);
1520 /* Removes all callgraph and varpool nodes that are marked by symtab
1524 sem_item_optimizer::filter_removed_items (void)
1526 auto_vec
<sem_item
*> filtered
;
1528 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1530 sem_item
*item
= m_items
[i
];
1532 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1538 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1544 bool no_body_function
= false;
1546 if (item
->type
== FUNC
)
1548 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1550 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1553 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1554 && !no_body_function
)
1556 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1557 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1559 filtered
.safe_push (m_items
[i
]);
1567 /* Clean-up of released semantic items. */
1570 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1571 m_items
.safe_push (filtered
[i
]);
1574 /* Optimizer entry point. */
1577 sem_item_optimizer::execute (void)
1579 filter_removed_items ();
1580 build_hash_based_classes ();
1583 fprintf (dump_file
, "Dump after hash based groups\n");
1584 dump_cong_classes ();
1586 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1587 m_items
[i
]->init_wpa ();
1591 subdivide_classes_by_equality (true);
1594 fprintf (dump_file
, "Dump after WPA based types groups\n");
1596 dump_cong_classes ();
1598 process_cong_reduction ();
1602 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1604 dump_cong_classes ();
1606 parse_nonsingleton_classes ();
1607 subdivide_classes_by_equality ();
1610 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1612 dump_cong_classes ();
1614 unsigned int prev_class_count
= m_classes_count
;
1616 process_cong_reduction ();
1617 dump_cong_classes ();
1619 merge_classes (prev_class_count
);
1621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1622 symtab_node::dump_table (dump_file
);
1625 /* Function responsible for visiting all potential functions and
1626 read-only variables that can be merged. */
1629 sem_item_optimizer::parse_funcs_and_vars (void)
1633 if (flag_ipa_icf_functions
)
1634 FOR_EACH_DEFINED_FUNCTION (cnode
)
1636 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1639 m_items
.safe_push (f
);
1640 m_symtab_node_map
.put (cnode
, f
);
1643 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1646 f
->dump_to_file (dump_file
);
1649 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1652 varpool_node
*vnode
;
1654 if (flag_ipa_icf_variables
)
1655 FOR_EACH_DEFINED_VARIABLE (vnode
)
1657 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1661 m_items
.safe_push (v
);
1662 m_symtab_node_map
.put (vnode
, v
);
1667 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1670 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1672 item
->index_in_class
= cls
->members
.length ();
1673 cls
->members
.safe_push (item
);
1677 /* Congruence classes are built by hash value. */
1680 sem_item_optimizer::build_hash_based_classes (void)
1682 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1684 sem_item
*item
= m_items
[i
];
1686 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1689 if (!group
->classes
.length ())
1692 group
->classes
.safe_push (new congruence_class (class_id
++));
1695 add_item_to_class (group
->classes
[0], item
);
1699 /* Build references according to call graph. */
1702 sem_item_optimizer::build_graph (void)
1704 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1706 sem_item
*item
= m_items
[i
];
1707 m_symtab_node_map
.put (item
->node
, item
);
1710 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1712 sem_item
*item
= m_items
[i
];
1714 if (item
->type
== FUNC
)
1716 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1718 cgraph_edge
*e
= cnode
->callees
;
1721 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1723 item
->add_reference (*slot
);
1729 ipa_ref
*ref
= NULL
;
1730 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1732 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1734 item
->add_reference (*slot
);
1739 /* Semantic items in classes having more than one element and initialized.
1740 In case of WPA, we load function body. */
1743 sem_item_optimizer::parse_nonsingleton_classes (void)
1745 unsigned int init_called_count
= 0;
1747 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1748 if (m_items
[i
]->cls
->members
.length () > 1)
1750 m_items
[i
]->init ();
1751 init_called_count
++;
1755 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1756 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1759 /* Equality function for semantic items is used to subdivide existing
1760 classes. If IN_WPA, fast equality function is invoked. */
1763 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1765 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1766 it
!= m_classes
.end (); ++it
)
1768 unsigned int class_count
= (*it
)->classes
.length ();
1770 for (unsigned i
= 0; i
< class_count
; i
++)
1772 congruence_class
*c
= (*it
)->classes
[i
];
1774 if (c
->members
.length() > 1)
1776 auto_vec
<sem_item
*> new_vector
;
1778 sem_item
*first
= c
->members
[0];
1779 new_vector
.safe_push (first
);
1781 unsigned class_split_first
= (*it
)->classes
.length ();
1783 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1785 sem_item
*item
= c
->members
[j
];
1787 bool equals
= in_wpa
? first
->equals_wpa (item
,
1788 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1791 new_vector
.safe_push (item
);
1794 bool integrated
= false;
1796 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1798 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1799 bool equals
= in_wpa
? x
->equals_wpa (item
,
1800 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1805 add_item_to_class ((*it
)->classes
[k
], item
);
1813 congruence_class
*c
= new congruence_class (class_id
++);
1815 add_item_to_class (c
, item
);
1817 (*it
)->classes
.safe_push (c
);
1822 // we replace newly created new_vector for the class we've just splitted
1823 c
->members
.release ();
1824 c
->members
.create (new_vector
.length ());
1826 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1827 add_item_to_class (c
, new_vector
[j
]);
1835 /* Verify congruence classes if checking is enabled. */
1838 sem_item_optimizer::verify_classes (void)
1841 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1842 it
!= m_classes
.end (); ++it
)
1844 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1846 congruence_class
*cls
= (*it
)->classes
[i
];
1848 gcc_checking_assert (cls
);
1849 gcc_checking_assert (cls
->members
.length () > 0);
1851 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1853 sem_item
*item
= cls
->members
[j
];
1855 gcc_checking_assert (item
);
1856 gcc_checking_assert (item
->cls
== cls
);
1858 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1860 sem_usage_pair
*usage
= item
->usages
[k
];
1861 gcc_checking_assert (usage
->item
->index_in_class
<
1862 usage
->item
->cls
->members
.length ());
1870 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1871 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1872 but unused argument. */
1875 sem_item_optimizer::release_split_map (congruence_class
* const &,
1876 bitmap
const &b
, traverse_split_pair
*)
1885 /* Process split operation for a class given as pointer CLS_PTR,
1886 where bitmap B splits congruence class members. DATA is used
1887 as argument of split pair. */
1890 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1891 bitmap
const &b
, traverse_split_pair
*pair
)
1893 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1894 const congruence_class
*splitter_cls
= pair
->cls
;
1896 /* If counted bits are greater than zero and less than the number of members
1897 a group will be splitted. */
1898 unsigned popcount
= bitmap_count_bits (b
);
1900 if (popcount
> 0 && popcount
< cls
->members
.length ())
1902 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1904 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1906 int target
= bitmap_bit_p (b
, i
);
1907 congruence_class
*tc
= newclasses
[target
];
1909 add_item_to_class (tc
, cls
->members
[i
]);
1912 #ifdef ENABLE_CHECKING
1913 for (unsigned int i
= 0; i
< 2; i
++)
1914 gcc_checking_assert (newclasses
[i
]->members
.length ());
1917 if (splitter_cls
== cls
)
1918 optimizer
->splitter_class_removed
= true;
1920 /* Remove old class from worklist if presented. */
1921 bool in_worklist
= cls
->in_worklist
;
1924 cls
->in_worklist
= false;
1926 congruence_class_group g
;
1927 g
.hash
= cls
->members
[0]->get_hash ();
1928 g
.type
= cls
->members
[0]->type
;
1930 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1932 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1933 if (slot
->classes
[i
] == cls
)
1935 slot
->classes
.ordered_remove (i
);
1939 /* New class will be inserted and integrated to work list. */
1940 for (unsigned int i
= 0; i
< 2; i
++)
1941 optimizer
->add_class (newclasses
[i
]);
1943 /* Two classes replace one, so that increment just by one. */
1944 optimizer
->m_classes_count
++;
1946 /* If OLD class was presented in the worklist, we remove the class
1947 and replace it will both newly created classes. */
1949 for (unsigned int i
= 0; i
< 2; i
++)
1950 optimizer
->worklist_push (newclasses
[i
]);
1951 else /* Just smaller class is inserted. */
1953 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1954 newclasses
[1]->members
.length () ?
1956 optimizer
->worklist_push (newclasses
[smaller_index
]);
1959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1961 fprintf (dump_file
, " congruence class splitted:\n");
1962 cls
->dump (dump_file
, 4);
1964 fprintf (dump_file
, " newly created groups:\n");
1965 for (unsigned int i
= 0; i
< 2; i
++)
1966 newclasses
[i
]->dump (dump_file
, 4);
1969 /* Release class if not presented in work list. */
1978 /* Tests if a class CLS used as INDEXth splits any congruence classes.
1979 Bitmap stack BMSTACK is used for bitmap allocation. */
1982 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
1985 hash_map
<congruence_class
*, bitmap
> split_map
;
1987 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1989 sem_item
*item
= cls
->members
[i
];
1991 /* Iterate all usages that have INDEX as usage of the item. */
1992 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
1994 sem_usage_pair
*usage
= item
->usages
[j
];
1996 if (usage
->index
!= index
)
1999 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2004 b
= BITMAP_ALLOC (&m_bmstack
);
2005 split_map
.put (usage
->item
->cls
, b
);
2011 gcc_checking_assert (usage
->item
->cls
);
2012 gcc_checking_assert (usage
->item
->index_in_class
<
2013 usage
->item
->cls
->members
.length ());
2016 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2020 traverse_split_pair pair
;
2021 pair
.optimizer
= this;
2024 splitter_class_removed
= false;
2026 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2028 /* Bitmap clean-up. */
2030 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2033 /* Every usage of a congruence class CLS is a candidate that can split the
2034 collection of classes. Bitmap stack BMSTACK is used for bitmap
2038 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2043 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2045 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2046 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2048 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2051 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2054 do_congruence_step_for_index (cls
, i
);
2056 if (splitter_class_removed
)
2060 BITMAP_FREE (usage
);
2063 /* Adds a newly created congruence class CLS to worklist. */
2066 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2068 /* Return if the class CLS is already presented in work list. */
2069 if (cls
->in_worklist
)
2072 cls
->in_worklist
= true;
2073 worklist
.push_back (cls
);
2076 /* Pops a class from worklist. */
2079 sem_item_optimizer::worklist_pop (void)
2081 congruence_class
*cls
;
2083 while (!worklist
.empty ())
2085 cls
= worklist
.front ();
2086 worklist
.pop_front ();
2087 if (cls
->in_worklist
)
2089 cls
->in_worklist
= false;
2095 /* Work list item was already intended to be removed.
2096 The only reason for doing it is to split a class.
2097 Thus, the class CLS is deleted. */
2105 /* Iterative congruence reduction function. */
2108 sem_item_optimizer::process_cong_reduction (void)
2110 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2111 it
!= m_classes
.end (); ++it
)
2112 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2113 if ((*it
)->classes
[i
]->is_class_used ())
2114 worklist_push ((*it
)->classes
[i
]);
2117 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2118 (unsigned long) worklist
.size ());
2120 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2121 fprintf (dump_file
, "Congruence class reduction\n");
2123 congruence_class
*cls
;
2124 while ((cls
= worklist_pop ()) != NULL
)
2125 do_congruence_step (cls
);
2128 /* Debug function prints all informations about congruence classes. */
2131 sem_item_optimizer::dump_cong_classes (void)
2137 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2138 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2140 /* Histogram calculation. */
2141 unsigned int max_index
= 0;
2142 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2144 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2145 it
!= m_classes
.end (); ++it
)
2147 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2149 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2157 "Class size histogram [num of members]: number of classe number of classess\n");
2159 for (unsigned int i
= 0; i
<= max_index
; i
++)
2161 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2163 fprintf (dump_file
, "\n\n");
2166 if (dump_flags
& TDF_DETAILS
)
2167 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2168 it
!= m_classes
.end (); ++it
)
2170 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2172 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2174 (*it
)->classes
[i
]->dump (dump_file
, 4);
2176 if(i
< (*it
)->classes
.length () - 1)
2177 fprintf (dump_file
, " ");
2184 /* After reduction is done, we can declare all items in a group
2185 to be equal. PREV_CLASS_COUNT is start number of classes
2186 before reduction. */
2189 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2191 unsigned int item_count
= m_items
.length ();
2192 unsigned int class_count
= m_classes_count
;
2193 unsigned int equal_items
= item_count
- class_count
;
2195 unsigned int non_singular_classes_count
= 0;
2196 unsigned int non_singular_classes_sum
= 0;
2198 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2199 it
!= m_classes
.end (); ++it
)
2200 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2202 congruence_class
*c
= (*it
)->classes
[i
];
2203 if (c
->members
.length () > 1)
2205 non_singular_classes_count
++;
2206 non_singular_classes_sum
+= c
->members
.length ();
2212 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2213 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2214 prev_class_count
, class_count
);
2215 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2216 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2217 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2218 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2219 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2220 non_singular_classes_count
: 0.0f
,
2221 non_singular_classes_count
);
2222 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2223 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2224 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2227 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2228 it
!= m_classes
.end (); ++it
)
2229 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2231 congruence_class
*c
= (*it
)->classes
[i
];
2233 if (c
->members
.length () == 1)
2236 gcc_assert (c
->members
.length ());
2238 sem_item
*source
= c
->members
[0];
2240 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2242 sem_item
*alias
= c
->members
[j
];
2243 source
->equals (alias
, m_symtab_node_map
);
2247 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2248 source
->name (), alias
->name ());
2249 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2250 source
->asm_name (), alias
->asm_name ());
2253 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2255 source
->dump_to_file (dump_file
);
2256 alias
->dump_to_file (dump_file
);
2259 source
->merge (alias
);
2264 /* Dump function prints all class members to a FILE with an INDENT. */
2267 congruence_class::dump (FILE *file
, unsigned int indent
) const
2269 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2270 id
, members
[0]->get_hash (), members
.length ());
2272 FPUTS_SPACES (file
, indent
+ 2, "");
2273 for (unsigned i
= 0; i
< members
.length (); i
++)
2274 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2275 members
[i
]->node
->order
);
2277 fprintf (file
, "\n");
2280 /* Returns true if there's a member that is used from another group. */
2283 congruence_class::is_class_used (void)
2285 for (unsigned int i
= 0; i
< members
.length (); i
++)
2286 if (members
[i
]->usages
.length ())
2292 /* Initialization and computation of symtab node hash, there data
2293 are propagated later on. */
2295 static sem_item_optimizer
*optimizer
= NULL
;
2297 /* Generate pass summary for IPA ICF pass. */
2300 ipa_icf_generate_summary (void)
2303 optimizer
= new sem_item_optimizer ();
2305 optimizer
->parse_funcs_and_vars ();
2308 /* Write pass summary for IPA ICF pass. */
2311 ipa_icf_write_summary (void)
2313 gcc_assert (optimizer
);
2315 optimizer
->write_summary ();
2318 /* Read pass summary for IPA ICF pass. */
2321 ipa_icf_read_summary (void)
2324 optimizer
= new sem_item_optimizer ();
2326 optimizer
->read_summary ();
2327 optimizer
->register_hooks ();
2330 /* Semantic equality exection function. */
2333 ipa_icf_driver (void)
2335 gcc_assert (optimizer
);
2337 optimizer
->execute ();
2338 optimizer
->unregister_hooks ();
2346 const pass_data pass_data_ipa_icf
=
2348 IPA_PASS
, /* type */
2350 OPTGROUP_IPA
, /* optinfo_flags */
2351 TV_IPA_ICF
, /* tv_id */
2352 0, /* properties_required */
2353 0, /* properties_provided */
2354 0, /* properties_destroyed */
2355 0, /* todo_flags_start */
2356 0, /* todo_flags_finish */
2359 class pass_ipa_icf
: public ipa_opt_pass_d
2362 pass_ipa_icf (gcc::context
*ctxt
)
2363 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2364 ipa_icf_generate_summary
, /* generate_summary */
2365 ipa_icf_write_summary
, /* write_summary */
2366 ipa_icf_read_summary
, /* read_summary */
2368 write_optimization_summary */
2370 read_optimization_summary */
2371 NULL
, /* stmt_fixup */
2372 0, /* function_transform_todo_flags_start */
2373 NULL
, /* function_transform */
2374 NULL
) /* variable_transform */
2377 /* opt_pass methods: */
2378 virtual bool gate (function
*)
2380 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2383 virtual unsigned int execute (function
*)
2385 return ipa_icf_driver();
2387 }; // class pass_ipa_icf
2389 } // ipa_icf namespace
2392 make_pass_ipa_icf (gcc::context
*ctxt
)
2394 return new ipa_icf::pass_ipa_icf (ctxt
);