1/* Localize comdats.
2   Copyright (C) 2014-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20/* This is very simple pass that looks for static symbols that are used
21   exlusively by symbol within one comdat group.  In this case it makes
22   sense to bring the symbol itself into the group to avoid dead code
23   that would arrise when the comdat group from current unit is replaced
24   by a different copy.  Consider for example:
25
26    static int q(void)
27    {
28      ....
29    }
30    inline int t(void)
31    {
32      return q();
33    }
34
35   if Q is used only by T, it makes sense to put Q into T's comdat group.
36
37   The pass solve simple dataflow across the callgraph trying to prove what
38   symbols are used exclusively from a given comdat group.
39
40   The implementation maintains a queue linked by AUX pointer terminated by
41   pointer value 1. Lattice values are NULL for TOP, actual comdat group, or
42   ERROR_MARK_NODE for bottom.
43
44   TODO: When symbol is used only by comdat symbols, but from different groups,
45   it would make sense to produce a new comdat group for it with anonymous name.
46
47   TODO2: We can't mix variables and functions within one group.  Currently
48   we just give up on references of symbols of different types.  We also should
49   handle this by anonymous comdat group section.  */
50
51#include "config.h"
52#include "system.h"
53#include "coretypes.h"
54#include "tm.h"
55#include "hash-set.h"
56#include "machmode.h"
57#include "vec.h"
58#include "double-int.h"
59#include "input.h"
60#include "alias.h"
61#include "symtab.h"
62#include "wide-int.h"
63#include "inchash.h"
64#include "tree.h"
65#include "hash-map.h"
66#include "is-a.h"
67#include "plugin-api.h"
68#include "vec.h"
69#include "hard-reg-set.h"
70#include "input.h"
71#include "function.h"
72#include "ipa-ref.h"
73#include "cgraph.h"
74#include "tree-pass.h"
75
76/* Main dataflow loop propagating comdat groups across
77   the symbol table.  All references to SYMBOL are examined
78   and NEWGROUP is updated accordingly. MAP holds current lattice
79   values for individual symbols.  */
80
81tree
82propagate_comdat_group (struct symtab_node *symbol,
83			tree newgroup, hash_map<symtab_node *, tree> &map)
84{
85  int i;
86  struct ipa_ref *ref;
87
88  /* Walk all references to SYMBOL, recursively dive into aliases.  */
89
90  for (i = 0;
91       symbol->iterate_referring (i, ref)
92       && newgroup != error_mark_node; i++)
93    {
94      struct symtab_node *symbol2 = ref->referring;
95
96      if (ref->use == IPA_REF_ALIAS)
97	{
98	  newgroup = propagate_comdat_group (symbol2, newgroup, map);
99	  continue;
100	}
101
102      /* One COMDAT group can not hold both variables and functions at
103	 a same time.  For now we just go to BOTTOM, in future we may
104	 invent special comdat groups for this case.  */
105
106      if (symbol->type != symbol2->type)
107	{
108	  newgroup = error_mark_node;
109	  break;
110	}
111
112      /* If we see inline clone, its comdat group actually
113	 corresponds to the comdat group of the function it is inlined
114	 to.  */
115
116      if (cgraph_node * cn = dyn_cast <cgraph_node *> (symbol2))
117	{
118	  if (cn->global.inlined_to)
119	    symbol2 = cn->global.inlined_to;
120	}
121
122      /* The actual merge operation.  */
123
124      tree *val2 = map.get (symbol2);
125
126      if (val2 && *val2 != newgroup)
127	{
128	  if (!newgroup)
129	    newgroup = *val2;
130	  else
131	    newgroup = error_mark_node;
132	}
133    }
134
135  /* If we analyze function, walk also callers.  */
136
137  cgraph_node *cnode = dyn_cast <cgraph_node *> (symbol);
138
139  if (cnode)
140    for (struct cgraph_edge * edge = cnode->callers;
141	 edge && newgroup != error_mark_node; edge = edge->next_caller)
142      {
143	struct symtab_node *symbol2 = edge->caller;
144
145	if (cgraph_node * cn = dyn_cast <cgraph_node *> (symbol2))
146	  {
147	    /* Thunks can not call across section boundary.  */
148	    if (cn->thunk.thunk_p)
149	      newgroup = propagate_comdat_group (symbol2, newgroup, map);
150	    /* If we see inline clone, its comdat group actually
151	       corresponds to the comdat group of the function it
152	       is inlined to.  */
153	    if (cn->global.inlined_to)
154	      symbol2 = cn->global.inlined_to;
155	  }
156
157        /* The actual merge operation.  */
158
159	tree *val2 = map.get (symbol2);
160
161	if (val2 && *val2 != newgroup)
162	  {
163	    if (!newgroup)
164	      newgroup = *val2;
165	    else
166	      newgroup = error_mark_node;
167	  }
168      }
169  return newgroup;
170}
171
172
173/* Add all references of SYMBOL that are defined into queue started by FIRST
174   and linked by AUX pointer (unless they are already enqueued).
175   Walk recursively inlined functions.  */
176
177void
178enqueue_references (symtab_node **first,
179		    symtab_node *symbol)
180{
181  int i;
182  struct ipa_ref *ref = NULL;
183
184  for (i = 0; symbol->iterate_reference (i, ref); i++)
185    {
186      symtab_node *node = ref->referred->ultimate_alias_target ();
187
188      /* Always keep thunks in same sections as target function.  */
189      if (is_a <cgraph_node *>(node))
190	node = dyn_cast <cgraph_node *> (node)->function_symbol ();
191      if (!node->aux && node->definition)
192	{
193	   node->aux = *first;
194	   *first = node;
195	}
196    }
197
198  if (cgraph_node *cnode = dyn_cast <cgraph_node *> (symbol))
199    {
200      struct cgraph_edge *edge;
201
202      for (edge = cnode->callees; edge; edge = edge->next_callee)
203	if (!edge->inline_failed)
204	  enqueue_references (first, edge->callee);
205	else
206	  {
207	    symtab_node *node = edge->callee->ultimate_alias_target ();
208
209	    /* Always keep thunks in same sections as target function.  */
210	    if (is_a <cgraph_node *>(node))
211	      node = dyn_cast <cgraph_node *> (node)->function_symbol ();
212	    if (!node->aux && node->definition)
213	      {
214		 node->aux = *first;
215		 *first = node;
216	      }
217	  }
218    }
219}
220
221/* Set comdat group of SYMBOL to GROUP.
222   Callback for for_node_and_aliases.  */
223
224bool
225set_comdat_group (symtab_node *symbol,
226	          void *head_p)
227{
228  symtab_node *head = (symtab_node *)head_p;
229
230  gcc_assert (!symbol->get_comdat_group ());
231  symbol->set_comdat_group (head->get_comdat_group ());
232  symbol->add_to_same_comdat_group (head);
233  return false;
234}
235
236/* Set comdat group of SYMBOL to GROUP.
237   Callback for for_node_thunks_and_aliases.  */
238
239bool
240set_comdat_group_1 (cgraph_node *symbol,
241		    void *head_p)
242{
243  return set_comdat_group (symbol, head_p);
244}
245
246/* The actual pass with the main dataflow loop.  */
247
248static unsigned int
249ipa_comdats (void)
250{
251  hash_map<symtab_node *, tree> map (251);
252  hash_map<tree, symtab_node *> comdat_head_map (251);
253  symtab_node *symbol;
254  bool comdat_group_seen = false;
255  symtab_node *first = (symtab_node *) (void *) 1;
256  tree group;
257
258  /* Start the dataflow by assigning comdat group to symbols that are in comdat
259     groups already.  All other externally visible symbols must stay, we use
260     ERROR_MARK_NODE as bottom for the propagation.  */
261
262  FOR_EACH_DEFINED_SYMBOL (symbol)
263    if (!symbol->real_symbol_p ())
264      ;
265    else if ((group = symbol->get_comdat_group ()) != NULL)
266      {
267        map.put (symbol, group);
268        comdat_head_map.put (group, symbol);
269	comdat_group_seen = true;
270
271	/* Mark the symbol so we won't waste time visiting it for dataflow.  */
272	symbol->aux = (symtab_node *) (void *) 1;
273      }
274    /* See symbols that can not be privatized to comdats; that is externally
275       visible symbols or otherwise used ones.  We also do not want to mangle
276       user section names.  */
277    else if (symbol->externally_visible
278	     || symbol->force_output
279	     || symbol->used_from_other_partition
280	     || TREE_THIS_VOLATILE (symbol->decl)
281	     || symbol->get_section ()
282	     || (TREE_CODE (symbol->decl) == FUNCTION_DECL
283		 && (DECL_STATIC_CONSTRUCTOR (symbol->decl)
284		     || DECL_STATIC_DESTRUCTOR (symbol->decl))))
285      {
286	symtab_node *target = symbol->ultimate_alias_target ();
287
288	/* Always keep thunks in same sections as target function.  */
289	if (is_a <cgraph_node *>(target))
290	  target = dyn_cast <cgraph_node *> (target)->function_symbol ();
291	map.put (target, error_mark_node);
292
293	/* Mark the symbol so we won't waste time visiting it for dataflow.  */
294	symbol->aux = (symtab_node *) (void *) 1;
295      }
296    else
297      {
298	/* Enqueue symbol for dataflow.  */
299        symbol->aux = first;
300	first = symbol;
301      }
302
303  if (!comdat_group_seen)
304    {
305      FOR_EACH_DEFINED_SYMBOL (symbol)
306        symbol->aux = NULL;
307      return 0;
308    }
309
310  /* The actual dataflow.  */
311
312  while (first != (void *) 1)
313    {
314      tree group = NULL;
315      tree newgroup, *val;
316
317      symbol = first;
318      first = (symtab_node *)first->aux;
319
320      /* Get current lattice value of SYMBOL.  */
321      val = map.get (symbol);
322      if (val)
323	group = *val;
324
325      /* If it is bottom, there is nothing to do; do not clear AUX
326	 so we won't re-queue the symbol.  */
327      if (group == error_mark_node)
328	continue;
329
330      newgroup = propagate_comdat_group (symbol, group, map);
331
332      /* If nothing changed, proceed to next symbol.  */
333      if (newgroup == group)
334	{
335	  symbol->aux = NULL;
336	  continue;
337	}
338
339      /* Update lattice value and enqueue all references for re-visiting.  */
340      gcc_assert (newgroup);
341      if (val)
342	*val = newgroup;
343      else
344	map.put (symbol, newgroup);
345      enqueue_references (&first, symbol);
346
347      /* We may need to revisit the symbol unless it is BOTTOM.  */
348      if (newgroup != error_mark_node)
349        symbol->aux = NULL;
350    }
351
352  /* Finally assign symbols to the sections.  */
353
354  FOR_EACH_DEFINED_SYMBOL (symbol)
355    {
356      struct cgraph_node *fun;
357      symbol->aux = NULL;
358      if (!symbol->get_comdat_group ()
359	  && !symbol->alias
360	  && (!(fun = dyn_cast <cgraph_node *> (symbol))
361	      || !fun->thunk.thunk_p)
362	  && symbol->real_symbol_p ())
363	{
364	  tree *val = map.get (symbol);
365
366	  /* A NULL here means that SYMBOL is unreachable in the definition
367	     of ipa-comdats. Either ipa-comdats is wrong about this or someone
368	     forgot to cleanup and remove unreachable functions earlier.  */
369	  gcc_assert (val);
370
371	  tree group = *val;
372
373	  if (group == error_mark_node)
374	    continue;
375	  if (dump_file)
376	    {
377	      fprintf (dump_file, "Localizing symbol\n");
378	      symbol->dump (dump_file);
379	      fprintf (dump_file, "To group: %s\n", IDENTIFIER_POINTER (group));
380	    }
381	  if (is_a <cgraph_node *> (symbol))
382	   dyn_cast <cgraph_node *>(symbol)->call_for_symbol_thunks_and_aliases
383		  (set_comdat_group_1,
384		   *comdat_head_map.get (group),
385		   true);
386	  else
387	   symbol->call_for_symbol_and_aliases
388		  (set_comdat_group,
389		   *comdat_head_map.get (group),
390		   true);
391	}
392    }
393  return 0;
394}
395
396namespace {
397
398const pass_data pass_data_ipa_comdats =
399{
400  IPA_PASS, /* type */
401  "comdats", /* name */
402  OPTGROUP_NONE, /* optinfo_flags */
403  TV_IPA_COMDATS, /* tv_id */
404  0, /* properties_required */
405  0, /* properties_provided */
406  0, /* properties_destroyed */
407  0, /* todo_flags_start */
408  0, /* todo_flags_finish */
409};
410
411class pass_ipa_comdats : public ipa_opt_pass_d
412{
413public:
414  pass_ipa_comdats (gcc::context *ctxt)
415    : ipa_opt_pass_d (pass_data_ipa_comdats, ctxt,
416		      NULL, /* generate_summary */
417		      NULL, /* write_summary */
418		      NULL, /* read_summary */
419		      NULL, /* write_optimization_summary */
420		      NULL, /* read_optimization_summary */
421		      NULL, /* stmt_fixup */
422		      0, /* function_transform_todo_flags_start */
423		      NULL, /* function_transform */
424		      NULL) /* variable_transform */
425  {}
426
427  /* opt_pass methods: */
428  virtual bool gate (function *);
429  virtual unsigned int execute (function *) { return ipa_comdats (); }
430
431}; // class pass_ipa_comdats
432
433bool
434pass_ipa_comdats::gate (function *)
435{
436  return optimize;
437}
438
439} // anon namespace
440
441ipa_opt_pass_d *
442make_pass_ipa_comdats (gcc::context *ctxt)
443{
444  return new pass_ipa_comdats (ctxt);
445}
446