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 "data-streamer.h"
88 #include "tree-streamer.h"
89 #include "ipa-inline.h"
90 #include "alloc-pool.h"
92 /* Estimate runtime of function can easilly run into huge numbers with many
93 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
94 integer. For anything larger we use gcov_type. */
95 #define MAX_TIME 500000
97 /* Number of bits in integer, but we really want to be stable across different
99 #define NUM_CONDITIONS 32
101 enum predicate_conditions
103 predicate_false_condition = 0,
104 predicate_not_inlined_condition = 1,
105 predicate_first_dynamic_condition = 2
108 /* Special condition code we use to represent test that operand is compile time
110 #define IS_NOT_CONSTANT ERROR_MARK
111 /* Special condition code we use to represent test that operand is not changed
112 across invocation of the function. When operand IS_NOT_CONSTANT it is always
113 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
114 of executions even when they are not compile time constants. */
115 #define CHANGED IDENTIFIER_NODE
117 /* Holders of ipa cgraph hooks: */
118 static struct cgraph_node_hook_list *function_insertion_hook_holder;
119 static struct cgraph_node_hook_list *node_removal_hook_holder;
120 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
121 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
122 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
123 static void inline_node_removal_hook (struct cgraph_node *, void *);
124 static void inline_node_duplication_hook (struct cgraph_node *,
125 struct cgraph_node *, void *);
126 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
127 static void inline_edge_duplication_hook (struct cgraph_edge *,
128 struct cgraph_edge *,
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 VEC(inline_summary_t,gc) *inline_summary_vec;
134 VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
136 /* Cached node/edge growths. */
137 VEC(int,heap) *node_growth_cache;
138 VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
140 /* Edge predicates goes here. */
141 static alloc_pool edge_predicate_pool;
143 /* Return true predicate (tautology).
144 We represent it by empty list of clauses. */
146 static inline struct predicate
147 true_predicate (void)
155 /* Return predicate testing single condition number COND. */
157 static inline struct predicate
158 single_cond_predicate (int cond)
161 p.clause[0]=1 << cond;
167 /* Return false predicate. First clause require false condition. */
169 static inline struct predicate
170 false_predicate (void)
172 return single_cond_predicate (predicate_false_condition);
176 /* Return true if P is (false). */
179 true_predicate_p (struct predicate *p)
181 return !p->clause[0];
185 /* Return true if P is (false). */
188 false_predicate_p (struct predicate *p)
190 if (p->clause[0] == (1 << predicate_false_condition))
192 gcc_checking_assert (!p->clause[1]
193 && p->clause[0] == 1 << predicate_false_condition);
200 /* Return predicate that is set true when function is not inlined. */
201 static inline struct predicate
202 not_inlined_predicate (void)
204 return single_cond_predicate (predicate_not_inlined_condition);
208 /* Add condition to condition list CONDS. */
210 static struct predicate
211 add_condition (struct inline_summary *summary, int operand_num,
212 enum tree_code code, tree val)
216 struct condition new_cond;
218 for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++)
220 if (c->operand_num == operand_num
223 return single_cond_predicate (i + predicate_first_dynamic_condition);
225 /* Too many conditions. Give up and return constant true. */
226 if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
227 return true_predicate ();
229 new_cond.operand_num = operand_num;
230 new_cond.code = code;
232 VEC_safe_push (condition, gc, summary->conds, &new_cond);
233 return single_cond_predicate (i + predicate_first_dynamic_condition);
237 /* Add clause CLAUSE into the predicate P. */
240 add_clause (conditions conditions, struct predicate *p, clause_t clause)
244 int insert_here = -1;
251 /* False clause makes the whole predicate false. Kill the other variants. */
252 if (clause == (1 << predicate_false_condition))
254 p->clause[0] = (1 << predicate_false_condition);
258 if (false_predicate_p (p))
261 /* No one should be sily enough to add false into nontrivial clauses. */
262 gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
264 /* Look where to insert the clause. At the same time prune out
265 clauses of P that are implied by the new clause and thus
267 for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
269 p->clause[i2] = p->clause[i];
274 /* If p->clause[i] implies clause, there is nothing to add. */
275 if ((p->clause[i] & clause) == p->clause[i])
277 /* We had nothing to add, none of clauses should've become
279 gcc_checking_assert (i == i2);
283 if (p->clause[i] < clause && insert_here < 0)
286 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
287 Otherwise the p->clause[i] has to stay. */
288 if ((p->clause[i] & clause) != clause)
292 /* Look for clauses that are obviously true. I.e.
293 op0 == 5 || op0 != 5. */
294 for (c1 = predicate_first_dynamic_condition; c1 < NUM_CONDITIONS; c1++)
297 if (!(clause & (1 << c1)))
299 cc1 = VEC_index (condition,
301 c1 - predicate_first_dynamic_condition);
302 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
303 and thus there is no point for looking for them. */
304 if (cc1->code == CHANGED
305 || cc1->code == IS_NOT_CONSTANT)
307 for (c2 = c1 + 1; c2 <= NUM_CONDITIONS; c2++)
308 if (clause & (1 << c2))
310 condition *cc1 = VEC_index (condition,
312 c1 - predicate_first_dynamic_condition);
313 condition *cc2 = VEC_index (condition,
315 c2 - predicate_first_dynamic_condition);
316 if (cc1->operand_num == cc2->operand_num
317 && cc1->val == cc2->val
318 && cc2->code != IS_NOT_CONSTANT
319 && cc2->code != CHANGED
320 && cc1->code == invert_tree_comparison
322 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1->val)))))
328 /* We run out of variants. Be conservative in positive direction. */
329 if (i2 == MAX_CLAUSES)
331 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
332 p->clause[i2 + 1] = 0;
333 if (insert_here >= 0)
334 for (;i2 > insert_here; i2--)
335 p->clause[i2] = p->clause[i2 - 1];
338 p->clause[insert_here] = clause;
344 static struct predicate
345 and_predicates (conditions conditions,
346 struct predicate *p, struct predicate *p2)
348 struct predicate out = *p;
351 /* Avoid busy work. */
352 if (false_predicate_p (p2) || true_predicate_p (p))
354 if (false_predicate_p (p) || true_predicate_p (p2))
357 /* See how far predicates match. */
358 for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
360 gcc_checking_assert (i < MAX_CLAUSES);
363 /* Combine the predicates rest. */
364 for (; p2->clause[i]; i++)
366 gcc_checking_assert (i < MAX_CLAUSES);
367 add_clause (conditions, &out, p2->clause[i]);
373 /* Return true if predicates are obviously equal. */
376 predicates_equal_p (struct predicate *p, struct predicate *p2)
379 for (i = 0; p->clause[i]; i++)
381 gcc_checking_assert (i < MAX_CLAUSES);
382 gcc_checking_assert (p->clause [i] > p->clause[i + 1]);
383 gcc_checking_assert (!p2->clause[i]
384 || p2->clause [i] > p2->clause[i + 1]);
385 if (p->clause[i] != p2->clause[i])
388 return !p2->clause[i];
394 static struct predicate
395 or_predicates (conditions conditions, struct predicate *p, struct predicate *p2)
397 struct predicate out = true_predicate ();
400 /* Avoid busy work. */
401 if (false_predicate_p (p2) || true_predicate_p (p))
403 if (false_predicate_p (p) || true_predicate_p (p2))
405 if (predicates_equal_p (p, p2))
408 /* OK, combine the predicates. */
409 for (i = 0; p->clause[i]; i++)
410 for (j = 0; p2->clause[j]; j++)
412 gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
413 add_clause (conditions, &out, p->clause[i] | p2->clause[j]);
419 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
420 if predicate P is known to be false. */
423 evaluate_predicate (struct predicate *p, clause_t possible_truths)
427 /* True remains true. */
428 if (true_predicate_p (p))
431 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
433 /* See if we can find clause we can disprove. */
434 for (i = 0; p->clause[i]; i++)
436 gcc_checking_assert (i < MAX_CLAUSES);
437 if (!(p->clause[i] & possible_truths))
443 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
444 instruction will be recomputed per invocation of the inlined call. */
447 predicate_probability (conditions conds,
448 struct predicate *p, clause_t possible_truths,
449 VEC (inline_param_summary_t, heap) *inline_param_summary)
452 int combined_prob = REG_BR_PROB_BASE;
454 /* True remains true. */
455 if (true_predicate_p (p))
456 return REG_BR_PROB_BASE;
458 if (false_predicate_p (p))
461 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
463 /* See if we can find clause we can disprove. */
464 for (i = 0; p->clause[i]; i++)
466 gcc_checking_assert (i < MAX_CLAUSES);
467 if (!(p->clause[i] & possible_truths))
473 if (!inline_param_summary)
474 return REG_BR_PROB_BASE;
475 for (i2 = 0; i2 < NUM_CONDITIONS; i2++)
476 if ((p->clause[i] & possible_truths) & (1 << i2))
478 if (i2 >= predicate_first_dynamic_condition)
480 condition *c = VEC_index
482 i2 - predicate_first_dynamic_condition);
483 if (c->code == CHANGED
485 < (int) VEC_length (inline_param_summary_t,
486 inline_param_summary)))
488 int iprob = VEC_index (inline_param_summary_t,
489 inline_param_summary,
490 c->operand_num)->change_prob;
491 this_prob = MAX (this_prob, iprob);
494 this_prob = REG_BR_PROB_BASE;
497 this_prob = REG_BR_PROB_BASE;
499 combined_prob = MIN (this_prob, combined_prob);
504 return combined_prob;
508 /* Dump conditional COND. */
511 dump_condition (FILE *f, conditions conditions, int cond)
514 if (cond == predicate_false_condition)
515 fprintf (f, "false");
516 else if (cond == predicate_not_inlined_condition)
517 fprintf (f, "not inlined");
520 c = VEC_index (condition, conditions,
521 cond - predicate_first_dynamic_condition);
522 fprintf (f, "op%i", c->operand_num);
523 if (c->code == IS_NOT_CONSTANT)
525 fprintf (f, " not constant");
528 if (c->code == CHANGED)
530 fprintf (f, " changed");
533 fprintf (f, " %s ", op_symbol_code (c->code));
534 print_generic_expr (f, c->val, 1);
539 /* Dump clause CLAUSE. */
542 dump_clause (FILE *f, conditions conds, clause_t clause)
549 for (i = 0; i < NUM_CONDITIONS; i++)
550 if (clause & (1 << i))
555 dump_condition (f, conds, i);
561 /* Dump predicate PREDICATE. */
564 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
567 if (true_predicate_p (pred))
568 dump_clause (f, conds, 0);
570 for (i = 0; pred->clause[i]; i++)
574 dump_clause (f, conds, pred->clause[i]);
580 /* Record SIZE and TIME under condition PRED into the inline summary. */
583 account_size_time (struct inline_summary *summary, int size, int time,
584 struct predicate *pred)
590 if (false_predicate_p (pred))
593 /* We need to create initial empty unconitional clause, but otherwie
594 we don't need to account empty times and sizes. */
595 if (!size && !time && summary->entry)
598 /* Watch overflow that might result from insane profiles. */
599 if (time > MAX_TIME * INLINE_TIME_SCALE)
600 time = MAX_TIME * INLINE_TIME_SCALE;
601 gcc_assert (time >= 0);
603 for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
604 if (predicates_equal_p (&e->predicate, pred))
613 e = VEC_index (size_time_entry, summary->entry, 0);
614 gcc_assert (!e->predicate.clause[0]);
616 if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
618 fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
619 ((double)size) / INLINE_SIZE_SCALE,
620 ((double)time) / INLINE_TIME_SCALE,
621 found ? "" : "new ");
622 dump_predicate (dump_file, summary->conds, pred);
626 struct size_time_entry new_entry;
627 new_entry.size = size;
628 new_entry.time = time;
629 new_entry.predicate = *pred;
630 VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry);
636 if (e->time > MAX_TIME * INLINE_TIME_SCALE)
637 e->time = MAX_TIME * INLINE_TIME_SCALE;
641 /* Set predicate for edge E. */
644 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
646 struct inline_edge_summary *es = inline_edge_summary (e);
647 if (predicate && !true_predicate_p (predicate))
650 es->predicate = (struct predicate *)pool_alloc (edge_predicate_pool);
651 *es->predicate = *predicate;
656 pool_free (edge_predicate_pool, es->predicate);
657 es->predicate = NULL;
662 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
663 Return clause of possible truths. When INLINE_P is true, assume that
666 ERROR_MARK means compile time invariant. */
669 evaluate_conditions_for_known_args (struct cgraph_node *node,
671 VEC (tree, heap) *known_vals)
673 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
674 struct inline_summary *info = inline_summary (node);
678 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
683 /* We allow call stmt to have fewer arguments than the callee
684 function (especially for K&R style programs). So bound
686 if (c->operand_num < (int)VEC_length (tree, known_vals))
687 val = VEC_index (tree, known_vals, c->operand_num);
691 if (val == error_mark_node && c->code != CHANGED)
696 clause |= 1 << (i + predicate_first_dynamic_condition);
699 if (c->code == IS_NOT_CONSTANT || c->code == CHANGED)
701 res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
703 && integer_zerop (res))
705 clause |= 1 << (i + predicate_first_dynamic_condition);
711 /* Work out what conditions might be true at invocation of E. */
714 evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
715 clause_t *clause_ptr,
716 VEC (tree, heap) **known_vals_ptr,
717 VEC (tree, heap) **known_binfos_ptr)
719 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
720 struct inline_summary *info = inline_summary (callee);
724 *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition;
726 *known_vals_ptr = NULL;
727 if (known_binfos_ptr)
728 *known_binfos_ptr = NULL;
730 if (ipa_node_params_vector
731 && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
733 struct ipa_node_params *parms_info;
734 struct ipa_edge_args *args = IPA_EDGE_REF (e);
735 struct inline_edge_summary *es = inline_edge_summary (e);
736 int i, count = ipa_get_cs_argument_count (args);
737 VEC (tree, heap) *known_vals = NULL;
739 if (e->caller->global.inlined_to)
740 parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
742 parms_info = IPA_NODE_REF (e->caller);
744 if (count && (info->conds || known_vals_ptr))
745 VEC_safe_grow_cleared (tree, heap, known_vals, count);
746 if (count && known_binfos_ptr)
747 VEC_safe_grow_cleared (tree, heap, *known_binfos_ptr, count);
749 for (i = 0; i < count; i++)
751 tree cst = ipa_value_from_jfunc (parms_info,
752 ipa_get_ith_jump_func (args, i));
755 if (info->conds && TREE_CODE (cst) != TREE_BINFO)
756 VEC_replace (tree, known_vals, i, cst);
757 else if (known_binfos_ptr != NULL)
758 VEC_replace (tree, *known_binfos_ptr, i, cst);
761 && !VEC_index (inline_param_summary_t,
764 VEC_replace (tree, known_vals, i, error_mark_node);
767 if (clause_ptr && info->conds)
768 *clause_ptr = evaluate_conditions_for_known_args (callee, inline_p,
772 *known_vals_ptr = known_vals;
774 VEC_free (tree, heap, known_vals);
777 if (clause_ptr && !info->conds)
778 for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
779 *clause_ptr |= 1 << (i + predicate_first_dynamic_condition);
783 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
786 inline_summary_alloc (void)
788 if (!node_removal_hook_holder)
789 node_removal_hook_holder =
790 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
791 if (!edge_removal_hook_holder)
792 edge_removal_hook_holder =
793 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
794 if (!node_duplication_hook_holder)
795 node_duplication_hook_holder =
796 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
797 if (!edge_duplication_hook_holder)
798 edge_duplication_hook_holder =
799 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
801 if (VEC_length (inline_summary_t, inline_summary_vec)
802 <= (unsigned) cgraph_max_uid)
803 VEC_safe_grow_cleared (inline_summary_t, gc,
804 inline_summary_vec, cgraph_max_uid + 1);
805 if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec)
806 <= (unsigned) cgraph_edge_max_uid)
807 VEC_safe_grow_cleared (inline_edge_summary_t, heap,
808 inline_edge_summary_vec, cgraph_edge_max_uid + 1);
809 if (!edge_predicate_pool)
810 edge_predicate_pool = create_alloc_pool ("edge predicates",
811 sizeof (struct predicate),
815 /* We are called multiple time for given function; clear
816 data from previous run so they are not cumulated. */
819 reset_inline_edge_summary (struct cgraph_edge *e)
822 < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec))
824 struct inline_edge_summary *es = inline_edge_summary (e);
826 es->call_stmt_size = es->call_stmt_time =0;
828 pool_free (edge_predicate_pool, es->predicate);
829 es->predicate = NULL;
830 VEC_free (inline_param_summary_t, heap, es->param);
834 /* We are called multiple time for given function; clear
835 data from previous run so they are not cumulated. */
838 reset_inline_summary (struct cgraph_node *node)
840 struct inline_summary *info = inline_summary (node);
841 struct cgraph_edge *e;
843 info->self_size = info->self_time = 0;
844 info->estimated_stack_size = 0;
845 info->estimated_self_stack_size = 0;
846 info->stack_frame_offset = 0;
849 VEC_free (condition, gc, info->conds);
850 VEC_free (size_time_entry,gc, info->entry);
851 for (e = node->callees; e; e = e->next_callee)
852 reset_inline_edge_summary (e);
853 for (e = node->indirect_calls; e; e = e->next_callee)
854 reset_inline_edge_summary (e);
857 /* Hook that is called by cgraph.c when a node is removed. */
860 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
862 struct inline_summary *info;
863 if (VEC_length (inline_summary_t, inline_summary_vec)
864 <= (unsigned)node->uid)
866 info = inline_summary (node);
867 reset_inline_summary (node);
868 memset (info, 0, sizeof (inline_summary_t));
872 /* Hook that is called by cgraph.c when a node is duplicated. */
875 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
876 ATTRIBUTE_UNUSED void *data)
878 struct inline_summary *info;
879 inline_summary_alloc ();
880 info = inline_summary (dst);
881 memcpy (info, inline_summary (src),
882 sizeof (struct inline_summary));
883 /* TODO: as an optimization, we may avoid copying conditions
884 that are known to be false or true. */
885 info->conds = VEC_copy (condition, gc, info->conds);
887 /* When there are any replacements in the function body, see if we can figure
888 out that something was optimized out. */
889 if (ipa_node_params_vector && dst->clone.tree_map)
891 VEC(size_time_entry,gc) *entry = info->entry;
892 /* Use SRC parm info since it may not be copied yet. */
893 struct ipa_node_params *parms_info = IPA_NODE_REF (src);
894 VEC (tree, heap) *known_vals = NULL;
895 int count = ipa_get_param_count (parms_info);
897 clause_t possible_truths;
898 struct predicate true_pred = true_predicate ();
900 int optimized_out_size = 0;
901 gcov_type optimized_out_time = 0;
902 bool inlined_to_p = false;
903 struct cgraph_edge *edge;
906 VEC_safe_grow_cleared (tree, heap, known_vals, count);
907 for (i = 0; i < count; i++)
909 tree t = ipa_get_param (parms_info, i);
910 struct ipa_replace_map *r;
913 VEC_iterate (ipa_replace_map_p, dst->clone.tree_map, j, r);
920 VEC_replace (tree, known_vals, i, r->new_tree);
925 possible_truths = evaluate_conditions_for_known_args (dst,
927 VEC_free (tree, heap, known_vals);
929 account_size_time (info, 0, 0, &true_pred);
931 /* Remap size_time vectors.
932 Simplify the predicate by prunning out alternatives that are known
934 TODO: as on optimization, we can also eliminate conditions known
936 for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
938 struct predicate new_predicate = true_predicate ();
939 for (j = 0; e->predicate.clause[j]; j++)
940 if (!(possible_truths & e->predicate.clause[j]))
942 new_predicate = false_predicate ();
946 add_clause (info->conds, &new_predicate,
947 possible_truths & e->predicate.clause[j]);
948 if (false_predicate_p (&new_predicate))
950 optimized_out_size += e->size;
951 optimized_out_time += e->time;
954 account_size_time (info, e->size, e->time, &new_predicate);
957 /* Remap edge predicates with the same simplification as above.
958 Also copy constantness arrays. */
959 for (edge = dst->callees; edge; edge = edge->next_callee)
961 struct predicate new_predicate = true_predicate ();
962 struct inline_edge_summary *es = inline_edge_summary (edge);
964 if (!edge->inline_failed)
968 for (j = 0; es->predicate->clause[j]; j++)
969 if (!(possible_truths & es->predicate->clause[j]))
971 new_predicate = false_predicate ();
975 add_clause (info->conds, &new_predicate,
976 possible_truths & es->predicate->clause[j]);
977 if (false_predicate_p (&new_predicate)
978 && !false_predicate_p (es->predicate))
980 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
981 optimized_out_time += (es->call_stmt_time
982 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
986 *es->predicate = new_predicate;
989 /* Remap indirect edge predicates with the same simplificaiton as above.
990 Also copy constantness arrays. */
991 for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
993 struct predicate new_predicate = true_predicate ();
994 struct inline_edge_summary *es = inline_edge_summary (edge);
996 if (!edge->inline_failed)
1000 for (j = 0; es->predicate->clause[j]; j++)
1001 if (!(possible_truths & es->predicate->clause[j]))
1003 new_predicate = false_predicate ();
1007 add_clause (info->conds, &new_predicate,
1008 possible_truths & es->predicate->clause[j]);
1009 if (false_predicate_p (&new_predicate)
1010 && !false_predicate_p (es->predicate))
1012 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
1013 optimized_out_time += (es->call_stmt_time
1014 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
1016 edge->frequency = 0;
1018 *es->predicate = new_predicate;
1021 /* If inliner or someone after inliner will ever start producing
1022 non-trivial clones, we will get trouble with lack of information
1023 about updating self sizes, because size vectors already contains
1024 sizes of the calees. */
1025 gcc_assert (!inlined_to_p
1026 || (!optimized_out_size && !optimized_out_time));
1028 info->size -= optimized_out_size / INLINE_SIZE_SCALE;
1029 info->self_size -= optimized_out_size / INLINE_SIZE_SCALE;
1030 gcc_assert (info->size > 0);
1031 gcc_assert (info->self_size > 0);
1033 optimized_out_time /= INLINE_TIME_SCALE;
1034 if (optimized_out_time > MAX_TIME)
1035 optimized_out_time = MAX_TIME;
1036 info->time -= optimized_out_time;
1037 info->self_time -= optimized_out_time;
1040 if (info->self_time < 0)
1041 info->self_time = 0;
1044 info->entry = VEC_copy (size_time_entry, gc, info->entry);
1048 /* Hook that is called by cgraph.c when a node is duplicated. */
1051 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1052 ATTRIBUTE_UNUSED void *data)
1054 struct inline_edge_summary *info;
1055 struct inline_edge_summary *srcinfo;
1056 inline_summary_alloc ();
1057 info = inline_edge_summary (dst);
1058 srcinfo = inline_edge_summary (src);
1059 memcpy (info, srcinfo,
1060 sizeof (struct inline_edge_summary));
1061 info->predicate = NULL;
1062 edge_set_predicate (dst, srcinfo->predicate);
1063 info->param = VEC_copy (inline_param_summary_t, heap, srcinfo->param);
1067 /* Keep edge cache consistent across edge removal. */
1070 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
1072 if (edge_growth_cache)
1073 reset_edge_growth_cache (edge);
1074 reset_inline_edge_summary (edge);
1078 /* Initialize growth caches. */
1081 initialize_growth_caches (void)
1083 if (cgraph_edge_max_uid)
1084 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
1085 cgraph_edge_max_uid);
1087 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
1091 /* Free growth caches. */
1094 free_growth_caches (void)
1096 VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
1097 edge_growth_cache = 0;
1098 VEC_free (int, heap, node_growth_cache);
1099 node_growth_cache = 0;
1103 /* Dump edge summaries associated to NODE and recursively to all clones.
1104 Indent by INDENT. */
1107 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node,
1108 struct inline_summary *info)
1110 struct cgraph_edge *edge;
1111 for (edge = node->callees; edge; edge = edge->next_callee)
1113 struct inline_edge_summary *es = inline_edge_summary (edge);
1114 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1117 fprintf (f, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
1118 indent, "", cgraph_node_name (callee),
1120 !edge->inline_failed ? "inlined"
1121 : cgraph_inline_failed_string (edge->inline_failed),
1127 (int)inline_summary (callee)->size / INLINE_SIZE_SCALE,
1128 (int)inline_summary (callee)->estimated_stack_size);
1132 fprintf (f, " predicate: ");
1133 dump_predicate (f, info->conds, es->predicate);
1138 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param);
1141 int prob = VEC_index (inline_param_summary_t,
1142 es->param, i)->change_prob;
1145 fprintf (f, "%*s op%i is compile time invariant\n",
1147 else if (prob != REG_BR_PROB_BASE)
1148 fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i,
1149 prob * 100.0 / REG_BR_PROB_BASE);
1151 if (!edge->inline_failed)
1153 fprintf (f, "%*sStack frame offset %i, callee self size %i,"
1154 " callee size %i\n",
1156 (int)inline_summary (callee)->stack_frame_offset,
1157 (int)inline_summary (callee)->estimated_self_stack_size,
1158 (int)inline_summary (callee)->estimated_stack_size);
1159 dump_inline_edge_summary (f, indent+2, callee, info);
1162 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1164 struct inline_edge_summary *es = inline_edge_summary (edge);
1165 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1171 es->call_stmt_time);
1174 fprintf (f, "predicate: ");
1175 dump_predicate (f, info->conds, es->predicate);
1184 dump_inline_summary (FILE * f, struct cgraph_node *node)
1188 struct inline_summary *s = inline_summary (node);
1191 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
1193 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1194 fprintf (f, " always_inline");
1196 fprintf (f, " inlinable");
1197 fprintf (f, "\n self time: %i\n",
1199 fprintf (f, " global time: %i\n", s->time);
1200 fprintf (f, " self size: %i\n",
1202 fprintf (f, " global size: %i\n", s->size);
1203 fprintf (f, " self stack: %i\n",
1204 (int) s->estimated_self_stack_size);
1205 fprintf (f, " global stack: %i\n",
1206 (int) s->estimated_stack_size);
1208 VEC_iterate (size_time_entry, s->entry, i, e);
1211 fprintf (f, " size:%f, time:%f, predicate:",
1212 (double) e->size / INLINE_SIZE_SCALE,
1213 (double) e->time / INLINE_TIME_SCALE);
1214 dump_predicate (f, s->conds, &e->predicate);
1216 fprintf (f, " calls:\n");
1217 dump_inline_edge_summary (f, 4, node, s);
1223 debug_inline_summary (struct cgraph_node *node)
1225 dump_inline_summary (stderr, node);
1229 dump_inline_summaries (FILE *f)
1231 struct cgraph_node *node;
1233 for (node = cgraph_nodes; node; node = node->next)
1234 if (node->analyzed && !node->global.inlined_to)
1235 dump_inline_summary (f, node);
1238 /* Give initial reasons why inlining would fail on EDGE. This gets either
1239 nullified or usually overwritten by more precise reasons later. */
1242 initialize_inline_failed (struct cgraph_edge *e)
1244 struct cgraph_node *callee = e->callee;
1246 if (e->indirect_unknown_callee)
1247 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1248 else if (!callee->analyzed)
1249 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1250 else if (callee->local.redefined_extern_inline)
1251 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1252 else if (e->call_stmt_cannot_inline_p)
1253 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1255 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1258 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1259 boolean variable pointed to by DATA. */
1262 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
1265 bool *b = (bool *) data;
1270 /* If OP reffers to value of function parameter, return
1271 the corresponding parameter. */
1274 unmodified_parm (gimple stmt, tree op)
1276 /* SSA_NAME referring to parm default def? */
1277 if (TREE_CODE (op) == SSA_NAME
1278 && SSA_NAME_IS_DEFAULT_DEF (op)
1279 && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL)
1280 return SSA_NAME_VAR (op);
1281 /* Non-SSA parm reference? */
1282 if (TREE_CODE (op) == PARM_DECL)
1284 bool modified = false;
1287 ao_ref_init (&refd, op);
1288 walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
1293 /* Assignment from a parameter? */
1294 if (TREE_CODE (op) == SSA_NAME
1295 && !SSA_NAME_IS_DEFAULT_DEF (op)
1296 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1297 return unmodified_parm (SSA_NAME_DEF_STMT (op),
1298 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)));
1302 /* See if statement might disappear after inlining.
1303 0 - means not eliminated
1304 1 - half of statements goes away
1305 2 - for sure it is eliminated.
1306 We are not terribly sophisticated, basically looking for simple abstraction
1307 penalty wrappers. */
1310 eliminated_by_inlining_prob (gimple stmt)
1312 enum gimple_code code = gimple_code (stmt);
1322 if (gimple_num_ops (stmt) != 2)
1325 /* Casts of parameters, loads from parameters passed by reference
1326 and stores to return value or parameters are often free after
1327 inlining dua to SRA and further combining.
1328 Assume that half of statements goes away. */
1329 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1330 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1331 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1332 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1334 tree rhs = gimple_assign_rhs1 (stmt);
1335 tree lhs = gimple_assign_lhs (stmt);
1336 tree inner_rhs = get_base_address (rhs);
1337 tree inner_lhs = get_base_address (lhs);
1338 bool rhs_free = false;
1339 bool lhs_free = false;
1346 /* Reads of parameter are expected to be free. */
1347 if (unmodified_parm (stmt, inner_rhs))
1350 /* When parameter is not SSA register because its address is taken
1351 and it is just copied into one, the statement will be completely
1352 free after inlining (we will copy propagate backward). */
1353 if (rhs_free && is_gimple_reg (lhs))
1356 /* Reads of parameters passed by reference
1357 expected to be free (i.e. optimized out after inlining). */
1358 if (TREE_CODE(inner_rhs) == MEM_REF
1359 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0)))
1362 /* Copying parameter passed by reference into gimple register is
1363 probably also going to copy propagate, but we can't be quite
1365 if (rhs_free && is_gimple_reg (lhs))
1368 /* Writes to parameters, parameters passed by value and return value
1369 (either dirrectly or passed via invisible reference) are free.
1371 TODO: We ought to handle testcase like
1372 struct a {int a,b;};
1374 retrurnsturct (void)
1380 This translate into:
1395 For that we either need to copy ipa-split logic detecting writes
1397 if (TREE_CODE (inner_lhs) == PARM_DECL
1398 || TREE_CODE (inner_lhs) == RESULT_DECL
1399 || (TREE_CODE(inner_lhs) == MEM_REF
1400 && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0))
1401 || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
1402 && TREE_CODE (SSA_NAME_VAR
1403 (TREE_OPERAND (inner_lhs, 0)))
1407 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1409 if (lhs_free && rhs_free)
1419 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1420 predicates to the CFG edges. */
1423 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1424 struct inline_summary *summary,
1430 enum tree_code code, inverted_code;
1438 last = last_stmt (bb);
1440 || gimple_code (last) != GIMPLE_COND)
1442 if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1444 op = gimple_cond_lhs (last);
1445 /* TODO: handle conditionals like
1448 parm = unmodified_parm (last, op);
1451 index = ipa_get_param_decl_index (info, parm);
1454 code = gimple_cond_code (last);
1456 = invert_tree_comparison (code,
1457 HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1459 FOR_EACH_EDGE (e, ei, bb->succs)
1461 struct predicate p = add_condition (summary,
1463 e->flags & EDGE_TRUE_VALUE
1464 ? code : inverted_code,
1465 gimple_cond_rhs (last));
1466 e->aux = pool_alloc (edge_predicate_pool);
1467 *(struct predicate *)e->aux = p;
1471 if (TREE_CODE (op) != SSA_NAME)
1474 if (builtin_constant_p (op))
1478 Here we can predicate nonconstant_code. We can't
1479 really handle constant_code since we have no predicate
1480 for this and also the constant code is not known to be
1481 optimized away when inliner doen't see operand is constant.
1482 Other optimizers might think otherwise. */
1483 set_stmt = SSA_NAME_DEF_STMT (op);
1484 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1485 || gimple_call_num_args (set_stmt) != 1)
1487 op2 = gimple_call_arg (set_stmt, 0);
1488 base = get_base_address (op2);
1489 parm = unmodified_parm (set_stmt, base ? base : op2);
1492 index = ipa_get_param_decl_index (info, parm);
1495 if (gimple_cond_code (last) != NE_EXPR
1496 || !integer_zerop (gimple_cond_rhs (last)))
1498 FOR_EACH_EDGE (e, ei, bb->succs)
1499 if (e->flags & EDGE_FALSE_VALUE)
1501 struct predicate p = add_condition (summary,
1505 e->aux = pool_alloc (edge_predicate_pool);
1506 *(struct predicate *)e->aux = p;
1511 /* If BB ends by a switch we can turn into predicates, attach corresponding
1512 predicates to the CFG edges. */
1515 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1516 struct inline_summary *summary,
1528 last = last_stmt (bb);
1530 || gimple_code (last) != GIMPLE_SWITCH)
1532 op = gimple_switch_index (last);
1533 parm = unmodified_parm (last, op);
1536 index = ipa_get_param_decl_index (info, parm);
1540 FOR_EACH_EDGE (e, ei, bb->succs)
1542 e->aux = pool_alloc (edge_predicate_pool);
1543 *(struct predicate *)e->aux = false_predicate ();
1545 n = gimple_switch_num_labels(last);
1546 for (case_idx = 0; case_idx < n; ++case_idx)
1548 tree cl = gimple_switch_label (last, case_idx);
1552 e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1553 min = CASE_LOW (cl);
1554 max = CASE_HIGH (cl);
1556 /* For default we might want to construct predicate that none
1557 of cases is met, but it is bit hard to do not having negations
1558 of conditionals handy. */
1560 p = true_predicate ();
1562 p = add_condition (summary, index,
1567 struct predicate p1, p2;
1568 p1 = add_condition (summary, index,
1571 p2 = add_condition (summary, index,
1574 p = and_predicates (summary->conds, &p1, &p2);
1576 *(struct predicate *)e->aux
1577 = or_predicates (summary->conds, &p, (struct predicate *)e->aux);
1582 /* For each BB in NODE attach to its AUX pointer predicate under
1583 which it is executable. */
1586 compute_bb_predicates (struct cgraph_node *node,
1587 struct ipa_node_params *parms_info,
1588 struct inline_summary *summary)
1590 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1594 FOR_EACH_BB_FN (bb, my_function)
1596 set_cond_stmt_execution_predicate (parms_info, summary, bb);
1597 set_switch_stmt_execution_predicate (parms_info, summary, bb);
1600 /* Entry block is always executable. */
1601 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1602 = pool_alloc (edge_predicate_pool);
1603 *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1604 = true_predicate ();
1606 /* A simple dataflow propagation of predicates forward in the CFG.
1607 TODO: work in reverse postorder. */
1611 FOR_EACH_BB_FN (bb, my_function)
1613 struct predicate p = false_predicate ();
1616 FOR_EACH_EDGE (e, ei, bb->preds)
1620 struct predicate this_bb_predicate
1621 = *(struct predicate *)e->src->aux;
1624 = and_predicates (summary->conds, &this_bb_predicate,
1625 (struct predicate *)e->aux);
1626 p = or_predicates (summary->conds, &p, &this_bb_predicate);
1627 if (true_predicate_p (&p))
1631 if (false_predicate_p (&p))
1632 gcc_assert (!bb->aux);
1638 bb->aux = pool_alloc (edge_predicate_pool);
1639 *((struct predicate *)bb->aux) = p;
1641 else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
1644 *((struct predicate *)bb->aux) = p;
1652 /* We keep info about constantness of SSA names. */
1654 typedef struct predicate predicate_t;
1655 DEF_VEC_O (predicate_t);
1656 DEF_VEC_ALLOC_O (predicate_t, heap);
1659 /* Return predicate specifying when the STMT might have result that is not
1660 a compile time constant. */
1662 static struct predicate
1663 will_be_nonconstant_predicate (struct ipa_node_params *info,
1664 struct inline_summary *summary,
1666 VEC (predicate_t, heap) *nonconstant_names)
1669 struct predicate p = true_predicate ();
1672 struct predicate op_non_const;
1675 /* What statments might be optimized away
1676 when their arguments are constant
1677 TODO: also trivial builtins.
1678 builtin_constant_p is already handled later. */
1679 if (gimple_code (stmt) != GIMPLE_ASSIGN
1680 && gimple_code (stmt) != GIMPLE_COND
1681 && gimple_code (stmt) != GIMPLE_SWITCH)
1684 /* Stores will stay anyway. */
1685 if (gimple_vdef (stmt))
1688 is_load = gimple_vuse (stmt) != NULL;
1690 /* Loads can be optimized when the value is known. */
1693 tree op = gimple_assign_rhs1 (stmt);
1694 tree base = get_base_address (op);
1697 gcc_assert (gimple_assign_single_p (stmt));
1700 parm = unmodified_parm (stmt, base);
1703 if (ipa_get_param_decl_index (info, parm) < 0)
1707 /* See if we understand all operands before we start
1708 adding conditionals. */
1709 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1711 tree parm = unmodified_parm (stmt, use);
1712 /* For arguments we can build a condition. */
1713 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1715 if (TREE_CODE (use) != SSA_NAME)
1717 /* If we know when operand is constant,
1718 we still can say something useful. */
1719 if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names,
1720 SSA_NAME_VERSION (use))))
1724 op_non_const = false_predicate ();
1727 tree parm = unmodified_parm
1728 (stmt, get_base_address (gimple_assign_rhs1 (stmt)));
1729 p = add_condition (summary,
1730 ipa_get_param_decl_index (info, parm),
1732 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1734 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1736 tree parm = unmodified_parm (stmt, use);
1737 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1738 p = add_condition (summary,
1739 ipa_get_param_decl_index (info, parm),
1742 p = *VEC_index (predicate_t, nonconstant_names,
1743 SSA_NAME_VERSION (use));
1744 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1746 if (gimple_code (stmt) == GIMPLE_ASSIGN
1747 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
1748 VEC_replace (predicate_t, nonconstant_names,
1749 SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const);
1750 return op_non_const;
1753 struct record_modified_bb_info
1759 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
1760 set except for info->stmt. */
1763 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef,
1766 struct record_modified_bb_info *info = (struct record_modified_bb_info *) data;
1767 if (SSA_NAME_DEF_STMT (vdef) == info->stmt)
1769 bitmap_set_bit (info->bb_set,
1770 SSA_NAME_IS_DEFAULT_DEF (vdef)
1771 ? ENTRY_BLOCK_PTR->index : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index);
1775 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
1776 will change since last invocation of STMT.
1778 Value 0 is reserved for compile time invariants.
1779 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
1780 ought to be REG_BR_PROB_BASE / estimated_iters. */
1783 param_change_prob (gimple stmt, int i)
1785 tree op = gimple_call_arg (stmt, i);
1786 basic_block bb = gimple_bb (stmt);
1789 if (is_gimple_min_invariant (op))
1791 /* We would have to do non-trivial analysis to really work out what
1792 is the probability of value to change (i.e. when init statement
1793 is in a sibling loop of the call).
1795 We do an conservative estimate: when call is executed N times more often
1796 than the statement defining value, we take the frequency 1/N. */
1797 if (TREE_CODE (op) == SSA_NAME)
1802 return REG_BR_PROB_BASE;
1804 if (SSA_NAME_IS_DEFAULT_DEF (op))
1805 init_freq = ENTRY_BLOCK_PTR->frequency;
1807 init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency;
1811 if (init_freq < bb->frequency)
1812 return MAX ((init_freq * REG_BR_PROB_BASE +
1813 bb->frequency / 2) / bb->frequency, 1);
1815 return REG_BR_PROB_BASE;
1818 base = get_base_address (op);
1823 struct record_modified_bb_info info;
1827 if (const_value_known_p (base))
1830 return REG_BR_PROB_BASE;
1831 ao_ref_init (&refd, op);
1833 info.bb_set = BITMAP_ALLOC (NULL);
1834 walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
1836 if (bitmap_bit_p (info.bb_set, bb->index))
1838 BITMAP_FREE (info.bb_set);
1839 return REG_BR_PROB_BASE;
1842 /* Assume that every memory is initialized at entry.
1843 TODO: Can we easilly determine if value is always defined
1844 and thus we may skip entry block? */
1845 if (ENTRY_BLOCK_PTR->frequency)
1846 max = ENTRY_BLOCK_PTR->frequency;
1850 EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi)
1851 max = MIN (max, BASIC_BLOCK (index)->frequency);
1853 BITMAP_FREE (info.bb_set);
1854 if (max < bb->frequency)
1855 return MAX ((max * REG_BR_PROB_BASE +
1856 bb->frequency / 2) / bb->frequency, 1);
1858 return REG_BR_PROB_BASE;
1860 return REG_BR_PROB_BASE;
1864 /* Compute function body size parameters for NODE.
1865 When EARLY is true, we compute only simple summaries without
1866 non-trivial predicates to drive the early inliner. */
1869 estimate_function_body_sizes (struct cgraph_node *node, bool early)
1872 /* Estimate static overhead for function prologue/epilogue and alignment. */
1874 /* Benefits are scaled by probability of elimination that is in range
1877 gimple_stmt_iterator bsi;
1878 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1880 struct inline_summary *info = inline_summary (node);
1881 struct predicate bb_predicate;
1882 struct ipa_node_params *parms_info = NULL;
1883 VEC (predicate_t, heap) *nonconstant_names = NULL;
1885 if (ipa_node_params_vector && !early && optimize)
1887 parms_info = IPA_NODE_REF (node);
1888 VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names,
1889 VEC_length (tree, SSANAMES (my_function)));
1897 fprintf (dump_file, "\nAnalyzing function body size: %s\n",
1898 cgraph_node_name (node));
1900 /* When we run into maximal number of entries, we assign everything to the
1901 constant truth case. Be sure to have it in list. */
1902 bb_predicate = true_predicate ();
1903 account_size_time (info, 0, 0, &bb_predicate);
1905 bb_predicate = not_inlined_predicate ();
1906 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
1908 gcc_assert (my_function && my_function->cfg);
1910 compute_bb_predicates (node, parms_info, info);
1911 FOR_EACH_BB_FN (bb, my_function)
1913 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1915 /* TODO: Obviously predicates can be propagated down across CFG. */
1919 bb_predicate = *(struct predicate *)bb->aux;
1921 bb_predicate = false_predicate ();
1924 bb_predicate = true_predicate ();
1926 if (dump_file && (dump_flags & TDF_DETAILS))
1928 fprintf (dump_file, "\n BB %i predicate:", bb->index);
1929 dump_predicate (dump_file, info->conds, &bb_predicate);
1932 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1934 gimple stmt = gsi_stmt (bsi);
1935 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1936 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1938 struct predicate will_be_nonconstant;
1940 if (dump_file && (dump_flags & TDF_DETAILS))
1942 fprintf (dump_file, " ");
1943 print_gimple_stmt (dump_file, stmt, 0, 0);
1944 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1945 ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
1948 if (is_gimple_call (stmt))
1950 struct cgraph_edge *edge = cgraph_edge (node, stmt);
1951 struct inline_edge_summary *es = inline_edge_summary (edge);
1953 /* Special case: results of BUILT_IN_CONSTANT_P will be always
1954 resolved as constant. We however don't want to optimize
1955 out the cgraph edges. */
1956 if (nonconstant_names
1957 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
1958 && gimple_call_lhs (stmt)
1959 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
1961 struct predicate false_p = false_predicate ();
1962 VEC_replace (predicate_t, nonconstant_names,
1963 SSA_NAME_VERSION (gimple_call_lhs (stmt)),
1966 if (ipa_node_params_vector)
1968 int count = gimple_call_num_args (stmt);
1972 VEC_safe_grow_cleared (inline_param_summary_t, heap,
1974 for (i = 0; i < count; i++)
1976 int prob = param_change_prob (stmt, i);
1977 gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
1978 VEC_index (inline_param_summary_t,
1979 es->param, i)->change_prob = prob;
1983 es->call_stmt_size = this_size;
1984 es->call_stmt_time = this_time;
1985 es->loop_depth = bb->loop_depth;
1986 edge_set_predicate (edge, &bb_predicate);
1989 /* TODO: When conditional jump or swithc is known to be constant, but
1990 we did not translate it into the predicates, we really can account
1991 just maximum of the possible paths. */
1994 = will_be_nonconstant_predicate (parms_info, info,
1995 stmt, nonconstant_names);
1996 if (this_time || this_size)
2004 prob = eliminated_by_inlining_prob (stmt);
2005 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
2006 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
2007 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
2008 fprintf (dump_file, "\t\tWill be eliminated by inlining\n");
2011 p = and_predicates (info->conds, &bb_predicate,
2012 &will_be_nonconstant);
2014 p = true_predicate ();
2016 /* We account everything but the calls. Calls have their own
2017 size/time info attached to cgraph edges. This is neccesary
2018 in order to make the cost disappear after inlining. */
2019 if (!is_gimple_call (stmt))
2023 struct predicate ip = not_inlined_predicate ();
2024 ip = and_predicates (info->conds, &ip, &p);
2025 account_size_time (info, this_size * prob,
2026 this_time * prob, &ip);
2029 account_size_time (info, this_size * (2 - prob),
2030 this_time * (2 - prob), &p);
2033 gcc_assert (time >= 0);
2034 gcc_assert (size >= 0);
2038 FOR_ALL_BB_FN (bb, my_function)
2044 pool_free (edge_predicate_pool, bb->aux);
2046 FOR_EACH_EDGE (e, ei, bb->succs)
2049 pool_free (edge_predicate_pool, e->aux);
2053 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2054 if (time > MAX_TIME)
2056 inline_summary (node)->self_time = time;
2057 inline_summary (node)->self_size = size;
2058 VEC_free (predicate_t, heap, nonconstant_names);
2061 fprintf (dump_file, "\n");
2062 dump_inline_summary (dump_file, node);
2067 /* Compute parameters of functions used by inliner.
2068 EARLY is true when we compute parameters for the early inliner */
2071 compute_inline_parameters (struct cgraph_node *node, bool early)
2073 HOST_WIDE_INT self_stack_size;
2074 struct cgraph_edge *e;
2075 struct inline_summary *info;
2076 tree old_decl = current_function_decl;
2078 gcc_assert (!node->global.inlined_to);
2080 inline_summary_alloc ();
2082 info = inline_summary (node);
2083 reset_inline_summary (node);
2085 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2086 Once this happen, we will need to more curefully predict call
2088 if (node->thunk.thunk_p)
2090 struct inline_edge_summary *es = inline_edge_summary (node->callees);
2091 struct predicate t = true_predicate ();
2093 info->inlinable = 0;
2094 node->callees->call_stmt_cannot_inline_p = true;
2095 node->local.can_change_signature = false;
2096 es->call_stmt_time = 1;
2097 es->call_stmt_size = 1;
2098 account_size_time (info, 0, 0, &t);
2102 /* Even is_gimple_min_invariant rely on current_function_decl. */
2103 current_function_decl = node->decl;
2104 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2106 /* Estimate the stack size for the function if we're optimizing. */
2107 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
2108 info->estimated_self_stack_size = self_stack_size;
2109 info->estimated_stack_size = self_stack_size;
2110 info->stack_frame_offset = 0;
2112 /* Can this function be inlined at all? */
2113 info->inlinable = tree_inlinable_function_p (node->decl);
2115 /* Type attributes can use parameter indices to describe them. */
2116 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
2117 node->local.can_change_signature = false;
2120 /* Otherwise, inlinable functions always can change signature. */
2121 if (info->inlinable)
2122 node->local.can_change_signature = true;
2125 /* Functions calling builtin_apply can not change signature. */
2126 for (e = node->callees; e; e = e->next_callee)
2128 tree cdecl = e->callee->decl;
2129 if (DECL_BUILT_IN (cdecl)
2130 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2131 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2132 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
2135 node->local.can_change_signature = !e;
2138 estimate_function_body_sizes (node, early);
2140 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2141 info->time = info->self_time;
2142 info->size = info->self_size;
2143 info->stack_frame_offset = 0;
2144 info->estimated_stack_size = info->estimated_self_stack_size;
2145 current_function_decl = old_decl;
2150 /* Compute parameters of functions used by inliner using
2151 current_function_decl. */
2154 compute_inline_parameters_for_current (void)
2156 compute_inline_parameters (cgraph_get_node (current_function_decl), true);
2160 struct gimple_opt_pass pass_inline_parameters =
2164 "inline_param", /* name */
2166 compute_inline_parameters_for_current,/* execute */
2169 0, /* static_pass_number */
2170 TV_INLINE_HEURISTICS, /* tv_id */
2171 0, /* properties_required */
2172 0, /* properties_provided */
2173 0, /* properties_destroyed */
2174 0, /* todo_flags_start */
2175 0 /* todo_flags_finish */
2180 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2183 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
2186 struct inline_edge_summary *es = inline_edge_summary (e);
2187 *size += es->call_stmt_size * INLINE_SIZE_SCALE;
2188 *time += (es->call_stmt_time * prob / REG_BR_PROB_BASE
2189 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
2190 if (*time > MAX_TIME * INLINE_TIME_SCALE)
2191 *time = MAX_TIME * INLINE_TIME_SCALE;
2195 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2199 estimate_edge_devirt_benefit (struct cgraph_edge *ie,
2200 int *size, int *time, int prob,
2201 VEC (tree, heap) *known_vals,
2202 VEC (tree, heap) *known_binfos)
2205 struct cgraph_node *callee;
2206 struct inline_summary *isummary;
2207 int edge_size = 0, edge_time = 0;
2209 if (!known_vals || !known_binfos)
2212 target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos);
2216 /* Account for difference in cost between indirect and direct calls. */
2217 *size -= ((eni_size_weights.indirect_call_cost - eni_size_weights.call_cost)
2218 * INLINE_SIZE_SCALE);
2219 *time -= ((eni_time_weights.indirect_call_cost - eni_time_weights.call_cost)
2220 * INLINE_TIME_SCALE * prob / REG_BR_PROB_BASE);
2222 callee = cgraph_get_node (target);
2223 if (!callee || !callee->analyzed)
2225 isummary = inline_summary (callee);
2226 if (!isummary->inlinable)
2229 estimate_edge_size_and_time (ie, &edge_size, &edge_time, prob);
2231 /* Count benefit only from functions that definitely will be inlined
2232 if additional context from NODE's caller were available. */
2233 if (edge_size >= isummary->size * INLINE_SIZE_SCALE)
2235 /* Subtract size and time that we added for edge IE. */
2239 /* Subtract benefit from inlining devirtualized call. */
2240 *size -= edge_size - isummary->size * INLINE_SIZE_SCALE;
2241 *time -= edge_time - (isummary->time * INLINE_TIME_SCALE * prob
2242 / REG_BR_PROB_BASE);
2244 /* TODO: estimate benefit from optimizing CALLEE's body provided
2245 additional context from IE call site.
2246 For insipiration see ipa-cp.c: devirtualization_time_bonus(). */
2251 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
2252 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
2256 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
2257 clause_t possible_truths,
2258 VEC (tree, heap) *known_vals,
2259 VEC (tree, heap) *known_binfos)
2261 struct cgraph_edge *e;
2262 for (e = node->callees; e; e = e->next_callee)
2264 struct inline_edge_summary *es = inline_edge_summary (e);
2265 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2267 if (e->inline_failed)
2269 /* Predicates of calls shall not use NOT_CHANGED codes,
2270 sowe do not need to compute probabilities. */
2271 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2274 estimate_calls_size_and_time (e->callee, size, time,
2276 known_vals, known_binfos);
2279 for (e = node->indirect_calls; e; e = e->next_callee)
2281 struct inline_edge_summary *es = inline_edge_summary (e);
2282 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2284 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2285 estimate_edge_devirt_benefit (e, size, time, REG_BR_PROB_BASE,
2286 known_vals, known_binfos);
2292 /* Estimate size and time needed to execute NODE assuming
2293 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
2294 about NODE's arguments. */
2297 estimate_node_size_and_time (struct cgraph_node *node,
2298 clause_t possible_truths,
2299 VEC (tree, heap) *known_vals,
2300 VEC (tree, heap) *known_binfos,
2301 int *ret_size, int *ret_time,
2302 VEC (inline_param_summary_t, heap)
2303 *inline_param_summary)
2305 struct inline_summary *info = inline_summary (node);
2307 int size = 0, time = 0;
2311 && (dump_flags & TDF_DETAILS))
2314 fprintf (dump_file, " Estimating body: %s/%i\n"
2315 " Known to be false: ",
2316 cgraph_node_name (node),
2319 for (i = predicate_not_inlined_condition;
2320 i < (predicate_first_dynamic_condition
2321 + (int)VEC_length (condition, info->conds)); i++)
2322 if (!(possible_truths & (1 << i)))
2325 fprintf (dump_file, ", ");
2327 dump_condition (dump_file, info->conds, i);
2331 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2332 if (evaluate_predicate (&e->predicate, possible_truths))
2335 if (!inline_param_summary)
2339 int prob = predicate_probability (info->conds,
2342 inline_param_summary);
2343 time += e->time * prob / REG_BR_PROB_BASE;
2348 if (time > MAX_TIME * INLINE_TIME_SCALE)
2349 time = MAX_TIME * INLINE_TIME_SCALE;
2351 estimate_calls_size_and_time (node, &size, &time, possible_truths,
2352 known_vals, known_binfos);
2353 time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2354 size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2358 && (dump_flags & TDF_DETAILS))
2359 fprintf (dump_file, "\n size:%i time:%i\n", size, time);
2368 /* Estimate size and time needed to execute callee of EDGE assuming that
2369 parameters known to be constant at caller of EDGE are propagated.
2370 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
2371 and types for parameters. */
2374 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
2375 VEC (tree, heap) *known_vals,
2376 VEC (tree, heap) *known_binfos,
2377 int *ret_size, int *ret_time)
2381 clause = evaluate_conditions_for_known_args (node, false, known_vals);
2382 estimate_node_size_and_time (node, clause, known_vals, known_binfos,
2388 /* Translate all conditions from callee representation into caller
2389 representation and symbolically evaluate predicate P into new predicate.
2391 INFO is inline_summary of function we are adding predicate into,
2392 CALLEE_INFO is summary of function predicate P is from. OPERAND_MAP is
2393 array giving callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is
2394 clausule of all callee conditions that may be true in caller context.
2395 TOPLEV_PREDICATE is predicate under which callee is executed. */
2397 static struct predicate
2398 remap_predicate (struct inline_summary *info,
2399 struct inline_summary *callee_info,
2400 struct predicate *p,
2401 VEC (int, heap) *operand_map,
2402 clause_t possible_truths,
2403 struct predicate *toplev_predicate)
2406 struct predicate out = true_predicate ();
2408 /* True predicate is easy. */
2409 if (true_predicate_p (p))
2410 return *toplev_predicate;
2411 for (i = 0; p->clause[i]; i++)
2413 clause_t clause = p->clause[i];
2415 struct predicate clause_predicate = false_predicate ();
2417 gcc_assert (i < MAX_CLAUSES);
2419 for (cond = 0; cond < NUM_CONDITIONS; cond ++)
2420 /* Do we have condition we can't disprove? */
2421 if (clause & possible_truths & (1 << cond))
2423 struct predicate cond_predicate;
2424 /* Work out if the condition can translate to predicate in the
2425 inlined function. */
2426 if (cond >= predicate_first_dynamic_condition)
2428 struct condition *c;
2430 c = VEC_index (condition, callee_info->conds,
2431 cond - predicate_first_dynamic_condition);
2432 /* See if we can remap condition operand to caller's operand.
2433 Otherwise give up. */
2435 || (int)VEC_length (int, operand_map) <= c->operand_num
2436 || VEC_index (int, operand_map, c->operand_num) == -1)
2437 cond_predicate = true_predicate ();
2439 cond_predicate = add_condition (info,
2440 VEC_index (int, operand_map,
2444 /* Fixed conditions remains same, construct single
2445 condition predicate. */
2448 cond_predicate.clause[0] = 1 << cond;
2449 cond_predicate.clause[1] = 0;
2451 clause_predicate = or_predicates (info->conds, &clause_predicate,
2454 out = and_predicates (info->conds, &out, &clause_predicate);
2456 return and_predicates (info->conds, &out, toplev_predicate);
2460 /* Update summary information of inline clones after inlining.
2461 Compute peak stack usage. */
2464 inline_update_callee_summaries (struct cgraph_node *node,
2467 struct cgraph_edge *e;
2468 struct inline_summary *callee_info = inline_summary (node);
2469 struct inline_summary *caller_info = inline_summary (node->callers->caller);
2472 callee_info->stack_frame_offset
2473 = caller_info->stack_frame_offset
2474 + caller_info->estimated_self_stack_size;
2475 peak = callee_info->stack_frame_offset
2476 + callee_info->estimated_self_stack_size;
2477 if (inline_summary (node->global.inlined_to)->estimated_stack_size
2479 inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
2480 cgraph_propagate_frequency (node);
2481 for (e = node->callees; e; e = e->next_callee)
2483 if (!e->inline_failed)
2484 inline_update_callee_summaries (e->callee, depth);
2485 inline_edge_summary (e)->loop_depth += depth;
2487 for (e = node->indirect_calls; e; e = e->next_callee)
2488 inline_edge_summary (e)->loop_depth += depth;
2491 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
2492 When functoin A is inlined in B and A calls C with parameter that
2493 changes with probability PROB1 and C is known to be passthroug
2494 of argument if B that change with probability PROB2, the probability
2495 of change is now PROB1*PROB2. */
2498 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
2499 struct cgraph_edge *edge)
2501 if (ipa_node_params_vector)
2504 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2505 struct inline_edge_summary *es = inline_edge_summary (edge);
2506 struct inline_edge_summary *inlined_es
2507 = inline_edge_summary (inlined_edge);
2509 for (i = 0; i < ipa_get_cs_argument_count (args); i++)
2511 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2512 if (jfunc->type == IPA_JF_PASS_THROUGH
2513 && (jfunc->value.pass_through.formal_id
2514 < (int) VEC_length (inline_param_summary_t,
2515 inlined_es->param)))
2517 int prob1 = VEC_index (inline_param_summary_t,
2518 es->param, i)->change_prob;
2519 int prob2 = VEC_index
2520 (inline_param_summary_t,
2522 jfunc->value.pass_through.formal_id)->change_prob;
2523 int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2)
2524 / REG_BR_PROB_BASE);
2526 if (prob1 && prob2 && !prob)
2529 VEC_index (inline_param_summary_t,
2530 es->param, i)->change_prob = prob;
2536 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
2538 Remap predicates of callees of NODE. Rest of arguments match
2541 Also update change probabilities. */
2544 remap_edge_summaries (struct cgraph_edge *inlined_edge,
2545 struct cgraph_node *node,
2546 struct inline_summary *info,
2547 struct inline_summary *callee_info,
2548 VEC (int, heap) *operand_map,
2549 clause_t possible_truths,
2550 struct predicate *toplev_predicate)
2552 struct cgraph_edge *e;
2553 for (e = node->callees; e; e = e->next_callee)
2555 struct inline_edge_summary *es = inline_edge_summary (e);
2558 if (e->inline_failed)
2560 remap_edge_change_prob (inlined_edge, e);
2564 p = remap_predicate (info, callee_info,
2565 es->predicate, operand_map, possible_truths,
2567 edge_set_predicate (e, &p);
2568 /* TODO: We should remove the edge for code that will be
2569 optimized out, but we need to keep verifiers and tree-inline
2570 happy. Make it cold for now. */
2571 if (false_predicate_p (&p))
2578 edge_set_predicate (e, toplev_predicate);
2581 remap_edge_summaries (inlined_edge, e->callee, info, callee_info,
2582 operand_map, possible_truths, toplev_predicate);
2584 for (e = node->indirect_calls; e; e = e->next_callee)
2586 struct inline_edge_summary *es = inline_edge_summary (e);
2589 remap_edge_change_prob (inlined_edge, e);
2592 p = remap_predicate (info, callee_info,
2593 es->predicate, operand_map, possible_truths,
2595 edge_set_predicate (e, &p);
2596 /* TODO: We should remove the edge for code that will be optimized
2597 out, but we need to keep verifiers and tree-inline happy.
2598 Make it cold for now. */
2599 if (false_predicate_p (&p))
2606 edge_set_predicate (e, toplev_predicate);
2611 /* We inlined EDGE. Update summary of the function we inlined into. */
2614 inline_merge_summary (struct cgraph_edge *edge)
2616 struct inline_summary *callee_info = inline_summary (edge->callee);
2617 struct cgraph_node *to = (edge->caller->global.inlined_to
2618 ? edge->caller->global.inlined_to : edge->caller);
2619 struct inline_summary *info = inline_summary (to);
2620 clause_t clause = 0; /* not_inline is known to be false. */
2622 VEC (int, heap) *operand_map = NULL;
2624 struct predicate toplev_predicate;
2625 struct predicate true_p = true_predicate ();
2626 struct inline_edge_summary *es = inline_edge_summary (edge);
2629 toplev_predicate = *es->predicate;
2631 toplev_predicate = true_predicate ();
2633 if (ipa_node_params_vector && callee_info->conds)
2635 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2636 int count = ipa_get_cs_argument_count (args);
2639 evaluate_properties_for_edge (edge, true, &clause, NULL, NULL);
2641 VEC_safe_grow_cleared (int, heap, operand_map, count);
2642 for (i = 0; i < count; i++)
2644 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2646 /* TODO: handle non-NOPs when merging. */
2647 if (jfunc->type == IPA_JF_PASS_THROUGH
2648 && jfunc->value.pass_through.operation == NOP_EXPR)
2649 map = jfunc->value.pass_through.formal_id;
2650 VEC_replace (int, operand_map, i, map);
2651 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
2654 for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
2656 struct predicate p = remap_predicate (info, callee_info,
2657 &e->predicate, operand_map, clause,
2659 if (!false_predicate_p (&p))
2661 gcov_type add_time = ((gcov_type)e->time * edge->frequency
2662 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2663 int prob = predicate_probability (callee_info->conds,
2666 add_time = add_time * prob / REG_BR_PROB_BASE;
2667 if (add_time > MAX_TIME * INLINE_TIME_SCALE)
2668 add_time = MAX_TIME * INLINE_TIME_SCALE;
2669 if (prob != REG_BR_PROB_BASE
2670 && dump_file && (dump_flags & TDF_DETAILS))
2672 fprintf (dump_file, "\t\tScaling time by probability:%f\n",
2673 (double)prob / REG_BR_PROB_BASE);
2675 account_size_time (info, e->size, add_time, &p);
2678 remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
2679 clause, &toplev_predicate);
2682 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2683 info->size += e->size, info->time += e->time;
2684 estimate_calls_size_and_time (to, &info->size, &info->time,
2685 ~(clause_t)(1 << predicate_false_condition),
2688 inline_update_callee_summaries (edge->callee,
2689 inline_edge_summary (edge)->loop_depth);
2691 /* We do not maintain predicates of inlined edges, free it. */
2692 edge_set_predicate (edge, &true_p);
2693 /* Similarly remove param summaries. */
2694 VEC_free (inline_param_summary_t, heap, es->param);
2696 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2697 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2701 /* Estimate the time cost for the caller when inlining EDGE.
2702 Only to be called via estimate_edge_time, that handles the
2705 When caching, also update the cache entry. Compute both time and
2706 size, since we always need both metrics eventually. */
2709 do_estimate_edge_time (struct cgraph_edge *edge)
2714 struct cgraph_node *callee;
2716 VEC (tree, heap) *known_vals;
2717 VEC (tree, heap) *known_binfos;
2718 struct inline_edge_summary *es = inline_edge_summary (edge);
2720 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
2722 gcc_checking_assert (edge->inline_failed);
2723 evaluate_properties_for_edge (edge, true,
2724 &clause, &known_vals, &known_binfos);
2725 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
2726 &size, &time, es->param);
2727 VEC_free (tree, heap, known_vals);
2728 VEC_free (tree, heap, known_binfos);
2730 ret = (((gcov_type)time
2731 - es->call_stmt_time) * edge->frequency
2732 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2734 /* When caching, update the cache entry. */
2735 if (edge_growth_cache)
2738 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
2740 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
2741 cgraph_edge_max_uid);
2742 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
2745 ret_size = size - es->call_stmt_size;
2746 gcc_checking_assert (es->call_stmt_size);
2747 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
2748 = ret_size + (ret_size >= 0);
2754 /* Estimate the growth of the caller when inlining EDGE.
2755 Only to be called via estimate_edge_size. */
2758 do_estimate_edge_growth (struct cgraph_edge *edge)
2761 struct cgraph_node *callee;
2763 VEC (tree, heap) *known_vals;
2764 VEC (tree, heap) *known_binfos;
2766 /* When we do caching, use do_estimate_edge_time to populate the entry. */
2768 if (edge_growth_cache)
2770 do_estimate_edge_time (edge);
2771 size = VEC_index (edge_growth_cache_entry,
2774 gcc_checking_assert (size);
2775 return size - (size > 0);
2778 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
2780 /* Early inliner runs without caching, go ahead and do the dirty work. */
2781 gcc_checking_assert (edge->inline_failed);
2782 evaluate_properties_for_edge (edge, true,
2783 &clause, &known_vals, &known_binfos);
2784 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
2786 VEC_free (tree, heap, known_vals);
2787 VEC_free (tree, heap, known_binfos);
2788 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
2789 return size - inline_edge_summary (edge)->call_stmt_size;
2793 /* Estimate self time of the function NODE after inlining EDGE. */
2796 estimate_time_after_inlining (struct cgraph_node *node,
2797 struct cgraph_edge *edge)
2799 struct inline_edge_summary *es = inline_edge_summary (edge);
2800 if (!es->predicate || !false_predicate_p (es->predicate))
2802 gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
2805 if (time > MAX_TIME)
2809 return inline_summary (node)->time;
2813 /* Estimate the size of NODE after inlining EDGE which should be an
2814 edge to either NODE or a call inlined into NODE. */
2817 estimate_size_after_inlining (struct cgraph_node *node,
2818 struct cgraph_edge *edge)
2820 struct inline_edge_summary *es = inline_edge_summary (edge);
2821 if (!es->predicate || !false_predicate_p (es->predicate))
2823 int size = inline_summary (node)->size + estimate_edge_growth (edge);
2824 gcc_assert (size >= 0);
2827 return inline_summary (node)->size;
2833 bool self_recursive;
2838 /* Worker for do_estimate_growth. Collect growth for all callers. */
2841 do_estimate_growth_1 (struct cgraph_node *node, void *data)
2843 struct cgraph_edge *e;
2844 struct growth_data *d = (struct growth_data *) data;
2846 for (e = node->callers; e; e = e->next_caller)
2848 gcc_checking_assert (e->inline_failed);
2850 if (e->caller == node
2851 || (e->caller->global.inlined_to
2852 && e->caller->global.inlined_to == node))
2853 d->self_recursive = true;
2854 d->growth += estimate_edge_growth (e);
2860 /* Estimate the growth caused by inlining NODE into all callees. */
2863 do_estimate_growth (struct cgraph_node *node)
2865 struct growth_data d = {0, false};
2866 struct inline_summary *info = inline_summary (node);
2868 cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
2870 /* For self recursive functions the growth estimation really should be
2871 infinity. We don't want to return very large values because the growth
2872 plays various roles in badness computation fractions. Be sure to not
2873 return zero or negative growths. */
2874 if (d.self_recursive)
2875 d.growth = d.growth < info->size ? info->size : d.growth;
2878 if (!DECL_EXTERNAL (node->decl)
2879 && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
2880 d.growth -= info->size;
2881 /* COMDAT functions are very often not shared across multiple units
2882 since they come from various template instantiations.
2883 Take this into account. */
2884 else if (DECL_COMDAT (node->decl)
2885 && cgraph_can_remove_if_no_direct_calls_p (node))
2886 d.growth -= (info->size
2887 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
2891 if (node_growth_cache)
2893 if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2894 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2895 VEC_replace (int, node_growth_cache, node->uid,
2896 d.growth + (d.growth >= 0));
2902 /* This function performs intraprocedural analysis in NODE that is required to
2903 inline indirect calls. */
2906 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2908 ipa_analyze_node (node);
2909 if (dump_file && (dump_flags & TDF_DETAILS))
2911 ipa_print_node_params (dump_file, node);
2912 ipa_print_node_jump_functions (dump_file, node);
2917 /* Note function body size. */
2920 inline_analyze_function (struct cgraph_node *node)
2922 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2923 current_function_decl = node->decl;
2926 fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2927 cgraph_node_name (node), node->uid);
2928 if (optimize && !node->thunk.thunk_p)
2929 inline_indirect_intraprocedural_analysis (node);
2930 compute_inline_parameters (node, false);
2932 current_function_decl = NULL;
2937 /* Called when new function is inserted to callgraph late. */
2940 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2942 inline_analyze_function (node);
2946 /* Note function body size. */
2949 inline_generate_summary (void)
2951 struct cgraph_node *node;
2953 function_insertion_hook_holder =
2954 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2956 ipa_register_cgraph_hooks ();
2957 inline_free_summary ();
2959 FOR_EACH_DEFINED_FUNCTION (node)
2961 inline_analyze_function (node);
2965 /* Read predicate from IB. */
2967 static struct predicate
2968 read_predicate (struct lto_input_block *ib)
2970 struct predicate out;
2976 gcc_assert (k <= MAX_CLAUSES);
2977 clause = out.clause[k++] = streamer_read_uhwi (ib);
2981 /* Zero-initialize the remaining clauses in OUT. */
2982 while (k <= MAX_CLAUSES)
2983 out.clause[k++] = 0;
2989 /* Write inline summary for edge E to OB. */
2992 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2994 struct inline_edge_summary *es = inline_edge_summary (e);
2998 es->call_stmt_size = streamer_read_uhwi (ib);
2999 es->call_stmt_time = streamer_read_uhwi (ib);
3000 es->loop_depth = streamer_read_uhwi (ib);
3001 p = read_predicate (ib);
3002 edge_set_predicate (e, &p);
3003 length = streamer_read_uhwi (ib);
3006 VEC_safe_grow_cleared (inline_param_summary_t, heap, es->param, length);
3007 for (i = 0; i < length; i++)
3008 VEC_index (inline_param_summary_t, es->param, i)->change_prob
3009 = streamer_read_uhwi (ib);
3014 /* Stream in inline summaries from the section. */
3017 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
3020 const struct lto_function_header *header =
3021 (const struct lto_function_header *) data;
3022 const int32_t cfg_offset = sizeof (struct lto_function_header);
3023 const int32_t main_offset = cfg_offset + header->cfg_size;
3024 const int32_t string_offset = main_offset + header->main_size;
3025 struct data_in *data_in;
3026 struct lto_input_block ib;
3027 unsigned int i, count2, j;
3028 unsigned int f_count;
3030 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
3034 lto_data_in_create (file_data, (const char *) data + string_offset,
3035 header->string_size, NULL);
3036 f_count = streamer_read_uhwi (&ib);
3037 for (i = 0; i < f_count; i++)
3040 struct cgraph_node *node;
3041 struct inline_summary *info;
3042 lto_cgraph_encoder_t encoder;
3043 struct bitpack_d bp;
3044 struct cgraph_edge *e;
3046 index = streamer_read_uhwi (&ib);
3047 encoder = file_data->cgraph_node_encoder;
3048 node = lto_cgraph_encoder_deref (encoder, index);
3049 info = inline_summary (node);
3051 info->estimated_stack_size
3052 = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
3053 info->size = info->self_size = streamer_read_uhwi (&ib);
3054 info->time = info->self_time = streamer_read_uhwi (&ib);
3056 bp = streamer_read_bitpack (&ib);
3057 info->inlinable = bp_unpack_value (&bp, 1);
3059 count2 = streamer_read_uhwi (&ib);
3060 gcc_assert (!info->conds);
3061 for (j = 0; j < count2; j++)
3064 c.operand_num = streamer_read_uhwi (&ib);
3065 c.code = (enum tree_code) streamer_read_uhwi (&ib);
3066 c.val = stream_read_tree (&ib, data_in);
3067 VEC_safe_push (condition, gc, info->conds, &c);
3069 count2 = streamer_read_uhwi (&ib);
3070 gcc_assert (!info->entry);
3071 for (j = 0; j < count2; j++)
3073 struct size_time_entry e;
3075 e.size = streamer_read_uhwi (&ib);
3076 e.time = streamer_read_uhwi (&ib);
3077 e.predicate = read_predicate (&ib);
3079 VEC_safe_push (size_time_entry, gc, info->entry, &e);
3081 for (e = node->callees; e; e = e->next_callee)
3082 read_inline_edge_summary (&ib, e);
3083 for (e = node->indirect_calls; e; e = e->next_callee)
3084 read_inline_edge_summary (&ib, e);
3087 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
3089 lto_data_in_delete (data_in);
3093 /* Read inline summary. Jump functions are shared among ipa-cp
3094 and inliner, so when ipa-cp is active, we don't need to write them
3098 inline_read_summary (void)
3100 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
3101 struct lto_file_decl_data *file_data;
3104 inline_summary_alloc ();
3106 while ((file_data = file_data_vec[j++]))
3109 const char *data = lto_get_section_data (file_data,
3110 LTO_section_inline_summary,
3113 inline_read_section (file_data, data, len);
3115 /* Fatal error here. We do not want to support compiling ltrans units
3116 with different version of compiler or different flags than the WPA
3117 unit, so this should never happen. */
3118 fatal_error ("ipa inline summary is missing in input file");
3122 ipa_register_cgraph_hooks ();
3124 ipa_prop_read_jump_functions ();
3126 function_insertion_hook_holder =
3127 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3131 /* Write predicate P to OB. */
3134 write_predicate (struct output_block *ob, struct predicate *p)
3138 for (j = 0; p->clause[j]; j++)
3140 gcc_assert (j < MAX_CLAUSES);
3141 streamer_write_uhwi (ob, p->clause[j]);
3143 streamer_write_uhwi (ob, 0);
3147 /* Write inline summary for edge E to OB. */
3150 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
3152 struct inline_edge_summary *es = inline_edge_summary (e);
3155 streamer_write_uhwi (ob, es->call_stmt_size);
3156 streamer_write_uhwi (ob, es->call_stmt_time);
3157 streamer_write_uhwi (ob, es->loop_depth);
3158 write_predicate (ob, es->predicate);
3159 streamer_write_uhwi (ob, VEC_length (inline_param_summary_t, es->param));
3160 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param); i++)
3161 streamer_write_uhwi (ob, VEC_index (inline_param_summary_t,
3162 es->param, i)->change_prob);
3166 /* Write inline summary for node in SET.
3167 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3168 active, we don't need to write them twice. */
3171 inline_write_summary (cgraph_node_set set,
3172 varpool_node_set vset ATTRIBUTE_UNUSED)
3174 struct cgraph_node *node;
3175 struct output_block *ob = create_output_block (LTO_section_inline_summary);
3176 lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
3177 unsigned int count = 0;
3180 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3181 if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
3183 streamer_write_uhwi (ob, count);
3185 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3187 node = lto_cgraph_encoder_deref (encoder, i);
3190 struct inline_summary *info = inline_summary (node);
3191 struct bitpack_d bp;
3192 struct cgraph_edge *edge;
3195 struct condition *c;
3197 streamer_write_uhwi (ob, lto_cgraph_encoder_encode (encoder, node));
3198 streamer_write_hwi (ob, info->estimated_self_stack_size);
3199 streamer_write_hwi (ob, info->self_size);
3200 streamer_write_hwi (ob, info->self_time);
3201 bp = bitpack_create (ob->main_stream);
3202 bp_pack_value (&bp, info->inlinable, 1);
3203 streamer_write_bitpack (&bp);
3204 streamer_write_uhwi (ob, VEC_length (condition, info->conds));
3205 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
3207 streamer_write_uhwi (ob, c->operand_num);
3208 streamer_write_uhwi (ob, c->code);
3209 stream_write_tree (ob, c->val, true);
3211 streamer_write_uhwi (ob, VEC_length (size_time_entry, info->entry));
3213 VEC_iterate (size_time_entry, info->entry, i, e);
3216 streamer_write_uhwi (ob, e->size);
3217 streamer_write_uhwi (ob, e->time);
3218 write_predicate (ob, &e->predicate);
3220 for (edge = node->callees; edge; edge = edge->next_callee)
3221 write_inline_edge_summary (ob, edge);
3222 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
3223 write_inline_edge_summary (ob, edge);
3226 streamer_write_char_stream (ob->main_stream, 0);
3227 produce_asm (ob, NULL);
3228 destroy_output_block (ob);
3230 if (optimize && !flag_ipa_cp)
3231 ipa_prop_write_jump_functions (set);
3235 /* Release inline summary. */
3238 inline_free_summary (void)
3240 struct cgraph_node *node;
3241 FOR_EACH_DEFINED_FUNCTION (node)
3242 reset_inline_summary (node);
3243 if (function_insertion_hook_holder)
3244 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
3245 function_insertion_hook_holder = NULL;
3246 if (node_removal_hook_holder)
3247 cgraph_remove_node_removal_hook (node_removal_hook_holder);
3248 node_removal_hook_holder = NULL;
3249 if (edge_removal_hook_holder)
3250 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
3251 edge_removal_hook_holder = NULL;
3252 if (node_duplication_hook_holder)
3253 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
3254 node_duplication_hook_holder = NULL;
3255 if (edge_duplication_hook_holder)
3256 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3257 edge_duplication_hook_holder = NULL;
3258 VEC_free (inline_summary_t, gc, inline_summary_vec);
3259 inline_summary_vec = NULL;
3260 VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
3261 inline_edge_summary_vec = NULL;
3262 if (edge_predicate_pool)
3263 free_alloc_pool (edge_predicate_pool);
3264 edge_predicate_pool = 0;