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 in integer.
94 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_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
716 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
717 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
718 struct inline_summary *info = inline_summary (callee);
721 if (ipa_node_params_vector && info->conds)
723 struct ipa_node_params *parms_info;
724 struct ipa_edge_args *args = IPA_EDGE_REF (e);
725 struct inline_edge_summary *es = inline_edge_summary (e);
726 int i, count = ipa_get_cs_argument_count (args);
727 VEC (tree, heap) *known_vals = NULL;
729 if (e->caller->global.inlined_to)
730 parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
732 parms_info = IPA_NODE_REF (e->caller);
735 VEC_safe_grow_cleared (tree, heap, known_vals, count);
736 for (i = 0; i < count; i++)
738 tree cst = ipa_cst_from_jfunc (parms_info,
739 ipa_get_ith_jump_func (args, i));
741 VEC_replace (tree, known_vals, i, cst);
743 && !VEC_index (inline_param_summary_t,
746 VEC_replace (tree, known_vals, i, error_mark_node);
748 clause = evaluate_conditions_for_known_args (callee,
749 inline_p, known_vals);
750 VEC_free (tree, heap, known_vals);
753 for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
754 clause |= 1 << (i + predicate_first_dynamic_condition);
760 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
763 inline_summary_alloc (void)
765 if (!node_removal_hook_holder)
766 node_removal_hook_holder =
767 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
768 if (!edge_removal_hook_holder)
769 edge_removal_hook_holder =
770 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
771 if (!node_duplication_hook_holder)
772 node_duplication_hook_holder =
773 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
774 if (!edge_duplication_hook_holder)
775 edge_duplication_hook_holder =
776 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
778 if (VEC_length (inline_summary_t, inline_summary_vec)
779 <= (unsigned) cgraph_max_uid)
780 VEC_safe_grow_cleared (inline_summary_t, gc,
781 inline_summary_vec, cgraph_max_uid + 1);
782 if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec)
783 <= (unsigned) cgraph_edge_max_uid)
784 VEC_safe_grow_cleared (inline_edge_summary_t, heap,
785 inline_edge_summary_vec, cgraph_edge_max_uid + 1);
786 if (!edge_predicate_pool)
787 edge_predicate_pool = create_alloc_pool ("edge predicates",
788 sizeof (struct predicate),
792 /* Hook that is called by cgraph.c when a node is removed. */
795 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
797 struct inline_summary *info;
798 if (VEC_length (inline_summary_t, inline_summary_vec)
799 <= (unsigned)node->uid)
801 info = inline_summary (node);
802 reset_node_growth_cache (node);
803 VEC_free (condition, gc, info->conds);
804 VEC_free (size_time_entry, gc, info->entry);
807 memset (info, 0, sizeof (inline_summary_t));
811 /* Hook that is called by cgraph.c when a node is duplicated. */
814 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
815 ATTRIBUTE_UNUSED void *data)
817 struct inline_summary *info;
818 inline_summary_alloc ();
819 info = inline_summary (dst);
820 memcpy (info, inline_summary (src),
821 sizeof (struct inline_summary));
822 /* TODO: as an optimization, we may avoid copying conditions
823 that are known to be false or true. */
824 info->conds = VEC_copy (condition, gc, info->conds);
826 /* When there are any replacements in the function body, see if we can figure
827 out that something was optimized out. */
828 if (ipa_node_params_vector && dst->clone.tree_map)
830 VEC(size_time_entry,gc) *entry = info->entry;
831 /* Use SRC parm info since it may not be copied yet. */
832 struct ipa_node_params *parms_info = IPA_NODE_REF (src);
833 VEC (tree, heap) *known_vals = NULL;
834 int count = ipa_get_param_count (parms_info);
836 clause_t possible_truths;
837 struct predicate true_pred = true_predicate ();
839 int optimized_out_size = 0;
840 gcov_type optimized_out_time = 0;
841 bool inlined_to_p = false;
842 struct cgraph_edge *edge;
845 VEC_safe_grow_cleared (tree, heap, known_vals, count);
846 for (i = 0; i < count; i++)
848 tree t = ipa_get_param (parms_info, i);
849 struct ipa_replace_map *r;
852 VEC_iterate (ipa_replace_map_p, dst->clone.tree_map, j, r);
859 VEC_replace (tree, known_vals, i, r->new_tree);
864 possible_truths = evaluate_conditions_for_known_args (dst,
866 VEC_free (tree, heap, known_vals);
868 account_size_time (info, 0, 0, &true_pred);
870 /* Remap size_time vectors.
871 Simplify the predicate by prunning out alternatives that are known
873 TODO: as on optimization, we can also eliminate conditions known
875 for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
877 struct predicate new_predicate = true_predicate ();
878 for (j = 0; e->predicate.clause[j]; j++)
879 if (!(possible_truths & e->predicate.clause[j]))
881 new_predicate = false_predicate ();
885 add_clause (info->conds, &new_predicate,
886 possible_truths & e->predicate.clause[j]);
887 if (false_predicate_p (&new_predicate))
889 optimized_out_size += e->size;
890 optimized_out_time += e->time;
893 account_size_time (info, e->size, e->time, &new_predicate);
896 /* Remap edge predicates with the same simplification as above.
897 Also copy constantness arrays. */
898 for (edge = dst->callees; edge; edge = edge->next_callee)
900 struct predicate new_predicate = true_predicate ();
901 struct inline_edge_summary *es = inline_edge_summary (edge);
903 if (!edge->inline_failed)
907 for (j = 0; es->predicate->clause[j]; j++)
908 if (!(possible_truths & es->predicate->clause[j]))
910 new_predicate = false_predicate ();
914 add_clause (info->conds, &new_predicate,
915 possible_truths & es->predicate->clause[j]);
916 if (false_predicate_p (&new_predicate)
917 && !false_predicate_p (es->predicate))
919 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
920 optimized_out_time += (es->call_stmt_time
921 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
925 *es->predicate = new_predicate;
928 /* Remap indirect edge predicates with the same simplificaiton as above.
929 Also copy constantness arrays. */
930 for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
932 struct predicate new_predicate = true_predicate ();
933 struct inline_edge_summary *es = inline_edge_summary (edge);
935 if (!edge->inline_failed)
939 for (j = 0; es->predicate->clause[j]; j++)
940 if (!(possible_truths & es->predicate->clause[j]))
942 new_predicate = false_predicate ();
946 add_clause (info->conds, &new_predicate,
947 possible_truths & es->predicate->clause[j]);
948 if (false_predicate_p (&new_predicate)
949 && !false_predicate_p (es->predicate))
951 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
952 optimized_out_time += (es->call_stmt_time
953 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
957 *es->predicate = new_predicate;
960 /* If inliner or someone after inliner will ever start producing
961 non-trivial clones, we will get trouble with lack of information
962 about updating self sizes, because size vectors already contains
963 sizes of the calees. */
964 gcc_assert (!inlined_to_p
965 || (!optimized_out_size && !optimized_out_time));
967 info->size -= optimized_out_size / INLINE_SIZE_SCALE;
968 info->self_size -= optimized_out_size / INLINE_SIZE_SCALE;
969 gcc_assert (info->size > 0);
970 gcc_assert (info->self_size > 0);
972 optimized_out_time /= INLINE_TIME_SCALE;
973 if (optimized_out_time > MAX_TIME)
974 optimized_out_time = MAX_TIME;
975 info->time -= optimized_out_time;
976 info->self_time -= optimized_out_time;
979 if (info->self_time < 0)
983 info->entry = VEC_copy (size_time_entry, gc, info->entry);
987 /* Hook that is called by cgraph.c when a node is duplicated. */
990 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
991 ATTRIBUTE_UNUSED void *data)
993 struct inline_edge_summary *info;
994 struct inline_edge_summary *srcinfo;
995 inline_summary_alloc ();
996 info = inline_edge_summary (dst);
997 srcinfo = inline_edge_summary (src);
998 memcpy (info, srcinfo,
999 sizeof (struct inline_edge_summary));
1000 info->predicate = NULL;
1001 edge_set_predicate (dst, srcinfo->predicate);
1002 info->param = VEC_copy (inline_param_summary_t, heap, srcinfo->param);
1006 /* Keep edge cache consistent across edge removal. */
1009 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
1011 if (edge_growth_cache)
1012 reset_edge_growth_cache (edge);
1014 < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec))
1016 edge_set_predicate (edge, NULL);
1017 VEC_free (inline_param_summary_t, heap,
1018 inline_edge_summary (edge)->param);
1019 memset (inline_edge_summary (edge), 0,
1020 sizeof (struct inline_edge_summary));
1025 /* Initialize growth caches. */
1028 initialize_growth_caches (void)
1030 if (cgraph_edge_max_uid)
1031 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
1032 cgraph_edge_max_uid);
1034 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
1038 /* Free growth caches. */
1041 free_growth_caches (void)
1043 VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
1044 edge_growth_cache = 0;
1045 VEC_free (int, heap, node_growth_cache);
1046 node_growth_cache = 0;
1050 /* Dump edge summaries associated to NODE and recursively to all clones.
1051 Indent by INDENT. */
1054 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node,
1055 struct inline_summary *info)
1057 struct cgraph_edge *edge;
1058 for (edge = node->callees; edge; edge = edge->next_callee)
1060 struct inline_edge_summary *es = inline_edge_summary (edge);
1061 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1064 fprintf (f, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
1065 indent, "", cgraph_node_name (callee),
1067 !edge->inline_failed ? "inlined"
1068 : cgraph_inline_failed_string (edge->inline_failed),
1074 (int)inline_summary (callee)->size / INLINE_SIZE_SCALE,
1075 (int)inline_summary (callee)->estimated_stack_size);
1079 fprintf (f, " predicate: ");
1080 dump_predicate (f, info->conds, es->predicate);
1085 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param);
1088 int prob = VEC_index (inline_param_summary_t,
1089 es->param, i)->change_prob;
1092 fprintf (f, "%*s op%i is compile time invariant\n",
1094 else if (prob != REG_BR_PROB_BASE)
1095 fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i,
1096 prob * 100.0 / REG_BR_PROB_BASE);
1098 if (!edge->inline_failed)
1100 fprintf (f, "%*sStack frame offset %i, callee self size %i,"
1101 " callee size %i\n",
1103 (int)inline_summary (callee)->stack_frame_offset,
1104 (int)inline_summary (callee)->estimated_self_stack_size,
1105 (int)inline_summary (callee)->estimated_stack_size);
1106 dump_inline_edge_summary (f, indent+2, callee, info);
1109 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1111 struct inline_edge_summary *es = inline_edge_summary (edge);
1112 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1118 es->call_stmt_time);
1121 fprintf (f, "predicate: ");
1122 dump_predicate (f, info->conds, es->predicate);
1131 dump_inline_summary (FILE * f, struct cgraph_node *node)
1135 struct inline_summary *s = inline_summary (node);
1138 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
1140 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1141 fprintf (f, " always_inline");
1143 fprintf (f, " inlinable");
1144 fprintf (f, "\n self time: %i\n",
1146 fprintf (f, " global time: %i\n", s->time);
1147 fprintf (f, " self size: %i\n",
1149 fprintf (f, " global size: %i\n", s->size);
1150 fprintf (f, " self stack: %i\n",
1151 (int) s->estimated_self_stack_size);
1152 fprintf (f, " global stack: %i\n",
1153 (int) s->estimated_stack_size);
1155 VEC_iterate (size_time_entry, s->entry, i, e);
1158 fprintf (f, " size:%f, time:%f, predicate:",
1159 (double) e->size / INLINE_SIZE_SCALE,
1160 (double) e->time / INLINE_TIME_SCALE);
1161 dump_predicate (f, s->conds, &e->predicate);
1163 fprintf (f, " calls:\n");
1164 dump_inline_edge_summary (f, 4, node, s);
1170 debug_inline_summary (struct cgraph_node *node)
1172 dump_inline_summary (stderr, node);
1176 dump_inline_summaries (FILE *f)
1178 struct cgraph_node *node;
1180 for (node = cgraph_nodes; node; node = node->next)
1181 if (node->analyzed && !node->global.inlined_to)
1182 dump_inline_summary (f, node);
1185 /* Give initial reasons why inlining would fail on EDGE. This gets either
1186 nullified or usually overwritten by more precise reasons later. */
1189 initialize_inline_failed (struct cgraph_edge *e)
1191 struct cgraph_node *callee = e->callee;
1193 if (e->indirect_unknown_callee)
1194 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1195 else if (!callee->analyzed)
1196 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1197 else if (callee->local.redefined_extern_inline)
1198 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1199 else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
1200 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1202 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1205 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1206 boolean variable pointed to by DATA. */
1209 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
1212 bool *b = (bool *) data;
1217 /* If OP reffers to value of function parameter, return
1218 the corresponding parameter. */
1221 unmodified_parm (gimple stmt, tree op)
1223 /* SSA_NAME referring to parm default def? */
1224 if (TREE_CODE (op) == SSA_NAME
1225 && SSA_NAME_IS_DEFAULT_DEF (op)
1226 && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL)
1227 return SSA_NAME_VAR (op);
1228 /* Non-SSA parm reference? */
1229 if (TREE_CODE (op) == PARM_DECL)
1231 bool modified = false;
1234 ao_ref_init (&refd, op);
1235 walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
1240 /* Assignment from a parameter? */
1241 if (TREE_CODE (op) == SSA_NAME
1242 && !SSA_NAME_IS_DEFAULT_DEF (op)
1243 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1244 return unmodified_parm (SSA_NAME_DEF_STMT (op),
1245 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)));
1249 /* See if statement might disappear after inlining.
1250 0 - means not eliminated
1251 1 - half of statements goes away
1252 2 - for sure it is eliminated.
1253 We are not terribly sophisticated, basically looking for simple abstraction
1254 penalty wrappers. */
1257 eliminated_by_inlining_prob (gimple stmt)
1259 enum gimple_code code = gimple_code (stmt);
1269 if (gimple_num_ops (stmt) != 2)
1272 /* Casts of parameters, loads from parameters passed by reference
1273 and stores to return value or parameters are often free after
1274 inlining dua to SRA and further combining.
1275 Assume that half of statements goes away. */
1276 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1277 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1278 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1279 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1281 tree rhs = gimple_assign_rhs1 (stmt);
1282 tree lhs = gimple_assign_lhs (stmt);
1283 tree inner_rhs = get_base_address (rhs);
1284 tree inner_lhs = get_base_address (lhs);
1285 bool rhs_free = false;
1286 bool lhs_free = false;
1293 /* Reads of parameter are expected to be free. */
1294 if (unmodified_parm (stmt, inner_rhs))
1297 /* When parameter is not SSA register because its address is taken
1298 and it is just copied into one, the statement will be completely
1299 free after inlining (we will copy propagate backward). */
1300 if (rhs_free && is_gimple_reg (lhs))
1303 /* Reads of parameters passed by reference
1304 expected to be free (i.e. optimized out after inlining). */
1305 if (TREE_CODE(inner_rhs) == MEM_REF
1306 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0)))
1309 /* Copying parameter passed by reference into gimple register is
1310 probably also going to copy propagate, but we can't be quite
1312 if (rhs_free && is_gimple_reg (lhs))
1315 /* Writes to parameters, parameters passed by value and return value
1316 (either dirrectly or passed via invisible reference) are free.
1318 TODO: We ought to handle testcase like
1319 struct a {int a,b;};
1321 retrurnsturct (void)
1327 This translate into:
1342 For that we either need to copy ipa-split logic detecting writes
1344 if (TREE_CODE (inner_lhs) == PARM_DECL
1345 || TREE_CODE (inner_lhs) == RESULT_DECL
1346 || (TREE_CODE(inner_lhs) == MEM_REF
1347 && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0))
1348 || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
1349 && TREE_CODE (SSA_NAME_VAR
1350 (TREE_OPERAND (inner_lhs, 0)))
1354 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1356 if (lhs_free && rhs_free)
1366 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1367 predicates to the CFG edges. */
1370 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1371 struct inline_summary *summary,
1377 enum tree_code code, inverted_code;
1385 last = last_stmt (bb);
1387 || gimple_code (last) != GIMPLE_COND)
1389 if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1391 op = gimple_cond_lhs (last);
1392 /* TODO: handle conditionals like
1395 parm = unmodified_parm (last, op);
1398 index = ipa_get_param_decl_index (info, parm);
1401 code = gimple_cond_code (last);
1403 = invert_tree_comparison (code,
1404 HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1406 FOR_EACH_EDGE (e, ei, bb->succs)
1408 struct predicate p = add_condition (summary,
1410 e->flags & EDGE_TRUE_VALUE
1411 ? code : inverted_code,
1412 gimple_cond_rhs (last));
1413 e->aux = pool_alloc (edge_predicate_pool);
1414 *(struct predicate *)e->aux = p;
1418 if (TREE_CODE (op) != SSA_NAME)
1421 if (builtin_constant_p (op))
1425 Here we can predicate nonconstant_code. We can't
1426 really handle constant_code since we have no predicate
1427 for this and also the constant code is not known to be
1428 optimized away when inliner doen't see operand is constant.
1429 Other optimizers might think otherwise. */
1430 set_stmt = SSA_NAME_DEF_STMT (op);
1431 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1432 || gimple_call_num_args (set_stmt) != 1)
1434 op2 = gimple_call_arg (set_stmt, 0);
1435 base = get_base_address (op2);
1436 parm = unmodified_parm (set_stmt, base ? base : op2);
1439 index = ipa_get_param_decl_index (info, parm);
1442 if (gimple_cond_code (last) != NE_EXPR
1443 || !integer_zerop (gimple_cond_rhs (last)))
1445 FOR_EACH_EDGE (e, ei, bb->succs)
1446 if (e->flags & EDGE_FALSE_VALUE)
1448 struct predicate p = add_condition (summary,
1452 e->aux = pool_alloc (edge_predicate_pool);
1453 *(struct predicate *)e->aux = p;
1458 /* If BB ends by a switch we can turn into predicates, attach corresponding
1459 predicates to the CFG edges. */
1462 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1463 struct inline_summary *summary,
1475 last = last_stmt (bb);
1477 || gimple_code (last) != GIMPLE_SWITCH)
1479 op = gimple_switch_index (last);
1480 parm = unmodified_parm (last, op);
1483 index = ipa_get_param_decl_index (info, parm);
1487 FOR_EACH_EDGE (e, ei, bb->succs)
1489 e->aux = pool_alloc (edge_predicate_pool);
1490 *(struct predicate *)e->aux = false_predicate ();
1492 n = gimple_switch_num_labels(last);
1493 for (case_idx = 0; case_idx < n; ++case_idx)
1495 tree cl = gimple_switch_label (last, case_idx);
1499 e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1500 min = CASE_LOW (cl);
1501 max = CASE_HIGH (cl);
1503 /* For default we might want to construct predicate that none
1504 of cases is met, but it is bit hard to do not having negations
1505 of conditionals handy. */
1507 p = true_predicate ();
1509 p = add_condition (summary, index,
1514 struct predicate p1, p2;
1515 p1 = add_condition (summary, index,
1518 p2 = add_condition (summary, index,
1521 p = and_predicates (summary->conds, &p1, &p2);
1523 *(struct predicate *)e->aux
1524 = or_predicates (summary->conds, &p, (struct predicate *)e->aux);
1529 /* For each BB in NODE attach to its AUX pointer predicate under
1530 which it is executable. */
1533 compute_bb_predicates (struct cgraph_node *node,
1534 struct ipa_node_params *parms_info,
1535 struct inline_summary *summary)
1537 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1541 FOR_EACH_BB_FN (bb, my_function)
1543 set_cond_stmt_execution_predicate (parms_info, summary, bb);
1544 set_switch_stmt_execution_predicate (parms_info, summary, bb);
1547 /* Entry block is always executable. */
1548 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1549 = pool_alloc (edge_predicate_pool);
1550 *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1551 = true_predicate ();
1553 /* A simple dataflow propagation of predicates forward in the CFG.
1554 TODO: work in reverse postorder. */
1558 FOR_EACH_BB_FN (bb, my_function)
1560 struct predicate p = false_predicate ();
1563 FOR_EACH_EDGE (e, ei, bb->preds)
1567 struct predicate this_bb_predicate
1568 = *(struct predicate *)e->src->aux;
1571 = and_predicates (summary->conds, &this_bb_predicate,
1572 (struct predicate *)e->aux);
1573 p = or_predicates (summary->conds, &p, &this_bb_predicate);
1574 if (true_predicate_p (&p))
1578 if (false_predicate_p (&p))
1579 gcc_assert (!bb->aux);
1585 bb->aux = pool_alloc (edge_predicate_pool);
1586 *((struct predicate *)bb->aux) = p;
1588 else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
1591 *((struct predicate *)bb->aux) = p;
1599 /* We keep info about constantness of SSA names. */
1601 typedef struct predicate predicate_t;
1602 DEF_VEC_O (predicate_t);
1603 DEF_VEC_ALLOC_O (predicate_t, heap);
1606 /* Return predicate specifying when the STMT might have result that is not
1607 a compile time constant. */
1609 static struct predicate
1610 will_be_nonconstant_predicate (struct ipa_node_params *info,
1611 struct inline_summary *summary,
1613 VEC (predicate_t, heap) *nonconstant_names)
1616 struct predicate p = true_predicate ();
1619 struct predicate op_non_const;
1622 /* What statments might be optimized away
1623 when their arguments are constant
1624 TODO: also trivial builtins.
1625 builtin_constant_p is already handled later. */
1626 if (gimple_code (stmt) != GIMPLE_ASSIGN
1627 && gimple_code (stmt) != GIMPLE_COND
1628 && gimple_code (stmt) != GIMPLE_SWITCH)
1631 /* Stores will stay anyway. */
1632 if (gimple_vdef (stmt))
1635 is_load = gimple_vuse (stmt) != NULL;
1637 /* Loads can be optimized when the value is known. */
1640 tree op = gimple_assign_rhs1 (stmt);
1641 tree base = get_base_address (op);
1644 gcc_assert (gimple_assign_single_p (stmt));
1647 parm = unmodified_parm (stmt, base);
1650 if (ipa_get_param_decl_index (info, parm) < 0)
1654 /* See if we understand all operands before we start
1655 adding conditionals. */
1656 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1658 tree parm = unmodified_parm (stmt, use);
1659 /* For arguments we can build a condition. */
1660 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1662 if (TREE_CODE (use) != SSA_NAME)
1664 /* If we know when operand is constant,
1665 we still can say something useful. */
1666 if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names,
1667 SSA_NAME_VERSION (use))))
1671 op_non_const = false_predicate ();
1674 tree parm = unmodified_parm
1675 (stmt, get_base_address (gimple_assign_rhs1 (stmt)));
1676 p = add_condition (summary,
1677 ipa_get_param_decl_index (info, parm),
1679 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1681 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1683 tree parm = unmodified_parm (stmt, use);
1684 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1685 p = add_condition (summary,
1686 ipa_get_param_decl_index (info, parm),
1689 p = *VEC_index (predicate_t, nonconstant_names,
1690 SSA_NAME_VERSION (use));
1691 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1693 if (gimple_code (stmt) == GIMPLE_ASSIGN
1694 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
1695 VEC_replace (predicate_t, nonconstant_names,
1696 SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const);
1697 return op_non_const;
1700 struct record_modified_bb_info
1706 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
1707 set except for info->stmt. */
1710 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef,
1713 struct record_modified_bb_info *info = (struct record_modified_bb_info *) data;
1714 if (SSA_NAME_DEF_STMT (vdef) == info->stmt)
1716 bitmap_set_bit (info->bb_set,
1717 SSA_NAME_IS_DEFAULT_DEF (vdef)
1718 ? ENTRY_BLOCK_PTR->index : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index);
1722 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
1723 will change since last invocation of STMT.
1725 Value 0 is reserved for compile time invariants.
1726 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
1727 ought to be REG_BR_PROB_BASE / estimated_iters. */
1730 param_change_prob (gimple stmt, int i)
1732 tree op = gimple_call_arg (stmt, i);
1733 basic_block bb = gimple_bb (stmt);
1736 if (is_gimple_min_invariant (op))
1738 /* We would have to do non-trivial analysis to really work out what
1739 is the probability of value to change (i.e. when init statement
1740 is in a sibling loop of the call).
1742 We do an conservative estimate: when call is executed N times more often
1743 than the statement defining value, we take the frequency 1/N. */
1744 if (TREE_CODE (op) == SSA_NAME)
1749 return REG_BR_PROB_BASE;
1751 if (SSA_NAME_IS_DEFAULT_DEF (op))
1752 init_freq = ENTRY_BLOCK_PTR->frequency;
1754 init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency;
1758 if (init_freq < bb->frequency)
1759 return MAX ((init_freq * REG_BR_PROB_BASE +
1760 bb->frequency / 2) / bb->frequency, 1);
1762 return REG_BR_PROB_BASE;
1765 base = get_base_address (op);
1770 struct record_modified_bb_info info;
1774 if (const_value_known_p (base))
1777 return REG_BR_PROB_BASE;
1778 ao_ref_init (&refd, op);
1780 info.bb_set = BITMAP_ALLOC (NULL);
1781 walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
1783 if (bitmap_bit_p (info.bb_set, bb->index))
1785 BITMAP_FREE (info.bb_set);
1786 return REG_BR_PROB_BASE;
1789 /* Assume that every memory is initialized at entry.
1790 TODO: Can we easilly determine if value is always defined
1791 and thus we may skip entry block? */
1792 if (ENTRY_BLOCK_PTR->frequency)
1793 max = ENTRY_BLOCK_PTR->frequency;
1797 EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi)
1798 max = MIN (max, BASIC_BLOCK (index)->frequency);
1800 BITMAP_FREE (info.bb_set);
1801 if (max < bb->frequency)
1802 return MAX ((max * REG_BR_PROB_BASE +
1803 bb->frequency / 2) / bb->frequency, 1);
1805 return REG_BR_PROB_BASE;
1807 return REG_BR_PROB_BASE;
1811 /* Compute function body size parameters for NODE.
1812 When EARLY is true, we compute only simple summaries without
1813 non-trivial predicates to drive the early inliner. */
1816 estimate_function_body_sizes (struct cgraph_node *node, bool early)
1819 /* Estimate static overhead for function prologue/epilogue and alignment. */
1821 /* Benefits are scaled by probability of elimination that is in range
1824 gimple_stmt_iterator bsi;
1825 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1827 struct inline_summary *info = inline_summary (node);
1828 struct predicate bb_predicate;
1829 struct ipa_node_params *parms_info = NULL;
1830 VEC (predicate_t, heap) *nonconstant_names = NULL;
1832 if (ipa_node_params_vector && !early && optimize)
1834 parms_info = IPA_NODE_REF (node);
1835 VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names,
1836 VEC_length (tree, SSANAMES (my_function)));
1844 fprintf (dump_file, "\nAnalyzing function body size: %s\n",
1845 cgraph_node_name (node));
1847 /* When we run into maximal number of entries, we assign everything to the
1848 constant truth case. Be sure to have it in list. */
1849 bb_predicate = true_predicate ();
1850 account_size_time (info, 0, 0, &bb_predicate);
1852 bb_predicate = not_inlined_predicate ();
1853 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
1855 gcc_assert (my_function && my_function->cfg);
1857 compute_bb_predicates (node, parms_info, info);
1858 FOR_EACH_BB_FN (bb, my_function)
1860 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1862 /* TODO: Obviously predicates can be propagated down across CFG. */
1866 bb_predicate = *(struct predicate *)bb->aux;
1868 bb_predicate = false_predicate ();
1871 bb_predicate = true_predicate ();
1873 if (dump_file && (dump_flags & TDF_DETAILS))
1875 fprintf (dump_file, "\n BB %i predicate:", bb->index);
1876 dump_predicate (dump_file, info->conds, &bb_predicate);
1879 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1881 gimple stmt = gsi_stmt (bsi);
1882 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1883 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1885 struct predicate will_be_nonconstant;
1887 if (dump_file && (dump_flags & TDF_DETAILS))
1889 fprintf (dump_file, " ");
1890 print_gimple_stmt (dump_file, stmt, 0, 0);
1891 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1892 ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
1895 if (is_gimple_call (stmt))
1897 struct cgraph_edge *edge = cgraph_edge (node, stmt);
1898 struct inline_edge_summary *es = inline_edge_summary (edge);
1900 /* Special case: results of BUILT_IN_CONSTANT_P will be always
1901 resolved as constant. We however don't want to optimize
1902 out the cgraph edges. */
1903 if (nonconstant_names
1904 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
1905 && gimple_call_lhs (stmt)
1906 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
1908 struct predicate false_p = false_predicate ();
1909 VEC_replace (predicate_t, nonconstant_names,
1910 SSA_NAME_VERSION (gimple_call_lhs (stmt)),
1913 if (ipa_node_params_vector)
1915 int count = gimple_call_num_args (stmt);
1919 VEC_safe_grow_cleared (inline_param_summary_t, heap,
1921 for (i = 0; i < count; i++)
1923 int prob = param_change_prob (stmt, i);
1924 gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
1925 VEC_index (inline_param_summary_t,
1926 es->param, i)->change_prob = prob;
1930 es->call_stmt_size = this_size;
1931 es->call_stmt_time = this_time;
1932 es->loop_depth = bb->loop_depth;
1933 edge_set_predicate (edge, &bb_predicate);
1935 /* Do not inline calls where we cannot triviall work around
1936 mismatches in argument or return types. */
1938 && cgraph_function_or_thunk_node (edge->callee, NULL)
1939 && !gimple_check_call_matching_types
1940 (stmt, cgraph_function_or_thunk_node (edge->callee,
1943 edge->call_stmt_cannot_inline_p = true;
1944 gimple_call_set_cannot_inline (stmt, true);
1947 gcc_assert (!gimple_call_cannot_inline_p (stmt));
1950 /* TODO: When conditional jump or swithc is known to be constant, but
1951 we did not translate it into the predicates, we really can account
1952 just maximum of the possible paths. */
1955 = will_be_nonconstant_predicate (parms_info, info,
1956 stmt, nonconstant_names);
1957 if (this_time || this_size)
1965 prob = eliminated_by_inlining_prob (stmt);
1966 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
1967 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
1968 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
1969 fprintf (dump_file, "\t\tWill be eliminated by inlining\n");
1972 p = and_predicates (info->conds, &bb_predicate,
1973 &will_be_nonconstant);
1975 p = true_predicate ();
1977 /* We account everything but the calls. Calls have their own
1978 size/time info attached to cgraph edges. This is neccesary
1979 in order to make the cost disappear after inlining. */
1980 if (!is_gimple_call (stmt))
1984 struct predicate ip = not_inlined_predicate ();
1985 ip = and_predicates (info->conds, &ip, &p);
1986 account_size_time (info, this_size * prob,
1987 this_time * prob, &ip);
1990 account_size_time (info, this_size * (2 - prob),
1991 this_time * (2 - prob), &p);
1994 gcc_assert (time >= 0);
1995 gcc_assert (size >= 0);
1999 FOR_ALL_BB_FN (bb, my_function)
2005 pool_free (edge_predicate_pool, bb->aux);
2007 FOR_EACH_EDGE (e, ei, bb->succs)
2010 pool_free (edge_predicate_pool, e->aux);
2014 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2015 if (time > MAX_TIME)
2017 inline_summary (node)->self_time = time;
2018 inline_summary (node)->self_size = size;
2019 VEC_free (predicate_t, heap, nonconstant_names);
2022 fprintf (dump_file, "\n");
2023 dump_inline_summary (dump_file, node);
2028 /* Compute parameters of functions used by inliner.
2029 EARLY is true when we compute parameters for the early inliner */
2032 compute_inline_parameters (struct cgraph_node *node, bool early)
2034 HOST_WIDE_INT self_stack_size;
2035 struct cgraph_edge *e;
2036 struct inline_summary *info;
2037 tree old_decl = current_function_decl;
2039 gcc_assert (!node->global.inlined_to);
2041 inline_summary_alloc ();
2043 info = inline_summary (node);
2045 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2046 Once this happen, we will need to more curefully predict call
2048 if (node->thunk.thunk_p)
2050 struct inline_edge_summary *es = inline_edge_summary (node->callees);
2051 struct predicate t = true_predicate ();
2053 info->inlinable = 0;
2054 node->callees->call_stmt_cannot_inline_p = true;
2055 node->local.can_change_signature = false;
2056 es->call_stmt_time = 1;
2057 es->call_stmt_size = 1;
2058 account_size_time (info, 0, 0, &t);
2062 /* Even is_gimple_min_invariant rely on current_function_decl. */
2063 current_function_decl = node->decl;
2064 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2066 /* Estimate the stack size for the function if we're optimizing. */
2067 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
2068 info->estimated_self_stack_size = self_stack_size;
2069 info->estimated_stack_size = self_stack_size;
2070 info->stack_frame_offset = 0;
2072 /* Can this function be inlined at all? */
2073 info->inlinable = tree_inlinable_function_p (node->decl);
2075 /* Type attributes can use parameter indices to describe them. */
2076 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
2077 node->local.can_change_signature = false;
2080 /* Otherwise, inlinable functions always can change signature. */
2081 if (info->inlinable)
2082 node->local.can_change_signature = true;
2085 /* Functions calling builtin_apply can not change signature. */
2086 for (e = node->callees; e; e = e->next_callee)
2088 tree cdecl = e->callee->decl;
2089 if (DECL_BUILT_IN (cdecl)
2090 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2091 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2092 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
2095 node->local.can_change_signature = !e;
2098 estimate_function_body_sizes (node, early);
2100 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2101 info->time = info->self_time;
2102 info->size = info->self_size;
2103 info->stack_frame_offset = 0;
2104 info->estimated_stack_size = info->estimated_self_stack_size;
2105 current_function_decl = old_decl;
2110 /* Compute parameters of functions used by inliner using
2111 current_function_decl. */
2114 compute_inline_parameters_for_current (void)
2116 compute_inline_parameters (cgraph_get_node (current_function_decl), true);
2120 struct gimple_opt_pass pass_inline_parameters =
2124 "inline_param", /* name */
2126 compute_inline_parameters_for_current,/* execute */
2129 0, /* static_pass_number */
2130 TV_INLINE_HEURISTICS, /* tv_id */
2131 0, /* properties_required */
2132 0, /* properties_provided */
2133 0, /* properties_destroyed */
2134 0, /* todo_flags_start */
2135 0 /* todo_flags_finish */
2140 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2143 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
2146 struct inline_edge_summary *es = inline_edge_summary (e);
2147 *size += es->call_stmt_size * INLINE_SIZE_SCALE;
2148 *time += (es->call_stmt_time * prob / REG_BR_PROB_BASE
2149 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
2150 if (*time > MAX_TIME * INLINE_TIME_SCALE)
2151 *time = MAX_TIME * INLINE_TIME_SCALE;
2155 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */
2158 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
2159 clause_t possible_truths)
2161 struct cgraph_edge *e;
2162 for (e = node->callees; e; e = e->next_callee)
2164 struct inline_edge_summary *es = inline_edge_summary (e);
2165 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2167 if (e->inline_failed)
2169 /* Predicates of calls shall not use NOT_CHANGED codes,
2170 sowe do not need to compute probabilities. */
2171 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2174 estimate_calls_size_and_time (e->callee, size, time,
2178 /* TODO: look for devirtualizing oppurtunities. */
2179 for (e = node->indirect_calls; e; e = e->next_callee)
2181 struct inline_edge_summary *es = inline_edge_summary (e);
2182 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2183 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2188 /* Estimate size and time needed to execute NODE assuming
2189 POSSIBLE_TRUTHS clause. */
2192 estimate_node_size_and_time (struct cgraph_node *node,
2193 clause_t possible_truths,
2194 int *ret_size, int *ret_time,
2195 VEC (inline_param_summary_t, heap)
2196 *inline_param_summary)
2198 struct inline_summary *info = inline_summary (node);
2200 int size = 0, time = 0;
2204 && (dump_flags & TDF_DETAILS))
2207 fprintf (dump_file, " Estimating body: %s/%i\n"
2208 " Known to be false: ",
2209 cgraph_node_name (node),
2212 for (i = predicate_not_inlined_condition;
2213 i < (predicate_first_dynamic_condition
2214 + (int)VEC_length (condition, info->conds)); i++)
2215 if (!(possible_truths & (1 << i)))
2218 fprintf (dump_file, ", ");
2220 dump_condition (dump_file, info->conds, i);
2224 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2225 if (evaluate_predicate (&e->predicate, possible_truths))
2228 if (!inline_param_summary)
2232 int prob = predicate_probability (info->conds,
2235 inline_param_summary);
2236 time += e->time * prob / REG_BR_PROB_BASE;
2241 if (time > MAX_TIME * INLINE_TIME_SCALE)
2242 time = MAX_TIME * INLINE_TIME_SCALE;
2244 estimate_calls_size_and_time (node, &size, &time, possible_truths);
2245 time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2246 size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2250 && (dump_flags & TDF_DETAILS))
2251 fprintf (dump_file, "\n size:%i time:%i\n", size, time);
2260 /* Estimate size and time needed to execute callee of EDGE assuming that
2261 parameters known to be constant at caller of EDGE are propagated.
2262 KNOWN_VALs is a vector of assumed known constant values for parameters. */
2265 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
2266 VEC (tree, heap) *known_vals,
2267 int *ret_size, int *ret_time)
2271 clause = evaluate_conditions_for_known_args (node, false, known_vals);
2272 estimate_node_size_and_time (node, clause, ret_size, ret_time,
2277 /* Translate all conditions from callee representation into caller
2278 representation and symbolically evaluate predicate P into new predicate.
2280 INFO is inline_summary of function we are adding predicate into,
2281 CALLEE_INFO is summary of function predicate P is from. OPERAND_MAP is
2282 array giving callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is
2283 clausule of all callee conditions that may be true in caller context.
2284 TOPLEV_PREDICATE is predicate under which callee is executed. */
2286 static struct predicate
2287 remap_predicate (struct inline_summary *info,
2288 struct inline_summary *callee_info,
2289 struct predicate *p,
2290 VEC (int, heap) *operand_map,
2291 clause_t possible_truths,
2292 struct predicate *toplev_predicate)
2295 struct predicate out = true_predicate ();
2297 /* True predicate is easy. */
2298 if (true_predicate_p (p))
2299 return *toplev_predicate;
2300 for (i = 0; p->clause[i]; i++)
2302 clause_t clause = p->clause[i];
2304 struct predicate clause_predicate = false_predicate ();
2306 gcc_assert (i < MAX_CLAUSES);
2308 for (cond = 0; cond < NUM_CONDITIONS; cond ++)
2309 /* Do we have condition we can't disprove? */
2310 if (clause & possible_truths & (1 << cond))
2312 struct predicate cond_predicate;
2313 /* Work out if the condition can translate to predicate in the
2314 inlined function. */
2315 if (cond >= predicate_first_dynamic_condition)
2317 struct condition *c;
2319 c = VEC_index (condition, callee_info->conds,
2320 cond - predicate_first_dynamic_condition);
2321 /* See if we can remap condition operand to caller's operand.
2322 Otherwise give up. */
2324 || (int)VEC_length (int, operand_map) <= c->operand_num
2325 || VEC_index (int, operand_map, c->operand_num) == -1)
2326 cond_predicate = true_predicate ();
2328 cond_predicate = add_condition (info,
2329 VEC_index (int, operand_map,
2333 /* Fixed conditions remains same, construct single
2334 condition predicate. */
2337 cond_predicate.clause[0] = 1 << cond;
2338 cond_predicate.clause[1] = 0;
2340 clause_predicate = or_predicates (info->conds, &clause_predicate,
2343 out = and_predicates (info->conds, &out, &clause_predicate);
2345 return and_predicates (info->conds, &out, toplev_predicate);
2349 /* Update summary information of inline clones after inlining.
2350 Compute peak stack usage. */
2353 inline_update_callee_summaries (struct cgraph_node *node,
2356 struct cgraph_edge *e;
2357 struct inline_summary *callee_info = inline_summary (node);
2358 struct inline_summary *caller_info = inline_summary (node->callers->caller);
2361 callee_info->stack_frame_offset
2362 = caller_info->stack_frame_offset
2363 + caller_info->estimated_self_stack_size;
2364 peak = callee_info->stack_frame_offset
2365 + callee_info->estimated_self_stack_size;
2366 if (inline_summary (node->global.inlined_to)->estimated_stack_size
2368 inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
2369 cgraph_propagate_frequency (node);
2370 for (e = node->callees; e; e = e->next_callee)
2372 if (!e->inline_failed)
2373 inline_update_callee_summaries (e->callee, depth);
2374 inline_edge_summary (e)->loop_depth += depth;
2376 for (e = node->indirect_calls; e; e = e->next_callee)
2377 inline_edge_summary (e)->loop_depth += depth;
2380 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
2381 When functoin A is inlined in B and A calls C with parameter that
2382 changes with probability PROB1 and C is known to be passthroug
2383 of argument if B that change with probability PROB2, the probability
2384 of change is now PROB1*PROB2. */
2387 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
2388 struct cgraph_edge *edge)
2390 if (ipa_node_params_vector)
2393 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2394 struct inline_edge_summary *es = inline_edge_summary (edge);
2395 struct inline_edge_summary *inlined_es
2396 = inline_edge_summary (inlined_edge);
2398 for (i = 0; i < ipa_get_cs_argument_count (args); i++)
2400 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2401 if (jfunc->type == IPA_JF_PASS_THROUGH
2402 && (jfunc->value.pass_through.formal_id
2403 < (int) VEC_length (inline_param_summary_t,
2404 inlined_es->param)))
2406 int prob1 = VEC_index (inline_param_summary_t,
2407 es->param, i)->change_prob;
2408 int prob2 = VEC_index
2409 (inline_param_summary_t,
2411 jfunc->value.pass_through.formal_id)->change_prob;
2412 int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2)
2413 / REG_BR_PROB_BASE);
2415 if (prob1 && prob2 && !prob)
2418 VEC_index (inline_param_summary_t,
2419 es->param, i)->change_prob = prob;
2425 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
2427 Remap predicates of callees of NODE. Rest of arguments match
2430 Also update change probabilities. */
2433 remap_edge_summaries (struct cgraph_edge *inlined_edge,
2434 struct cgraph_node *node,
2435 struct inline_summary *info,
2436 struct inline_summary *callee_info,
2437 VEC (int, heap) *operand_map,
2438 clause_t possible_truths,
2439 struct predicate *toplev_predicate)
2441 struct cgraph_edge *e;
2442 for (e = node->callees; e; e = e->next_callee)
2444 struct inline_edge_summary *es = inline_edge_summary (e);
2447 if (e->inline_failed)
2449 remap_edge_change_prob (inlined_edge, e);
2453 p = remap_predicate (info, callee_info,
2454 es->predicate, operand_map, possible_truths,
2456 edge_set_predicate (e, &p);
2457 /* TODO: We should remove the edge for code that will be
2458 optimized out, but we need to keep verifiers and tree-inline
2459 happy. Make it cold for now. */
2460 if (false_predicate_p (&p))
2467 edge_set_predicate (e, toplev_predicate);
2470 remap_edge_summaries (inlined_edge, e->callee, info, callee_info,
2471 operand_map, possible_truths, toplev_predicate);
2473 for (e = node->indirect_calls; e; e = e->next_callee)
2475 struct inline_edge_summary *es = inline_edge_summary (e);
2478 remap_edge_change_prob (inlined_edge, e);
2481 p = remap_predicate (info, callee_info,
2482 es->predicate, operand_map, possible_truths,
2484 edge_set_predicate (e, &p);
2485 /* TODO: We should remove the edge for code that will be optimized
2486 out, but we need to keep verifiers and tree-inline happy.
2487 Make it cold for now. */
2488 if (false_predicate_p (&p))
2495 edge_set_predicate (e, toplev_predicate);
2500 /* We inlined EDGE. Update summary of the function we inlined into. */
2503 inline_merge_summary (struct cgraph_edge *edge)
2505 struct inline_summary *callee_info = inline_summary (edge->callee);
2506 struct cgraph_node *to = (edge->caller->global.inlined_to
2507 ? edge->caller->global.inlined_to : edge->caller);
2508 struct inline_summary *info = inline_summary (to);
2509 clause_t clause = 0; /* not_inline is known to be false. */
2511 VEC (int, heap) *operand_map = NULL;
2513 struct predicate toplev_predicate;
2514 struct predicate true_p = true_predicate ();
2515 struct inline_edge_summary *es = inline_edge_summary (edge);
2518 toplev_predicate = *es->predicate;
2520 toplev_predicate = true_predicate ();
2522 if (ipa_node_params_vector && callee_info->conds)
2524 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2525 int count = ipa_get_cs_argument_count (args);
2528 clause = evaluate_conditions_for_edge (edge, true);
2530 VEC_safe_grow_cleared (int, heap, operand_map, count);
2531 for (i = 0; i < count; i++)
2533 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2535 /* TODO: handle non-NOPs when merging. */
2536 if (jfunc->type == IPA_JF_PASS_THROUGH
2537 && jfunc->value.pass_through.operation == NOP_EXPR)
2538 map = jfunc->value.pass_through.formal_id;
2539 VEC_replace (int, operand_map, i, map);
2540 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
2543 for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
2545 struct predicate p = remap_predicate (info, callee_info,
2546 &e->predicate, operand_map, clause,
2548 if (!false_predicate_p (&p))
2550 gcov_type add_time = ((gcov_type)e->time * edge->frequency
2551 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2552 int prob = predicate_probability (callee_info->conds,
2555 add_time = add_time * prob / REG_BR_PROB_BASE;
2556 if (add_time > MAX_TIME * INLINE_TIME_SCALE)
2557 add_time = MAX_TIME * INLINE_TIME_SCALE;
2558 if (prob != REG_BR_PROB_BASE
2559 && dump_file && (dump_flags & TDF_DETAILS))
2561 fprintf (dump_file, "\t\tScaling time by probability:%f\n",
2562 (double)prob / REG_BR_PROB_BASE);
2564 account_size_time (info, e->size, add_time, &p);
2567 remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
2568 clause, &toplev_predicate);
2571 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2572 info->size += e->size, info->time += e->time;
2573 estimate_calls_size_and_time (to, &info->size, &info->time,
2574 ~(clause_t)(1 << predicate_false_condition));
2576 inline_update_callee_summaries (edge->callee,
2577 inline_edge_summary (edge)->loop_depth);
2579 /* We do not maintain predicates of inlined edges, free it. */
2580 edge_set_predicate (edge, &true_p);
2581 /* Similarly remove param summaries. */
2582 VEC_free (inline_param_summary_t, heap, es->param);
2584 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2585 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2589 /* Estimate the time cost for the caller when inlining EDGE.
2590 Only to be called via estimate_edge_time, that handles the
2593 When caching, also update the cache entry. Compute both time and
2594 size, since we always need both metrics eventually. */
2597 do_estimate_edge_time (struct cgraph_edge *edge)
2602 struct inline_edge_summary *es = inline_edge_summary (edge);
2604 gcc_checking_assert (edge->inline_failed);
2605 estimate_node_size_and_time (cgraph_function_or_thunk_node (edge->callee,
2607 evaluate_conditions_for_edge (edge, true),
2608 &size, &time, es->param);
2610 ret = (((gcov_type)time
2611 - es->call_stmt_time) * edge->frequency
2612 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2614 /* When caching, update the cache entry. */
2615 if (edge_growth_cache)
2618 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
2620 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
2621 cgraph_edge_max_uid);
2622 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
2625 ret_size = size - es->call_stmt_size;
2626 gcc_checking_assert (es->call_stmt_size);
2627 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
2628 = ret_size + (ret_size >= 0);
2634 /* Estimate the growth of the caller when inlining EDGE.
2635 Only to be called via estimate_edge_size. */
2638 do_estimate_edge_growth (struct cgraph_edge *edge)
2641 struct cgraph_node *callee;
2643 /* When we do caching, use do_estimate_edge_time to populate the entry. */
2645 if (edge_growth_cache)
2647 do_estimate_edge_time (edge);
2648 size = VEC_index (edge_growth_cache_entry,
2651 gcc_checking_assert (size);
2652 return size - (size > 0);
2654 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
2656 /* Early inliner runs without caching, go ahead and do the dirty work. */
2657 gcc_checking_assert (edge->inline_failed);
2658 estimate_node_size_and_time (callee,
2659 evaluate_conditions_for_edge (edge, true),
2661 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
2662 return size - inline_edge_summary (edge)->call_stmt_size;
2666 /* Estimate self time of the function NODE after inlining EDGE. */
2669 estimate_time_after_inlining (struct cgraph_node *node,
2670 struct cgraph_edge *edge)
2672 struct inline_edge_summary *es = inline_edge_summary (edge);
2673 if (!es->predicate || !false_predicate_p (es->predicate))
2675 gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
2678 if (time > MAX_TIME)
2682 return inline_summary (node)->time;
2686 /* Estimate the size of NODE after inlining EDGE which should be an
2687 edge to either NODE or a call inlined into NODE. */
2690 estimate_size_after_inlining (struct cgraph_node *node,
2691 struct cgraph_edge *edge)
2693 struct inline_edge_summary *es = inline_edge_summary (edge);
2694 if (!es->predicate || !false_predicate_p (es->predicate))
2696 int size = inline_summary (node)->size + estimate_edge_growth (edge);
2697 gcc_assert (size >= 0);
2700 return inline_summary (node)->size;
2706 bool self_recursive;
2711 /* Worker for do_estimate_growth. Collect growth for all callers. */
2714 do_estimate_growth_1 (struct cgraph_node *node, void *data)
2716 struct cgraph_edge *e;
2717 struct growth_data *d = (struct growth_data *) data;
2719 for (e = node->callers; e; e = e->next_caller)
2721 gcc_checking_assert (e->inline_failed);
2723 if (e->caller == node
2724 || (e->caller->global.inlined_to
2725 && e->caller->global.inlined_to == node))
2726 d->self_recursive = true;
2727 d->growth += estimate_edge_growth (e);
2733 /* Estimate the growth caused by inlining NODE into all callees. */
2736 do_estimate_growth (struct cgraph_node *node)
2738 struct growth_data d = {0, false};
2739 struct inline_summary *info = inline_summary (node);
2741 cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
2743 /* For self recursive functions the growth estimation really should be
2744 infinity. We don't want to return very large values because the growth
2745 plays various roles in badness computation fractions. Be sure to not
2746 return zero or negative growths. */
2747 if (d.self_recursive)
2748 d.growth = d.growth < info->size ? info->size : d.growth;
2751 if (!DECL_EXTERNAL (node->decl)
2752 && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
2753 d.growth -= info->size;
2754 /* COMDAT functions are very often not shared across multiple units
2755 since they come from various template instantiations.
2756 Take this into account. */
2757 else if (DECL_COMDAT (node->decl)
2758 && cgraph_can_remove_if_no_direct_calls_p (node))
2759 d.growth -= (info->size
2760 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
2764 if (node_growth_cache)
2766 if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2767 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2768 VEC_replace (int, node_growth_cache, node->uid,
2769 d.growth + (d.growth >= 0));
2775 /* This function performs intraprocedural analysis in NODE that is required to
2776 inline indirect calls. */
2779 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2781 ipa_analyze_node (node);
2782 if (dump_file && (dump_flags & TDF_DETAILS))
2784 ipa_print_node_params (dump_file, node);
2785 ipa_print_node_jump_functions (dump_file, node);
2790 /* Note function body size. */
2793 inline_analyze_function (struct cgraph_node *node)
2795 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2796 current_function_decl = node->decl;
2799 fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2800 cgraph_node_name (node), node->uid);
2801 if (optimize && !node->thunk.thunk_p)
2802 inline_indirect_intraprocedural_analysis (node);
2803 compute_inline_parameters (node, false);
2805 current_function_decl = NULL;
2810 /* Called when new function is inserted to callgraph late. */
2813 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2815 inline_analyze_function (node);
2819 /* Note function body size. */
2822 inline_generate_summary (void)
2824 struct cgraph_node *node;
2826 function_insertion_hook_holder =
2827 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2829 ipa_register_cgraph_hooks ();
2831 FOR_EACH_DEFINED_FUNCTION (node)
2833 inline_analyze_function (node);
2837 /* Read predicate from IB. */
2839 static struct predicate
2840 read_predicate (struct lto_input_block *ib)
2842 struct predicate out;
2848 gcc_assert (k <= MAX_CLAUSES);
2849 clause = out.clause[k++] = streamer_read_uhwi (ib);
2853 /* Zero-initialize the remaining clauses in OUT. */
2854 while (k <= MAX_CLAUSES)
2855 out.clause[k++] = 0;
2861 /* Write inline summary for edge E to OB. */
2864 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2866 struct inline_edge_summary *es = inline_edge_summary (e);
2870 es->call_stmt_size = streamer_read_uhwi (ib);
2871 es->call_stmt_time = streamer_read_uhwi (ib);
2872 es->loop_depth = streamer_read_uhwi (ib);
2873 p = read_predicate (ib);
2874 edge_set_predicate (e, &p);
2875 length = streamer_read_uhwi (ib);
2878 VEC_safe_grow_cleared (inline_param_summary_t, heap, es->param, length);
2879 for (i = 0; i < length; i++)
2880 VEC_index (inline_param_summary_t, es->param, i)->change_prob
2881 = streamer_read_uhwi (ib);
2886 /* Stream in inline summaries from the section. */
2889 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
2892 const struct lto_function_header *header =
2893 (const struct lto_function_header *) data;
2894 const int32_t cfg_offset = sizeof (struct lto_function_header);
2895 const int32_t main_offset = cfg_offset + header->cfg_size;
2896 const int32_t string_offset = main_offset + header->main_size;
2897 struct data_in *data_in;
2898 struct lto_input_block ib;
2899 unsigned int i, count2, j;
2900 unsigned int f_count;
2902 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
2906 lto_data_in_create (file_data, (const char *) data + string_offset,
2907 header->string_size, NULL);
2908 f_count = streamer_read_uhwi (&ib);
2909 for (i = 0; i < f_count; i++)
2912 struct cgraph_node *node;
2913 struct inline_summary *info;
2914 lto_cgraph_encoder_t encoder;
2915 struct bitpack_d bp;
2916 struct cgraph_edge *e;
2918 index = streamer_read_uhwi (&ib);
2919 encoder = file_data->cgraph_node_encoder;
2920 node = lto_cgraph_encoder_deref (encoder, index);
2921 info = inline_summary (node);
2923 info->estimated_stack_size
2924 = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
2925 info->size = info->self_size = streamer_read_uhwi (&ib);
2926 info->time = info->self_time = streamer_read_uhwi (&ib);
2928 bp = streamer_read_bitpack (&ib);
2929 info->inlinable = bp_unpack_value (&bp, 1);
2931 count2 = streamer_read_uhwi (&ib);
2932 gcc_assert (!info->conds);
2933 for (j = 0; j < count2; j++)
2936 c.operand_num = streamer_read_uhwi (&ib);
2937 c.code = (enum tree_code) streamer_read_uhwi (&ib);
2938 c.val = stream_read_tree (&ib, data_in);
2939 VEC_safe_push (condition, gc, info->conds, &c);
2941 count2 = streamer_read_uhwi (&ib);
2942 gcc_assert (!info->entry);
2943 for (j = 0; j < count2; j++)
2945 struct size_time_entry e;
2947 e.size = streamer_read_uhwi (&ib);
2948 e.time = streamer_read_uhwi (&ib);
2949 e.predicate = read_predicate (&ib);
2951 VEC_safe_push (size_time_entry, gc, info->entry, &e);
2953 for (e = node->callees; e; e = e->next_callee)
2954 read_inline_edge_summary (&ib, e);
2955 for (e = node->indirect_calls; e; e = e->next_callee)
2956 read_inline_edge_summary (&ib, e);
2959 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
2961 lto_data_in_delete (data_in);
2965 /* Read inline summary. Jump functions are shared among ipa-cp
2966 and inliner, so when ipa-cp is active, we don't need to write them
2970 inline_read_summary (void)
2972 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2973 struct lto_file_decl_data *file_data;
2976 inline_summary_alloc ();
2978 while ((file_data = file_data_vec[j++]))
2981 const char *data = lto_get_section_data (file_data,
2982 LTO_section_inline_summary,
2985 inline_read_section (file_data, data, len);
2987 /* Fatal error here. We do not want to support compiling ltrans units
2988 with different version of compiler or different flags than the WPA
2989 unit, so this should never happen. */
2990 fatal_error ("ipa inline summary is missing in input file");
2994 ipa_register_cgraph_hooks ();
2996 ipa_prop_read_jump_functions ();
2998 function_insertion_hook_holder =
2999 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3003 /* Write predicate P to OB. */
3006 write_predicate (struct output_block *ob, struct predicate *p)
3010 for (j = 0; p->clause[j]; j++)
3012 gcc_assert (j < MAX_CLAUSES);
3013 streamer_write_uhwi (ob, p->clause[j]);
3015 streamer_write_uhwi (ob, 0);
3019 /* Write inline summary for edge E to OB. */
3022 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
3024 struct inline_edge_summary *es = inline_edge_summary (e);
3027 streamer_write_uhwi (ob, es->call_stmt_size);
3028 streamer_write_uhwi (ob, es->call_stmt_time);
3029 streamer_write_uhwi (ob, es->loop_depth);
3030 write_predicate (ob, es->predicate);
3031 streamer_write_uhwi (ob, VEC_length (inline_param_summary_t, es->param));
3032 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param); i++)
3033 streamer_write_uhwi (ob, VEC_index (inline_param_summary_t,
3034 es->param, i)->change_prob);
3038 /* Write inline summary for node in SET.
3039 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3040 active, we don't need to write them twice. */
3043 inline_write_summary (cgraph_node_set set,
3044 varpool_node_set vset ATTRIBUTE_UNUSED)
3046 struct cgraph_node *node;
3047 struct output_block *ob = create_output_block (LTO_section_inline_summary);
3048 lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
3049 unsigned int count = 0;
3052 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3053 if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
3055 streamer_write_uhwi (ob, count);
3057 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3059 node = lto_cgraph_encoder_deref (encoder, i);
3062 struct inline_summary *info = inline_summary (node);
3063 struct bitpack_d bp;
3064 struct cgraph_edge *edge;
3067 struct condition *c;
3069 streamer_write_uhwi (ob, lto_cgraph_encoder_encode (encoder, node));
3070 streamer_write_hwi (ob, info->estimated_self_stack_size);
3071 streamer_write_hwi (ob, info->self_size);
3072 streamer_write_hwi (ob, info->self_time);
3073 bp = bitpack_create (ob->main_stream);
3074 bp_pack_value (&bp, info->inlinable, 1);
3075 streamer_write_bitpack (&bp);
3076 streamer_write_uhwi (ob, VEC_length (condition, info->conds));
3077 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
3079 streamer_write_uhwi (ob, c->operand_num);
3080 streamer_write_uhwi (ob, c->code);
3081 stream_write_tree (ob, c->val, true);
3083 streamer_write_uhwi (ob, VEC_length (size_time_entry, info->entry));
3085 VEC_iterate (size_time_entry, info->entry, i, e);
3088 streamer_write_uhwi (ob, e->size);
3089 streamer_write_uhwi (ob, e->time);
3090 write_predicate (ob, &e->predicate);
3092 for (edge = node->callees; edge; edge = edge->next_callee)
3093 write_inline_edge_summary (ob, edge);
3094 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
3095 write_inline_edge_summary (ob, edge);
3098 streamer_write_char_stream (ob->main_stream, 0);
3099 produce_asm (ob, NULL);
3100 destroy_output_block (ob);
3102 if (optimize && !flag_ipa_cp)
3103 ipa_prop_write_jump_functions (set);
3107 /* Release inline summary. */
3110 inline_free_summary (void)
3112 if (function_insertion_hook_holder)
3113 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
3114 function_insertion_hook_holder = NULL;
3115 if (node_removal_hook_holder)
3116 cgraph_remove_node_removal_hook (node_removal_hook_holder);
3117 if (edge_removal_hook_holder)
3118 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
3119 node_removal_hook_holder = NULL;
3120 if (node_duplication_hook_holder)
3121 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
3122 if (edge_duplication_hook_holder)
3123 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3124 node_duplication_hook_holder = NULL;
3125 VEC_free (inline_summary_t, gc, inline_summary_vec);
3126 inline_summary_vec = NULL;
3127 VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
3128 inline_edge_summary_vec = NULL;
3129 if (edge_predicate_pool)
3130 free_alloc_pool (edge_predicate_pool);
3131 edge_predicate_pool = 0;