Daily bump.
[official-gcc.git] / gcc / ipa.c
bloba74f28c2aa1236e4e8877a647e924f146a90799e
1 /* Basic IPA optimizations and utilities.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "target.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "alloc-pool.h"
28 #include "tree-pass.h"
29 #include "stringpool.h"
30 #include "cgraph.h"
31 #include "gimplify.h"
32 #include "tree-iterator.h"
33 #include "ipa-utils.h"
34 #include "symbol-summary.h"
35 #include "tree-vrp.h"
36 #include "ipa-prop.h"
37 #include "ipa-inline.h"
38 #include "dbgcnt.h"
39 #include "debug.h"
42 /* Return true when NODE has ADDR reference. */
44 static bool
45 has_addr_references_p (struct cgraph_node *node,
46 void *)
48 int i;
49 struct ipa_ref *ref = NULL;
51 for (i = 0; node->iterate_referring (i, ref); i++)
52 if (ref->use == IPA_REF_ADDR)
53 return true;
54 return false;
57 /* Return true when NODE can be target of an indirect call. */
59 static bool
60 is_indirect_call_target_p (struct cgraph_node *node, void *)
62 return node->indirect_call_target;
65 /* Look for all functions inlined to NODE and update their inlined_to pointers
66 to INLINED_TO. */
68 static void
69 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
71 struct cgraph_edge *e;
72 for (e = node->callees; e; e = e->next_callee)
73 if (e->callee->global.inlined_to)
75 e->callee->global.inlined_to = inlined_to;
76 update_inlined_to_pointer (e->callee, inlined_to);
80 /* Add symtab NODE to queue starting at FIRST.
82 The queue is linked via AUX pointers and terminated by pointer to 1.
83 We enqueue nodes at two occasions: when we find them reachable or when we find
84 their bodies needed for further clonning. In the second case we mark them
85 by pointer to 2 after processing so they are re-queue when they become
86 reachable. */
88 static void
89 enqueue_node (symtab_node *node, symtab_node **first,
90 hash_set<symtab_node *> *reachable)
92 /* Node is still in queue; do nothing. */
93 if (node->aux && node->aux != (void *) 2)
94 return;
95 /* Node was already processed as unreachable, re-enqueue
96 only if it became reachable now. */
97 if (node->aux == (void *)2 && !reachable->contains (node))
98 return;
99 node->aux = *first;
100 *first = node;
103 /* Process references. */
105 static void
106 process_references (symtab_node *snode,
107 symtab_node **first,
108 bool before_inlining_p,
109 hash_set<symtab_node *> *reachable)
111 int i;
112 struct ipa_ref *ref = NULL;
113 for (i = 0; snode->iterate_reference (i, ref); i++)
115 symtab_node *node = ref->referred;
116 symtab_node *body = node->ultimate_alias_target ();
118 if (node->definition && !node->in_other_partition
119 && ((!DECL_EXTERNAL (node->decl) || node->alias)
120 || (((before_inlining_p
121 && ((TREE_CODE (node->decl) != FUNCTION_DECL
122 && optimize)
123 || (TREE_CODE (node->decl) == FUNCTION_DECL
124 && opt_for_fn (body->decl, optimize))
125 || (symtab->state < IPA_SSA
126 && lookup_attribute
127 ("always_inline",
128 DECL_ATTRIBUTES (body->decl))))))
129 /* We use variable constructors during late compilation for
130 constant folding. Keep references alive so partitioning
131 knows about potential references. */
132 || (VAR_P (node->decl)
133 && flag_wpa
134 && ctor_for_folding (node->decl)
135 != error_mark_node))))
137 /* Be sure that we will not optimize out alias target
138 body. */
139 if (DECL_EXTERNAL (node->decl)
140 && node->alias
141 && before_inlining_p)
142 reachable->add (body);
143 reachable->add (node);
145 enqueue_node (node, first, reachable);
149 /* EDGE is an polymorphic call. If BEFORE_INLINING_P is set, mark
150 all its potential targets as reachable to permit later inlining if
151 devirtualization happens. After inlining still keep their declarations
152 around, so we can devirtualize to a direct call.
154 Also try to make trivial devirutalization when no or only one target is
155 possible. */
157 static void
158 walk_polymorphic_call_targets (hash_set<void *> *reachable_call_targets,
159 struct cgraph_edge *edge,
160 symtab_node **first,
161 hash_set<symtab_node *> *reachable,
162 bool before_inlining_p)
164 unsigned int i;
165 void *cache_token;
166 bool final;
167 vec <cgraph_node *>targets
168 = possible_polymorphic_call_targets
169 (edge, &final, &cache_token);
171 if (!reachable_call_targets->add (cache_token))
173 for (i = 0; i < targets.length (); i++)
175 struct cgraph_node *n = targets[i];
177 /* Do not bother to mark virtual methods in anonymous namespace;
178 either we will find use of virtual table defining it, or it is
179 unused. */
180 if (TREE_CODE (TREE_TYPE (n->decl)) == METHOD_TYPE
181 && type_in_anonymous_namespace_p
182 (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl))))
183 continue;
185 n->indirect_call_target = true;
186 symtab_node *body = n->function_symbol ();
188 /* Prior inlining, keep alive bodies of possible targets for
189 devirtualization. */
190 if (n->definition
191 && (before_inlining_p
192 && opt_for_fn (body->decl, optimize)
193 && opt_for_fn (body->decl, flag_devirtualize)))
195 /* Be sure that we will not optimize out alias target
196 body. */
197 if (DECL_EXTERNAL (n->decl)
198 && n->alias
199 && before_inlining_p)
200 reachable->add (body);
201 reachable->add (n);
203 /* Even after inlining we want to keep the possible targets in the
204 boundary, so late passes can still produce direct call even if
205 the chance for inlining is lost. */
206 enqueue_node (n, first, reachable);
210 /* Very trivial devirtualization; when the type is
211 final or anonymous (so we know all its derivation)
212 and there is only one possible virtual call target,
213 make the edge direct. */
214 if (final)
216 if (targets.length () <= 1 && dbg_cnt (devirt))
218 cgraph_node *target, *node = edge->caller;
219 if (targets.length () == 1)
220 target = targets[0];
221 else
222 target = cgraph_node::get_create
223 (builtin_decl_implicit (BUILT_IN_UNREACHABLE));
225 if (dump_enabled_p ())
227 location_t locus;
228 if (edge->call_stmt)
229 locus = gimple_location (edge->call_stmt);
230 else
231 locus = UNKNOWN_LOCATION;
232 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
233 "devirtualizing call in %s/%i to %s/%i\n",
234 edge->caller->name (), edge->caller->order,
235 target->name (),
236 target->order);
238 edge = edge->make_direct (target);
239 if (inline_summaries)
240 inline_update_overall_summary (node);
241 else if (edge->call_stmt)
243 edge->redirect_call_stmt_to_callee ();
245 /* Call to __builtin_unreachable shouldn't be instrumented. */
246 if (!targets.length ())
247 gimple_call_set_with_bounds (edge->call_stmt, false);
253 /* Perform reachability analysis and reclaim all unreachable nodes.
255 The algorithm is basically mark&sweep but with some extra refinements:
257 - reachable extern inline functions needs special handling; the bodies needs
258 to stay in memory until inlining in hope that they will be inlined.
259 After inlining we release their bodies and turn them into unanalyzed
260 nodes even when they are reachable.
262 - virtual functions are kept in callgraph even if they seem unreachable in
263 hope calls to them will be devirtualized.
265 Again we remove them after inlining. In late optimization some
266 devirtualization may happen, but it is not important since we won't inline
267 the call. In theory early opts and IPA should work out all important cases.
269 - virtual clones needs bodies of their origins for later materialization;
270 this means that we want to keep the body even if the origin is unreachable
271 otherwise. To avoid origin from sitting in the callgraph and being
272 walked by IPA passes, we turn them into unanalyzed nodes with body
273 defined.
275 We maintain set of function declaration where body needs to stay in
276 body_needed_for_clonning
278 Inline clones represent special case: their declaration match the
279 declaration of origin and cgraph_remove_node already knows how to
280 reshape callgraph and preserve body when offline copy of function or
281 inline clone is being removed.
283 - C++ virtual tables keyed to other unit are represented as DECL_EXTERNAL
284 variables with DECL_INITIAL set. We finalize these and keep reachable
285 ones around for constant folding purposes. After inlining we however
286 stop walking their references to let everything static referneced by them
287 to be removed when it is otherwise unreachable.
289 We maintain queue of both reachable symbols (i.e. defined symbols that needs
290 to stay) and symbols that are in boundary (i.e. external symbols referenced
291 by reachable symbols or origins of clones). The queue is represented
292 as linked list by AUX pointer terminated by 1.
294 At the end we keep all reachable symbols. For symbols in boundary we always
295 turn definition into a declaration, but we may keep function body around
296 based on body_needed_for_clonning
298 All symbols that enter the queue have AUX pointer non-zero and are in the
299 boundary. Pointer set REACHABLE is used to track reachable symbols.
301 Every symbol can be visited twice - once as part of boundary and once
302 as real reachable symbol. enqueue_node needs to decide whether the
303 node needs to be re-queued for second processing. For this purpose
304 we set AUX pointer of processed symbols in the boundary to constant 2. */
306 bool
307 symbol_table::remove_unreachable_nodes (FILE *file)
309 symtab_node *first = (symtab_node *) (void *) 1;
310 struct cgraph_node *node, *next;
311 varpool_node *vnode, *vnext;
312 bool changed = false;
313 hash_set<symtab_node *> reachable;
314 hash_set<tree> body_needed_for_clonning;
315 hash_set<void *> reachable_call_targets;
316 bool before_inlining_p = symtab->state < (!optimize ? IPA_SSA
317 : IPA_SSA_AFTER_INLINING);
319 timevar_push (TV_IPA_UNREACHABLE);
320 build_type_inheritance_graph ();
321 if (file)
322 fprintf (file, "\nReclaiming functions:");
323 if (flag_checking)
325 FOR_EACH_FUNCTION (node)
326 gcc_assert (!node->aux);
327 FOR_EACH_VARIABLE (vnode)
328 gcc_assert (!vnode->aux);
330 /* Mark functions whose bodies are obviously needed.
331 This is mostly when they can be referenced externally. Inline clones
332 are special since their declarations are shared with master clone and thus
333 cgraph_can_remove_if_no_direct_calls_and_refs_p should not be called on them. */
334 FOR_EACH_FUNCTION (node)
336 node->used_as_abstract_origin = false;
337 node->indirect_call_target = false;
338 if (node->definition
339 && !node->global.inlined_to
340 && !node->in_other_partition
341 && !node->can_remove_if_no_direct_calls_and_refs_p ())
343 gcc_assert (!node->global.inlined_to);
344 reachable.add (node);
345 enqueue_node (node, &first, &reachable);
347 else
348 gcc_assert (!node->aux);
351 /* Mark variables that are obviously needed. */
352 FOR_EACH_DEFINED_VARIABLE (vnode)
353 if (!vnode->can_remove_if_no_refs_p()
354 && !vnode->in_other_partition)
356 reachable.add (vnode);
357 enqueue_node (vnode, &first, &reachable);
360 /* Perform reachability analysis. */
361 while (first != (symtab_node *) (void *) 1)
363 bool in_boundary_p = !reachable.contains (first);
364 symtab_node *node = first;
366 first = (symtab_node *)first->aux;
368 /* If we are processing symbol in boundary, mark its AUX pointer for
369 possible later re-processing in enqueue_node. */
370 if (in_boundary_p)
372 node->aux = (void *)2;
373 if (node->alias && node->analyzed)
374 enqueue_node (node->get_alias_target (), &first, &reachable);
376 else
378 if (TREE_CODE (node->decl) == FUNCTION_DECL
379 && DECL_ABSTRACT_ORIGIN (node->decl))
381 struct cgraph_node *origin_node
382 = cgraph_node::get (DECL_ABSTRACT_ORIGIN (node->decl));
383 if (origin_node && !origin_node->used_as_abstract_origin)
385 origin_node->used_as_abstract_origin = true;
386 gcc_assert (!origin_node->prev_sibling_clone);
387 gcc_assert (!origin_node->next_sibling_clone);
388 for (cgraph_node *n = origin_node->clones; n;
389 n = n->next_sibling_clone)
390 if (n->decl == DECL_ABSTRACT_ORIGIN (node->decl))
391 n->used_as_abstract_origin = true;
394 /* If any symbol in a comdat group is reachable, force
395 all externally visible symbols in the same comdat
396 group to be reachable as well. Comdat-local symbols
397 can be discarded if all uses were inlined. */
398 if (node->same_comdat_group)
400 symtab_node *next;
401 for (next = node->same_comdat_group;
402 next != node;
403 next = next->same_comdat_group)
404 if (!next->comdat_local_p ()
405 && !reachable.add (next))
406 enqueue_node (next, &first, &reachable);
408 /* Mark references as reachable. */
409 process_references (node, &first, before_inlining_p, &reachable);
412 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
414 /* Mark the callees reachable unless they are direct calls to extern
415 inline functions we decided to not inline. */
416 if (!in_boundary_p)
418 struct cgraph_edge *e;
419 /* Keep alive possible targets for devirtualization. */
420 if (opt_for_fn (cnode->decl, optimize)
421 && opt_for_fn (cnode->decl, flag_devirtualize))
423 struct cgraph_edge *next;
424 for (e = cnode->indirect_calls; e; e = next)
426 next = e->next_callee;
427 if (e->indirect_info->polymorphic)
428 walk_polymorphic_call_targets (&reachable_call_targets,
429 e, &first, &reachable,
430 before_inlining_p);
433 for (e = cnode->callees; e; e = e->next_callee)
435 symtab_node *body = e->callee->function_symbol ();
436 if (e->callee->definition
437 && !e->callee->in_other_partition
438 && (!e->inline_failed
439 || !DECL_EXTERNAL (e->callee->decl)
440 || e->callee->alias
441 || (before_inlining_p
442 && (opt_for_fn (body->decl, optimize)
443 || (symtab->state < IPA_SSA
444 && lookup_attribute
445 ("always_inline",
446 DECL_ATTRIBUTES (body->decl)))))))
448 /* Be sure that we will not optimize out alias target
449 body. */
450 if (DECL_EXTERNAL (e->callee->decl)
451 && e->callee->alias
452 && before_inlining_p)
453 reachable.add (body);
454 reachable.add (e->callee);
456 enqueue_node (e->callee, &first, &reachable);
459 /* When inline clone exists, mark body to be preserved so when removing
460 offline copy of the function we don't kill it. */
461 if (cnode->global.inlined_to)
462 body_needed_for_clonning.add (cnode->decl);
464 /* For instrumentation clones we always need original
465 function node for proper LTO privatization. */
466 if (cnode->instrumentation_clone
467 && cnode->definition)
469 gcc_assert (cnode->instrumented_version || in_lto_p);
470 if (cnode->instrumented_version)
472 enqueue_node (cnode->instrumented_version, &first,
473 &reachable);
474 reachable.add (cnode->instrumented_version);
478 /* For non-inline clones, force their origins to the boundary and ensure
479 that body is not removed. */
480 while (cnode->clone_of)
482 bool noninline = cnode->clone_of->decl != cnode->decl;
483 cnode = cnode->clone_of;
484 if (noninline)
486 body_needed_for_clonning.add (cnode->decl);
487 enqueue_node (cnode, &first, &reachable);
492 else if (cnode->thunk.thunk_p)
493 enqueue_node (cnode->callees->callee, &first, &reachable);
495 /* If any reachable function has simd clones, mark them as
496 reachable as well. */
497 if (cnode->simd_clones)
499 cgraph_node *next;
500 for (next = cnode->simd_clones;
501 next;
502 next = next->simdclone->next_clone)
503 if (in_boundary_p
504 || !reachable.add (next))
505 enqueue_node (next, &first, &reachable);
508 /* When we see constructor of external variable, keep referred nodes in the
509 boundary. This will also hold initializers of the external vars NODE
510 refers to. */
511 varpool_node *vnode = dyn_cast <varpool_node *> (node);
512 if (vnode
513 && DECL_EXTERNAL (node->decl)
514 && !vnode->alias
515 && in_boundary_p)
517 struct ipa_ref *ref = NULL;
518 for (int i = 0; node->iterate_reference (i, ref); i++)
519 enqueue_node (ref->referred, &first, &reachable);
523 /* Remove unreachable functions. */
524 for (node = first_function (); node; node = next)
526 next = next_function (node);
528 /* If node is not needed at all, remove it. */
529 if (!node->aux)
531 if (file)
532 fprintf (file, " %s/%i", node->name (), node->order);
533 node->remove ();
534 changed = true;
536 /* If node is unreachable, remove its body. */
537 else if (!reachable.contains (node))
539 /* We keep definitions of thunks and aliases in the boundary so
540 we can walk to the ultimate alias targets and function symbols
541 reliably. */
542 if (node->alias || node->thunk.thunk_p)
544 else if (!body_needed_for_clonning.contains (node->decl)
545 && !node->alias && !node->thunk.thunk_p)
546 node->release_body ();
547 else if (!node->clone_of)
548 gcc_assert (in_lto_p || DECL_RESULT (node->decl));
549 if (node->definition && !node->alias && !node->thunk.thunk_p)
551 if (file)
552 fprintf (file, " %s/%i", node->name (), node->order);
553 node->body_removed = true;
554 node->analyzed = false;
555 node->definition = false;
556 node->cpp_implicit_alias = false;
557 node->alias = false;
558 node->transparent_alias = false;
559 node->thunk.thunk_p = false;
560 node->weakref = false;
561 /* After early inlining we drop always_inline attributes on
562 bodies of functions that are still referenced (have their
563 address taken). */
564 DECL_ATTRIBUTES (node->decl)
565 = remove_attribute ("always_inline",
566 DECL_ATTRIBUTES (node->decl));
567 if (!node->in_other_partition)
568 node->local.local = false;
569 node->remove_callees ();
570 node->remove_all_references ();
571 changed = true;
572 if (node->thunk.thunk_p
573 && node->thunk.add_pointer_bounds_args)
575 node->thunk.thunk_p = false;
576 node->thunk.add_pointer_bounds_args = false;
580 else
581 gcc_assert (node->clone_of || !node->has_gimple_body_p ()
582 || in_lto_p || DECL_RESULT (node->decl));
585 /* Inline clones might be kept around so their materializing allows further
586 cloning. If the function the clone is inlined into is removed, we need
587 to turn it into normal cone. */
588 FOR_EACH_FUNCTION (node)
590 if (node->global.inlined_to
591 && !node->callers)
593 gcc_assert (node->clones);
594 node->global.inlined_to = NULL;
595 update_inlined_to_pointer (node, node);
597 node->aux = NULL;
600 /* Remove unreachable variables. */
601 if (file)
602 fprintf (file, "\nReclaiming variables:");
603 for (vnode = first_variable (); vnode; vnode = vnext)
605 vnext = next_variable (vnode);
606 if (!vnode->aux
607 /* For can_refer_decl_in_current_unit_p we want to track for
608 all external variables if they are defined in other partition
609 or not. */
610 && (!flag_ltrans || !DECL_EXTERNAL (vnode->decl)))
612 struct ipa_ref *ref = NULL;
614 /* First remove the aliases, so varpool::remove can possibly lookup
615 the constructor and save it for future use. */
616 while (vnode->iterate_direct_aliases (0, ref))
618 if (file)
619 fprintf (file, " %s/%i", ref->referred->name (),
620 ref->referred->order);
621 ref->referring->remove ();
623 if (file)
624 fprintf (file, " %s/%i", vnode->name (), vnode->order);
625 vnext = next_variable (vnode);
626 /* Signal removal to the debug machinery. */
627 if (! flag_wpa)
629 vnode->definition = false;
630 (*debug_hooks->late_global_decl) (vnode->decl);
632 vnode->remove ();
633 changed = true;
635 else if (!reachable.contains (vnode) && !vnode->alias)
637 tree init;
638 if (vnode->definition)
640 if (file)
641 fprintf (file, " %s", vnode->name ());
642 changed = true;
644 /* Keep body if it may be useful for constant folding. */
645 if ((init = ctor_for_folding (vnode->decl)) == error_mark_node
646 && !POINTER_BOUNDS_P (vnode->decl))
647 vnode->remove_initializer ();
648 else
649 DECL_INITIAL (vnode->decl) = init;
650 vnode->body_removed = true;
651 vnode->definition = false;
652 vnode->analyzed = false;
653 vnode->aux = NULL;
655 vnode->remove_from_same_comdat_group ();
657 vnode->remove_all_references ();
659 else
660 vnode->aux = NULL;
663 /* Now update address_taken flags and try to promote functions to be local. */
664 if (file)
665 fprintf (file, "\nClearing address taken flags:");
666 FOR_EACH_DEFINED_FUNCTION (node)
667 if (node->address_taken
668 && !node->used_from_other_partition)
670 if (!node->call_for_symbol_and_aliases
671 (has_addr_references_p, NULL, true)
672 && (!node->instrumentation_clone
673 || !node->instrumented_version
674 || !node->instrumented_version->address_taken))
676 if (file)
677 fprintf (file, " %s", node->name ());
678 node->address_taken = false;
679 changed = true;
680 if (node->local_p ()
681 /* Virtual functions may be kept in cgraph just because
682 of possible later devirtualization. Do not mark them as
683 local too early so we won't optimize them out before
684 we are done with polymorphic call analysis. */
685 && (!before_inlining_p
686 || !node->call_for_symbol_and_aliases
687 (is_indirect_call_target_p, NULL, true)))
689 node->local.local = true;
690 if (file)
691 fprintf (file, " (local)");
695 if (file)
696 fprintf (file, "\n");
698 symtab_node::checking_verify_symtab_nodes ();
700 /* If we removed something, perhaps profile could be improved. */
701 if (changed && optimize && inline_edge_summary_vec.exists ())
702 FOR_EACH_DEFINED_FUNCTION (node)
703 ipa_propagate_frequency (node);
705 timevar_pop (TV_IPA_UNREACHABLE);
706 return changed;
709 /* Process references to VNODE and set flags WRITTEN, ADDRESS_TAKEN, READ
710 as needed, also clear EXPLICIT_REFS if the references to given variable
711 do not need to be explicit. */
713 void
714 process_references (varpool_node *vnode,
715 bool *written, bool *address_taken,
716 bool *read, bool *explicit_refs)
718 int i;
719 struct ipa_ref *ref;
721 if (!vnode->all_refs_explicit_p ()
722 || TREE_THIS_VOLATILE (vnode->decl))
723 *explicit_refs = false;
725 for (i = 0; vnode->iterate_referring (i, ref)
726 && *explicit_refs && (!*written || !*address_taken || !*read); i++)
727 switch (ref->use)
729 case IPA_REF_ADDR:
730 *address_taken = true;
731 break;
732 case IPA_REF_LOAD:
733 *read = true;
734 break;
735 case IPA_REF_STORE:
736 *written = true;
737 break;
738 case IPA_REF_ALIAS:
739 process_references (dyn_cast<varpool_node *> (ref->referring), written,
740 address_taken, read, explicit_refs);
741 break;
742 case IPA_REF_CHKP:
743 gcc_unreachable ();
747 /* Set TREE_READONLY bit. */
749 bool
750 set_readonly_bit (varpool_node *vnode, void *data ATTRIBUTE_UNUSED)
752 TREE_READONLY (vnode->decl) = true;
753 return false;
756 /* Set writeonly bit and clear the initalizer, since it will not be needed. */
758 bool
759 set_writeonly_bit (varpool_node *vnode, void *data)
761 vnode->writeonly = true;
762 if (optimize)
764 DECL_INITIAL (vnode->decl) = NULL;
765 if (!vnode->alias)
767 if (vnode->num_references ())
768 *(bool *)data = true;
769 vnode->remove_all_references ();
772 return false;
775 /* Clear addressale bit of VNODE. */
777 bool
778 clear_addressable_bit (varpool_node *vnode, void *data ATTRIBUTE_UNUSED)
780 vnode->address_taken = false;
781 TREE_ADDRESSABLE (vnode->decl) = 0;
782 return false;
785 /* Discover variables that have no longer address taken or that are read only
786 and update their flags.
788 Return true when unreachable symbol removan should be done.
790 FIXME: This can not be done in between gimplify and omp_expand since
791 readonly flag plays role on what is shared and what is not. Currently we do
792 this transformation as part of whole program visibility and re-do at
793 ipa-reference pass (to take into account clonning), but it would
794 make sense to do it before early optimizations. */
796 bool
797 ipa_discover_readonly_nonaddressable_vars (void)
799 bool remove_p = false;
800 varpool_node *vnode;
801 if (dump_file)
802 fprintf (dump_file, "Clearing variable flags:");
803 FOR_EACH_VARIABLE (vnode)
804 if (!vnode->alias
805 && (TREE_ADDRESSABLE (vnode->decl)
806 || !vnode->writeonly
807 || !TREE_READONLY (vnode->decl)))
809 bool written = false;
810 bool address_taken = false;
811 bool read = false;
812 bool explicit_refs = true;
814 process_references (vnode, &written, &address_taken, &read,
815 &explicit_refs);
816 if (!explicit_refs)
817 continue;
818 if (!address_taken)
820 if (TREE_ADDRESSABLE (vnode->decl) && dump_file)
821 fprintf (dump_file, " %s (non-addressable)", vnode->name ());
822 vnode->call_for_symbol_and_aliases (clear_addressable_bit, NULL,
823 true);
825 if (!address_taken && !written
826 /* Making variable in explicit section readonly can cause section
827 type conflict.
828 See e.g. gcc.c-torture/compile/pr23237.c */
829 && vnode->get_section () == NULL)
831 if (!TREE_READONLY (vnode->decl) && dump_file)
832 fprintf (dump_file, " %s (read-only)", vnode->name ());
833 vnode->call_for_symbol_and_aliases (set_readonly_bit, NULL, true);
835 if (!vnode->writeonly && !read && !address_taken && written)
837 if (dump_file)
838 fprintf (dump_file, " %s (write-only)", vnode->name ());
839 vnode->call_for_symbol_and_aliases (set_writeonly_bit, &remove_p,
840 true);
843 if (dump_file)
844 fprintf (dump_file, "\n");
845 return remove_p;
848 /* Free inline summary. */
850 namespace {
852 const pass_data pass_data_ipa_free_inline_summary =
854 SIMPLE_IPA_PASS, /* type */
855 "free-inline-summary", /* name */
856 OPTGROUP_NONE, /* optinfo_flags */
857 TV_IPA_FREE_INLINE_SUMMARY, /* tv_id */
858 0, /* properties_required */
859 0, /* properties_provided */
860 0, /* properties_destroyed */
861 0, /* todo_flags_start */
862 /* Early optimizations may make function unreachable. We can not
863 remove unreachable functions as part of the ealry opts pass because
864 TODOs are run before subpasses. Do it here. */
865 ( TODO_remove_functions | TODO_dump_symtab ), /* todo_flags_finish */
868 class pass_ipa_free_inline_summary : public simple_ipa_opt_pass
870 public:
871 pass_ipa_free_inline_summary (gcc::context *ctxt)
872 : simple_ipa_opt_pass (pass_data_ipa_free_inline_summary, ctxt)
875 /* opt_pass methods: */
876 virtual unsigned int execute (function *)
878 inline_free_summary ();
879 return 0;
882 }; // class pass_ipa_free_inline_summary
884 } // anon namespace
886 simple_ipa_opt_pass *
887 make_pass_ipa_free_inline_summary (gcc::context *ctxt)
889 return new pass_ipa_free_inline_summary (ctxt);
892 /* Generate and emit a static constructor or destructor. WHICH must
893 be one of 'I' (for a constructor), 'D' (for a destructor), 'P'
894 (for chp static vars constructor) or 'B' (for chkp static bounds
895 constructor). BODY is a STATEMENT_LIST containing GENERIC
896 statements. PRIORITY is the initialization priority for this
897 constructor or destructor.
899 FINAL specify whether the externally visible name for collect2 should
900 be produced. */
902 static void
903 cgraph_build_static_cdtor_1 (char which, tree body, int priority, bool final)
905 static int counter = 0;
906 char which_buf[16];
907 tree decl, name, resdecl;
909 /* The priority is encoded in the constructor or destructor name.
910 collect2 will sort the names and arrange that they are called at
911 program startup. */
912 if (final)
913 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
914 else
915 /* Proudce sane name but one not recognizable by collect2, just for the
916 case we fail to inline the function. */
917 sprintf (which_buf, "sub_%c_%.5d_%d", which, priority, counter++);
918 name = get_file_function_name (which_buf);
920 decl = build_decl (input_location, FUNCTION_DECL, name,
921 build_function_type_list (void_type_node, NULL_TREE));
922 current_function_decl = decl;
924 resdecl = build_decl (input_location,
925 RESULT_DECL, NULL_TREE, void_type_node);
926 DECL_ARTIFICIAL (resdecl) = 1;
927 DECL_RESULT (decl) = resdecl;
928 DECL_CONTEXT (resdecl) = decl;
930 allocate_struct_function (decl, false);
932 TREE_STATIC (decl) = 1;
933 TREE_USED (decl) = 1;
934 DECL_ARTIFICIAL (decl) = 1;
935 DECL_IGNORED_P (decl) = 1;
936 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
937 DECL_SAVED_TREE (decl) = body;
938 if (!targetm.have_ctors_dtors && final)
940 TREE_PUBLIC (decl) = 1;
941 DECL_PRESERVE_P (decl) = 1;
943 DECL_UNINLINABLE (decl) = 1;
945 DECL_INITIAL (decl) = make_node (BLOCK);
946 BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
947 TREE_USED (DECL_INITIAL (decl)) = 1;
949 DECL_SOURCE_LOCATION (decl) = input_location;
950 cfun->function_end_locus = input_location;
952 switch (which)
954 case 'I':
955 DECL_STATIC_CONSTRUCTOR (decl) = 1;
956 decl_init_priority_insert (decl, priority);
957 break;
958 case 'P':
959 DECL_STATIC_CONSTRUCTOR (decl) = 1;
960 DECL_ATTRIBUTES (decl) = tree_cons (get_identifier ("chkp ctor"),
961 NULL,
962 NULL_TREE);
963 decl_init_priority_insert (decl, priority);
964 break;
965 case 'B':
966 DECL_STATIC_CONSTRUCTOR (decl) = 1;
967 DECL_ATTRIBUTES (decl) = tree_cons (get_identifier ("bnd_legacy"),
968 NULL,
969 NULL_TREE);
970 decl_init_priority_insert (decl, priority);
971 break;
972 case 'D':
973 DECL_STATIC_DESTRUCTOR (decl) = 1;
974 decl_fini_priority_insert (decl, priority);
975 break;
976 default:
977 gcc_unreachable ();
980 gimplify_function_tree (decl);
982 cgraph_node::add_new_function (decl, false);
984 set_cfun (NULL);
985 current_function_decl = NULL;
988 /* Generate and emit a static constructor or destructor. WHICH must
989 be one of 'I' (for a constructor), 'D' (for a destructor), 'P'
990 (for chkp static vars constructor) or 'B' (for chkp static bounds
991 constructor). BODY is a STATEMENT_LIST containing GENERIC
992 statements. PRIORITY is the initialization priority for this
993 constructor or destructor. */
995 void
996 cgraph_build_static_cdtor (char which, tree body, int priority)
998 cgraph_build_static_cdtor_1 (which, body, priority, false);
1001 /* When target does not have ctors and dtors, we call all constructor
1002 and destructor by special initialization/destruction function
1003 recognized by collect2.
1005 When we are going to build this function, collect all constructors and
1006 destructors and turn them into normal functions. */
1008 static void
1009 record_cdtor_fn (struct cgraph_node *node, vec<tree> *ctors, vec<tree> *dtors)
1011 if (DECL_STATIC_CONSTRUCTOR (node->decl))
1012 ctors->safe_push (node->decl);
1013 if (DECL_STATIC_DESTRUCTOR (node->decl))
1014 dtors->safe_push (node->decl);
1015 node = cgraph_node::get (node->decl);
1016 DECL_DISREGARD_INLINE_LIMITS (node->decl) = 1;
1019 /* Define global constructors/destructor functions for the CDTORS, of
1020 which they are LEN. The CDTORS are sorted by initialization
1021 priority. If CTOR_P is true, these are constructors; otherwise,
1022 they are destructors. */
1024 static void
1025 build_cdtor (bool ctor_p, const vec<tree> &cdtors)
1027 size_t i,j;
1028 size_t len = cdtors.length ();
1030 i = 0;
1031 while (i < len)
1033 tree body;
1034 tree fn;
1035 priority_type priority;
1037 priority = 0;
1038 body = NULL_TREE;
1039 j = i;
1042 priority_type p;
1043 fn = cdtors[j];
1044 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
1045 if (j == i)
1046 priority = p;
1047 else if (p != priority)
1048 break;
1049 j++;
1051 while (j < len);
1053 /* When there is only one cdtor and target supports them, do nothing. */
1054 if (j == i + 1
1055 && targetm.have_ctors_dtors)
1057 i++;
1058 continue;
1060 /* Find the next batch of constructors/destructors with the same
1061 initialization priority. */
1062 for (;i < j; i++)
1064 tree call;
1065 fn = cdtors[i];
1066 call = build_call_expr (fn, 0);
1067 if (ctor_p)
1068 DECL_STATIC_CONSTRUCTOR (fn) = 0;
1069 else
1070 DECL_STATIC_DESTRUCTOR (fn) = 0;
1071 /* We do not want to optimize away pure/const calls here.
1072 When optimizing, these should be already removed, when not
1073 optimizing, we want user to be able to breakpoint in them. */
1074 TREE_SIDE_EFFECTS (call) = 1;
1075 append_to_statement_list (call, &body);
1077 gcc_assert (body != NULL_TREE);
1078 /* Generate a function to call all the function of like
1079 priority. */
1080 cgraph_build_static_cdtor_1 (ctor_p ? 'I' : 'D', body, priority, true);
1084 /* Comparison function for qsort. P1 and P2 are actually of type
1085 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
1086 used to determine the sort order. */
1088 static int
1089 compare_ctor (const void *p1, const void *p2)
1091 tree f1;
1092 tree f2;
1093 int priority1;
1094 int priority2;
1096 f1 = *(const tree *)p1;
1097 f2 = *(const tree *)p2;
1098 priority1 = DECL_INIT_PRIORITY (f1);
1099 priority2 = DECL_INIT_PRIORITY (f2);
1101 if (priority1 < priority2)
1102 return -1;
1103 else if (priority1 > priority2)
1104 return 1;
1105 else
1106 /* Ensure a stable sort. Constructors are executed in backwarding
1107 order to make LTO initialize braries first. */
1108 return DECL_UID (f2) - DECL_UID (f1);
1111 /* Comparison function for qsort. P1 and P2 are actually of type
1112 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
1113 used to determine the sort order. */
1115 static int
1116 compare_dtor (const void *p1, const void *p2)
1118 tree f1;
1119 tree f2;
1120 int priority1;
1121 int priority2;
1123 f1 = *(const tree *)p1;
1124 f2 = *(const tree *)p2;
1125 priority1 = DECL_FINI_PRIORITY (f1);
1126 priority2 = DECL_FINI_PRIORITY (f2);
1128 if (priority1 < priority2)
1129 return -1;
1130 else if (priority1 > priority2)
1131 return 1;
1132 else
1133 /* Ensure a stable sort. */
1134 return DECL_UID (f1) - DECL_UID (f2);
1137 /* Generate functions to call static constructors and destructors
1138 for targets that do not support .ctors/.dtors sections. These
1139 functions have magic names which are detected by collect2. */
1141 static void
1142 build_cdtor_fns (vec<tree> *ctors, vec<tree> *dtors)
1144 if (!ctors->is_empty ())
1146 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1147 ctors->qsort (compare_ctor);
1148 build_cdtor (/*ctor_p=*/true, *ctors);
1151 if (!dtors->is_empty ())
1153 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1154 dtors->qsort (compare_dtor);
1155 build_cdtor (/*ctor_p=*/false, *dtors);
1159 /* Look for constructors and destructors and produce function calling them.
1160 This is needed for targets not supporting ctors or dtors, but we perform the
1161 transformation also at linktime to merge possibly numerous
1162 constructors/destructors into single function to improve code locality and
1163 reduce size. */
1165 static unsigned int
1166 ipa_cdtor_merge (void)
1168 /* A vector of FUNCTION_DECLs declared as static constructors. */
1169 auto_vec<tree, 20> ctors;
1170 /* A vector of FUNCTION_DECLs declared as static destructors. */
1171 auto_vec<tree, 20> dtors;
1172 struct cgraph_node *node;
1173 FOR_EACH_DEFINED_FUNCTION (node)
1174 if (DECL_STATIC_CONSTRUCTOR (node->decl)
1175 || DECL_STATIC_DESTRUCTOR (node->decl))
1176 record_cdtor_fn (node, &ctors, &dtors);
1177 build_cdtor_fns (&ctors, &dtors);
1178 return 0;
1181 namespace {
1183 const pass_data pass_data_ipa_cdtor_merge =
1185 IPA_PASS, /* type */
1186 "cdtor", /* name */
1187 OPTGROUP_NONE, /* optinfo_flags */
1188 TV_CGRAPHOPT, /* tv_id */
1189 0, /* properties_required */
1190 0, /* properties_provided */
1191 0, /* properties_destroyed */
1192 0, /* todo_flags_start */
1193 0, /* todo_flags_finish */
1196 class pass_ipa_cdtor_merge : public ipa_opt_pass_d
1198 public:
1199 pass_ipa_cdtor_merge (gcc::context *ctxt)
1200 : ipa_opt_pass_d (pass_data_ipa_cdtor_merge, ctxt,
1201 NULL, /* generate_summary */
1202 NULL, /* write_summary */
1203 NULL, /* read_summary */
1204 NULL, /* write_optimization_summary */
1205 NULL, /* read_optimization_summary */
1206 NULL, /* stmt_fixup */
1207 0, /* function_transform_todo_flags_start */
1208 NULL, /* function_transform */
1209 NULL) /* variable_transform */
1212 /* opt_pass methods: */
1213 virtual bool gate (function *);
1214 virtual unsigned int execute (function *) { return ipa_cdtor_merge (); }
1216 }; // class pass_ipa_cdtor_merge
1218 bool
1219 pass_ipa_cdtor_merge::gate (function *)
1221 /* Perform the pass when we have no ctors/dtors support
1222 or at LTO time to merge multiple constructors into single
1223 function. */
1224 return !targetm.have_ctors_dtors || (optimize && in_lto_p);
1227 } // anon namespace
1229 ipa_opt_pass_d *
1230 make_pass_ipa_cdtor_merge (gcc::context *ctxt)
1232 return new pass_ipa_cdtor_merge (ctxt);
1235 /* Invalid pointer representing BOTTOM for single user dataflow. */
1236 #define BOTTOM ((cgraph_node *)(size_t) 2)
1238 /* Meet operation for single user dataflow.
1239 Here we want to associate variables with sigle function that may access it.
1241 FUNCTION is current single user of a variable, VAR is variable that uses it.
1242 Latttice is stored in SINGLE_USER_MAP.
1244 We represent:
1245 - TOP by no entry in SIGNLE_USER_MAP
1246 - BOTTOM by BOTTOM in AUX pointer (to save lookups)
1247 - known single user by cgraph pointer in SINGLE_USER_MAP. */
1249 cgraph_node *
1250 meet (cgraph_node *function, varpool_node *var,
1251 hash_map<varpool_node *, cgraph_node *> &single_user_map)
1253 struct cgraph_node *user, **f;
1255 if (var->aux == BOTTOM)
1256 return BOTTOM;
1258 f = single_user_map.get (var);
1259 if (!f)
1260 return function;
1261 user = *f;
1262 if (!function)
1263 return user;
1264 else if (function != user)
1265 return BOTTOM;
1266 else
1267 return function;
1270 /* Propagation step of single-use dataflow.
1272 Check all uses of VNODE and see if they are used by single function FUNCTION.
1273 SINGLE_USER_MAP represents the dataflow lattice. */
1275 cgraph_node *
1276 propagate_single_user (varpool_node *vnode, cgraph_node *function,
1277 hash_map<varpool_node *, cgraph_node *> &single_user_map)
1279 int i;
1280 struct ipa_ref *ref;
1282 gcc_assert (!vnode->externally_visible);
1284 /* If node is an alias, first meet with its target. */
1285 if (vnode->alias)
1286 function = meet (function, vnode->get_alias_target (), single_user_map);
1288 /* Check all users and see if they correspond to a single function. */
1289 for (i = 0; vnode->iterate_referring (i, ref) && function != BOTTOM; i++)
1291 struct cgraph_node *cnode = dyn_cast <cgraph_node *> (ref->referring);
1292 if (cnode)
1294 if (cnode->global.inlined_to)
1295 cnode = cnode->global.inlined_to;
1296 if (!function)
1297 function = cnode;
1298 else if (function != cnode)
1299 function = BOTTOM;
1301 else
1302 function = meet (function, dyn_cast <varpool_node *> (ref->referring),
1303 single_user_map);
1305 return function;
1308 /* Pass setting used_by_single_function flag.
1309 This flag is set on variable when there is only one function that may
1310 possibly referr to it. */
1312 static unsigned int
1313 ipa_single_use (void)
1315 varpool_node *first = (varpool_node *) (void *) 1;
1316 varpool_node *var;
1317 hash_map<varpool_node *, cgraph_node *> single_user_map;
1319 FOR_EACH_DEFINED_VARIABLE (var)
1320 if (!var->all_refs_explicit_p ())
1321 var->aux = BOTTOM;
1322 else
1324 /* Enqueue symbol for dataflow. */
1325 var->aux = first;
1326 first = var;
1329 /* The actual dataflow. */
1331 while (first != (void *) 1)
1333 cgraph_node *user, *orig_user, **f;
1335 var = first;
1336 first = (varpool_node *)first->aux;
1338 f = single_user_map.get (var);
1339 if (f)
1340 orig_user = *f;
1341 else
1342 orig_user = NULL;
1343 user = propagate_single_user (var, orig_user, single_user_map);
1345 gcc_checking_assert (var->aux != BOTTOM);
1347 /* If user differs, enqueue all references. */
1348 if (user != orig_user)
1350 unsigned int i;
1351 ipa_ref *ref;
1353 single_user_map.put (var, user);
1355 /* Enqueue all aliases for re-processing. */
1356 for (i = 0; var->iterate_direct_aliases (i, ref); i++)
1357 if (!ref->referring->aux)
1359 ref->referring->aux = first;
1360 first = dyn_cast <varpool_node *> (ref->referring);
1362 /* Enqueue all users for re-processing. */
1363 for (i = 0; var->iterate_reference (i, ref); i++)
1364 if (!ref->referred->aux
1365 && ref->referred->definition
1366 && is_a <varpool_node *> (ref->referred))
1368 ref->referred->aux = first;
1369 first = dyn_cast <varpool_node *> (ref->referred);
1372 /* If user is BOTTOM, just punt on this var. */
1373 if (user == BOTTOM)
1374 var->aux = BOTTOM;
1375 else
1376 var->aux = NULL;
1378 else
1379 var->aux = NULL;
1382 FOR_EACH_DEFINED_VARIABLE (var)
1384 if (var->aux != BOTTOM)
1386 /* Not having the single user known means that the VAR is
1387 unreachable. Either someone forgot to remove unreachable
1388 variables or the reachability here is wrong. */
1390 gcc_checking_assert (single_user_map.get (var));
1392 if (dump_file)
1394 fprintf (dump_file, "Variable %s/%i is used by single function\n",
1395 var->name (), var->order);
1397 var->used_by_single_function = true;
1399 var->aux = NULL;
1401 return 0;
1404 namespace {
1406 const pass_data pass_data_ipa_single_use =
1408 IPA_PASS, /* type */
1409 "single-use", /* name */
1410 OPTGROUP_NONE, /* optinfo_flags */
1411 TV_CGRAPHOPT, /* tv_id */
1412 0, /* properties_required */
1413 0, /* properties_provided */
1414 0, /* properties_destroyed */
1415 0, /* todo_flags_start */
1416 0, /* todo_flags_finish */
1419 class pass_ipa_single_use : public ipa_opt_pass_d
1421 public:
1422 pass_ipa_single_use (gcc::context *ctxt)
1423 : ipa_opt_pass_d (pass_data_ipa_single_use, ctxt,
1424 NULL, /* generate_summary */
1425 NULL, /* write_summary */
1426 NULL, /* read_summary */
1427 NULL, /* write_optimization_summary */
1428 NULL, /* read_optimization_summary */
1429 NULL, /* stmt_fixup */
1430 0, /* function_transform_todo_flags_start */
1431 NULL, /* function_transform */
1432 NULL) /* variable_transform */
1435 /* opt_pass methods: */
1436 virtual bool gate (function *);
1437 virtual unsigned int execute (function *) { return ipa_single_use (); }
1439 }; // class pass_ipa_single_use
1441 bool
1442 pass_ipa_single_use::gate (function *)
1444 return optimize;
1447 } // anon namespace
1449 ipa_opt_pass_d *
1450 make_pass_ipa_single_use (gcc::context *ctxt)
1452 return new pass_ipa_single_use (ctxt);
1455 /* Materialize all clones. */
1457 namespace {
1459 const pass_data pass_data_materialize_all_clones =
1461 SIMPLE_IPA_PASS, /* type */
1462 "materialize-all-clones", /* name */
1463 OPTGROUP_NONE, /* optinfo_flags */
1464 TV_IPA_OPT, /* tv_id */
1465 0, /* properties_required */
1466 0, /* properties_provided */
1467 0, /* properties_destroyed */
1468 0, /* todo_flags_start */
1469 0, /* todo_flags_finish */
1472 class pass_materialize_all_clones : public simple_ipa_opt_pass
1474 public:
1475 pass_materialize_all_clones (gcc::context *ctxt)
1476 : simple_ipa_opt_pass (pass_data_materialize_all_clones, ctxt)
1479 /* opt_pass methods: */
1480 virtual unsigned int execute (function *)
1482 symtab->materialize_all_clones ();
1483 return 0;
1486 }; // class pass_materialize_all_clones
1488 } // anon namespace
1490 simple_ipa_opt_pass *
1491 make_pass_materialize_all_clones (gcc::context *ctxt)
1493 return new pass_materialize_all_clones (ctxt);