Daily bump.
[gcc.git] / gcc / ipa-icf.h
1 /* Interprocedural semantic function equality pass
2 Copyright (C) 2014-2021 Free Software Foundation, Inc.
3
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
5
6 This file is part of GCC.
7
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
11 version.
12
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
16 for more details.
17
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/>. */
21
22 namespace ipa_icf {
23 class sem_item;
24
25 /* Congruence class encompasses a collection of either functions or
26 read-only variables. These items are considered to be equivalent
27 if not proved the opposite. */
28 class congruence_class
29 {
30 public:
31 /* Congruence class constructor for a new class with _ID. */
32 congruence_class (unsigned int _id): in_worklist (false), id (_id),
33 referenced_by_count (0)
34 {
35 }
36
37 /* Destructor. */
38 ~congruence_class ()
39 {
40 }
41
42 /* Dump function prints all class members to a FILE with an INDENT. */
43 void dump (FILE *file, unsigned int indent = 0) const;
44
45 /* Returns true if there's a member that is used from another group. */
46 bool is_class_used (void);
47
48 /* Flag is used in case we want to remove a class from worklist and
49 delete operation is quite expensive for
50 the data structure (linked list). */
51 bool in_worklist;
52
53 /* Vector of all group members. */
54 auto_vec <sem_item *> members;
55
56 /* Global unique class identifier. */
57 unsigned int id;
58
59 /* Total number of references to items of this class. */
60 unsigned referenced_by_count;
61 };
62
63 /* Semantic item type enum. */
64 enum sem_item_type
65 {
66 FUNC,
67 VAR
68 };
69
70 /* Class is container for address references for a symtab_node. */
71
72 class symbol_compare_collection
73 {
74 public:
75 /* Constructor. */
76 symbol_compare_collection (symtab_node *node);
77
78 /* Destructor. */
79 ~symbol_compare_collection ()
80 {
81 m_references.release ();
82 m_interposables.release ();
83 }
84
85 /* Vector of address references. */
86 vec<symtab_node *> m_references;
87
88 /* Vector of interposable references. */
89 vec<symtab_node *> m_interposables;
90 };
91
92 /* Hash traits for symbol_compare_collection map. */
93
94 struct symbol_compare_hash : nofree_ptr_hash <symbol_compare_collection>
95 {
96 static hashval_t
97 hash (value_type v)
98 {
99 inchash::hash hstate;
100 hstate.add_int (v->m_references.length ());
101
102 for (unsigned i = 0; i < v->m_references.length (); i++)
103 hstate.add_int (v->m_references[i]->ultimate_alias_target ()->order);
104
105 hstate.add_int (v->m_interposables.length ());
106
107 for (unsigned i = 0; i < v->m_interposables.length (); i++)
108 hstate.add_int (v->m_interposables[i]->ultimate_alias_target ()->order);
109
110 return hstate.end ();
111 }
112
113 static bool
114 equal (value_type a, value_type b)
115 {
116 if (a->m_references.length () != b->m_references.length ()
117 || a->m_interposables.length () != b->m_interposables.length ())
118 return false;
119
120 for (unsigned i = 0; i < a->m_references.length (); i++)
121 if (a->m_references[i]->equal_address_to (b->m_references[i]) != 1)
122 return false;
123
124 for (unsigned i = 0; i < a->m_interposables.length (); i++)
125 if (!a->m_interposables[i]->semantically_equivalent_p
126 (b->m_interposables[i]))
127 return false;
128
129 return true;
130 }
131 };
132
133 /* Semantic item usage pair. */
134 class sem_usage_pair
135 {
136 public:
137 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
138 sem_usage_pair (sem_item *_item, unsigned int _index);
139
140 /* Target semantic item where an item is used. */
141 sem_item *item;
142
143 /* Index of usage of such an item. */
144 unsigned int index;
145 };
146
147 struct sem_usage_pair_hash : pointer_hash <sem_usage_pair>
148 {
149 static inline hashval_t hash (sem_usage_pair *);
150 static inline bool equal (sem_usage_pair *, sem_usage_pair *);
151 };
152
153 inline hashval_t
154 sem_usage_pair_hash::hash (sem_usage_pair *pair)
155 {
156 inchash::hash hstate;
157
158 hstate.add_ptr (pair->item);
159 hstate.add_int (pair->index);
160
161 return hstate.end ();
162 }
163
164 inline bool
165 sem_usage_pair_hash::equal (sem_usage_pair *p1, sem_usage_pair *p2)
166 {
167 return p1->item == p2->item && p1->index == p2->index;
168 }
169
170 struct sem_usage_hash : sem_usage_pair_hash, typed_delete_remove <sem_usage_pair> {};
171 typedef hash_map<sem_usage_hash, auto_vec<sem_item *> > ref_map;
172
173 typedef std::pair<symtab_node *, symtab_node *> symtab_pair;
174
175 /* Semantic item is a base class that encapsulates all shared functionality
176 for both semantic function and variable items. */
177 class sem_item
178 {
179 public:
180 /* Semantic item constructor for a node of _TYPE, where STACK is used
181 for bitmap memory allocation. */
182 sem_item (sem_item_type _type, bitmap_obstack *stack);
183
184 /* Semantic item constructor for a node of _TYPE, where STACK is used
185 for bitmap memory allocation. The item is based on symtab node _NODE. */
186 sem_item (sem_item_type _type, symtab_node *_node, bitmap_obstack *stack);
187
188 virtual ~sem_item ();
189
190 /* Dump function for debugging purpose. */
191 DEBUG_FUNCTION void dump (void);
192
193 /* Semantic item initialization function. */
194 virtual void init (ipa_icf_gimple::func_checker *) = 0;
195
196 /* Add reference to a semantic TARGET. */
197 void add_reference (ref_map *map, sem_item *target);
198
199 /* Fast equality function based on knowledge known in WPA. */
200 virtual bool equals_wpa (sem_item *item,
201 hash_map <symtab_node *, sem_item *> &ignored_nodes) = 0;
202
203 /* Returns true if the item equals to ITEM given as argument. */
204 virtual bool equals (sem_item *item,
205 hash_map <symtab_node *, sem_item *> &ignored_nodes) = 0;
206
207 /* References independent hash function. */
208 virtual hashval_t get_hash (void) = 0;
209
210 /* Set new hash value of the item. */
211 void set_hash (hashval_t hash);
212
213 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
214 be applied. */
215 virtual bool merge (sem_item *alias_item) = 0;
216
217 /* Dump symbol to FILE. */
218 virtual void dump_to_file (FILE *file) = 0;
219
220 /* Update hash by address sensitive references. */
221 void update_hash_by_addr_refs (hash_map <symtab_node *,
222 sem_item *> &m_symtab_node_map);
223
224 /* Update hash by computed local hash values taken from different
225 semantic items. */
226 void update_hash_by_local_refs (hash_map <symtab_node *,
227 sem_item *> &m_symtab_node_map);
228
229 /* Return base tree that can be used for compatible_types_p and
230 contains_polymorphic_type_p comparison. */
231 static bool get_base_types (tree *t1, tree *t2);
232
233 /* Return true if target supports alias symbols. */
234 bool target_supports_symbol_aliases_p (void);
235
236 /* Item type. */
237 sem_item_type type;
238
239 /* Symtab node. */
240 symtab_node *node;
241
242 /* Declaration tree node. */
243 tree decl;
244
245 /* Number of references to a semantic symbols (function calls,
246 variable references). */
247 unsigned reference_count;
248
249 /* Pointer to a congruence class the item belongs to. */
250 congruence_class *cls;
251
252 /* Index of the item in a class belonging to. */
253 unsigned int index_in_class;
254
255 /* A bitmap with indices of all classes referencing this item. */
256 bitmap usage_index_bitmap;
257
258 /* List of tree references (either FUNC_DECL or VAR_DECL). */
259 vec <tree> tree_refs;
260
261 /* A set with symbol table references. */
262 hash_set <symtab_node *> refs_set;
263
264 /* Temporary hash used where hash values of references are added. */
265 hashval_t global_hash;
266
267 /* Number of references to this symbol. */
268 unsigned referenced_by_count;
269 protected:
270 /* Cached, once calculated hash for the item. */
271
272 /* Compare properties of symbol that does not affect semantics of symbol
273 itself but affects semantics of its references.
274 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR. */
275 static bool compare_referenced_symbol_properties (symtab_node *used_by,
276 symtab_node *n1,
277 symtab_node *n2,
278 bool address);
279
280 /* Hash properties compared by compare_referenced_symbol_properties. */
281 void hash_referenced_symbol_properties (symtab_node *ref,
282 inchash::hash &hstate,
283 bool address);
284
285 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
286 point to a same function. Comparison can be skipped if IGNORED_NODES
287 contains these nodes. ADDRESS indicate if address is taken. */
288 bool compare_symbol_references (hash_map <symtab_node *, sem_item *>
289 &ignored_nodes,
290 symtab_node *n1, symtab_node *n2,
291 bool address);
292 protected:
293 /* Hash of item. */
294 hashval_t m_hash;
295
296 /* Indicated whether a hash value has been set or not. */
297 bool m_hash_set;
298
299 private:
300 /* Initialize internal data structures. Bitmap STACK is used for
301 bitmap memory allocation process. */
302 void setup (bitmap_obstack *stack);
303
304 /* Because types can be arbitrarily large, avoid quadratic bottleneck. */
305 static hash_map<const_tree, hashval_t> m_type_hash_cache;
306 }; // class sem_item
307
308 class sem_function: public sem_item
309 {
310 public:
311 /* Semantic function constructor that uses STACK as bitmap memory stack. */
312 sem_function (bitmap_obstack *stack);
313
314 /* Constructor based on callgraph node _NODE.
315 Bitmap STACK is used for memory allocation. */
316 sem_function (cgraph_node *_node, bitmap_obstack *stack);
317
318 ~sem_function ();
319
320 virtual void init (ipa_icf_gimple::func_checker *);
321 virtual bool equals_wpa (sem_item *item,
322 hash_map <symtab_node *, sem_item *> &ignored_nodes);
323 virtual hashval_t get_hash (void);
324 virtual bool equals (sem_item *item,
325 hash_map <symtab_node *, sem_item *> &ignored_nodes);
326 virtual bool merge (sem_item *alias_item);
327
328 /* Dump symbol to FILE. */
329 virtual void dump_to_file (FILE *file)
330 {
331 gcc_assert (file);
332 dump_function_to_file (decl, file, TDF_DETAILS);
333 }
334
335 /* Returns cgraph_node. */
336 inline cgraph_node *get_node (void)
337 {
338 return dyn_cast <cgraph_node *> (node);
339 }
340
341 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
342 void hash_stmt (gimple *stmt, inchash::hash &inchash);
343
344 /* Return true if polymorphic comparison must be processed. */
345 bool compare_polymorphic_p (void);
346
347 /* For a given call graph NODE, the function constructs new
348 semantic function item. */
349 static sem_function *parse (cgraph_node *node, bitmap_obstack *stack,
350 ipa_icf_gimple::func_checker *checker);
351
352 /* Perform additional checks needed to match types of used function
353 parameters. */
354 bool compatible_parm_types_p (tree, tree);
355
356 /* Exception handling region tree. */
357 eh_region region_tree;
358
359 /* Number of function arguments. */
360 unsigned int arg_count;
361
362 /* Total amount of edges in the function. */
363 unsigned int edge_count;
364
365 /* Vector of sizes of all basic blocks. */
366 vec <unsigned int> bb_sizes;
367
368 /* Control flow graph checksum. */
369 hashval_t cfg_checksum;
370
371 /* GIMPLE codes hash value. */
372 hashval_t gcode_hash;
373
374 /* Vector of subpart of memory access types. */
375 vec<tree> memory_access_types;
376
377 /* Total number of SSA names used in the function. */
378 unsigned ssa_names_size;
379
380 /* Array of structures for all basic blocks. */
381 vec <ipa_icf_gimple::sem_bb *> bb_sorted;
382
383 /* Hash of canonical types used for memory references in the
384 function. */
385 hashval_t m_alias_sets_hash;
386
387 /* Return true if parameter I may be used. */
388 bool param_used_p (unsigned int i);
389
390 private:
391 /* Calculates hash value based on a BASIC_BLOCK. */
392 hashval_t get_bb_hash (const ipa_icf_gimple::sem_bb *basic_block);
393
394 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
395 true value is returned if phi nodes are semantically
396 equivalent in these blocks . */
397 bool compare_phi_node (basic_block bb1, basic_block bb2);
398
399 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
400 corresponds to TARGET. */
401 bool bb_dict_test (vec<int> *bb_dict, int source, int target);
402
403 /* If cgraph edges E1 and E2 are indirect calls, verify that
404 ICF flags are the same. */
405 bool compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2);
406
407 /* Processes function equality comparison. */
408 bool equals_private (sem_item *item);
409
410 /* Function checker stores binding between functions. */
411 ipa_icf_gimple::func_checker *m_checker;
412
413 /* COMPARED_FUNC is a function that we compare to. */
414 sem_function *m_compared_func;
415 }; // class sem_function
416
417 class sem_variable: public sem_item
418 {
419 public:
420 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
421 sem_variable (bitmap_obstack *stack);
422
423 /* Constructor based on callgraph node _NODE.
424 Bitmap STACK is used for memory allocation. */
425
426 sem_variable (varpool_node *_node, bitmap_obstack *stack);
427
428 /* Semantic variable initialization function. */
429 virtual void init (ipa_icf_gimple::func_checker *);
430
431 virtual hashval_t get_hash (void);
432 virtual bool merge (sem_item *alias_item);
433 virtual void dump_to_file (FILE *file);
434 virtual bool equals (sem_item *item,
435 hash_map <symtab_node *, sem_item *> &ignored_nodes);
436
437 /* Fast equality variable based on knowledge known in WPA. */
438 virtual bool equals_wpa (sem_item *item,
439 hash_map <symtab_node *, sem_item *> &ignored_nodes);
440
441 /* Returns varpool_node. */
442 inline varpool_node *get_node (void)
443 {
444 return dyn_cast <varpool_node *> (node);
445 }
446
447 /* Parser function that visits a varpool NODE. */
448 static sem_variable *parse (varpool_node *node, bitmap_obstack *stack,
449 ipa_icf_gimple::func_checker *checker);
450
451 private:
452 /* Compares trees T1 and T2 for semantic equality. */
453 static bool equals (tree t1, tree t2);
454 }; // class sem_variable
455
456 class sem_item_optimizer;
457
458 struct congruence_class_group
459 {
460 hashval_t hash;
461 sem_item_type type;
462 vec <congruence_class *> classes;
463 };
464
465 /* Congruence class set structure. */
466 struct congruence_class_hash : nofree_ptr_hash <congruence_class_group>
467 {
468 static inline hashval_t hash (const congruence_class_group *item)
469 {
470 return item->hash;
471 }
472
473 static inline int equal (const congruence_class_group *item1,
474 const congruence_class_group *item2)
475 {
476 return item1->hash == item2->hash && item1->type == item2->type;
477 }
478 };
479
480 struct traverse_split_pair
481 {
482 sem_item_optimizer *optimizer;
483 class congruence_class *cls;
484 };
485
486 /* Semantic item optimizer includes all top-level logic
487 related to semantic equality comparison. */
488 class sem_item_optimizer
489 {
490 public:
491 sem_item_optimizer ();
492 ~sem_item_optimizer ();
493
494 /* Function responsible for visiting all potential functions and
495 read-only variables that can be merged. */
496 void parse_funcs_and_vars (void);
497
498 /* Optimizer entry point which returns true in case it processes
499 a merge operation. True is returned if there's a merge operation
500 processed. */
501 bool execute (void);
502
503 /* Dump function. */
504 void dump (void);
505
506 /* Verify congruence classes if checking is enabled. */
507 void checking_verify_classes (void);
508
509 /* Verify congruence classes. */
510 void verify_classes (void);
511
512 /* Write IPA ICF summary for symbols. */
513 void write_summary (void);
514
515 /* Read IPA ICF summary for symbols. */
516 void read_summary (void);
517
518 /* Callgraph removal hook called for a NODE with a custom DATA. */
519 static void cgraph_removal_hook (cgraph_node *node, void *data);
520
521 /* Varpool removal hook called for a NODE with a custom DATA. */
522 static void varpool_removal_hook (varpool_node *node, void *data);
523
524 /* Worklist of congruence classes that can potentially
525 refine classes of congruence. */
526 fibonacci_heap<unsigned, congruence_class> worklist;
527
528 /* Remove semantic ITEM and release memory. */
529 void remove_item (sem_item *item);
530
531 /* Remove symtab NODE triggered by symtab removal hooks. */
532 void remove_symtab_node (symtab_node *node);
533
534 /* Register callgraph and varpool hooks. */
535 void register_hooks (void);
536
537 /* Unregister callgraph and varpool hooks. */
538 void unregister_hooks (void);
539
540 /* Adds a CLS to hashtable associated by hash value. */
541 void add_class (congruence_class *cls);
542
543 /* Gets a congruence class group based on given HASH value and TYPE. */
544 congruence_class_group *get_group_by_hash (hashval_t hash,
545 sem_item_type type);
546 private:
547
548 /* For each semantic item, append hash values of references. */
549 void update_hash_by_addr_refs ();
550
551 /* Update hash by canonical types of memory accesses. */
552 void update_hash_by_memory_access_type ();
553
554 /* Congruence classes are built by hash value. */
555 void build_hash_based_classes (void);
556
557 /* Semantic items in classes having more than one element and initialized.
558 In case of WPA, we load function body. */
559 unsigned int parse_nonsingleton_classes (void);
560
561 /* Equality function for semantic items is used to subdivide existing
562 classes. If IN_WPA, fast equality function is invoked. */
563 void subdivide_classes_by_equality (bool in_wpa = false);
564
565 /* Subdivide classes by address and interposable references
566 that members of the class reference.
567 Example can be a pair of functions that have an address
568 taken from a function. If these addresses are different the class
569 is split. */
570 unsigned subdivide_classes_by_sensitive_refs();
571
572 /* Debug function prints all informations about congruence classes. */
573 void dump_cong_classes (void);
574
575 /* Build references according to call graph. */
576 void build_graph (void);
577
578 /* Iterative congruence reduction function. */
579 void process_cong_reduction (void);
580
581 /* After reduction is done, we can declare all items in a group
582 to be equal. PREV_CLASS_COUNT is start number of classes
583 before reduction. True is returned if there's a merge operation
584 processed. LOADED_SYMBOLS is number of symbols that were loaded
585 in WPA. */
586 bool merge_classes (unsigned int prev_class_count,
587 unsigned int loaded_symbols);
588
589 /* Fixup points to analysis info. */
590 void fixup_points_to_sets (void);
591
592 /* Fixup points to set PT. */
593 void fixup_pt_set (struct pt_solution *pt);
594
595 /* Adds a newly created congruence class CLS to worklist. */
596 void worklist_push (congruence_class *cls);
597
598 /* Pops a class from worklist. */
599 congruence_class *worklist_pop ();
600
601 /* Every usage of a congruence class CLS is a candidate that can split the
602 collection of classes. Bitmap stack BMSTACK is used for bitmap
603 allocation. */
604 void do_congruence_step (congruence_class *cls);
605
606 /* Tests if a class CLS used as INDEXth splits any congruence classes.
607 Bitmap stack BMSTACK is used for bitmap allocation. */
608 bool do_congruence_step_for_index (congruence_class *cls, unsigned int index);
609
610 /* Makes pairing between a congruence class CLS and semantic ITEM. */
611 static void add_item_to_class (congruence_class *cls, sem_item *item);
612
613 /* Disposes split map traverse function. CLS is congruence
614 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
615 but unused argument. */
616 static bool release_split_map (congruence_class * const &cls, bitmap const &b,
617 traverse_split_pair *pair);
618
619 /* Process split operation for a congruence class CLS,
620 where bitmap B splits congruence class members. DATA is used
621 as argument of split pair. */
622 static bool traverse_congruence_split (congruence_class * const &cls,
623 bitmap const &b,
624 traverse_split_pair *pair);
625
626 /* Compare function for sorting pairs in do_congruence_step_f. */
627 static int sort_congruence_split (const void *, const void *);
628
629 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
630 contains LEN bytes. */
631 void read_section (lto_file_decl_data *file_data, const char *data,
632 size_t len);
633
634 /* Removes all callgraph and varpool nodes that are marked by symtab
635 as deleted. */
636 void filter_removed_items (void);
637
638 /* Vector of semantic items. */
639 vec <sem_item *> m_items;
640
641 /* A set containing all items removed by hooks. */
642 hash_set <symtab_node *> m_removed_items_set;
643
644 /* Hashtable of congruence classes. */
645 hash_table <congruence_class_hash> m_classes;
646
647 /* Count of congruence classes. */
648 unsigned int m_classes_count;
649
650 /* Map data structure maps symtab nodes to semantic items. */
651 hash_map <symtab_node *, sem_item *> m_symtab_node_map;
652
653 /* Set to true if a splitter class is removed. */
654 bool splitter_class_removed;
655
656 /* Global unique class id counter. */
657 static unsigned int class_id;
658
659 /* Callgraph node removal hook holder. */
660 cgraph_node_hook_list *m_cgraph_node_hooks;
661
662 /* Varpool node removal hook holder. */
663 varpool_node_hook_list *m_varpool_node_hooks;
664
665 /* Bitmap stack. */
666 bitmap_obstack m_bmstack;
667
668 /* Vector of merged variables. Needed for fixup of points-to-analysis
669 info. */
670 vec <symtab_pair> m_merged_variables;
671
672 /* Hash map will all references. */
673 ref_map m_references;
674 }; // class sem_item_optimizer
675
676 } // ipa_icf namespace