1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Analysis used by the inliner and other passes limiting code size growth.
24 We estimate for each function
26 - average function execution time
27 - inlining size benefit (that is how much of function body size
28 and its call sequence is expected to disappear by inlining)
29 - inlining time benefit
32 - call statement size and time
34 inlinie_summary datastructures store above information locally (i.e.
35 parameters of the function itself) and globally (i.e. parameters of
36 the function created by applying all the inline decisions already
37 present in the callgraph).
39 We provide accestor to the inline_summary datastructure and
40 basic logic updating the parameters when inlining is performed.
42 The summaries are context sensitive. Context means
43 1) partial assignment of known constant values of operands
44 2) whether function is inlined into the call or not.
45 It is easy to add more variants. To represent function size and time
46 that depends on context (i.e. it is known to be optimized away when
47 context is known either by inlining or from IP-CP and clonning),
48 we use predicates. Predicates are logical formulas in
49 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
50 specifying what conditions must be true. Conditions are simple test
51 of the form described above.
53 In order to make predicate (possibly) true, all of its clauses must
54 be (possibly) true. To make clause (possibly) true, one of conditions
55 it mentions must be (possibly) true. There are fixed bounds on
56 number of clauses and conditions and all the manipulation functions
57 are conservative in positive direction. I.e. we may lose precision
58 by thinking that predicate may be true even when it is not.
60 estimate_edge_size and estimate_edge_growth can be used to query
61 function size/time in the given context. inline_merge_summary merges
62 properties of caller and callee after inlining.
64 Finally pass_inline_parameters is exported. This is used to drive
65 computation of function parameters used by the early inliner. IPA
66 inlined performs analysis via its analyze_function method. */
70 #include "coretypes.h"
73 #include "tree-inline.h"
74 #include "langhooks.h"
77 #include "diagnostic.h"
78 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
84 #include "tree-flow.h"
86 #include "lto-streamer.h"
87 #include "ipa-inline.h"
88 #include "alloc-pool.h"
90 /* Estimate runtime of function can easilly run into huge numbers with many
91 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE in integer.
92 For anything larger we use gcov_type. */
93 #define MAX_TIME 1000000
95 /* Number of bits in integer, but we really want to be stable across different
97 #define NUM_CONDITIONS 32
99 enum predicate_conditions
101 predicate_false_condition = 0,
102 predicate_not_inlined_condition = 1,
103 predicate_first_dynamic_condition = 2
106 /* Special condition code we use to represent test that operand is compile time
108 #define IS_NOT_CONSTANT ERROR_MARK
110 /* Holders of ipa cgraph hooks: */
111 static struct cgraph_node_hook_list *function_insertion_hook_holder;
112 static struct cgraph_node_hook_list *node_removal_hook_holder;
113 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
114 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
115 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
116 static void inline_node_removal_hook (struct cgraph_node *, void *);
117 static void inline_node_duplication_hook (struct cgraph_node *,
118 struct cgraph_node *, void *);
119 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
120 static void inline_edge_duplication_hook (struct cgraph_edge *,
121 struct cgraph_edge *,
124 /* VECtor holding inline summaries.
125 In GGC memory because conditions might point to constant trees. */
126 VEC(inline_summary_t,gc) *inline_summary_vec;
127 VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
129 /* Cached node/edge growths. */
130 VEC(int,heap) *node_growth_cache;
131 VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
133 /* Edge predicates goes here. */
134 static alloc_pool edge_predicate_pool;
136 /* Return true predicate (tautology).
137 We represent it by empty list of clauses. */
139 static inline struct predicate
140 true_predicate (void)
148 /* Return predicate testing single condition number COND. */
150 static inline struct predicate
151 single_cond_predicate (int cond)
154 p.clause[0]=1 << cond;
160 /* Return false predicate. First clause require false condition. */
162 static inline struct predicate
163 false_predicate (void)
165 return single_cond_predicate (predicate_false_condition);
169 /* Return true if P is (false). */
172 true_predicate_p (struct predicate *p)
174 return !p->clause[0];
178 /* Return true if P is (false). */
181 false_predicate_p (struct predicate *p)
183 if (p->clause[0] == (1 << predicate_false_condition))
185 gcc_checking_assert (!p->clause[1]
186 && p->clause[0] == 1 << predicate_false_condition);
193 /* Return predicate that is set true when function is not inlined. */
194 static inline struct predicate
195 not_inlined_predicate (void)
197 return single_cond_predicate (predicate_not_inlined_condition);
201 /* Add condition to condition list CONDS. */
203 static struct predicate
204 add_condition (struct inline_summary *summary, int operand_num,
205 enum tree_code code, tree val)
209 struct condition new_cond;
211 for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++)
213 if (c->operand_num == operand_num
216 return single_cond_predicate (i + predicate_first_dynamic_condition);
218 /* Too many conditions. Give up and return constant true. */
219 if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
220 return true_predicate ();
222 new_cond.operand_num = operand_num;
223 new_cond.code = code;
225 VEC_safe_push (condition, gc, summary->conds, &new_cond);
226 return single_cond_predicate (i + predicate_first_dynamic_condition);
230 /* Add clause CLAUSE into the predicate P. */
233 add_clause (struct predicate *p, clause_t clause)
237 int insert_here = -1;
243 /* False clause makes the whole predicate false. Kill the other variants. */
244 if (clause == (1 << predicate_false_condition))
246 p->clause[0] = (1 << predicate_false_condition);
250 if (false_predicate_p (p))
253 /* No one should be sily enough to add false into nontrivial clauses. */
254 gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
256 /* Look where to insert the clause. At the same time prune out
257 clauses of P that are implied by the new clause and thus
259 for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
261 p->clause[i2] = p->clause[i];
266 /* If p->clause[i] implies clause, there is nothing to add. */
267 if ((p->clause[i] & clause) == p->clause[i])
269 /* We had nothing to add, none of clauses should've become redundant. */
270 gcc_checking_assert (i == i2);
274 if (p->clause[i] < clause && insert_here < 0)
277 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
278 Otherwise the p->clause[i] has to stay. */
279 if ((p->clause[i] & clause) != clause)
282 /* We run out of variants. Be conservative in positive direction. */
283 if (i2 == MAX_CLAUSES)
285 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
286 p->clause[i2 + 1] = 0;
287 if (insert_here >= 0)
288 for (;i2 > insert_here; i2--)
289 p->clause[i2] = p->clause[i2 - 1];
292 p->clause[insert_here] = clause;
298 static struct predicate
299 and_predicates (struct predicate *p, struct predicate *p2)
301 struct predicate out = *p;
304 /* Avoid busy work. */
305 if (false_predicate_p (p2) || true_predicate_p (p))
307 if (false_predicate_p (p) || true_predicate_p (p2))
310 /* See how far predicates match. */
311 for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
313 gcc_checking_assert (i < MAX_CLAUSES);
316 /* Combine the predicates rest. */
317 for (; p2->clause[i]; i++)
319 gcc_checking_assert (i < MAX_CLAUSES);
320 add_clause (&out, p2->clause[i]);
326 /* Return true if predicates are obviously equal. */
329 predicates_equal_p (struct predicate *p, struct predicate *p2)
332 for (i = 0; p->clause[i]; i++)
334 gcc_checking_assert (i < MAX_CLAUSES);
335 gcc_checking_assert (p->clause [i] > p->clause[i + 1]);
336 gcc_checking_assert (!p2->clause[i] || p2->clause [i] > p2->clause[i + 1]);
337 if (p->clause[i] != p2->clause[i])
340 return !p2->clause[i];
346 static struct predicate
347 or_predicates (struct predicate *p, struct predicate *p2)
349 struct predicate out = true_predicate ();
352 /* Avoid busy work. */
353 if (false_predicate_p (p2) || true_predicate_p (p))
355 if (false_predicate_p (p) || true_predicate_p (p2))
357 if (predicates_equal_p (p, p2))
360 /* OK, combine the predicates. */
361 for (i = 0; p->clause[i]; i++)
362 for (j = 0; p2->clause[j]; j++)
364 gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
365 add_clause (&out, p->clause[i] | p2->clause[j]);
371 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
375 evaluate_predicate (struct predicate *p, clause_t possible_truths)
379 /* True remains true. */
380 if (true_predicate_p (p))
383 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
385 /* See if we can find clause we can disprove. */
386 for (i = 0; p->clause[i]; i++)
388 gcc_checking_assert (i < MAX_CLAUSES);
389 if (!(p->clause[i] & possible_truths))
396 /* Dump conditional COND. */
399 dump_condition (FILE *f, conditions conditions, int cond)
402 if (cond == predicate_false_condition)
403 fprintf (f, "false");
404 else if (cond == predicate_not_inlined_condition)
405 fprintf (f, "not inlined");
408 c = VEC_index (condition, conditions, cond - predicate_first_dynamic_condition);
409 fprintf (f, "op%i", c->operand_num);
410 if (c->code == IS_NOT_CONSTANT)
412 fprintf (f, " not constant");
415 fprintf (f, " %s ", op_symbol_code (c->code));
416 print_generic_expr (f, c->val, 1);
421 /* Dump clause CLAUSE. */
424 dump_clause (FILE *f, conditions conds, clause_t clause)
431 for (i = 0; i < NUM_CONDITIONS; i++)
432 if (clause & (1 << i))
437 dump_condition (f, conds, i);
443 /* Dump predicate PREDICATE. */
446 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
449 if (true_predicate_p (pred))
450 dump_clause (f, conds, 0);
452 for (i = 0; pred->clause[i]; i++)
456 dump_clause (f, conds, pred->clause[i]);
462 /* Record SIZE and TIME under condition PRED into the inline summary. */
465 account_size_time (struct inline_summary *summary, int size, int time, struct predicate *pred)
471 if (false_predicate_p (pred))
474 /* We need to create initial empty unconitional clause, but otherwie
475 we don't need to account empty times and sizes. */
476 if (!size && !time && summary->conds)
479 /* Watch overflow that might result from insane profiles. */
480 if (time > MAX_TIME * INLINE_TIME_SCALE)
481 time = MAX_TIME * INLINE_TIME_SCALE;
482 gcc_assert (time >= 0);
484 for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
485 if (predicates_equal_p (&e->predicate, pred))
494 e = VEC_index (size_time_entry, summary->entry, 0);
495 gcc_assert (!e->predicate.clause[0]);
497 if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
499 fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
500 ((double)size) / INLINE_SIZE_SCALE, ((double)time) / INLINE_TIME_SCALE,
501 found ? "" : "new ");
502 dump_predicate (dump_file, summary->conds, pred);
506 struct size_time_entry new_entry;
507 new_entry.size = size;
508 new_entry.time = time;
509 new_entry.predicate = *pred;
510 VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry);
516 if (e->time > MAX_TIME * INLINE_TIME_SCALE)
517 e->time = MAX_TIME * INLINE_TIME_SCALE;
521 /* Set predicate for edge E. */
524 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
526 struct inline_edge_summary *es = inline_edge_summary (e);
527 if (predicate && !true_predicate_p (predicate))
530 es->predicate = (struct predicate *)pool_alloc (edge_predicate_pool);
531 *es->predicate = *predicate;
536 pool_free (edge_predicate_pool, es->predicate);
537 es->predicate = NULL;
542 /* Work out what conditions might be true at invocation of E. */
545 evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
547 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
548 struct inline_summary *info = inline_summary (e->callee);
551 if (ipa_node_params_vector && info->conds
552 /* FIXME: it seems that we forget to get argument count in some cases,
553 probaby for previously indirect edges or so. */
554 && ipa_get_cs_argument_count (IPA_EDGE_REF (e)))
556 struct ipa_node_params *parms_info;
557 struct ipa_edge_args *args = IPA_EDGE_REF (e);
558 int i, count = ipa_get_cs_argument_count (args);
559 struct ipcp_lattice lat;
561 VEC (tree, heap) *known_vals = NULL;
563 if (e->caller->global.inlined_to)
564 parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
566 parms_info = IPA_NODE_REF (e->caller);
568 VEC_safe_grow_cleared (tree, heap, known_vals, count);
569 for (i = 0; i < count; i++)
571 ipa_lattice_from_jfunc (parms_info, &lat, ipa_get_ith_jump_func (args, i));
572 if (lat.type == IPA_CONST_VALUE)
573 VEC_replace (tree, known_vals, i, lat.constant);
575 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
577 tree val = VEC_index (tree, known_vals, c->operand_num);
582 clause |= 1 << (i + predicate_first_dynamic_condition);
585 if (c->code == IS_NOT_CONSTANT)
587 res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
589 && integer_zerop (res))
591 clause |= 1 << (i + predicate_first_dynamic_condition);
593 VEC_free (tree, heap, known_vals);
596 for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
597 clause |= 1 << (i + predicate_first_dynamic_condition);
603 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
606 inline_summary_alloc (void)
608 if (!node_removal_hook_holder)
609 node_removal_hook_holder =
610 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
611 if (!edge_removal_hook_holder)
612 edge_removal_hook_holder =
613 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
614 if (!node_duplication_hook_holder)
615 node_duplication_hook_holder =
616 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
617 if (!edge_duplication_hook_holder)
618 edge_duplication_hook_holder =
619 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
621 if (VEC_length (inline_summary_t, inline_summary_vec)
622 <= (unsigned) cgraph_max_uid)
623 VEC_safe_grow_cleared (inline_summary_t, gc,
624 inline_summary_vec, cgraph_max_uid + 1);
625 if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec)
626 <= (unsigned) cgraph_edge_max_uid)
627 VEC_safe_grow_cleared (inline_edge_summary_t, heap,
628 inline_edge_summary_vec, cgraph_edge_max_uid + 1);
629 if (!edge_predicate_pool)
630 edge_predicate_pool = create_alloc_pool ("edge predicates", sizeof (struct predicate),
634 /* Hook that is called by cgraph.c when a node is removed. */
637 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
639 struct inline_summary *info;
640 if (VEC_length (inline_summary_t, inline_summary_vec)
641 <= (unsigned)node->uid)
643 info = inline_summary (node);
644 reset_node_growth_cache (node);
645 VEC_free (condition, gc, info->conds);
646 VEC_free (size_time_entry, gc, info->entry);
649 memset (info, 0, sizeof (inline_summary_t));
653 /* Hook that is called by cgraph.c when a node is duplicated. */
656 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
657 ATTRIBUTE_UNUSED void *data)
659 struct inline_summary *info;
660 inline_summary_alloc ();
661 info = inline_summary (dst);
662 memcpy (info, inline_summary (src),
663 sizeof (struct inline_summary));
664 info->conds = VEC_copy (condition, gc, info->conds);
665 info->entry = VEC_copy (size_time_entry, gc, info->entry);
669 /* Hook that is called by cgraph.c when a node is duplicated. */
672 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
673 ATTRIBUTE_UNUSED void *data)
675 struct inline_edge_summary *info;
676 struct inline_edge_summary *srcinfo;
677 inline_summary_alloc ();
678 info = inline_edge_summary (dst);
679 srcinfo = inline_edge_summary (src);
680 memcpy (info, srcinfo,
681 sizeof (struct inline_edge_summary));
682 info->predicate = NULL;
683 edge_set_predicate (dst, srcinfo->predicate);
687 /* Keep edge cache consistent across edge removal. */
690 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
692 if (edge_growth_cache)
693 reset_edge_growth_cache (edge);
694 if (edge->uid < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec))
696 edge_set_predicate (edge, NULL);
697 memset (inline_edge_summary (edge), 0, sizeof (struct inline_edge_summary));
702 /* Initialize growth caches. */
705 initialize_growth_caches (void)
707 if (cgraph_edge_max_uid)
708 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
709 cgraph_edge_max_uid);
711 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
715 /* Free growth caches. */
718 free_growth_caches (void)
720 VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
721 edge_growth_cache = 0;
722 VEC_free (int, heap, node_growth_cache);
723 node_growth_cache = 0;
727 /* Dump edge summaries associated to NODE and recursively to all clones.
731 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node,
732 struct inline_summary *info)
734 struct cgraph_edge *edge;
735 for (edge = node->callees; edge; edge = edge->next_callee)
737 struct inline_edge_summary *es = inline_edge_summary (edge);
738 fprintf (f, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
739 indent, "", cgraph_node_name (edge->callee),
741 !edge->inline_failed ? "inlined"
742 : cgraph_inline_failed_string (edge->inline_failed),
748 (int)inline_summary (edge->callee)->size,
749 (int)inline_summary (edge->callee)->estimated_stack_size);
752 fprintf (f, " predicate: ");
753 dump_predicate (f, info->conds, es->predicate);
757 if (!edge->inline_failed)
759 fprintf (f, "%*sStack frame offset %i, callee self size %i, callee size %i\n",
761 (int)inline_summary (edge->callee)->stack_frame_offset,
762 (int)inline_summary (edge->callee)->estimated_self_stack_size,
763 (int)inline_summary (edge->callee)->estimated_stack_size);
764 dump_inline_edge_summary (f, indent+2, edge->callee, info);
767 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
769 struct inline_edge_summary *es = inline_edge_summary (edge);
770 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i time: %2i\n",
778 fprintf (f, "predicate: ");
779 dump_predicate (f, info->conds, es->predicate);
788 dump_inline_summary (FILE * f, struct cgraph_node *node)
792 struct inline_summary *s = inline_summary (node);
795 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
797 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
798 fprintf (f, " always_inline");
800 fprintf (f, " inlinable");
802 fprintf (f, " versionable");
803 fprintf (f, "\n self time: %i\n",
805 fprintf (f, " global time: %i\n", s->time);
806 fprintf (f, " self size: %i\n",
808 fprintf (f, " global size: %i\n", s->size);
809 fprintf (f, " self stack: %i\n",
810 (int) s->estimated_self_stack_size);
811 fprintf (f, " global stack: %i\n",
812 (int) s->estimated_stack_size);
814 VEC_iterate (size_time_entry, s->entry, i, e);
817 fprintf (f, " size:%f, time:%f, predicate:",
818 (double) e->size / INLINE_SIZE_SCALE,
819 (double) e->time / INLINE_TIME_SCALE);
820 dump_predicate (f, s->conds, &e->predicate);
822 fprintf (f, " calls:\n");
823 dump_inline_edge_summary (f, 4, node, s);
829 debug_inline_summary (struct cgraph_node *node)
831 dump_inline_summary (stderr, node);
835 dump_inline_summaries (FILE *f)
837 struct cgraph_node *node;
839 for (node = cgraph_nodes; node; node = node->next)
840 if (node->analyzed && !node->global.inlined_to)
841 dump_inline_summary (f, node);
844 /* Give initial reasons why inlining would fail on EDGE. This gets either
845 nullified or usually overwritten by more precise reasons later. */
848 initialize_inline_failed (struct cgraph_edge *e)
850 struct cgraph_node *callee = e->callee;
852 if (e->indirect_unknown_callee)
853 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
854 else if (!callee->analyzed)
855 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
856 else if (callee->local.redefined_extern_inline)
857 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
858 else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
859 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
861 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
864 /* See if statement might disappear after inlining.
865 0 - means not eliminated
866 1 - half of statements goes away
867 2 - for sure it is eliminated.
868 We are not terribly sophisticated, basically looking for simple abstraction
872 eliminated_by_inlining_prob (gimple stmt)
874 enum gimple_code code = gimple_code (stmt);
880 if (gimple_num_ops (stmt) != 2)
883 /* Casts of parameters, loads from parameters passed by reference
884 and stores to return value or parameters are often free after
885 inlining dua to SRA and further combining.
886 Assume that half of statements goes away. */
887 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
888 || gimple_assign_rhs_code (stmt) == NOP_EXPR
889 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
890 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
892 tree rhs = gimple_assign_rhs1 (stmt);
893 tree lhs = gimple_assign_lhs (stmt);
894 tree inner_rhs = rhs;
895 tree inner_lhs = lhs;
896 bool rhs_free = false;
897 bool lhs_free = false;
899 while (handled_component_p (inner_lhs)
900 || TREE_CODE (inner_lhs) == MEM_REF)
901 inner_lhs = TREE_OPERAND (inner_lhs, 0);
902 while (handled_component_p (inner_rhs)
903 || TREE_CODE (inner_rhs) == ADDR_EXPR
904 || TREE_CODE (inner_rhs) == MEM_REF)
905 inner_rhs = TREE_OPERAND (inner_rhs, 0);
908 if (TREE_CODE (inner_rhs) == PARM_DECL
909 || (TREE_CODE (inner_rhs) == SSA_NAME
910 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
911 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
913 if (rhs_free && is_gimple_reg (lhs))
915 if (((TREE_CODE (inner_lhs) == PARM_DECL
916 || (TREE_CODE (inner_lhs) == SSA_NAME
917 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
918 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
920 || TREE_CODE (inner_lhs) == RESULT_DECL
921 || (TREE_CODE (inner_lhs) == SSA_NAME
922 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
925 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
927 if (lhs_free && rhs_free)
937 /* If BB ends by a conditional we can turn into predicates, attach corresponding
938 predicates to the CFG edges. */
941 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
942 struct inline_summary *summary,
948 enum tree_code code, inverted_code;
954 last = last_stmt (bb);
956 || gimple_code (last) != GIMPLE_COND)
958 if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
960 op = gimple_cond_lhs (last);
961 /* TODO: handle conditionals like
964 if (TREE_CODE (op) != SSA_NAME)
966 if (SSA_NAME_IS_DEFAULT_DEF (op))
968 index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
971 code = gimple_cond_code (last);
972 inverted_code = invert_tree_comparison (code,
973 HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
975 FOR_EACH_EDGE (e, ei, bb->succs)
977 struct predicate p = add_condition (summary,
979 e->flags & EDGE_TRUE_VALUE
980 ? code : inverted_code,
981 gimple_cond_rhs (last));
982 e->aux = pool_alloc (edge_predicate_pool);
983 *(struct predicate *)e->aux = p;
988 if (builtin_constant_p (op))
992 Here we can predicate nonconstant_code. We can't
993 really handle constant_code since we have no predicate
994 for this and also the constant code is not known to be
995 optimized away when inliner doen't see operand is constant.
996 Other optimizers might think otherwise. */
997 set_stmt = SSA_NAME_DEF_STMT (op);
998 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
999 || gimple_call_num_args (set_stmt) != 1)
1001 op2 = gimple_call_arg (set_stmt, 0);
1002 if (!SSA_NAME_IS_DEFAULT_DEF (op2))
1004 index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op2));
1007 if (gimple_cond_code (last) != NE_EXPR
1008 || !integer_zerop (gimple_cond_rhs (last)))
1010 FOR_EACH_EDGE (e, ei, bb->succs)
1011 if (e->flags & EDGE_FALSE_VALUE)
1013 struct predicate p = add_condition (summary,
1017 e->aux = pool_alloc (edge_predicate_pool);
1018 *(struct predicate *)e->aux = p;
1023 /* If BB ends by a switch we can turn into predicates, attach corresponding
1024 predicates to the CFG edges. */
1027 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1028 struct inline_summary *summary,
1039 last = last_stmt (bb);
1041 || gimple_code (last) != GIMPLE_SWITCH)
1043 op = gimple_switch_index (last);
1044 if (TREE_CODE (op) != SSA_NAME
1045 || !SSA_NAME_IS_DEFAULT_DEF (op))
1047 index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
1051 FOR_EACH_EDGE (e, ei, bb->succs)
1053 e->aux = pool_alloc (edge_predicate_pool);
1054 *(struct predicate *)e->aux = false_predicate ();
1056 n = gimple_switch_num_labels(last);
1057 for (case_idx = 0; case_idx < n; ++case_idx)
1059 tree cl = gimple_switch_label (last, case_idx);
1063 e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1064 min = CASE_LOW (cl);
1065 max = CASE_HIGH (cl);
1067 /* For default we might want to construct predicate that none
1068 of cases is met, but it is bit hard to do not having negations
1069 of conditionals handy. */
1071 p = true_predicate ();
1073 p = add_condition (summary, index,
1078 struct predicate p1, p2;
1079 p1 = add_condition (summary, index,
1082 p2 = add_condition (summary, index,
1085 p = and_predicates (&p1, &p2);
1087 *(struct predicate *)e->aux
1088 = or_predicates (&p, (struct predicate *)e->aux);
1093 /* For each BB in NODE attach to its AUX pointer predicate under
1094 which it is executable. */
1097 compute_bb_predicates (struct cgraph_node *node,
1098 struct ipa_node_params *parms_info,
1099 struct inline_summary *summary)
1101 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1105 FOR_EACH_BB_FN (bb, my_function)
1107 set_cond_stmt_execution_predicate (parms_info, summary, bb);
1108 set_switch_stmt_execution_predicate (parms_info, summary, bb);
1111 /* Entry block is always executable. */
1112 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux = pool_alloc (edge_predicate_pool);
1113 *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1114 = true_predicate ();
1116 /* A simple dataflow propagation of predicates forward in the CFG.
1117 TODO: work in reverse postorder. */
1121 FOR_EACH_BB_FN (bb, my_function)
1123 struct predicate p = false_predicate ();
1126 FOR_EACH_EDGE (e, ei, bb->preds)
1130 struct predicate this_bb_predicate = *(struct predicate *)e->src->aux;
1132 this_bb_predicate = and_predicates (&this_bb_predicate,
1133 (struct predicate *)e->aux);
1134 p = or_predicates (&p, &this_bb_predicate);
1135 if (true_predicate_p (&p))
1139 if (false_predicate_p (&p))
1140 gcc_assert (!bb->aux);
1146 bb->aux = pool_alloc (edge_predicate_pool);
1147 *((struct predicate *)bb->aux) = p;
1149 else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
1152 *((struct predicate *)bb->aux) = p;
1160 /* We keep info about constantness of SSA names. */
1162 typedef struct predicate predicate_t;
1163 DEF_VEC_O (predicate_t);
1164 DEF_VEC_ALLOC_O (predicate_t, heap);
1167 /* Return predicate specifying when the STMT might have result that is not a compile
1170 static struct predicate
1171 will_be_nonconstant_predicate (struct ipa_node_params *info,
1172 struct inline_summary *summary,
1174 VEC (predicate_t, heap) *nonconstant_names)
1177 struct predicate p = true_predicate ();
1180 struct predicate op_non_const;
1182 /* What statments might be optimized away
1183 when their arguments are constant
1184 TODO: also trivial builtins.
1185 builtin_constant_p is already handled later. */
1186 if (gimple_code (stmt) != GIMPLE_ASSIGN
1187 && gimple_code (stmt) != GIMPLE_COND
1188 && gimple_code (stmt) != GIMPLE_SWITCH)
1191 /* Stores and loads will stay anyway.
1192 TODO: Constant memory accesses could be handled here, too. */
1193 if (gimple_vuse (stmt))
1196 /* See if we understand all operands before we start
1197 adding conditionals. */
1198 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1200 if (TREE_CODE (use) != SSA_NAME)
1202 /* For arguments we can build a condition. */
1203 if (SSA_NAME_IS_DEFAULT_DEF (use)
1204 && ipa_get_param_decl_index (info, SSA_NAME_VAR (use)) >= 0)
1206 /* If we know when operand is constant,
1207 we still can say something useful. */
1208 if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names,
1209 SSA_NAME_VERSION (use))))
1213 op_non_const = false_predicate ();
1214 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1216 if (SSA_NAME_IS_DEFAULT_DEF (use)
1217 && ipa_get_param_decl_index (info, SSA_NAME_VAR (use)) >= 0)
1218 p = add_condition (summary,
1219 ipa_get_param_decl_index (info, SSA_NAME_VAR (use)),
1220 IS_NOT_CONSTANT, NULL);
1222 p = *VEC_index (predicate_t, nonconstant_names,
1223 SSA_NAME_VERSION (use));
1224 op_non_const = or_predicates (&p, &op_non_const);
1226 if (gimple_code (stmt) == GIMPLE_ASSIGN
1227 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
1228 VEC_replace (predicate_t, nonconstant_names,
1229 SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const);
1230 return op_non_const;
1234 /* Compute function body size parameters for NODE.
1235 When EARLY is true, we compute only simple summaries without
1236 non-trivial predicates to drive the early inliner. */
1239 estimate_function_body_sizes (struct cgraph_node *node, bool early)
1242 /* Estimate static overhead for function prologue/epilogue and alignment. */
1244 /* Benefits are scaled by probability of elimination that is in range
1247 gimple_stmt_iterator bsi;
1248 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1250 struct inline_summary *info = inline_summary (node);
1251 struct predicate bb_predicate;
1252 struct ipa_node_params *parms_info = NULL;
1253 VEC (predicate_t, heap) *nonconstant_names = NULL;
1255 if (ipa_node_params_vector && !early && optimize)
1257 parms_info = IPA_NODE_REF (node);
1258 VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names,
1259 VEC_length (tree, SSANAMES (my_function)));
1267 fprintf (dump_file, "\nAnalyzing function body size: %s\n",
1268 cgraph_node_name (node));
1270 /* When we run into maximal number of entries, we assign everything to the
1271 constant truth case. Be sure to have it in list. */
1272 bb_predicate = true_predicate ();
1273 account_size_time (info, 0, 0, &bb_predicate);
1275 bb_predicate = not_inlined_predicate ();
1276 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
1278 gcc_assert (my_function && my_function->cfg);
1280 compute_bb_predicates (node, parms_info, info);
1281 FOR_EACH_BB_FN (bb, my_function)
1283 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1285 /* TODO: Obviously predicates can be propagated down across CFG. */
1289 bb_predicate = *(struct predicate *)bb->aux;
1291 bb_predicate = false_predicate ();
1294 bb_predicate = true_predicate ();
1296 if (dump_file && (dump_flags & TDF_DETAILS))
1298 fprintf (dump_file, "\n BB %i predicate:", bb->index);
1299 dump_predicate (dump_file, info->conds, &bb_predicate);
1302 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1304 gimple stmt = gsi_stmt (bsi);
1305 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1306 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1308 struct predicate will_be_nonconstant;
1310 if (dump_file && (dump_flags & TDF_DETAILS))
1312 fprintf (dump_file, " ");
1313 print_gimple_stmt (dump_file, stmt, 0, 0);
1314 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1315 ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
1318 if (is_gimple_call (stmt))
1320 struct cgraph_edge *edge = cgraph_edge (node, stmt);
1321 struct inline_edge_summary *es = inline_edge_summary (edge);
1323 /* Special case: results of BUILT_IN_CONSTANT_P will be always
1324 resolved as constant. We however don't want to optimize
1325 out the cgraph edges. */
1326 if (nonconstant_names
1327 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
1328 && gimple_call_lhs (stmt)
1329 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
1331 struct predicate false_p = false_predicate ();
1332 VEC_replace (predicate_t, nonconstant_names,
1333 SSA_NAME_VERSION (gimple_call_lhs (stmt)), &false_p);
1336 es->call_stmt_size = this_size;
1337 es->call_stmt_time = this_time;
1338 es->loop_depth = bb->loop_depth;
1339 edge_set_predicate (edge, &bb_predicate);
1341 /* Do not inline calls where we cannot triviall work around
1342 mismatches in argument or return types. */
1344 && !gimple_check_call_matching_types (stmt, edge->callee->decl))
1346 edge->call_stmt_cannot_inline_p = true;
1347 gimple_call_set_cannot_inline (stmt, true);
1350 gcc_assert (!gimple_call_cannot_inline_p (stmt));
1353 /* TODO: When conditional jump or swithc is known to be constant, but
1354 we did not translate it into the predicates, we really can account
1355 just maximum of the possible paths. */
1358 = will_be_nonconstant_predicate (parms_info, info,
1359 stmt, nonconstant_names);
1360 if (this_time || this_size)
1368 prob = eliminated_by_inlining_prob (stmt);
1369 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
1370 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
1371 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
1372 fprintf (dump_file, "\t\twill eliminated by inlining\n");
1375 p = and_predicates (&bb_predicate, &will_be_nonconstant);
1377 p = true_predicate ();
1379 /* We account everything but the calls. Calls have their own
1380 size/time info attached to cgraph edges. This is neccesary
1381 in order to make the cost disappear after inlining. */
1382 if (!is_gimple_call (stmt))
1386 struct predicate ip = not_inlined_predicate ();
1387 ip = and_predicates (&ip, &p);
1388 account_size_time (info, this_size * prob,
1389 this_time * prob, &ip);
1392 account_size_time (info, this_size * (2 - prob),
1393 this_time * (2 - prob), &p);
1396 gcc_assert (time >= 0);
1397 gcc_assert (size >= 0);
1401 FOR_ALL_BB_FN (bb, my_function)
1407 pool_free (edge_predicate_pool, bb->aux);
1409 FOR_EACH_EDGE (e, ei, bb->succs)
1412 pool_free (edge_predicate_pool, e->aux);
1416 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1417 if (time > MAX_TIME)
1419 inline_summary (node)->self_time = time;
1420 inline_summary (node)->self_size = size;
1421 VEC_free (predicate_t, heap, nonconstant_names);
1424 fprintf (dump_file, "\n");
1425 dump_inline_summary (dump_file, node);
1430 /* Compute parameters of functions used by inliner.
1431 EARLY is true when we compute parameters for the early inliner */
1434 compute_inline_parameters (struct cgraph_node *node, bool early)
1436 HOST_WIDE_INT self_stack_size;
1437 struct cgraph_edge *e;
1438 struct inline_summary *info;
1440 gcc_assert (!node->global.inlined_to);
1442 inline_summary_alloc ();
1444 info = inline_summary (node);
1446 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
1447 Once this happen, we will need to more curefully predict call
1449 if (node->thunk.thunk_p)
1451 struct inline_edge_summary *es = inline_edge_summary (node->callees);
1452 struct predicate t = true_predicate ();
1454 info->inlinable = info->versionable = 0;
1455 node->callees->call_stmt_cannot_inline_p = true;
1456 node->local.can_change_signature = false;
1457 es->call_stmt_time = 1;
1458 es->call_stmt_size = 1;
1459 account_size_time (info, 0, 0, &t);
1463 /* Estimate the stack size for the function if we're optimizing. */
1464 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
1465 info->estimated_self_stack_size = self_stack_size;
1466 info->estimated_stack_size = self_stack_size;
1467 info->stack_frame_offset = 0;
1469 /* Can this function be inlined at all? */
1470 info->inlinable = tree_inlinable_function_p (node->decl);
1472 /* Inlinable functions always can change signature. */
1473 if (info->inlinable)
1474 node->local.can_change_signature = true;
1477 /* Functions calling builtin_apply can not change signature. */
1478 for (e = node->callees; e; e = e->next_callee)
1479 if (DECL_BUILT_IN (e->callee->decl)
1480 && DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
1481 && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_APPLY_ARGS)
1483 node->local.can_change_signature = !e;
1485 estimate_function_body_sizes (node, early);
1487 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1488 info->time = info->self_time;
1489 info->size = info->self_size;
1490 info->stack_frame_offset = 0;
1491 info->estimated_stack_size = info->estimated_self_stack_size;
1495 /* Compute parameters of functions used by inliner using
1496 current_function_decl. */
1499 compute_inline_parameters_for_current (void)
1501 compute_inline_parameters (cgraph_get_node (current_function_decl), true);
1505 struct gimple_opt_pass pass_inline_parameters =
1509 "inline_param", /* name */
1511 compute_inline_parameters_for_current,/* execute */
1514 0, /* static_pass_number */
1515 TV_INLINE_HEURISTICS, /* tv_id */
1516 0, /* properties_required */
1517 0, /* properties_provided */
1518 0, /* properties_destroyed */
1519 0, /* todo_flags_start */
1520 0 /* todo_flags_finish */
1525 /* Increase SIZE and TIME for size and time needed to handle edge E. */
1528 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time)
1530 struct inline_edge_summary *es = inline_edge_summary (e);
1531 *size += es->call_stmt_size * INLINE_SIZE_SCALE;
1532 *time += (es->call_stmt_time
1533 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
1534 if (*time > MAX_TIME * INLINE_TIME_SCALE)
1535 *time = MAX_TIME * INLINE_TIME_SCALE;
1539 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */
1542 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
1543 clause_t possible_truths)
1545 struct cgraph_edge *e;
1546 for (e = node->callees; e; e = e->next_callee)
1548 struct inline_edge_summary *es = inline_edge_summary (e);
1549 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1551 if (e->inline_failed)
1552 estimate_edge_size_and_time (e, size, time);
1554 estimate_calls_size_and_time (e->callee, size, time,
1558 /* TODO: look for devirtualizing oppurtunities. */
1559 for (e = node->indirect_calls; e; e = e->next_callee)
1561 struct inline_edge_summary *es = inline_edge_summary (e);
1562 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1563 estimate_edge_size_and_time (e, size, time);
1568 /* Estimate size and time needed to execute callee of EDGE assuming
1569 that parameters known to be constant at caller of EDGE are
1570 propagated. If INLINE_P is true, it is assumed that call will
1574 estimate_callee_size_and_time (struct cgraph_edge *edge, bool inline_p,
1575 int *ret_size, int *ret_time)
1577 struct inline_summary *info = inline_summary (edge->callee);
1578 clause_t clause = evaluate_conditions_for_edge (edge, inline_p);
1580 int size = 0, time = 0;
1584 && (dump_flags & TDF_DETAILS))
1587 fprintf (dump_file, " Estimating callee body: %s/%i\n"
1588 " Known to be false: ",
1589 cgraph_node_name (edge->callee),
1592 for (i = predicate_not_inlined_condition;
1593 i < (predicate_first_dynamic_condition
1594 + (int)VEC_length (condition, info->conds)); i++)
1595 if (!(clause & (1 << i)))
1598 fprintf (dump_file, ", ");
1600 dump_condition (dump_file, info->conds, i);
1604 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1605 if (evaluate_predicate (&e->predicate, clause))
1606 time += e->time, size += e->size;
1608 if (time > MAX_TIME * INLINE_TIME_SCALE)
1609 time = MAX_TIME * INLINE_TIME_SCALE;
1611 estimate_calls_size_and_time (edge->callee, &size, &time, clause);
1612 time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1613 size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1617 && (dump_flags & TDF_DETAILS))
1618 fprintf (dump_file, "\n size:%i time:%i\n", size, time);
1627 /* Translate all conditions from callee representation into caller representation and
1628 symbolically evaluate predicate P into new predicate.
1630 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO is summary
1631 of function predicate P is from. OPERAND_MAP is array giving callee formal IDs the
1632 caller formal IDs. POSSSIBLE_TRUTHS is clausule of all callee conditions that
1633 may be true in caller context. TOPLEV_PREDICATE is predicate under which callee
1636 static struct predicate
1637 remap_predicate (struct inline_summary *info, struct inline_summary *callee_info,
1638 struct predicate *p,
1639 VEC (int, heap) *operand_map,
1640 clause_t possible_truths,
1641 struct predicate *toplev_predicate)
1644 struct predicate out = true_predicate ();
1646 /* True predicate is easy. */
1647 if (true_predicate_p (p))
1648 return *toplev_predicate;
1649 for (i = 0; p->clause[i]; i++)
1651 clause_t clause = p->clause[i];
1653 struct predicate clause_predicate = false_predicate ();
1655 gcc_assert (i < MAX_CLAUSES);
1657 for (cond = 0; cond < NUM_CONDITIONS; cond ++)
1658 /* Do we have condition we can't disprove? */
1659 if (clause & possible_truths & (1 << cond))
1661 struct predicate cond_predicate;
1662 /* Work out if the condition can translate to predicate in the
1663 inlined function. */
1664 if (cond >= predicate_first_dynamic_condition)
1666 struct condition *c;
1668 c = VEC_index (condition, callee_info->conds,
1669 cond - predicate_first_dynamic_condition);
1670 /* See if we can remap condition operand to caller's operand.
1671 Otherwise give up. */
1673 || VEC_index (int, operand_map, c->operand_num) == -1)
1674 cond_predicate = true_predicate ();
1676 cond_predicate = add_condition (info,
1677 VEC_index (int, operand_map,
1681 /* Fixed conditions remains same, construct single
1682 condition predicate. */
1685 cond_predicate.clause[0] = 1 << cond;
1686 cond_predicate.clause[1] = 0;
1688 clause_predicate = or_predicates (&clause_predicate, &cond_predicate);
1690 out = and_predicates (&out, &clause_predicate);
1692 return and_predicates (&out, toplev_predicate);
1696 /* Update summary information of inline clones after inlining.
1697 Compute peak stack usage. */
1700 inline_update_callee_summaries (struct cgraph_node *node,
1703 struct cgraph_edge *e;
1704 struct inline_summary *callee_info = inline_summary (node);
1705 struct inline_summary *caller_info = inline_summary (node->callers->caller);
1708 callee_info->stack_frame_offset
1709 = caller_info->stack_frame_offset
1710 + caller_info->estimated_self_stack_size;
1711 peak = callee_info->stack_frame_offset
1712 + callee_info->estimated_self_stack_size;
1713 if (inline_summary (node->global.inlined_to)->estimated_stack_size
1715 inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
1716 cgraph_propagate_frequency (node);
1717 for (e = node->callees; e; e = e->next_callee)
1719 if (!e->inline_failed)
1720 inline_update_callee_summaries (e->callee, depth);
1721 inline_edge_summary (e)->loop_depth += depth;
1723 for (e = node->indirect_calls; e; e = e->next_callee)
1724 inline_edge_summary (e)->loop_depth += depth;
1728 /* Remap predicates of callees of NODE. Rest of arguments match
1732 remap_edge_predicates (struct cgraph_node *node,
1733 struct inline_summary *info,
1734 struct inline_summary *callee_info,
1735 VEC (int, heap) *operand_map,
1736 clause_t possible_truths,
1737 struct predicate *toplev_predicate)
1739 struct cgraph_edge *e;
1740 for (e = node->callees; e; e = e->next_callee)
1742 struct inline_edge_summary *es = inline_edge_summary (e);
1746 p = remap_predicate (info, callee_info,
1747 es->predicate, operand_map, possible_truths,
1749 edge_set_predicate (e, &p);
1750 /* TODO: We should remove the edge for code that will be optimized out,
1751 but we need to keep verifiers and tree-inline happy.
1752 Make it cold for now. */
1753 if (false_predicate_p (&p))
1759 if (!e->inline_failed)
1760 remap_edge_predicates (e->callee, info, callee_info, operand_map,
1761 possible_truths, toplev_predicate);
1763 for (e = node->indirect_calls; e; e = e->next_callee)
1765 struct inline_edge_summary *es = inline_edge_summary (e);
1769 p = remap_predicate (info, callee_info,
1770 es->predicate, operand_map, possible_truths,
1772 edge_set_predicate (e, &p);
1773 /* TODO: We should remove the edge for code that will be optimized out,
1774 but we need to keep verifiers and tree-inline happy.
1775 Make it cold for now. */
1776 if (false_predicate_p (&p))
1786 /* We inlined EDGE. Update summary of the function we inlined into. */
1789 inline_merge_summary (struct cgraph_edge *edge)
1791 struct inline_summary *callee_info = inline_summary (edge->callee);
1792 struct cgraph_node *to = (edge->caller->global.inlined_to
1793 ? edge->caller->global.inlined_to : edge->caller);
1794 struct inline_summary *info = inline_summary (to);
1795 clause_t clause = 0; /* not_inline is known to be false. */
1797 VEC (int, heap) *operand_map = NULL;
1799 struct predicate toplev_predicate;
1800 struct inline_edge_summary *es = inline_edge_summary (edge);
1803 toplev_predicate = *es->predicate;
1805 toplev_predicate = true_predicate ();
1807 if (ipa_node_params_vector && callee_info->conds
1808 /* FIXME: it seems that we forget to get argument count in some cases,
1809 probaby for previously indirect edges or so.
1810 Removing the test leads to ICE on tramp3d. */
1811 && ipa_get_cs_argument_count (IPA_EDGE_REF (edge)))
1813 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
1814 int count = ipa_get_cs_argument_count (args);
1817 clause = evaluate_conditions_for_edge (edge, true);
1818 VEC_safe_grow_cleared (int, heap, operand_map, count);
1819 for (i = 0; i < count; i++)
1821 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
1823 /* TODO: handle non-NOPs when merging. */
1824 if (jfunc->type == IPA_JF_PASS_THROUGH
1825 && jfunc->value.pass_through.operation == NOP_EXPR)
1826 map = jfunc->value.pass_through.formal_id;
1827 VEC_replace (int, operand_map, i, map);
1828 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
1831 for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
1833 struct predicate p = remap_predicate (info, callee_info,
1834 &e->predicate, operand_map, clause,
1836 gcov_type add_time = ((gcov_type)e->time * edge->frequency
1837 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1838 if (add_time > MAX_TIME)
1839 add_time = MAX_TIME;
1840 account_size_time (info, e->size, add_time, &p);
1842 remap_edge_predicates (edge->callee, info, callee_info, operand_map,
1843 clause, &toplev_predicate);
1846 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1847 info->size += e->size, info->time += e->time;
1848 estimate_calls_size_and_time (to, &info->size, &info->time,
1849 ~(clause_t)(1 << predicate_false_condition));
1851 inline_update_callee_summaries (edge->callee,
1852 inline_edge_summary (edge)->loop_depth);
1854 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1855 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1859 /* Estimate the time cost for the caller when inlining EDGE.
1860 Only to be called via estimate_edge_time, that handles the
1863 When caching, also update the cache entry. Compute both time and
1864 size, since we always need both metrics eventually. */
1867 do_estimate_edge_time (struct cgraph_edge *edge)
1872 struct inline_edge_summary *es = inline_edge_summary (edge);
1874 gcc_checking_assert (edge->inline_failed);
1875 estimate_callee_size_and_time (edge, true, &size, &time);
1877 ret = (((gcov_type)time - es->call_stmt_time) * edge->frequency
1878 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1882 /* When caching, update the cache entry. */
1883 if (edge_growth_cache)
1886 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
1888 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
1889 cgraph_edge_max_uid);
1890 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
1893 ret_size = size - es->call_stmt_size;
1894 gcc_checking_assert (es->call_stmt_size);
1895 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
1896 = ret_size + (ret_size >= 0);
1902 /* Estimate the growth of the caller when inlining EDGE.
1903 Only to be called via estimate_edge_size. */
1906 do_estimate_edge_growth (struct cgraph_edge *edge)
1910 /* When we do caching, use do_estimate_edge_time to populate the entry. */
1912 if (edge_growth_cache)
1914 do_estimate_edge_time (edge);
1915 size = VEC_index (edge_growth_cache_entry,
1918 gcc_checking_assert (size);
1919 return size - (size > 0);
1922 /* Early inliner runs without caching, go ahead and do the dirty work. */
1923 gcc_checking_assert (edge->inline_failed);
1924 estimate_callee_size_and_time (edge, true, &size, NULL);
1925 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
1926 return size - inline_edge_summary (edge)->call_stmt_size;
1930 /* Estimate self time of the function NODE after inlining EDGE. */
1933 estimate_time_after_inlining (struct cgraph_node *node,
1934 struct cgraph_edge *edge)
1936 struct inline_edge_summary *es = inline_edge_summary (edge);
1937 if (!es->predicate || !false_predicate_p (es->predicate))
1939 gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
1942 if (time > MAX_TIME)
1946 return inline_summary (node)->time;
1950 /* Estimate the size of NODE after inlining EDGE which should be an
1951 edge to either NODE or a call inlined into NODE. */
1954 estimate_size_after_inlining (struct cgraph_node *node,
1955 struct cgraph_edge *edge)
1957 struct inline_edge_summary *es = inline_edge_summary (edge);
1958 if (!es->predicate || !false_predicate_p (es->predicate))
1960 int size = inline_summary (node)->size + estimate_edge_growth (edge);
1961 gcc_assert (size >= 0);
1964 return inline_summary (node)->size;
1968 /* Estimate the growth caused by inlining NODE into all callees. */
1971 do_estimate_growth (struct cgraph_node *node)
1974 struct cgraph_edge *e;
1975 bool self_recursive = false;
1976 struct inline_summary *info = inline_summary (node);
1978 for (e = node->callers; e; e = e->next_caller)
1980 gcc_checking_assert (e->inline_failed);
1982 if (e->caller == node
1983 || (e->caller->global.inlined_to
1984 && e->caller->global.inlined_to == node))
1985 self_recursive = true;
1986 growth += estimate_edge_growth (e);
1990 /* For self recursive functions the growth estimation really should be
1991 infinity. We don't want to return very large values because the growth
1992 plays various roles in badness computation fractions. Be sure to not
1993 return zero or negative growths. */
1995 growth = growth < info->size ? info->size : growth;
1998 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
1999 && !DECL_EXTERNAL (node->decl))
2000 growth -= info->size;
2001 /* COMDAT functions are very often not shared across multiple units since they
2002 come from various template instantiations. Take this into account. */
2003 else if (DECL_COMDAT (node->decl)
2004 && cgraph_can_remove_if_no_direct_calls_p (node))
2005 growth -= (info->size
2006 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
2009 if (node_growth_cache)
2011 if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2012 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2013 VEC_replace (int, node_growth_cache, node->uid, growth + (growth >= 0));
2019 /* This function performs intraprocedural analysis in NODE that is required to
2020 inline indirect calls. */
2023 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2025 ipa_analyze_node (node);
2026 if (dump_file && (dump_flags & TDF_DETAILS))
2028 ipa_print_node_params (dump_file, node);
2029 ipa_print_node_jump_functions (dump_file, node);
2034 /* Note function body size. */
2037 inline_analyze_function (struct cgraph_node *node)
2039 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2040 current_function_decl = node->decl;
2043 fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2044 cgraph_node_name (node), node->uid);
2045 /* FIXME: We should remove the optimize check after we ensure we never run
2046 IPA passes when not optimizing. */
2047 if (flag_indirect_inlining && optimize && !node->thunk.thunk_p)
2048 inline_indirect_intraprocedural_analysis (node);
2049 compute_inline_parameters (node, false);
2051 current_function_decl = NULL;
2056 /* Called when new function is inserted to callgraph late. */
2059 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2061 inline_analyze_function (node);
2065 /* Note function body size. */
2068 inline_generate_summary (void)
2070 struct cgraph_node *node;
2072 function_insertion_hook_holder =
2073 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2075 if (flag_indirect_inlining)
2076 ipa_register_cgraph_hooks ();
2078 FOR_EACH_DEFINED_FUNCTION (node)
2079 inline_analyze_function (node);
2083 /* Read predicate from IB. */
2085 static struct predicate
2086 read_predicate (struct lto_input_block *ib)
2088 struct predicate out;
2094 gcc_assert (k <= MAX_CLAUSES);
2095 clause = out.clause[k++] = lto_input_uleb128 (ib);
2102 /* Write inline summary for edge E to OB. */
2105 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2107 struct inline_edge_summary *es = inline_edge_summary (e);
2110 es->call_stmt_size = lto_input_uleb128 (ib);
2111 es->call_stmt_time = lto_input_uleb128 (ib);
2112 es->loop_depth = lto_input_uleb128 (ib);
2113 p = read_predicate (ib);
2114 edge_set_predicate (e, &p);
2118 /* Stream in inline summaries from the section. */
2121 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
2124 const struct lto_function_header *header =
2125 (const struct lto_function_header *) data;
2126 const int32_t cfg_offset = sizeof (struct lto_function_header);
2127 const int32_t main_offset = cfg_offset + header->cfg_size;
2128 const int32_t string_offset = main_offset + header->main_size;
2129 struct data_in *data_in;
2130 struct lto_input_block ib;
2131 unsigned int i, count2, j;
2132 unsigned int f_count;
2134 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
2138 lto_data_in_create (file_data, (const char *) data + string_offset,
2139 header->string_size, NULL);
2140 f_count = lto_input_uleb128 (&ib);
2141 for (i = 0; i < f_count; i++)
2144 struct cgraph_node *node;
2145 struct inline_summary *info;
2146 lto_cgraph_encoder_t encoder;
2147 struct bitpack_d bp;
2148 struct cgraph_edge *e;
2150 index = lto_input_uleb128 (&ib);
2151 encoder = file_data->cgraph_node_encoder;
2152 node = lto_cgraph_encoder_deref (encoder, index);
2153 info = inline_summary (node);
2155 info->estimated_stack_size
2156 = info->estimated_self_stack_size = lto_input_uleb128 (&ib);
2157 info->size = info->self_size = lto_input_uleb128 (&ib);
2158 info->time = info->self_time = lto_input_uleb128 (&ib);
2160 bp = lto_input_bitpack (&ib);
2161 info->inlinable = bp_unpack_value (&bp, 1);
2162 info->versionable = bp_unpack_value (&bp, 1);
2164 count2 = lto_input_uleb128 (&ib);
2165 gcc_assert (!info->conds);
2166 for (j = 0; j < count2; j++)
2169 c.operand_num = lto_input_uleb128 (&ib);
2170 c.code = (enum tree_code) lto_input_uleb128 (&ib);
2171 c.val = lto_input_tree (&ib, data_in);
2172 VEC_safe_push (condition, gc, info->conds, &c);
2174 count2 = lto_input_uleb128 (&ib);
2175 gcc_assert (!info->entry);
2176 for (j = 0; j < count2; j++)
2178 struct size_time_entry e;
2180 e.size = lto_input_uleb128 (&ib);
2181 e.time = lto_input_uleb128 (&ib);
2182 e.predicate = read_predicate (&ib);
2184 VEC_safe_push (size_time_entry, gc, info->entry, &e);
2186 for (e = node->callees; e; e = e->next_callee)
2187 read_inline_edge_summary (&ib, e);
2188 for (e = node->indirect_calls; e; e = e->next_callee)
2189 read_inline_edge_summary (&ib, e);
2192 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
2194 lto_data_in_delete (data_in);
2198 /* Read inline summary. Jump functions are shared among ipa-cp
2199 and inliner, so when ipa-cp is active, we don't need to write them
2203 inline_read_summary (void)
2205 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2206 struct lto_file_decl_data *file_data;
2209 inline_summary_alloc ();
2211 while ((file_data = file_data_vec[j++]))
2214 const char *data = lto_get_section_data (file_data, LTO_section_inline_summary, NULL, &len);
2216 inline_read_section (file_data, data, len);
2218 /* Fatal error here. We do not want to support compiling ltrans units with
2219 different version of compiler or different flags than the WPA unit, so
2220 this should never happen. */
2221 fatal_error ("ipa inline summary is missing in input file");
2223 if (flag_indirect_inlining)
2225 ipa_register_cgraph_hooks ();
2227 ipa_prop_read_jump_functions ();
2229 function_insertion_hook_holder =
2230 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2234 /* Write predicate P to OB. */
2237 write_predicate (struct output_block *ob, struct predicate *p)
2241 for (j = 0; p->clause[j]; j++)
2243 gcc_assert (j < MAX_CLAUSES);
2244 lto_output_uleb128_stream (ob->main_stream,
2247 lto_output_uleb128_stream (ob->main_stream, 0);
2251 /* Write inline summary for edge E to OB. */
2254 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
2256 struct inline_edge_summary *es = inline_edge_summary (e);
2257 lto_output_uleb128_stream (ob->main_stream, es->call_stmt_size);
2258 lto_output_uleb128_stream (ob->main_stream, es->call_stmt_time);
2259 lto_output_uleb128_stream (ob->main_stream, es->loop_depth);
2260 write_predicate (ob, es->predicate);
2264 /* Write inline summary for node in SET.
2265 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2266 active, we don't need to write them twice. */
2269 inline_write_summary (cgraph_node_set set,
2270 varpool_node_set vset ATTRIBUTE_UNUSED)
2272 struct cgraph_node *node;
2273 struct output_block *ob = create_output_block (LTO_section_inline_summary);
2274 lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
2275 unsigned int count = 0;
2278 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2279 if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
2281 lto_output_uleb128_stream (ob->main_stream, count);
2283 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2285 node = lto_cgraph_encoder_deref (encoder, i);
2288 struct inline_summary *info = inline_summary (node);
2289 struct bitpack_d bp;
2290 struct cgraph_edge *edge;
2293 struct condition *c;
2296 lto_output_uleb128_stream (ob->main_stream,
2297 lto_cgraph_encoder_encode (encoder, node));
2298 lto_output_sleb128_stream (ob->main_stream,
2299 info->estimated_self_stack_size);
2300 lto_output_sleb128_stream (ob->main_stream,
2302 lto_output_sleb128_stream (ob->main_stream,
2304 bp = bitpack_create (ob->main_stream);
2305 bp_pack_value (&bp, info->inlinable, 1);
2306 bp_pack_value (&bp, info->versionable, 1);
2307 lto_output_bitpack (&bp);
2308 lto_output_uleb128_stream (ob->main_stream,
2309 VEC_length (condition, info->conds));
2310 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
2312 lto_output_uleb128_stream (ob->main_stream,
2314 lto_output_uleb128_stream (ob->main_stream,
2316 lto_output_tree (ob, c->val, true);
2318 lto_output_uleb128_stream (ob->main_stream,
2319 VEC_length (size_time_entry, info->entry));
2321 VEC_iterate (size_time_entry, info->entry, i, e);
2324 lto_output_uleb128_stream (ob->main_stream,
2326 lto_output_uleb128_stream (ob->main_stream,
2328 write_predicate (ob, &e->predicate);
2330 for (edge = node->callees; edge; edge = edge->next_callee)
2331 write_inline_edge_summary (ob, edge);
2332 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
2333 write_inline_edge_summary (ob, edge);
2336 lto_output_1_stream (ob->main_stream, 0);
2337 produce_asm (ob, NULL);
2338 destroy_output_block (ob);
2340 if (flag_indirect_inlining && !flag_ipa_cp)
2341 ipa_prop_write_jump_functions (set);
2345 /* Release inline summary. */
2348 inline_free_summary (void)
2350 if (function_insertion_hook_holder)
2351 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
2352 function_insertion_hook_holder = NULL;
2353 if (node_removal_hook_holder)
2354 cgraph_remove_node_removal_hook (node_removal_hook_holder);
2355 if (edge_removal_hook_holder)
2356 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
2357 node_removal_hook_holder = NULL;
2358 if (node_duplication_hook_holder)
2359 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
2360 if (edge_duplication_hook_holder)
2361 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2362 node_duplication_hook_holder = NULL;
2363 VEC_free (inline_summary_t, gc, inline_summary_vec);
2364 inline_summary_vec = NULL;
2365 VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
2366 inline_edge_summary_vec = NULL;
2367 if (edge_predicate_pool)
2368 free_alloc_pool (edge_predicate_pool);
2369 edge_predicate_pool = 0;