summaryrefslogtreecommitdiff
path: root/gcc/ipa-icf.h
blob: c57224c1517e5f892140c649307b2774a998c424 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
/* Interprocedural semantic function equality pass
   Copyright (C) 2014-2017 Free Software Foundation, Inc.

   Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

namespace ipa_icf {
class sem_item;

/* Congruence class encompasses a collection of either functions or
   read-only variables. These items are considered to be equivalent
   if not proved the oposite.  */
class congruence_class
{
public:
  /* Congruence class constructor for a new class with _ID.  */
  congruence_class (unsigned int _id): in_worklist (false), id(_id)
  {
  }

  /* Destructor.  */
  ~congruence_class ()
  {
  }

  /* Dump function prints all class members to a FILE with an INDENT.  */
  void dump (FILE *file, unsigned int indent = 0) const;

  /* Returns true if there's a member that is used from another group.  */
  bool is_class_used (void);

  /* Flag is used in case we want to remove a class from worklist and
     delete operation is quite expensive for
     the data structure (linked list).  */
  bool in_worklist;

  /* Vector of all group members.  */
  auto_vec <sem_item *> members;

  /* Global unique class identifier.  */
  unsigned int id;
};

/* Semantic item type enum.  */
enum sem_item_type
{
  FUNC,
  VAR
};

/* Class is container for address references for a symtab_node.  */

class symbol_compare_collection
{
public:
  /* Constructor.  */
  symbol_compare_collection (symtab_node *node);

  /* Destructor.  */
  ~symbol_compare_collection ()
  {
    m_references.release ();
    m_interposables.release ();
  }

  /* Vector of address references.  */
  vec<symtab_node *> m_references;

  /* Vector of interposable references.  */
  vec<symtab_node *> m_interposables;
};

/* Hash traits for symbol_compare_collection map.  */

struct symbol_compare_hash : nofree_ptr_hash <symbol_compare_collection>
{
  static hashval_t
  hash (value_type v)
  {
    inchash::hash hstate;
    hstate.add_int (v->m_references.length ());

    for (unsigned i = 0; i < v->m_references.length (); i++)
      hstate.add_int (v->m_references[i]->ultimate_alias_target ()->order);

    hstate.add_int (v->m_interposables.length ());

    for (unsigned i = 0; i < v->m_interposables.length (); i++)
      hstate.add_int (v->m_interposables[i]->ultimate_alias_target ()->order);

    return hstate.end ();
  }

  static bool
  equal (value_type a, value_type b)
  {
    if (a->m_references.length () != b->m_references.length ()
	|| a->m_interposables.length () != b->m_interposables.length ())
      return false;

    for (unsigned i = 0; i < a->m_references.length (); i++)
      if (a->m_references[i]->equal_address_to (b->m_references[i]) != 1)
	return false;

    for (unsigned i = 0; i < a->m_interposables.length (); i++)
      if (!a->m_interposables[i]->semantically_equivalent_p
	(b->m_interposables[i]))
	return false;

    return true;
  }
};


/* Semantic item usage pair.  */
class sem_usage_pair
{
public:
  /* Constructor for key value pair, where _ITEM is key and _INDEX is a target.  */
  sem_usage_pair (sem_item *_item, unsigned int _index);

  /* Target semantic item where an item is used.  */
  sem_item *item;

  /* Index of usage of such an item.  */
  unsigned int index;
};

/* Semantic item is a base class that encapsulates all shared functionality
   for both semantic function and variable items.  */
class sem_item
{
public:
  /* Semantic item constructor for a node of _TYPE, where STACK is used
     for bitmap memory allocation.  */
  sem_item (sem_item_type _type, bitmap_obstack *stack);

  /* Semantic item constructor for a node of _TYPE, where STACK is used
     for bitmap memory allocation.  The item is based on symtab node _NODE.  */
  sem_item (sem_item_type _type, symtab_node *_node, bitmap_obstack *stack);

  virtual ~sem_item ();

  /* Dump function for debugging purpose.  */
  DEBUG_FUNCTION void dump (void);

  /* Initialize semantic item by info reachable during LTO WPA phase.  */
  virtual void init_wpa (void) = 0;

  /* Semantic item initialization function.  */
  virtual void init (void) = 0;

  /* Add reference to a semantic TARGET.  */
  void add_reference (sem_item *target);

  /* Fast equality function based on knowledge known in WPA.  */
  virtual bool equals_wpa (sem_item *item,
			   hash_map <symtab_node *, sem_item *> &ignored_nodes) = 0;

  /* Returns true if the item equals to ITEM given as arguemnt.  */
  virtual bool equals (sem_item *item,
		       hash_map <symtab_node *, sem_item *> &ignored_nodes) = 0;

  /* References independent hash function.  */
  virtual hashval_t get_hash (void) = 0;

  /* Set new hash value of the item.  */
  void set_hash (hashval_t hash);

  /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
     be applied.  */
  virtual bool merge (sem_item *alias_item) = 0;

  /* Dump symbol to FILE.  */
  virtual void dump_to_file (FILE *file) = 0;

  /* Update hash by address sensitive references.  */
  void update_hash_by_addr_refs (hash_map <symtab_node *,
				 sem_item *> &m_symtab_node_map);

  /* Update hash by computed local hash values taken from different
     semantic items.  */
  void update_hash_by_local_refs (hash_map <symtab_node *,
				  sem_item *> &m_symtab_node_map);

  /* Return base tree that can be used for compatible_types_p and
     contains_polymorphic_type_p comparison.  */
  static bool get_base_types (tree *t1, tree *t2);

  /* Return true if target supports alias symbols.  */
  bool target_supports_symbol_aliases_p (void);

  /* Item type.  */
  sem_item_type type;

  /* Symtab node.  */
  symtab_node *node;

  /* Declaration tree node.  */
  tree decl;

  /* Semantic references used that generate congruence groups.  */
  vec <sem_item *> refs;

  /* Pointer to a congruence class the item belongs to.  */
  congruence_class *cls;

  /* Index of the item in a class belonging to.  */
  unsigned int index_in_class;

  /* List of semantic items where the instance is used.  */
  vec <sem_usage_pair *> usages;

  /* A bitmap with indices of all classes referencing this item.  */
  bitmap usage_index_bitmap;

  /* List of tree references (either FUNC_DECL or VAR_DECL).  */
  vec <tree> tree_refs;

  /* A set with symbol table references.  */
  hash_set <symtab_node *> refs_set;

  /* Temporary hash used where hash values of references are added.  */
  hashval_t global_hash;
protected:
  /* Cached, once calculated hash for the item.  */

  /* Accumulate to HSTATE a hash of expression EXP.  */
  static void add_expr (const_tree exp, inchash::hash &hstate);
  /* Accumulate to HSTATE a hash of type T.  */
  static void add_type (const_tree t, inchash::hash &hstate);

  /* Compare properties of symbol that does not affect semantics of symbol
     itself but affects semantics of its references.
     If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.  */
  static bool compare_referenced_symbol_properties (symtab_node *used_by,
						    symtab_node *n1,
					            symtab_node *n2,
					            bool address);

  /* Compare two attribute lists.  */
  static bool compare_attributes (const_tree list1, const_tree list2);

  /* Hash properties compared by compare_referenced_symbol_properties.  */
  void hash_referenced_symbol_properties (symtab_node *ref,
					  inchash::hash &hstate,
					  bool address);

  /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
     point to a same function. Comparison can be skipped if IGNORED_NODES
     contains these nodes.  ADDRESS indicate if address is taken.  */
  bool compare_symbol_references (hash_map <symtab_node *, sem_item *>
				  &ignored_nodes,
				  symtab_node *n1, symtab_node *n2,
				  bool address);
protected:
  /* Hash of item.  */
  hashval_t m_hash;

  /* Indicated whether a hash value has been set or not.  */
  bool m_hash_set;

private:
  /* Initialize internal data structures. Bitmap STACK is used for
     bitmap memory allocation process.  */
  void setup (bitmap_obstack *stack);
}; // class sem_item

class sem_function: public sem_item
{
public:
  /* Semantic function constructor that uses STACK as bitmap memory stack.  */
  sem_function (bitmap_obstack *stack);

  /*  Constructor based on callgraph node _NODE.
      Bitmap STACK is used for memory allocation.  */
  sem_function (cgraph_node *_node, bitmap_obstack *stack);

  ~sem_function ();

  inline virtual void init_wpa (void)
  {
  }

  virtual void init (void);
  virtual bool equals_wpa (sem_item *item,
			   hash_map <symtab_node *, sem_item *> &ignored_nodes);
  virtual hashval_t get_hash (void);
  virtual bool equals (sem_item *item,
		       hash_map <symtab_node *, sem_item *> &ignored_nodes);
  virtual bool merge (sem_item *alias_item);

  /* Dump symbol to FILE.  */
  virtual void dump_to_file (FILE *file)
  {
    gcc_assert (file);
    dump_function_to_file (decl, file, TDF_DETAILS);
  }

  /* Returns cgraph_node.  */
  inline cgraph_node *get_node (void)
  {
    return dyn_cast <cgraph_node *> (node);
  }

  /* Improve accumulated hash for HSTATE based on a gimple statement STMT.  */
  void hash_stmt (gimple *stmt, inchash::hash &inchash);

  /* Return true if polymorphic comparison must be processed.  */
  bool compare_polymorphic_p (void);

  /* For a given call graph NODE, the function constructs new
     semantic function item.  */
  static sem_function *parse (cgraph_node *node, bitmap_obstack *stack);

  /* Perform additional checks needed to match types of used function
     paramters.  */
  bool compatible_parm_types_p (tree, tree);

  /* Exception handling region tree.  */
  eh_region region_tree;

  /* Number of function arguments.  */
  unsigned int arg_count;

  /* Total amount of edges in the function.  */
  unsigned int edge_count;

  /* Vector of sizes of all basic blocks.  */
  vec <unsigned int> bb_sizes;

  /* Control flow graph checksum.  */
  hashval_t cfg_checksum;

  /* GIMPLE codes hash value.  */
  hashval_t gcode_hash;

  /* Total number of SSA names used in the function.  */
  unsigned ssa_names_size;

  /* Array of structures for all basic blocks.  */
  vec <ipa_icf_gimple::sem_bb *> bb_sorted;

  /* Return true if parameter I may be used.  */
  bool param_used_p (unsigned int i);

private:
  /* Calculates hash value based on a BASIC_BLOCK.  */
  hashval_t get_bb_hash (const ipa_icf_gimple::sem_bb *basic_block);

  /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
     true value is returned if phi nodes are semantically
     equivalent in these blocks .  */
  bool compare_phi_node (basic_block bb1, basic_block bb2);

  /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
     corresponds to TARGET.  */
  bool bb_dict_test (vec<int> *bb_dict, int source, int target);

  /* If cgraph edges E1 and E2 are indirect calls, verify that
     ICF flags are the same.  */
  bool compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2);

  /* Processes function equality comparison.  */
  bool equals_private (sem_item *item);

  /* Returns true if tree T can be compared as a handled component.  */
  static bool icf_handled_component_p (tree t);

  /* Function checker stores binding between functions.   */
  ipa_icf_gimple::func_checker *m_checker;

  /* COMPARED_FUNC is a function that we compare to.  */
  sem_function *m_compared_func;
}; // class sem_function

class sem_variable: public sem_item
{
public:
  /* Semantic variable constructor that uses STACK as bitmap memory stack.  */
  sem_variable (bitmap_obstack *stack);

  /*  Constructor based on callgraph node _NODE.
      Bitmap STACK is used for memory allocation.  */

  sem_variable (varpool_node *_node, bitmap_obstack *stack);

  inline virtual void init_wpa (void) {}

  /* Semantic variable initialization function.  */
  inline virtual void init (void)
  {
    decl = get_node ()->decl;
  }

  virtual hashval_t get_hash (void);
  virtual bool merge (sem_item *alias_item);
  virtual void dump_to_file (FILE *file);
  virtual bool equals (sem_item *item,
		       hash_map <symtab_node *, sem_item *> &ignored_nodes);

  /* Fast equality variable based on knowledge known in WPA.  */
  virtual bool equals_wpa (sem_item *item,
			   hash_map <symtab_node *, sem_item *> &ignored_nodes);

  /* Returns varpool_node.  */
  inline varpool_node *get_node (void)
  {
    return dyn_cast <varpool_node *> (node);
  }

  /* Parser function that visits a varpool NODE.  */
  static sem_variable *parse (varpool_node *node, bitmap_obstack *stack);

private:
  /* Compares trees T1 and T2 for semantic equality.  */
  static bool equals (tree t1, tree t2);
}; // class sem_variable

class sem_item_optimizer;

struct congruence_class_group
{
  hashval_t hash;
  sem_item_type type;
  vec <congruence_class *> classes;
};

/* Congruence class set structure.  */
struct congruence_class_hash : nofree_ptr_hash <congruence_class_group>
{
  static inline hashval_t hash (const congruence_class_group *item)
  {
    return item->hash;
  }

  static inline int equal (const congruence_class_group *item1,
			   const congruence_class_group *item2)
  {
    return item1->hash == item2->hash && item1->type == item2->type;
  }
};

struct traverse_split_pair
{
  sem_item_optimizer *optimizer;
  class congruence_class *cls;
};

/* Semantic item optimizer includes all top-level logic
   related to semantic equality comparison.  */
class sem_item_optimizer
{
public:
  sem_item_optimizer ();
  ~sem_item_optimizer ();

  /* Function responsible for visiting all potential functions and
     read-only variables that can be merged.  */
  void parse_funcs_and_vars (void);

  /* Optimizer entry point which returns true in case it processes
     a merge operation. True is returned if there's a merge operation
     processed.  */
  bool execute (void);

  /* Dump function. */
  void dump (void);

  /* Verify congruence classes if checking is enabled.  */
  void checking_verify_classes (void);

  /* Verify congruence classes.  */
  void verify_classes (void);

  /* Write IPA ICF summary for symbols.  */
  void write_summary (void);

  /* Read IPA ICF summary for symbols.  */
  void read_summary (void);

  /* Callgraph removal hook called for a NODE with a custom DATA.  */
  static void cgraph_removal_hook (cgraph_node *node, void *data);

  /* Varpool removal hook called for a NODE with a custom DATA.  */
  static void varpool_removal_hook (varpool_node *node, void *data);

  /* Worklist of congruence classes that can potentially
     refine classes of congruence.  */
  std::list<congruence_class *> worklist;

  /* Remove semantic ITEM and release memory.  */
  void remove_item (sem_item *item);

  /* Remove symtab NODE triggered by symtab removal hooks.  */
  void remove_symtab_node (symtab_node *node);

  /* Register callgraph and varpool hooks.  */
  void register_hooks (void);

  /* Unregister callgraph and varpool hooks.  */
  void unregister_hooks (void);

  /* Adds a CLS to hashtable associated by hash value.  */
  void add_class (congruence_class *cls);

  /* Gets a congruence class group based on given HASH value and TYPE.  */
  congruence_class_group *get_group_by_hash (hashval_t hash,
      sem_item_type type);

  /* Because types can be arbitrarily large, avoid quadratic bottleneck.  */
  hash_map<const_tree, hashval_t> m_type_hash_cache;
private:

  /* For each semantic item, append hash values of references.  */
  void update_hash_by_addr_refs ();

  /* Congruence classes are built by hash value.  */
  void build_hash_based_classes (void);

  /* Semantic items in classes having more than one element and initialized.
     In case of WPA, we load function body.  */
  void parse_nonsingleton_classes (void);

  /* Equality function for semantic items is used to subdivide existing
     classes. If IN_WPA, fast equality function is invoked.  */
  void subdivide_classes_by_equality (bool in_wpa = false);

  /* Subdivide classes by address and interposable references
     that members of the class reference.
     Example can be a pair of functions that have an address
     taken from a function. If these addresses are different the class
     is split.  */
  unsigned subdivide_classes_by_sensitive_refs();

  /* Debug function prints all informations about congruence classes.  */
  void dump_cong_classes (void);

  /* Build references according to call graph.  */
  void build_graph (void);

  /* Iterative congruence reduction function.  */
  void process_cong_reduction (void);

  /* After reduction is done, we can declare all items in a group
     to be equal. PREV_CLASS_COUNT is start number of classes
     before reduction. True is returned if there's a merge operation
     processed.  */
  bool merge_classes (unsigned int prev_class_count);

  /* Adds a newly created congruence class CLS to worklist.  */
  void worklist_push (congruence_class *cls);

  /* Pops a class from worklist. */
  congruence_class *worklist_pop ();

  /* Every usage of a congruence class CLS is a candidate that can split the
     collection of classes. Bitmap stack BMSTACK is used for bitmap
     allocation.  */
  void do_congruence_step (congruence_class *cls);

  /* Tests if a class CLS used as INDEXth splits any congruence classes.
     Bitmap stack BMSTACK is used for bitmap allocation.  */
  void do_congruence_step_for_index (congruence_class *cls, unsigned int index);

  /* Makes pairing between a congruence class CLS and semantic ITEM.  */
  static void add_item_to_class (congruence_class *cls, sem_item *item);

  /* Disposes split map traverse function. CLS is congruence
     class, BSLOT is bitmap slot we want to release. DATA is mandatory,
     but unused argument.  */
  static bool release_split_map (congruence_class * const &cls, bitmap const &b,
				 traverse_split_pair *pair);

  /* Process split operation for a cognruence class CLS,
     where bitmap B splits congruence class members. DATA is used
     as argument of split pair.  */
  static bool traverse_congruence_split (congruence_class * const &cls,
					 bitmap const &b,
					 traverse_split_pair *pair);

  /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
     contains LEN bytes.  */
  void read_section (lto_file_decl_data *file_data, const char *data,
		     size_t len);

  /* Removes all callgraph and varpool nodes that are marked by symtab
     as deleted.  */
  void filter_removed_items (void);

  /* Vector of semantic items.  */
  vec <sem_item *> m_items;

  /* A set containing all items removed by hooks.  */
  hash_set <symtab_node *> m_removed_items_set;

  /* Hashtable of congruence classes.  */
  hash_table <congruence_class_hash> m_classes;

  /* Count of congruence classes.  */
  unsigned int m_classes_count;

  /* Map data structure maps symtab nodes to semantic items.  */
  hash_map <symtab_node *, sem_item *> m_symtab_node_map;

  /* Set to true if a splitter class is removed.  */
  bool splitter_class_removed;

  /* Global unique class id counter.  */
  static unsigned int class_id;

  /* Callgraph node removal hook holder.  */
  cgraph_node_hook_list *m_cgraph_node_hooks;

  /* Varpool node removal hook holder.  */
  varpool_node_hook_list *m_varpool_node_hooks;

  /* Bitmap stack.  */
  bitmap_obstack m_bmstack;
}; // class sem_item_optimizer

} // ipa_icf namespace