|
111
|
1 /* Interprocedural semantic function equality pass
|
|
145
|
2 Copyright (C) 2014-2020 Free Software Foundation, Inc.
|
|
111
|
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
|
|
145
|
27 if not proved the opposite. */
|
|
111
|
28 class congruence_class
|
|
|
29 {
|
|
|
30 public:
|
|
|
31 /* Congruence class constructor for a new class with _ID. */
|
|
145
|
32 congruence_class (unsigned int _id): in_worklist (false), id (_id),
|
|
|
33 referenced_by_count (0)
|
|
111
|
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;
|
|
145
|
58
|
|
|
59 /* Total number of references to items of this class. */
|
|
|
60 unsigned referenced_by_count;
|
|
111
|
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
|
|
145
|
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
|
|
131
|
173 typedef std::pair<symtab_node *, symtab_node *> symtab_pair;
|
|
|
174
|
|
111
|
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. */
|
|
145
|
194 virtual void init (ipa_icf_gimple::func_checker *) = 0;
|
|
111
|
195
|
|
|
196 /* Add reference to a semantic TARGET. */
|
|
145
|
197 void add_reference (ref_map *map, sem_item *target);
|
|
111
|
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
|
|
145
|
203 /* Returns true if the item equals to ITEM given as argument. */
|
|
111
|
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
|
|
145
|
245 /* Number of references to a semantic symbols (function calls,
|
|
|
246 variable references). */
|
|
|
247 unsigned reference_count;
|
|
111
|
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;
|
|
145
|
266
|
|
|
267 /* Number of references to this symbol. */
|
|
|
268 unsigned referenced_by_count;
|
|
111
|
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);
|
|
131
|
303
|
|
|
304 /* Because types can be arbitrarily large, avoid quadratic bottleneck. */
|
|
|
305 static hash_map<const_tree, hashval_t> m_type_hash_cache;
|
|
111
|
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
|
|
145
|
320 virtual void init (ipa_icf_gimple::func_checker *);
|
|
111
|
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. */
|
|
145
|
349 static sem_function *parse (cgraph_node *node, bitmap_obstack *stack,
|
|
|
350 ipa_icf_gimple::func_checker *checker);
|
|
111
|
351
|
|
|
352 /* Perform additional checks needed to match types of used function
|
|
145
|
353 parameters. */
|
|
111
|
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 /* Total number of SSA names used in the function. */
|
|
|
375 unsigned ssa_names_size;
|
|
|
376
|
|
|
377 /* Array of structures for all basic blocks. */
|
|
|
378 vec <ipa_icf_gimple::sem_bb *> bb_sorted;
|
|
|
379
|
|
|
380 /* Return true if parameter I may be used. */
|
|
|
381 bool param_used_p (unsigned int i);
|
|
|
382
|
|
|
383 private:
|
|
|
384 /* Calculates hash value based on a BASIC_BLOCK. */
|
|
|
385 hashval_t get_bb_hash (const ipa_icf_gimple::sem_bb *basic_block);
|
|
|
386
|
|
|
387 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
|
|
|
388 true value is returned if phi nodes are semantically
|
|
|
389 equivalent in these blocks . */
|
|
|
390 bool compare_phi_node (basic_block bb1, basic_block bb2);
|
|
|
391
|
|
|
392 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
|
|
|
393 corresponds to TARGET. */
|
|
|
394 bool bb_dict_test (vec<int> *bb_dict, int source, int target);
|
|
|
395
|
|
|
396 /* If cgraph edges E1 and E2 are indirect calls, verify that
|
|
|
397 ICF flags are the same. */
|
|
|
398 bool compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2);
|
|
|
399
|
|
|
400 /* Processes function equality comparison. */
|
|
|
401 bool equals_private (sem_item *item);
|
|
|
402
|
|
|
403 /* Function checker stores binding between functions. */
|
|
|
404 ipa_icf_gimple::func_checker *m_checker;
|
|
|
405
|
|
|
406 /* COMPARED_FUNC is a function that we compare to. */
|
|
|
407 sem_function *m_compared_func;
|
|
|
408 }; // class sem_function
|
|
|
409
|
|
|
410 class sem_variable: public sem_item
|
|
|
411 {
|
|
|
412 public:
|
|
|
413 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
|
|
|
414 sem_variable (bitmap_obstack *stack);
|
|
|
415
|
|
|
416 /* Constructor based on callgraph node _NODE.
|
|
|
417 Bitmap STACK is used for memory allocation. */
|
|
|
418
|
|
|
419 sem_variable (varpool_node *_node, bitmap_obstack *stack);
|
|
|
420
|
|
|
421 /* Semantic variable initialization function. */
|
|
145
|
422 virtual void init (ipa_icf_gimple::func_checker *);
|
|
111
|
423
|
|
|
424 virtual hashval_t get_hash (void);
|
|
|
425 virtual bool merge (sem_item *alias_item);
|
|
|
426 virtual void dump_to_file (FILE *file);
|
|
|
427 virtual bool equals (sem_item *item,
|
|
|
428 hash_map <symtab_node *, sem_item *> &ignored_nodes);
|
|
|
429
|
|
|
430 /* Fast equality variable based on knowledge known in WPA. */
|
|
|
431 virtual bool equals_wpa (sem_item *item,
|
|
|
432 hash_map <symtab_node *, sem_item *> &ignored_nodes);
|
|
|
433
|
|
|
434 /* Returns varpool_node. */
|
|
|
435 inline varpool_node *get_node (void)
|
|
|
436 {
|
|
|
437 return dyn_cast <varpool_node *> (node);
|
|
|
438 }
|
|
|
439
|
|
|
440 /* Parser function that visits a varpool NODE. */
|
|
145
|
441 static sem_variable *parse (varpool_node *node, bitmap_obstack *stack,
|
|
|
442 ipa_icf_gimple::func_checker *checker);
|
|
111
|
443
|
|
|
444 private:
|
|
|
445 /* Compares trees T1 and T2 for semantic equality. */
|
|
|
446 static bool equals (tree t1, tree t2);
|
|
|
447 }; // class sem_variable
|
|
|
448
|
|
|
449 class sem_item_optimizer;
|
|
|
450
|
|
|
451 struct congruence_class_group
|
|
|
452 {
|
|
|
453 hashval_t hash;
|
|
|
454 sem_item_type type;
|
|
|
455 vec <congruence_class *> classes;
|
|
|
456 };
|
|
|
457
|
|
|
458 /* Congruence class set structure. */
|
|
|
459 struct congruence_class_hash : nofree_ptr_hash <congruence_class_group>
|
|
|
460 {
|
|
|
461 static inline hashval_t hash (const congruence_class_group *item)
|
|
|
462 {
|
|
|
463 return item->hash;
|
|
|
464 }
|
|
|
465
|
|
|
466 static inline int equal (const congruence_class_group *item1,
|
|
|
467 const congruence_class_group *item2)
|
|
|
468 {
|
|
|
469 return item1->hash == item2->hash && item1->type == item2->type;
|
|
|
470 }
|
|
|
471 };
|
|
|
472
|
|
|
473 struct traverse_split_pair
|
|
|
474 {
|
|
|
475 sem_item_optimizer *optimizer;
|
|
|
476 class congruence_class *cls;
|
|
|
477 };
|
|
|
478
|
|
|
479 /* Semantic item optimizer includes all top-level logic
|
|
|
480 related to semantic equality comparison. */
|
|
|
481 class sem_item_optimizer
|
|
|
482 {
|
|
|
483 public:
|
|
|
484 sem_item_optimizer ();
|
|
|
485 ~sem_item_optimizer ();
|
|
|
486
|
|
|
487 /* Function responsible for visiting all potential functions and
|
|
|
488 read-only variables that can be merged. */
|
|
|
489 void parse_funcs_and_vars (void);
|
|
|
490
|
|
|
491 /* Optimizer entry point which returns true in case it processes
|
|
|
492 a merge operation. True is returned if there's a merge operation
|
|
|
493 processed. */
|
|
|
494 bool execute (void);
|
|
|
495
|
|
|
496 /* Dump function. */
|
|
|
497 void dump (void);
|
|
|
498
|
|
|
499 /* Verify congruence classes if checking is enabled. */
|
|
|
500 void checking_verify_classes (void);
|
|
|
501
|
|
|
502 /* Verify congruence classes. */
|
|
|
503 void verify_classes (void);
|
|
|
504
|
|
|
505 /* Write IPA ICF summary for symbols. */
|
|
|
506 void write_summary (void);
|
|
|
507
|
|
|
508 /* Read IPA ICF summary for symbols. */
|
|
|
509 void read_summary (void);
|
|
|
510
|
|
|
511 /* Callgraph removal hook called for a NODE with a custom DATA. */
|
|
|
512 static void cgraph_removal_hook (cgraph_node *node, void *data);
|
|
|
513
|
|
|
514 /* Varpool removal hook called for a NODE with a custom DATA. */
|
|
|
515 static void varpool_removal_hook (varpool_node *node, void *data);
|
|
|
516
|
|
|
517 /* Worklist of congruence classes that can potentially
|
|
|
518 refine classes of congruence. */
|
|
145
|
519 fibonacci_heap<unsigned, congruence_class> worklist;
|
|
111
|
520
|
|
|
521 /* Remove semantic ITEM and release memory. */
|
|
|
522 void remove_item (sem_item *item);
|
|
|
523
|
|
|
524 /* Remove symtab NODE triggered by symtab removal hooks. */
|
|
|
525 void remove_symtab_node (symtab_node *node);
|
|
|
526
|
|
|
527 /* Register callgraph and varpool hooks. */
|
|
|
528 void register_hooks (void);
|
|
|
529
|
|
|
530 /* Unregister callgraph and varpool hooks. */
|
|
|
531 void unregister_hooks (void);
|
|
|
532
|
|
|
533 /* Adds a CLS to hashtable associated by hash value. */
|
|
|
534 void add_class (congruence_class *cls);
|
|
|
535
|
|
|
536 /* Gets a congruence class group based on given HASH value and TYPE. */
|
|
|
537 congruence_class_group *get_group_by_hash (hashval_t hash,
|
|
|
538 sem_item_type type);
|
|
|
539 private:
|
|
|
540
|
|
|
541 /* For each semantic item, append hash values of references. */
|
|
|
542 void update_hash_by_addr_refs ();
|
|
|
543
|
|
|
544 /* Congruence classes are built by hash value. */
|
|
|
545 void build_hash_based_classes (void);
|
|
|
546
|
|
|
547 /* Semantic items in classes having more than one element and initialized.
|
|
|
548 In case of WPA, we load function body. */
|
|
145
|
549 unsigned int parse_nonsingleton_classes (void);
|
|
111
|
550
|
|
|
551 /* Equality function for semantic items is used to subdivide existing
|
|
|
552 classes. If IN_WPA, fast equality function is invoked. */
|
|
|
553 void subdivide_classes_by_equality (bool in_wpa = false);
|
|
|
554
|
|
|
555 /* Subdivide classes by address and interposable references
|
|
|
556 that members of the class reference.
|
|
|
557 Example can be a pair of functions that have an address
|
|
|
558 taken from a function. If these addresses are different the class
|
|
|
559 is split. */
|
|
|
560 unsigned subdivide_classes_by_sensitive_refs();
|
|
|
561
|
|
|
562 /* Debug function prints all informations about congruence classes. */
|
|
|
563 void dump_cong_classes (void);
|
|
|
564
|
|
|
565 /* Build references according to call graph. */
|
|
|
566 void build_graph (void);
|
|
|
567
|
|
|
568 /* Iterative congruence reduction function. */
|
|
|
569 void process_cong_reduction (void);
|
|
|
570
|
|
|
571 /* After reduction is done, we can declare all items in a group
|
|
|
572 to be equal. PREV_CLASS_COUNT is start number of classes
|
|
|
573 before reduction. True is returned if there's a merge operation
|
|
145
|
574 processed. LOADED_SYMBOLS is number of symbols that were loaded
|
|
|
575 in WPA. */
|
|
|
576 bool merge_classes (unsigned int prev_class_count,
|
|
|
577 unsigned int loaded_symbols);
|
|
111
|
578
|
|
131
|
579 /* Fixup points to analysis info. */
|
|
|
580 void fixup_points_to_sets (void);
|
|
|
581
|
|
|
582 /* Fixup points to set PT. */
|
|
|
583 void fixup_pt_set (struct pt_solution *pt);
|
|
|
584
|
|
111
|
585 /* Adds a newly created congruence class CLS to worklist. */
|
|
|
586 void worklist_push (congruence_class *cls);
|
|
|
587
|
|
|
588 /* Pops a class from worklist. */
|
|
|
589 congruence_class *worklist_pop ();
|
|
|
590
|
|
|
591 /* Every usage of a congruence class CLS is a candidate that can split the
|
|
|
592 collection of classes. Bitmap stack BMSTACK is used for bitmap
|
|
|
593 allocation. */
|
|
|
594 void do_congruence_step (congruence_class *cls);
|
|
|
595
|
|
|
596 /* Tests if a class CLS used as INDEXth splits any congruence classes.
|
|
|
597 Bitmap stack BMSTACK is used for bitmap allocation. */
|
|
145
|
598 bool do_congruence_step_for_index (congruence_class *cls, unsigned int index);
|
|
111
|
599
|
|
|
600 /* Makes pairing between a congruence class CLS and semantic ITEM. */
|
|
|
601 static void add_item_to_class (congruence_class *cls, sem_item *item);
|
|
|
602
|
|
|
603 /* Disposes split map traverse function. CLS is congruence
|
|
|
604 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
|
|
|
605 but unused argument. */
|
|
|
606 static bool release_split_map (congruence_class * const &cls, bitmap const &b,
|
|
|
607 traverse_split_pair *pair);
|
|
|
608
|
|
145
|
609 /* Process split operation for a congruence class CLS,
|
|
111
|
610 where bitmap B splits congruence class members. DATA is used
|
|
|
611 as argument of split pair. */
|
|
|
612 static bool traverse_congruence_split (congruence_class * const &cls,
|
|
|
613 bitmap const &b,
|
|
|
614 traverse_split_pair *pair);
|
|
|
615
|
|
145
|
616 /* Compare function for sorting pairs in do_congruence_step_f. */
|
|
|
617 static int sort_congruence_split (const void *, const void *);
|
|
|
618
|
|
111
|
619 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
|
|
|
620 contains LEN bytes. */
|
|
|
621 void read_section (lto_file_decl_data *file_data, const char *data,
|
|
|
622 size_t len);
|
|
|
623
|
|
|
624 /* Removes all callgraph and varpool nodes that are marked by symtab
|
|
|
625 as deleted. */
|
|
|
626 void filter_removed_items (void);
|
|
|
627
|
|
|
628 /* Vector of semantic items. */
|
|
|
629 vec <sem_item *> m_items;
|
|
|
630
|
|
|
631 /* A set containing all items removed by hooks. */
|
|
|
632 hash_set <symtab_node *> m_removed_items_set;
|
|
|
633
|
|
|
634 /* Hashtable of congruence classes. */
|
|
|
635 hash_table <congruence_class_hash> m_classes;
|
|
|
636
|
|
|
637 /* Count of congruence classes. */
|
|
|
638 unsigned int m_classes_count;
|
|
|
639
|
|
|
640 /* Map data structure maps symtab nodes to semantic items. */
|
|
|
641 hash_map <symtab_node *, sem_item *> m_symtab_node_map;
|
|
|
642
|
|
|
643 /* Set to true if a splitter class is removed. */
|
|
|
644 bool splitter_class_removed;
|
|
|
645
|
|
|
646 /* Global unique class id counter. */
|
|
|
647 static unsigned int class_id;
|
|
|
648
|
|
|
649 /* Callgraph node removal hook holder. */
|
|
|
650 cgraph_node_hook_list *m_cgraph_node_hooks;
|
|
|
651
|
|
|
652 /* Varpool node removal hook holder. */
|
|
|
653 varpool_node_hook_list *m_varpool_node_hooks;
|
|
|
654
|
|
|
655 /* Bitmap stack. */
|
|
|
656 bitmap_obstack m_bmstack;
|
|
131
|
657
|
|
|
658 /* Vector of merged variables. Needed for fixup of points-to-analysis
|
|
|
659 info. */
|
|
|
660 vec <symtab_pair> m_merged_variables;
|
|
145
|
661
|
|
|
662 /* Hash map will all references. */
|
|
|
663 ref_map m_references;
|
|
111
|
664 }; // class sem_item_optimizer
|
|
|
665
|
|
|
666 } // ipa_icf namespace
|
