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