1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
72 #include "tree-inline.h"
73 #include "langhooks.h"
76 #include "diagnostic.h"
77 #include "gimple-pretty-print.h"
79 #include "tree-pass.h"
82 #include "tree-flow.h"
84 #include "lto-streamer.h"
85 #include "data-streamer.h"
86 #include "tree-streamer.h"
87 #include "ipa-inline.h"
88 #include "alloc-pool.h"
91 #include "tree-scalar-evolution.h"
93 /* Estimate runtime of function can easilly run into huge numbers with many
94 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
95 integer. For anything larger we use gcov_type. */
96 #define MAX_TIME 500000
98 /* Number of bits in integer, but we really want to be stable across different
100 #define NUM_CONDITIONS 32
102 enum predicate_conditions
104 predicate_false_condition = 0,
105 predicate_not_inlined_condition = 1,
106 predicate_first_dynamic_condition = 2
109 /* Special condition code we use to represent test that operand is compile time
111 #define IS_NOT_CONSTANT ERROR_MARK
112 /* Special condition code we use to represent test that operand is not changed
113 across invocation of the function. When operand IS_NOT_CONSTANT it is always
114 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
115 of executions even when they are not compile time constants. */
116 #define CHANGED IDENTIFIER_NODE
118 /* Holders of ipa cgraph hooks: */
119 static struct cgraph_node_hook_list *function_insertion_hook_holder;
120 static struct cgraph_node_hook_list *node_removal_hook_holder;
121 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
122 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
123 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
124 static void inline_node_removal_hook (struct cgraph_node *, void *);
125 static void inline_node_duplication_hook (struct cgraph_node *,
126 struct cgraph_node *, void *);
127 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
128 static void inline_edge_duplication_hook (struct cgraph_edge *,
129 struct cgraph_edge *, void *);
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 vec<inline_summary_t, va_gc> *inline_summary_vec;
134 vec<inline_edge_summary_t> inline_edge_summary_vec;
136 /* Cached node/edge growths. */
137 vec<int> node_growth_cache;
138 vec<edge_growth_cache_entry> 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. */
202 static inline struct predicate
203 not_inlined_predicate (void)
205 return single_cond_predicate (predicate_not_inlined_condition);
208 /* Simple description of whether a memory load or a condition refers to a load
209 from an aggregate and if so, how and where from in the aggregate.
210 Individual fields have the same meaning like fields with the same name in
213 struct agg_position_info
215 HOST_WIDE_INT offset;
220 /* Add condition to condition list CONDS. AGGPOS describes whether the used
221 oprand is loaded from an aggregate and where in the aggregate it is. It can
222 be NULL, which means this not a load from an aggregate. */
224 static struct predicate
225 add_condition (struct inline_summary *summary, int operand_num,
226 struct agg_position_info *aggpos,
227 enum tree_code code, tree val)
231 struct condition new_cond;
232 HOST_WIDE_INT offset;
233 bool agg_contents, by_ref;
237 offset = aggpos->offset;
238 agg_contents = aggpos->agg_contents;
239 by_ref = aggpos->by_ref;
244 agg_contents = false;
248 gcc_checking_assert (operand_num >= 0);
249 for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
251 if (c->operand_num == operand_num
254 && c->agg_contents == agg_contents
255 && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
256 return single_cond_predicate (i + predicate_first_dynamic_condition);
258 /* Too many conditions. Give up and return constant true. */
259 if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
260 return true_predicate ();
262 new_cond.operand_num = operand_num;
263 new_cond.code = code;
265 new_cond.agg_contents = agg_contents;
266 new_cond.by_ref = by_ref;
267 new_cond.offset = offset;
268 vec_safe_push (summary->conds, new_cond);
269 return single_cond_predicate (i + predicate_first_dynamic_condition);
273 /* Add clause CLAUSE into the predicate P. */
276 add_clause (conditions conditions, struct predicate *p, clause_t clause)
280 int insert_here = -1;
287 /* False clause makes the whole predicate false. Kill the other variants. */
288 if (clause == (1 << predicate_false_condition))
290 p->clause[0] = (1 << predicate_false_condition);
294 if (false_predicate_p (p))
297 /* No one should be sily enough to add false into nontrivial clauses. */
298 gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
300 /* Look where to insert the clause. At the same time prune out
301 clauses of P that are implied by the new clause and thus
303 for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
305 p->clause[i2] = p->clause[i];
310 /* If p->clause[i] implies clause, there is nothing to add. */
311 if ((p->clause[i] & clause) == p->clause[i])
313 /* We had nothing to add, none of clauses should've become
315 gcc_checking_assert (i == i2);
319 if (p->clause[i] < clause && insert_here < 0)
322 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
323 Otherwise the p->clause[i] has to stay. */
324 if ((p->clause[i] & clause) != clause)
328 /* Look for clauses that are obviously true. I.e.
329 op0 == 5 || op0 != 5. */
330 for (c1 = predicate_first_dynamic_condition; c1 < NUM_CONDITIONS; c1++)
333 if (!(clause & (1 << c1)))
335 cc1 = &(*conditions)[c1 - predicate_first_dynamic_condition];
336 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
337 and thus there is no point for looking for them. */
338 if (cc1->code == CHANGED || cc1->code == IS_NOT_CONSTANT)
340 for (c2 = c1 + 1; c2 <= NUM_CONDITIONS; c2++)
341 if (clause & (1 << c2))
344 &(*conditions)[c1 - predicate_first_dynamic_condition];
346 &(*conditions)[c2 - predicate_first_dynamic_condition];
347 if (cc1->operand_num == cc2->operand_num
348 && cc1->val == cc2->val
349 && cc2->code != IS_NOT_CONSTANT
350 && cc2->code != CHANGED
351 && cc1->code == invert_tree_comparison
353 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1->val)))))
359 /* We run out of variants. Be conservative in positive direction. */
360 if (i2 == MAX_CLAUSES)
362 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
363 p->clause[i2 + 1] = 0;
364 if (insert_here >= 0)
365 for (; i2 > insert_here; i2--)
366 p->clause[i2] = p->clause[i2 - 1];
369 p->clause[insert_here] = clause;
375 static struct predicate
376 and_predicates (conditions conditions,
377 struct predicate *p, struct predicate *p2)
379 struct predicate out = *p;
382 /* Avoid busy work. */
383 if (false_predicate_p (p2) || true_predicate_p (p))
385 if (false_predicate_p (p) || true_predicate_p (p2))
388 /* See how far predicates match. */
389 for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
391 gcc_checking_assert (i < MAX_CLAUSES);
394 /* Combine the predicates rest. */
395 for (; p2->clause[i]; i++)
397 gcc_checking_assert (i < MAX_CLAUSES);
398 add_clause (conditions, &out, p2->clause[i]);
404 /* Return true if predicates are obviously equal. */
407 predicates_equal_p (struct predicate *p, struct predicate *p2)
410 for (i = 0; p->clause[i]; i++)
412 gcc_checking_assert (i < MAX_CLAUSES);
413 gcc_checking_assert (p->clause[i] > p->clause[i + 1]);
414 gcc_checking_assert (!p2->clause[i]
415 || p2->clause[i] > p2->clause[i + 1]);
416 if (p->clause[i] != p2->clause[i])
419 return !p2->clause[i];
425 static struct predicate
426 or_predicates (conditions conditions,
427 struct predicate *p, struct predicate *p2)
429 struct predicate out = true_predicate ();
432 /* Avoid busy work. */
433 if (false_predicate_p (p2) || true_predicate_p (p))
435 if (false_predicate_p (p) || true_predicate_p (p2))
437 if (predicates_equal_p (p, p2))
440 /* OK, combine the predicates. */
441 for (i = 0; p->clause[i]; i++)
442 for (j = 0; p2->clause[j]; j++)
444 gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
445 add_clause (conditions, &out, p->clause[i] | p2->clause[j]);
451 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
452 if predicate P is known to be false. */
455 evaluate_predicate (struct predicate *p, clause_t possible_truths)
459 /* True remains true. */
460 if (true_predicate_p (p))
463 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
465 /* See if we can find clause we can disprove. */
466 for (i = 0; p->clause[i]; i++)
468 gcc_checking_assert (i < MAX_CLAUSES);
469 if (!(p->clause[i] & possible_truths))
475 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
476 instruction will be recomputed per invocation of the inlined call. */
479 predicate_probability (conditions conds,
480 struct predicate *p, clause_t possible_truths,
481 vec<inline_param_summary_t> inline_param_summary)
484 int combined_prob = REG_BR_PROB_BASE;
486 /* True remains true. */
487 if (true_predicate_p (p))
488 return REG_BR_PROB_BASE;
490 if (false_predicate_p (p))
493 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
495 /* See if we can find clause we can disprove. */
496 for (i = 0; p->clause[i]; i++)
498 gcc_checking_assert (i < MAX_CLAUSES);
499 if (!(p->clause[i] & possible_truths))
505 if (!inline_param_summary.exists ())
506 return REG_BR_PROB_BASE;
507 for (i2 = 0; i2 < NUM_CONDITIONS; i2++)
508 if ((p->clause[i] & possible_truths) & (1 << i2))
510 if (i2 >= predicate_first_dynamic_condition)
513 &(*conds)[i2 - predicate_first_dynamic_condition];
514 if (c->code == CHANGED
516 (int) inline_param_summary.length ()))
519 inline_param_summary[c->operand_num].change_prob;
520 this_prob = MAX (this_prob, iprob);
523 this_prob = REG_BR_PROB_BASE;
526 this_prob = REG_BR_PROB_BASE;
528 combined_prob = MIN (this_prob, combined_prob);
533 return combined_prob;
537 /* Dump conditional COND. */
540 dump_condition (FILE *f, conditions conditions, int cond)
543 if (cond == predicate_false_condition)
544 fprintf (f, "false");
545 else if (cond == predicate_not_inlined_condition)
546 fprintf (f, "not inlined");
549 c = &(*conditions)[cond - predicate_first_dynamic_condition];
550 fprintf (f, "op%i", c->operand_num);
552 fprintf (f, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
553 c->by_ref ? "ref " : "", c->offset);
554 if (c->code == IS_NOT_CONSTANT)
556 fprintf (f, " not constant");
559 if (c->code == CHANGED)
561 fprintf (f, " changed");
564 fprintf (f, " %s ", op_symbol_code (c->code));
565 print_generic_expr (f, c->val, 1);
570 /* Dump clause CLAUSE. */
573 dump_clause (FILE *f, conditions conds, clause_t clause)
580 for (i = 0; i < NUM_CONDITIONS; i++)
581 if (clause & (1 << i))
586 dump_condition (f, conds, i);
592 /* Dump predicate PREDICATE. */
595 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
598 if (true_predicate_p (pred))
599 dump_clause (f, conds, 0);
601 for (i = 0; pred->clause[i]; i++)
605 dump_clause (f, conds, pred->clause[i]);
611 /* Dump inline hints. */
613 dump_inline_hints (FILE *f, inline_hints hints)
617 fprintf (f, "inline hints:");
618 if (hints & INLINE_HINT_indirect_call)
620 hints &= ~INLINE_HINT_indirect_call;
621 fprintf (f, " indirect_call");
623 if (hints & INLINE_HINT_loop_iterations)
625 hints &= ~INLINE_HINT_loop_iterations;
626 fprintf (f, " loop_iterations");
628 if (hints & INLINE_HINT_loop_stride)
630 hints &= ~INLINE_HINT_loop_stride;
631 fprintf (f, " loop_stride");
633 if (hints & INLINE_HINT_same_scc)
635 hints &= ~INLINE_HINT_same_scc;
636 fprintf (f, " same_scc");
638 if (hints & INLINE_HINT_in_scc)
640 hints &= ~INLINE_HINT_in_scc;
641 fprintf (f, " in_scc");
643 if (hints & INLINE_HINT_cross_module)
645 hints &= ~INLINE_HINT_cross_module;
646 fprintf (f, " cross_module");
648 if (hints & INLINE_HINT_declared_inline)
650 hints &= ~INLINE_HINT_declared_inline;
651 fprintf (f, " declared_inline");
653 if (hints & INLINE_HINT_array_index)
655 hints &= ~INLINE_HINT_array_index;
656 fprintf (f, " array_index");
662 /* Record SIZE and TIME under condition PRED into the inline summary. */
665 account_size_time (struct inline_summary *summary, int size, int time,
666 struct predicate *pred)
672 if (false_predicate_p (pred))
675 /* We need to create initial empty unconitional clause, but otherwie
676 we don't need to account empty times and sizes. */
677 if (!size && !time && summary->entry)
680 /* Watch overflow that might result from insane profiles. */
681 if (time > MAX_TIME * INLINE_TIME_SCALE)
682 time = MAX_TIME * INLINE_TIME_SCALE;
683 gcc_assert (time >= 0);
685 for (i = 0; vec_safe_iterate (summary->entry, i, &e); i++)
686 if (predicates_equal_p (&e->predicate, pred))
695 e = &(*summary->entry)[0];
696 gcc_assert (!e->predicate.clause[0]);
697 if (dump_file && (dump_flags & TDF_DETAILS))
699 "\t\tReached limit on number of entries, "
700 "ignoring the predicate.");
702 if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
705 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
706 ((double) size) / INLINE_SIZE_SCALE,
707 ((double) time) / INLINE_TIME_SCALE, found ? "" : "new ");
708 dump_predicate (dump_file, summary->conds, pred);
712 struct size_time_entry new_entry;
713 new_entry.size = size;
714 new_entry.time = time;
715 new_entry.predicate = *pred;
716 vec_safe_push (summary->entry, new_entry);
722 if (e->time > MAX_TIME * INLINE_TIME_SCALE)
723 e->time = MAX_TIME * INLINE_TIME_SCALE;
727 /* Set predicate for edge E. */
730 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
732 struct inline_edge_summary *es = inline_edge_summary (e);
733 if (predicate && !true_predicate_p (predicate))
736 es->predicate = (struct predicate *) pool_alloc (edge_predicate_pool);
737 *es->predicate = *predicate;
742 pool_free (edge_predicate_pool, es->predicate);
743 es->predicate = NULL;
747 /* Set predicate for hint *P. */
750 set_hint_predicate (struct predicate **p, struct predicate new_predicate)
752 if (false_predicate_p (&new_predicate) || true_predicate_p (&new_predicate))
755 pool_free (edge_predicate_pool, *p);
761 *p = (struct predicate *) pool_alloc (edge_predicate_pool);
767 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
768 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
769 Return clause of possible truths. When INLINE_P is true, assume that we are
772 ERROR_MARK means compile time invariant. */
775 evaluate_conditions_for_known_args (struct cgraph_node *node,
777 vec<tree> known_vals,
778 vec<ipa_agg_jump_function_p>
781 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
782 struct inline_summary *info = inline_summary (node);
786 for (i = 0; vec_safe_iterate (info->conds, i, &c); i++)
791 /* We allow call stmt to have fewer arguments than the callee function
792 (especially for K&R style programs). So bound check here (we assume
793 known_aggs vector, if non-NULL, has the same length as
795 gcc_checking_assert (!known_aggs.exists ()
796 || (known_vals.length () == known_aggs.length ()));
797 if (c->operand_num >= (int) known_vals.length ())
799 clause |= 1 << (i + predicate_first_dynamic_condition);
805 struct ipa_agg_jump_function *agg;
807 if (c->code == CHANGED
809 && (known_vals[c->operand_num] == error_mark_node))
812 if (known_aggs.exists ())
814 agg = known_aggs[c->operand_num];
815 val = ipa_find_agg_cst_for_param (agg, c->offset, c->by_ref);
822 val = known_vals[c->operand_num];
823 if (val == error_mark_node && c->code != CHANGED)
829 clause |= 1 << (i + predicate_first_dynamic_condition);
832 if (c->code == IS_NOT_CONSTANT || c->code == CHANGED)
834 res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
835 if (res && integer_zerop (res))
837 clause |= 1 << (i + predicate_first_dynamic_condition);
843 /* Work out what conditions might be true at invocation of E. */
846 evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
847 clause_t *clause_ptr,
848 vec<tree> *known_vals_ptr,
849 vec<tree> *known_binfos_ptr,
850 vec<ipa_agg_jump_function_p> *known_aggs_ptr)
852 struct cgraph_node *callee =
853 cgraph_function_or_thunk_node (e->callee, NULL);
854 struct inline_summary *info = inline_summary (callee);
855 vec<tree> known_vals = vNULL;
856 vec<ipa_agg_jump_function_p> known_aggs = vNULL;
859 *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition;
861 known_vals_ptr->create (0);
862 if (known_binfos_ptr)
863 known_binfos_ptr->create (0);
865 if (ipa_node_params_vector.exists ()
866 && !e->call_stmt_cannot_inline_p
867 && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
869 struct ipa_node_params *parms_info;
870 struct ipa_edge_args *args = IPA_EDGE_REF (e);
871 struct inline_edge_summary *es = inline_edge_summary (e);
872 int i, count = ipa_get_cs_argument_count (args);
874 if (e->caller->global.inlined_to)
875 parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
877 parms_info = IPA_NODE_REF (e->caller);
879 if (count && (info->conds || known_vals_ptr))
880 known_vals.safe_grow_cleared (count);
881 if (count && (info->conds || known_aggs_ptr))
882 known_aggs.safe_grow_cleared (count);
883 if (count && known_binfos_ptr)
884 known_binfos_ptr->safe_grow_cleared (count);
886 for (i = 0; i < count; i++)
888 struct ipa_jump_func *jf = ipa_get_ith_jump_func (args, i);
889 tree cst = ipa_value_from_jfunc (parms_info, jf);
892 if (known_vals.exists () && TREE_CODE (cst) != TREE_BINFO)
894 else if (known_binfos_ptr != NULL
895 && TREE_CODE (cst) == TREE_BINFO)
896 (*known_binfos_ptr)[i] = cst;
898 else if (inline_p && !es->param[i].change_prob)
899 known_vals[i] = error_mark_node;
900 /* TODO: When IPA-CP starts propagating and merging aggregate jump
901 functions, use its knowledge of the caller too, just like the
902 scalar case above. */
903 known_aggs[i] = &jf->agg;
908 *clause_ptr = evaluate_conditions_for_known_args (callee, inline_p,
909 known_vals, known_aggs);
912 *known_vals_ptr = known_vals;
914 known_vals.release ();
917 *known_aggs_ptr = known_aggs;
919 known_aggs.release ();
923 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
926 inline_summary_alloc (void)
928 if (!node_removal_hook_holder)
929 node_removal_hook_holder =
930 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
931 if (!edge_removal_hook_holder)
932 edge_removal_hook_holder =
933 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
934 if (!node_duplication_hook_holder)
935 node_duplication_hook_holder =
936 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
937 if (!edge_duplication_hook_holder)
938 edge_duplication_hook_holder =
939 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
941 if (vec_safe_length (inline_summary_vec) <= (unsigned) cgraph_max_uid)
942 vec_safe_grow_cleared (inline_summary_vec, cgraph_max_uid + 1);
943 if (inline_edge_summary_vec.length () <= (unsigned) cgraph_edge_max_uid)
944 inline_edge_summary_vec.safe_grow_cleared (cgraph_edge_max_uid + 1);
945 if (!edge_predicate_pool)
946 edge_predicate_pool = create_alloc_pool ("edge predicates",
947 sizeof (struct predicate), 10);
950 /* We are called multiple time for given function; clear
951 data from previous run so they are not cumulated. */
954 reset_inline_edge_summary (struct cgraph_edge *e)
956 if (e->uid < (int) inline_edge_summary_vec.length ())
958 struct inline_edge_summary *es = inline_edge_summary (e);
960 es->call_stmt_size = es->call_stmt_time = 0;
962 pool_free (edge_predicate_pool, es->predicate);
963 es->predicate = NULL;
964 es->param.release ();
968 /* We are called multiple time for given function; clear
969 data from previous run so they are not cumulated. */
972 reset_inline_summary (struct cgraph_node *node)
974 struct inline_summary *info = inline_summary (node);
975 struct cgraph_edge *e;
977 info->self_size = info->self_time = 0;
978 info->estimated_stack_size = 0;
979 info->estimated_self_stack_size = 0;
980 info->stack_frame_offset = 0;
985 if (info->loop_iterations)
987 pool_free (edge_predicate_pool, info->loop_iterations);
988 info->loop_iterations = NULL;
990 if (info->loop_stride)
992 pool_free (edge_predicate_pool, info->loop_stride);
993 info->loop_stride = NULL;
995 if (info->array_index)
997 pool_free (edge_predicate_pool, info->array_index);
998 info->array_index = NULL;
1000 vec_free (info->conds);
1001 vec_free (info->entry);
1002 for (e = node->callees; e; e = e->next_callee)
1003 reset_inline_edge_summary (e);
1004 for (e = node->indirect_calls; e; e = e->next_callee)
1005 reset_inline_edge_summary (e);
1008 /* Hook that is called by cgraph.c when a node is removed. */
1011 inline_node_removal_hook (struct cgraph_node *node,
1012 void *data ATTRIBUTE_UNUSED)
1014 struct inline_summary *info;
1015 if (vec_safe_length (inline_summary_vec) <= (unsigned) node->uid)
1017 info = inline_summary (node);
1018 reset_inline_summary (node);
1019 memset (info, 0, sizeof (inline_summary_t));
1022 /* Remap predicate P of former function to be predicate of duplicated functoin.
1023 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1024 INFO is inline summary of the duplicated node. */
1026 static struct predicate
1027 remap_predicate_after_duplication (struct predicate *p,
1028 clause_t possible_truths,
1029 struct inline_summary *info)
1031 struct predicate new_predicate = true_predicate ();
1033 for (j = 0; p->clause[j]; j++)
1034 if (!(possible_truths & p->clause[j]))
1036 new_predicate = false_predicate ();
1040 add_clause (info->conds, &new_predicate,
1041 possible_truths & p->clause[j]);
1042 return new_predicate;
1045 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1046 Additionally care about allocating new memory slot for updated predicate
1047 and set it to NULL when it becomes true or false (and thus uninteresting).
1051 remap_hint_predicate_after_duplication (struct predicate **p,
1052 clause_t possible_truths,
1053 struct inline_summary *info)
1055 struct predicate new_predicate;
1060 new_predicate = remap_predicate_after_duplication (*p,
1061 possible_truths, info);
1062 /* We do not want to free previous predicate; it is used by node origin. */
1064 set_hint_predicate (p, new_predicate);
1068 /* Hook that is called by cgraph.c when a node is duplicated. */
1071 inline_node_duplication_hook (struct cgraph_node *src,
1072 struct cgraph_node *dst,
1073 ATTRIBUTE_UNUSED void *data)
1075 struct inline_summary *info;
1076 inline_summary_alloc ();
1077 info = inline_summary (dst);
1078 memcpy (info, inline_summary (src), sizeof (struct inline_summary));
1079 /* TODO: as an optimization, we may avoid copying conditions
1080 that are known to be false or true. */
1081 info->conds = vec_safe_copy (info->conds);
1083 /* When there are any replacements in the function body, see if we can figure
1084 out that something was optimized out. */
1085 if (ipa_node_params_vector.exists () && dst->clone.tree_map)
1087 vec<size_time_entry, va_gc> *entry = info->entry;
1088 /* Use SRC parm info since it may not be copied yet. */
1089 struct ipa_node_params *parms_info = IPA_NODE_REF (src);
1090 vec<tree> known_vals = vNULL;
1091 int count = ipa_get_param_count (parms_info);
1093 clause_t possible_truths;
1094 struct predicate true_pred = true_predicate ();
1096 int optimized_out_size = 0;
1097 bool inlined_to_p = false;
1098 struct cgraph_edge *edge;
1101 known_vals.safe_grow_cleared (count);
1102 for (i = 0; i < count; i++)
1104 tree t = ipa_get_param (parms_info, i);
1105 struct ipa_replace_map *r;
1107 for (j = 0; vec_safe_iterate (dst->clone.tree_map, j, &r); j++)
1109 if (r->old_tree == t && r->replace_p && !r->ref_p)
1111 known_vals[i] = r->new_tree;
1116 possible_truths = evaluate_conditions_for_known_args (dst, false,
1119 known_vals.release ();
1121 account_size_time (info, 0, 0, &true_pred);
1123 /* Remap size_time vectors.
1124 Simplify the predicate by prunning out alternatives that are known
1126 TODO: as on optimization, we can also eliminate conditions known
1128 for (i = 0; vec_safe_iterate (entry, i, &e); i++)
1130 struct predicate new_predicate;
1131 new_predicate = remap_predicate_after_duplication (&e->predicate,
1134 if (false_predicate_p (&new_predicate))
1135 optimized_out_size += e->size;
1137 account_size_time (info, e->size, e->time, &new_predicate);
1140 /* Remap edge predicates with the same simplification as above.
1141 Also copy constantness arrays. */
1142 for (edge = dst->callees; edge; edge = edge->next_callee)
1144 struct predicate new_predicate;
1145 struct inline_edge_summary *es = inline_edge_summary (edge);
1147 if (!edge->inline_failed)
1148 inlined_to_p = true;
1151 new_predicate = remap_predicate_after_duplication (es->predicate,
1154 if (false_predicate_p (&new_predicate)
1155 && !false_predicate_p (es->predicate))
1157 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
1158 edge->frequency = 0;
1160 edge_set_predicate (edge, &new_predicate);
1163 /* Remap indirect edge predicates with the same simplificaiton as above.
1164 Also copy constantness arrays. */
1165 for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
1167 struct predicate new_predicate;
1168 struct inline_edge_summary *es = inline_edge_summary (edge);
1170 gcc_checking_assert (edge->inline_failed);
1173 new_predicate = remap_predicate_after_duplication (es->predicate,
1176 if (false_predicate_p (&new_predicate)
1177 && !false_predicate_p (es->predicate))
1179 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
1180 edge->frequency = 0;
1182 edge_set_predicate (edge, &new_predicate);
1184 remap_hint_predicate_after_duplication (&info->loop_iterations,
1185 possible_truths, info);
1186 remap_hint_predicate_after_duplication (&info->loop_stride,
1187 possible_truths, info);
1188 remap_hint_predicate_after_duplication (&info->array_index,
1189 possible_truths, info);
1191 /* If inliner or someone after inliner will ever start producing
1192 non-trivial clones, we will get trouble with lack of information
1193 about updating self sizes, because size vectors already contains
1194 sizes of the calees. */
1195 gcc_assert (!inlined_to_p || !optimized_out_size);
1199 info->entry = vec_safe_copy (info->entry);
1200 if (info->loop_iterations)
1202 predicate p = *info->loop_iterations;
1203 info->loop_iterations = NULL;
1204 set_hint_predicate (&info->loop_iterations, p);
1206 if (info->loop_stride)
1208 predicate p = *info->loop_stride;
1209 info->loop_stride = NULL;
1210 set_hint_predicate (&info->loop_stride, p);
1212 if (info->array_index)
1214 predicate p = *info->array_index;
1215 info->array_index = NULL;
1216 set_hint_predicate (&info->array_index, p);
1219 inline_update_overall_summary (dst);
1223 /* Hook that is called by cgraph.c when a node is duplicated. */
1226 inline_edge_duplication_hook (struct cgraph_edge *src,
1227 struct cgraph_edge *dst,
1228 ATTRIBUTE_UNUSED void *data)
1230 struct inline_edge_summary *info;
1231 struct inline_edge_summary *srcinfo;
1232 inline_summary_alloc ();
1233 info = inline_edge_summary (dst);
1234 srcinfo = inline_edge_summary (src);
1235 memcpy (info, srcinfo, sizeof (struct inline_edge_summary));
1236 info->predicate = NULL;
1237 edge_set_predicate (dst, srcinfo->predicate);
1238 info->param = srcinfo->param.copy ();
1242 /* Keep edge cache consistent across edge removal. */
1245 inline_edge_removal_hook (struct cgraph_edge *edge,
1246 void *data ATTRIBUTE_UNUSED)
1248 if (edge_growth_cache.exists ())
1249 reset_edge_growth_cache (edge);
1250 reset_inline_edge_summary (edge);
1254 /* Initialize growth caches. */
1257 initialize_growth_caches (void)
1259 if (cgraph_edge_max_uid)
1260 edge_growth_cache.safe_grow_cleared (cgraph_edge_max_uid);
1262 node_growth_cache.safe_grow_cleared (cgraph_max_uid);
1266 /* Free growth caches. */
1269 free_growth_caches (void)
1271 edge_growth_cache.release ();
1272 node_growth_cache.release ();
1276 /* Dump edge summaries associated to NODE and recursively to all clones.
1277 Indent by INDENT. */
1280 dump_inline_edge_summary (FILE *f, int indent, struct cgraph_node *node,
1281 struct inline_summary *info)
1283 struct cgraph_edge *edge;
1284 for (edge = node->callees; edge; edge = edge->next_callee)
1286 struct inline_edge_summary *es = inline_edge_summary (edge);
1287 struct cgraph_node *callee =
1288 cgraph_function_or_thunk_node (edge->callee, NULL);
1292 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1293 " time: %2i callee size:%2i stack:%2i",
1294 indent, "", cgraph_node_name (callee), callee->uid,
1295 !edge->inline_failed
1296 ? "inlined" : cgraph_inline_failed_string (edge-> inline_failed),
1297 indent, "", es->loop_depth, edge->frequency,
1298 es->call_stmt_size, es->call_stmt_time,
1299 (int) inline_summary (callee)->size / INLINE_SIZE_SCALE,
1300 (int) inline_summary (callee)->estimated_stack_size);
1304 fprintf (f, " predicate: ");
1305 dump_predicate (f, info->conds, es->predicate);
1309 if (es->param.exists ())
1310 for (i = 0; i < (int) es->param.length (); i++)
1312 int prob = es->param[i].change_prob;
1315 fprintf (f, "%*s op%i is compile time invariant\n",
1317 else if (prob != REG_BR_PROB_BASE)
1318 fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i,
1319 prob * 100.0 / REG_BR_PROB_BASE);
1321 if (!edge->inline_failed)
1323 fprintf (f, "%*sStack frame offset %i, callee self size %i,"
1324 " callee size %i\n",
1326 (int) inline_summary (callee)->stack_frame_offset,
1327 (int) inline_summary (callee)->estimated_self_stack_size,
1328 (int) inline_summary (callee)->estimated_stack_size);
1329 dump_inline_edge_summary (f, indent + 2, callee, info);
1332 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1334 struct inline_edge_summary *es = inline_edge_summary (edge);
1335 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1339 edge->frequency, es->call_stmt_size, es->call_stmt_time);
1342 fprintf (f, "predicate: ");
1343 dump_predicate (f, info->conds, es->predicate);
1352 dump_inline_summary (FILE *f, struct cgraph_node *node)
1356 struct inline_summary *s = inline_summary (node);
1359 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
1361 if (DECL_DISREGARD_INLINE_LIMITS (node->symbol.decl))
1362 fprintf (f, " always_inline");
1364 fprintf (f, " inlinable");
1365 fprintf (f, "\n self time: %i\n", s->self_time);
1366 fprintf (f, " global time: %i\n", s->time);
1367 fprintf (f, " self size: %i\n", s->self_size);
1368 fprintf (f, " global size: %i\n", s->size);
1369 fprintf (f, " self stack: %i\n",
1370 (int) s->estimated_self_stack_size);
1371 fprintf (f, " global stack: %i\n", (int) s->estimated_stack_size);
1373 fprintf (f, " estimated growth:%i\n", (int) s->growth);
1375 fprintf (f, " In SCC: %i\n", (int) s->scc_no);
1376 for (i = 0; vec_safe_iterate (s->entry, i, &e); i++)
1378 fprintf (f, " size:%f, time:%f, predicate:",
1379 (double) e->size / INLINE_SIZE_SCALE,
1380 (double) e->time / INLINE_TIME_SCALE);
1381 dump_predicate (f, s->conds, &e->predicate);
1383 if (s->loop_iterations)
1385 fprintf (f, " loop iterations:");
1386 dump_predicate (f, s->conds, s->loop_iterations);
1390 fprintf (f, " loop stride:");
1391 dump_predicate (f, s->conds, s->loop_stride);
1395 fprintf (f, " array index:");
1396 dump_predicate (f, s->conds, s->array_index);
1398 fprintf (f, " calls:\n");
1399 dump_inline_edge_summary (f, 4, node, s);
1405 debug_inline_summary (struct cgraph_node *node)
1407 dump_inline_summary (stderr, node);
1411 dump_inline_summaries (FILE *f)
1413 struct cgraph_node *node;
1415 FOR_EACH_DEFINED_FUNCTION (node)
1416 if (!node->global.inlined_to)
1417 dump_inline_summary (f, node);
1420 /* Give initial reasons why inlining would fail on EDGE. This gets either
1421 nullified or usually overwritten by more precise reasons later. */
1424 initialize_inline_failed (struct cgraph_edge *e)
1426 struct cgraph_node *callee = e->callee;
1428 if (e->indirect_unknown_callee)
1429 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1430 else if (!callee->analyzed)
1431 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1432 else if (callee->local.redefined_extern_inline)
1433 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1434 else if (e->call_stmt_cannot_inline_p)
1435 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1437 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1440 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1441 boolean variable pointed to by DATA. */
1444 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
1447 bool *b = (bool *) data;
1452 /* If OP refers to value of function parameter, return the corresponding
1456 unmodified_parm_1 (gimple stmt, tree op)
1458 /* SSA_NAME referring to parm default def? */
1459 if (TREE_CODE (op) == SSA_NAME
1460 && SSA_NAME_IS_DEFAULT_DEF (op)
1461 && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL)
1462 return SSA_NAME_VAR (op);
1463 /* Non-SSA parm reference? */
1464 if (TREE_CODE (op) == PARM_DECL)
1466 bool modified = false;
1469 ao_ref_init (&refd, op);
1470 walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
1478 /* If OP refers to value of function parameter, return the corresponding
1479 parameter. Also traverse chains of SSA register assignments. */
1482 unmodified_parm (gimple stmt, tree op)
1484 tree res = unmodified_parm_1 (stmt, op);
1488 if (TREE_CODE (op) == SSA_NAME
1489 && !SSA_NAME_IS_DEFAULT_DEF (op)
1490 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1491 return unmodified_parm (SSA_NAME_DEF_STMT (op),
1492 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)));
1496 /* If OP refers to a value of a function parameter or value loaded from an
1497 aggregate passed to a parameter (either by value or reference), return TRUE
1498 and store the number of the parameter to *INDEX_P and information whether
1499 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1500 the function parameters, STMT is the statement in which OP is used or
1504 unmodified_parm_or_parm_agg_item (struct ipa_node_params *info,
1505 gimple stmt, tree op, int *index_p,
1506 struct agg_position_info *aggpos)
1508 tree res = unmodified_parm_1 (stmt, op);
1510 gcc_checking_assert (aggpos);
1513 *index_p = ipa_get_param_decl_index (info, res);
1516 aggpos->agg_contents = false;
1517 aggpos->by_ref = false;
1521 if (TREE_CODE (op) == SSA_NAME)
1523 if (SSA_NAME_IS_DEFAULT_DEF (op)
1524 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1526 stmt = SSA_NAME_DEF_STMT (op);
1527 op = gimple_assign_rhs1 (stmt);
1528 if (!REFERENCE_CLASS_P (op))
1529 return unmodified_parm_or_parm_agg_item (info, stmt, op, index_p,
1533 aggpos->agg_contents = true;
1534 return ipa_load_from_parm_agg (info, stmt, op, index_p, &aggpos->offset,
1538 /* See if statement might disappear after inlining.
1539 0 - means not eliminated
1540 1 - half of statements goes away
1541 2 - for sure it is eliminated.
1542 We are not terribly sophisticated, basically looking for simple abstraction
1543 penalty wrappers. */
1546 eliminated_by_inlining_prob (gimple stmt)
1548 enum gimple_code code = gimple_code (stmt);
1549 enum tree_code rhs_code;
1559 if (gimple_num_ops (stmt) != 2)
1562 rhs_code = gimple_assign_rhs_code (stmt);
1564 /* Casts of parameters, loads from parameters passed by reference
1565 and stores to return value or parameters are often free after
1566 inlining dua to SRA and further combining.
1567 Assume that half of statements goes away. */
1568 if (rhs_code == CONVERT_EXPR
1569 || rhs_code == NOP_EXPR
1570 || rhs_code == VIEW_CONVERT_EXPR
1571 || rhs_code == ADDR_EXPR
1572 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1574 tree rhs = gimple_assign_rhs1 (stmt);
1575 tree lhs = gimple_assign_lhs (stmt);
1576 tree inner_rhs = get_base_address (rhs);
1577 tree inner_lhs = get_base_address (lhs);
1578 bool rhs_free = false;
1579 bool lhs_free = false;
1586 /* Reads of parameter are expected to be free. */
1587 if (unmodified_parm (stmt, inner_rhs))
1589 /* Match expressions of form &this->field. Those will most likely
1590 combine with something upstream after inlining. */
1591 else if (TREE_CODE (inner_rhs) == ADDR_EXPR)
1593 tree op = get_base_address (TREE_OPERAND (inner_rhs, 0));
1594 if (TREE_CODE (op) == PARM_DECL)
1596 else if (TREE_CODE (op) == MEM_REF
1597 && unmodified_parm (stmt, TREE_OPERAND (op, 0)))
1601 /* When parameter is not SSA register because its address is taken
1602 and it is just copied into one, the statement will be completely
1603 free after inlining (we will copy propagate backward). */
1604 if (rhs_free && is_gimple_reg (lhs))
1607 /* Reads of parameters passed by reference
1608 expected to be free (i.e. optimized out after inlining). */
1609 if (TREE_CODE (inner_rhs) == MEM_REF
1610 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0)))
1613 /* Copying parameter passed by reference into gimple register is
1614 probably also going to copy propagate, but we can't be quite
1616 if (rhs_free && is_gimple_reg (lhs))
1619 /* Writes to parameters, parameters passed by value and return value
1620 (either dirrectly or passed via invisible reference) are free.
1622 TODO: We ought to handle testcase like
1623 struct a {int a,b;};
1625 retrurnsturct (void)
1631 This translate into:
1646 For that we either need to copy ipa-split logic detecting writes
1648 if (TREE_CODE (inner_lhs) == PARM_DECL
1649 || TREE_CODE (inner_lhs) == RESULT_DECL
1650 || (TREE_CODE (inner_lhs) == MEM_REF
1651 && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0))
1652 || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
1653 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs, 0))
1654 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1656 0))) == RESULT_DECL))))
1659 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1661 if (lhs_free && rhs_free)
1671 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1672 predicates to the CFG edges. */
1675 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1676 struct inline_summary *summary,
1682 struct agg_position_info aggpos;
1683 enum tree_code code, inverted_code;
1689 last = last_stmt (bb);
1690 if (!last || gimple_code (last) != GIMPLE_COND)
1692 if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1694 op = gimple_cond_lhs (last);
1695 /* TODO: handle conditionals like
1698 if (unmodified_parm_or_parm_agg_item (info, last, op, &index, &aggpos))
1700 code = gimple_cond_code (last);
1702 = invert_tree_comparison (code,
1703 HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1705 FOR_EACH_EDGE (e, ei, bb->succs)
1707 struct predicate p = add_condition (summary, index, &aggpos,
1708 e->flags & EDGE_TRUE_VALUE
1709 ? code : inverted_code,
1710 gimple_cond_rhs (last));
1711 e->aux = pool_alloc (edge_predicate_pool);
1712 *(struct predicate *) e->aux = p;
1716 if (TREE_CODE (op) != SSA_NAME)
1719 if (builtin_constant_p (op))
1723 Here we can predicate nonconstant_code. We can't
1724 really handle constant_code since we have no predicate
1725 for this and also the constant code is not known to be
1726 optimized away when inliner doen't see operand is constant.
1727 Other optimizers might think otherwise. */
1728 if (gimple_cond_code (last) != NE_EXPR
1729 || !integer_zerop (gimple_cond_rhs (last)))
1731 set_stmt = SSA_NAME_DEF_STMT (op);
1732 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1733 || gimple_call_num_args (set_stmt) != 1)
1735 op2 = gimple_call_arg (set_stmt, 0);
1736 if (!unmodified_parm_or_parm_agg_item
1737 (info, set_stmt, op2, &index, &aggpos))
1739 FOR_EACH_EDGE (e, ei, bb->succs) if (e->flags & EDGE_FALSE_VALUE)
1741 struct predicate p = add_condition (summary, index, &aggpos,
1742 IS_NOT_CONSTANT, NULL_TREE);
1743 e->aux = pool_alloc (edge_predicate_pool);
1744 *(struct predicate *) e->aux = p;
1749 /* If BB ends by a switch we can turn into predicates, attach corresponding
1750 predicates to the CFG edges. */
1753 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1754 struct inline_summary *summary,
1760 struct agg_position_info aggpos;
1766 last = last_stmt (bb);
1767 if (!last || gimple_code (last) != GIMPLE_SWITCH)
1769 op = gimple_switch_index (last);
1770 if (!unmodified_parm_or_parm_agg_item (info, last, op, &index, &aggpos))
1773 FOR_EACH_EDGE (e, ei, bb->succs)
1775 e->aux = pool_alloc (edge_predicate_pool);
1776 *(struct predicate *) e->aux = false_predicate ();
1778 n = gimple_switch_num_labels (last);
1779 for (case_idx = 0; case_idx < n; ++case_idx)
1781 tree cl = gimple_switch_label (last, case_idx);
1785 e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1786 min = CASE_LOW (cl);
1787 max = CASE_HIGH (cl);
1789 /* For default we might want to construct predicate that none
1790 of cases is met, but it is bit hard to do not having negations
1791 of conditionals handy. */
1793 p = true_predicate ();
1795 p = add_condition (summary, index, &aggpos, EQ_EXPR, min);
1798 struct predicate p1, p2;
1799 p1 = add_condition (summary, index, &aggpos, GE_EXPR, min);
1800 p2 = add_condition (summary, index, &aggpos, LE_EXPR, max);
1801 p = and_predicates (summary->conds, &p1, &p2);
1803 *(struct predicate *) e->aux
1804 = or_predicates (summary->conds, &p, (struct predicate *) e->aux);
1809 /* For each BB in NODE attach to its AUX pointer predicate under
1810 which it is executable. */
1813 compute_bb_predicates (struct cgraph_node *node,
1814 struct ipa_node_params *parms_info,
1815 struct inline_summary *summary)
1817 struct function *my_function = DECL_STRUCT_FUNCTION (node->symbol.decl);
1821 FOR_EACH_BB_FN (bb, my_function)
1823 set_cond_stmt_execution_predicate (parms_info, summary, bb);
1824 set_switch_stmt_execution_predicate (parms_info, summary, bb);
1827 /* Entry block is always executable. */
1828 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1829 = pool_alloc (edge_predicate_pool);
1830 *(struct predicate *) ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1831 = true_predicate ();
1833 /* A simple dataflow propagation of predicates forward in the CFG.
1834 TODO: work in reverse postorder. */
1838 FOR_EACH_BB_FN (bb, my_function)
1840 struct predicate p = false_predicate ();
1843 FOR_EACH_EDGE (e, ei, bb->preds)
1847 struct predicate this_bb_predicate
1848 = *(struct predicate *) e->src->aux;
1851 = and_predicates (summary->conds, &this_bb_predicate,
1852 (struct predicate *) e->aux);
1853 p = or_predicates (summary->conds, &p, &this_bb_predicate);
1854 if (true_predicate_p (&p))
1858 if (false_predicate_p (&p))
1859 gcc_assert (!bb->aux);
1865 bb->aux = pool_alloc (edge_predicate_pool);
1866 *((struct predicate *) bb->aux) = p;
1868 else if (!predicates_equal_p (&p, (struct predicate *) bb->aux))
1871 *((struct predicate *) bb->aux) = p;
1879 /* We keep info about constantness of SSA names. */
1881 typedef struct predicate predicate_t;
1882 /* Return predicate specifying when the STMT might have result that is not
1883 a compile time constant. */
1885 static struct predicate
1886 will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
1887 struct inline_summary *summary,
1889 vec<predicate_t> nonconstant_names)
1894 while (UNARY_CLASS_P (expr))
1895 expr = TREE_OPERAND (expr, 0);
1897 parm = unmodified_parm (NULL, expr);
1898 if (parm && (index = ipa_get_param_decl_index (info, parm)) >= 0)
1899 return add_condition (summary, index, NULL, CHANGED, NULL_TREE);
1900 if (is_gimple_min_invariant (expr))
1901 return false_predicate ();
1902 if (TREE_CODE (expr) == SSA_NAME)
1903 return nonconstant_names[SSA_NAME_VERSION (expr)];
1904 if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
1906 struct predicate p1 = will_be_nonconstant_expr_predicate
1907 (info, summary, TREE_OPERAND (expr, 0),
1909 struct predicate p2;
1910 if (true_predicate_p (&p1))
1912 p2 = will_be_nonconstant_expr_predicate (info, summary,
1913 TREE_OPERAND (expr, 1),
1915 return or_predicates (summary->conds, &p1, &p2);
1917 else if (TREE_CODE (expr) == COND_EXPR)
1919 struct predicate p1 = will_be_nonconstant_expr_predicate
1920 (info, summary, TREE_OPERAND (expr, 0),
1922 struct predicate p2;
1923 if (true_predicate_p (&p1))
1925 p2 = will_be_nonconstant_expr_predicate (info, summary,
1926 TREE_OPERAND (expr, 1),
1928 if (true_predicate_p (&p2))
1930 p1 = or_predicates (summary->conds, &p1, &p2);
1931 p2 = will_be_nonconstant_expr_predicate (info, summary,
1932 TREE_OPERAND (expr, 2),
1934 return or_predicates (summary->conds, &p1, &p2);
1941 return false_predicate ();
1945 /* Return predicate specifying when the STMT might have result that is not
1946 a compile time constant. */
1948 static struct predicate
1949 will_be_nonconstant_predicate (struct ipa_node_params *info,
1950 struct inline_summary *summary,
1952 vec<predicate_t> nonconstant_names)
1954 struct predicate p = true_predicate ();
1957 struct predicate op_non_const;
1960 struct agg_position_info aggpos;
1962 /* What statments might be optimized away
1963 when their arguments are constant
1964 TODO: also trivial builtins.
1965 builtin_constant_p is already handled later. */
1966 if (gimple_code (stmt) != GIMPLE_ASSIGN
1967 && gimple_code (stmt) != GIMPLE_COND
1968 && gimple_code (stmt) != GIMPLE_SWITCH)
1971 /* Stores will stay anyway. */
1972 if (gimple_store_p (stmt))
1975 is_load = gimple_assign_load_p (stmt);
1977 /* Loads can be optimized when the value is known. */
1981 gcc_assert (gimple_assign_single_p (stmt));
1982 op = gimple_assign_rhs1 (stmt);
1983 if (!unmodified_parm_or_parm_agg_item (info, stmt, op, &base_index,
1990 /* See if we understand all operands before we start
1991 adding conditionals. */
1992 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1994 tree parm = unmodified_parm (stmt, use);
1995 /* For arguments we can build a condition. */
1996 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1998 if (TREE_CODE (use) != SSA_NAME)
2000 /* If we know when operand is constant,
2001 we still can say something useful. */
2002 if (!true_predicate_p (&nonconstant_names[SSA_NAME_VERSION (use)]))
2009 add_condition (summary, base_index, &aggpos, CHANGED, NULL);
2011 op_non_const = false_predicate ();
2012 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2014 tree parm = unmodified_parm (stmt, use);
2017 if (parm && (index = ipa_get_param_decl_index (info, parm)) >= 0)
2019 if (index != base_index)
2020 p = add_condition (summary, index, NULL, CHANGED, NULL_TREE);
2025 p = nonconstant_names[SSA_NAME_VERSION (use)];
2026 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
2028 if (gimple_code (stmt) == GIMPLE_ASSIGN
2029 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
2030 nonconstant_names[SSA_NAME_VERSION (gimple_assign_lhs (stmt))]
2032 return op_non_const;
2035 struct record_modified_bb_info
2041 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2042 set except for info->stmt. */
2045 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
2047 struct record_modified_bb_info *info =
2048 (struct record_modified_bb_info *) data;
2049 if (SSA_NAME_DEF_STMT (vdef) == info->stmt)
2051 bitmap_set_bit (info->bb_set,
2052 SSA_NAME_IS_DEFAULT_DEF (vdef)
2053 ? ENTRY_BLOCK_PTR->index
2054 : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index);
2058 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2059 will change since last invocation of STMT.
2061 Value 0 is reserved for compile time invariants.
2062 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2063 ought to be REG_BR_PROB_BASE / estimated_iters. */
2066 param_change_prob (gimple stmt, int i)
2068 tree op = gimple_call_arg (stmt, i);
2069 basic_block bb = gimple_bb (stmt);
2072 /* Global invariants neve change. */
2073 if (is_gimple_min_invariant (op))
2075 /* We would have to do non-trivial analysis to really work out what
2076 is the probability of value to change (i.e. when init statement
2077 is in a sibling loop of the call).
2079 We do an conservative estimate: when call is executed N times more often
2080 than the statement defining value, we take the frequency 1/N. */
2081 if (TREE_CODE (op) == SSA_NAME)
2086 return REG_BR_PROB_BASE;
2088 if (SSA_NAME_IS_DEFAULT_DEF (op))
2089 init_freq = ENTRY_BLOCK_PTR->frequency;
2091 init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency;
2095 if (init_freq < bb->frequency)
2096 return MAX ((init_freq * REG_BR_PROB_BASE +
2097 bb->frequency / 2) / bb->frequency, 1);
2099 return REG_BR_PROB_BASE;
2102 base = get_base_address (op);
2107 struct record_modified_bb_info info;
2111 if (const_value_known_p (base))
2114 return REG_BR_PROB_BASE;
2115 ao_ref_init (&refd, op);
2117 info.bb_set = BITMAP_ALLOC (NULL);
2118 walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
2120 if (bitmap_bit_p (info.bb_set, bb->index))
2122 BITMAP_FREE (info.bb_set);
2123 return REG_BR_PROB_BASE;
2126 /* Assume that every memory is initialized at entry.
2127 TODO: Can we easilly determine if value is always defined
2128 and thus we may skip entry block? */
2129 if (ENTRY_BLOCK_PTR->frequency)
2130 max = ENTRY_BLOCK_PTR->frequency;
2134 EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi)
2135 max = MIN (max, BASIC_BLOCK (index)->frequency);
2137 BITMAP_FREE (info.bb_set);
2138 if (max < bb->frequency)
2139 return MAX ((max * REG_BR_PROB_BASE +
2140 bb->frequency / 2) / bb->frequency, 1);
2142 return REG_BR_PROB_BASE;
2144 return REG_BR_PROB_BASE;
2147 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2148 sub-graph and if the predicate the condition depends on is known. If so,
2149 return true and store the pointer the predicate in *P. */
2152 phi_result_unknown_predicate (struct ipa_node_params *info,
2153 struct inline_summary *summary, basic_block bb,
2154 struct predicate *p,
2155 vec<predicate_t> nonconstant_names)
2159 basic_block first_bb = NULL;
2162 if (single_pred_p (bb))
2164 *p = false_predicate ();
2168 FOR_EACH_EDGE (e, ei, bb->preds)
2170 if (single_succ_p (e->src))
2172 if (!single_pred_p (e->src))
2175 first_bb = single_pred (e->src);
2176 else if (single_pred (e->src) != first_bb)
2183 else if (e->src != first_bb)
2191 stmt = last_stmt (first_bb);
2193 || gimple_code (stmt) != GIMPLE_COND
2194 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt)))
2197 *p = will_be_nonconstant_expr_predicate (info, summary,
2198 gimple_cond_lhs (stmt),
2200 if (true_predicate_p (p))
2206 /* Given a PHI statement in a function described by inline properties SUMMARY
2207 and *P being the predicate describing whether the selected PHI argument is
2208 known, store a predicate for the result of the PHI statement into
2209 NONCONSTANT_NAMES, if possible. */
2212 predicate_for_phi_result (struct inline_summary *summary, gimple phi,
2213 struct predicate *p,
2214 vec<predicate_t> nonconstant_names)
2218 for (i = 0; i < gimple_phi_num_args (phi); i++)
2220 tree arg = gimple_phi_arg (phi, i)->def;
2221 if (!is_gimple_min_invariant (arg))
2223 gcc_assert (TREE_CODE (arg) == SSA_NAME);
2224 *p = or_predicates (summary->conds, p,
2225 &nonconstant_names[SSA_NAME_VERSION (arg)]);
2226 if (true_predicate_p (p))
2231 if (dump_file && (dump_flags & TDF_DETAILS))
2233 fprintf (dump_file, "\t\tphi predicate: ");
2234 dump_predicate (dump_file, summary->conds, p);
2236 nonconstant_names[SSA_NAME_VERSION (gimple_phi_result (phi))] = *p;
2239 /* Return predicate specifying when array index in access OP becomes non-constant. */
2241 static struct predicate
2242 array_index_predicate (struct inline_summary *info,
2243 vec< predicate_t> nonconstant_names, tree op)
2245 struct predicate p = false_predicate ();
2246 while (handled_component_p (op))
2248 if (TREE_CODE (op) == ARRAY_REF || TREE_CODE (op) == ARRAY_RANGE_REF)
2250 if (TREE_CODE (TREE_OPERAND (op, 1)) == SSA_NAME)
2251 p = or_predicates (info->conds, &p,
2252 &nonconstant_names[SSA_NAME_VERSION
2253 (TREE_OPERAND (op, 1))]);
2255 op = TREE_OPERAND (op, 0);
2260 /* Compute function body size parameters for NODE.
2261 When EARLY is true, we compute only simple summaries without
2262 non-trivial predicates to drive the early inliner. */
2265 estimate_function_body_sizes (struct cgraph_node *node, bool early)
2268 /* Estimate static overhead for function prologue/epilogue and alignment. */
2270 /* Benefits are scaled by probability of elimination that is in range
2273 gimple_stmt_iterator bsi;
2274 struct function *my_function = DECL_STRUCT_FUNCTION (node->symbol.decl);
2276 struct inline_summary *info = inline_summary (node);
2277 struct predicate bb_predicate;
2278 struct ipa_node_params *parms_info = NULL;
2279 vec<predicate_t> nonconstant_names = vNULL;
2282 predicate array_index = true_predicate ();
2287 if (optimize && !early)
2289 calculate_dominance_info (CDI_DOMINATORS);
2290 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
2292 if (ipa_node_params_vector.exists ())
2294 parms_info = IPA_NODE_REF (node);
2295 nonconstant_names.safe_grow_cleared
2296 (SSANAMES (my_function)->length ());
2301 fprintf (dump_file, "\nAnalyzing function body size: %s\n",
2302 cgraph_node_name (node));
2304 /* When we run into maximal number of entries, we assign everything to the
2305 constant truth case. Be sure to have it in list. */
2306 bb_predicate = true_predicate ();
2307 account_size_time (info, 0, 0, &bb_predicate);
2309 bb_predicate = not_inlined_predicate ();
2310 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
2312 gcc_assert (my_function && my_function->cfg);
2314 compute_bb_predicates (node, parms_info, info);
2315 gcc_assert (cfun == my_function);
2316 order = XNEWVEC (int, n_basic_blocks);
2317 nblocks = pre_and_rev_post_order_compute (NULL, order, false);
2318 for (n = 0; n < nblocks; n++)
2320 bb = BASIC_BLOCK (order[n]);
2321 freq = compute_call_stmt_bb_frequency (node->symbol.decl, bb);
2323 /* TODO: Obviously predicates can be propagated down across CFG. */
2327 bb_predicate = *(struct predicate *) bb->aux;
2329 bb_predicate = false_predicate ();
2332 bb_predicate = true_predicate ();
2334 if (dump_file && (dump_flags & TDF_DETAILS))
2336 fprintf (dump_file, "\n BB %i predicate:", bb->index);
2337 dump_predicate (dump_file, info->conds, &bb_predicate);
2340 if (parms_info && nonconstant_names.exists ())
2342 struct predicate phi_predicate;
2343 bool first_phi = true;
2345 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2348 && !phi_result_unknown_predicate (parms_info, info, bb,
2353 if (dump_file && (dump_flags & TDF_DETAILS))
2355 fprintf (dump_file, " ");
2356 print_gimple_stmt (dump_file, gsi_stmt (bsi), 0, 0);
2358 predicate_for_phi_result (info, gsi_stmt (bsi), &phi_predicate,
2363 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2365 gimple stmt = gsi_stmt (bsi);
2366 int this_size = estimate_num_insns (stmt, &eni_size_weights);
2367 int this_time = estimate_num_insns (stmt, &eni_time_weights);
2369 struct predicate will_be_nonconstant;
2371 if (dump_file && (dump_flags & TDF_DETAILS))
2373 fprintf (dump_file, " ");
2374 print_gimple_stmt (dump_file, stmt, 0, 0);
2375 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2376 ((double) freq) / CGRAPH_FREQ_BASE, this_size,
2380 if (gimple_assign_load_p (stmt) && nonconstant_names.exists ())
2382 struct predicate this_array_index;
2384 array_index_predicate (info, nonconstant_names,
2385 gimple_assign_rhs1 (stmt));
2386 if (!false_predicate_p (&this_array_index))
2388 and_predicates (info->conds, &array_index,
2391 if (gimple_store_p (stmt) && nonconstant_names.exists ())
2393 struct predicate this_array_index;
2395 array_index_predicate (info, nonconstant_names,
2396 gimple_get_lhs (stmt));
2397 if (!false_predicate_p (&this_array_index))
2399 and_predicates (info->conds, &array_index,
2404 if (is_gimple_call (stmt))
2406 struct cgraph_edge *edge = cgraph_edge (node, stmt);
2407 struct inline_edge_summary *es = inline_edge_summary (edge);
2409 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2410 resolved as constant. We however don't want to optimize
2411 out the cgraph edges. */
2412 if (nonconstant_names.exists ()
2413 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
2414 && gimple_call_lhs (stmt)
2415 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
2417 struct predicate false_p = false_predicate ();
2418 nonconstant_names[SSA_NAME_VERSION (gimple_call_lhs (stmt))]
2421 if (ipa_node_params_vector.exists ())
2423 int count = gimple_call_num_args (stmt);
2427 es->param.safe_grow_cleared (count);
2428 for (i = 0; i < count; i++)
2430 int prob = param_change_prob (stmt, i);
2431 gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
2432 es->param[i].change_prob = prob;
2436 es->call_stmt_size = this_size;
2437 es->call_stmt_time = this_time;
2438 es->loop_depth = bb_loop_depth (bb);
2439 edge_set_predicate (edge, &bb_predicate);
2442 /* TODO: When conditional jump or swithc is known to be constant, but
2443 we did not translate it into the predicates, we really can account
2444 just maximum of the possible paths. */
2447 = will_be_nonconstant_predicate (parms_info, info,
2448 stmt, nonconstant_names);
2449 if (this_time || this_size)
2455 prob = eliminated_by_inlining_prob (stmt);
2456 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
2458 "\t\t50%% will be eliminated by inlining\n");
2459 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
2460 fprintf (dump_file, "\t\tWill be eliminated by inlining\n");
2463 p = and_predicates (info->conds, &bb_predicate,
2464 &will_be_nonconstant);
2466 p = true_predicate ();
2468 if (!false_predicate_p (&p))
2472 if (time > MAX_TIME * INLINE_TIME_SCALE)
2473 time = MAX_TIME * INLINE_TIME_SCALE;
2476 /* We account everything but the calls. Calls have their own
2477 size/time info attached to cgraph edges. This is necessary
2478 in order to make the cost disappear after inlining. */
2479 if (!is_gimple_call (stmt))
2483 struct predicate ip = not_inlined_predicate ();
2484 ip = and_predicates (info->conds, &ip, &p);
2485 account_size_time (info, this_size * prob,
2486 this_time * prob, &ip);
2489 account_size_time (info, this_size * (2 - prob),
2490 this_time * (2 - prob), &p);
2493 gcc_assert (time >= 0);
2494 gcc_assert (size >= 0);
2498 set_hint_predicate (&inline_summary (node)->array_index, array_index);
2499 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2500 if (time > MAX_TIME)
2504 if (!early && nonconstant_names.exists ())
2508 predicate loop_iterations = true_predicate ();
2509 predicate loop_stride = true_predicate ();
2511 if (dump_file && (dump_flags & TDF_DETAILS))
2512 flow_loops_dump (dump_file, NULL, 0);
2514 FOR_EACH_LOOP (li, loop, 0)
2519 struct tree_niter_desc niter_desc;
2520 basic_block *body = get_loop_body (loop);
2521 bb_predicate = *(struct predicate *) loop->header->aux;
2523 exits = get_loop_exit_edges (loop);
2524 FOR_EACH_VEC_ELT (exits, j, ex)
2525 if (number_of_iterations_exit (loop, ex, &niter_desc, false)
2526 && !is_gimple_min_invariant (niter_desc.niter))
2528 predicate will_be_nonconstant
2529 = will_be_nonconstant_expr_predicate (parms_info, info,
2532 if (!true_predicate_p (&will_be_nonconstant))
2533 will_be_nonconstant = and_predicates (info->conds,
2535 &will_be_nonconstant);
2536 if (!true_predicate_p (&will_be_nonconstant)
2537 && !false_predicate_p (&will_be_nonconstant))
2538 /* This is slightly inprecise. We may want to represent each
2539 loop with independent predicate. */
2541 and_predicates (info->conds, &loop_iterations,
2542 &will_be_nonconstant);
2546 for (i = 0; i < loop->num_nodes; i++)
2548 gimple_stmt_iterator gsi;
2549 bb_predicate = *(struct predicate *) body[i]->aux;
2550 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi);
2553 gimple stmt = gsi_stmt (gsi);
2558 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2560 predicate will_be_nonconstant;
2563 (loop, loop_containing_stmt (stmt), use, &iv, true)
2564 || is_gimple_min_invariant (iv.step))
2567 = will_be_nonconstant_expr_predicate (parms_info, info,
2570 if (!true_predicate_p (&will_be_nonconstant))
2572 = and_predicates (info->conds,
2574 &will_be_nonconstant);
2575 if (!true_predicate_p (&will_be_nonconstant)
2576 && !false_predicate_p (&will_be_nonconstant))
2577 /* This is slightly inprecise. We may want to represent
2578 each loop with independent predicate. */
2580 and_predicates (info->conds, &loop_stride,
2581 &will_be_nonconstant);
2587 set_hint_predicate (&inline_summary (node)->loop_iterations,
2589 set_hint_predicate (&inline_summary (node)->loop_stride, loop_stride);
2592 FOR_ALL_BB_FN (bb, my_function)
2598 pool_free (edge_predicate_pool, bb->aux);
2600 FOR_EACH_EDGE (e, ei, bb->succs)
2603 pool_free (edge_predicate_pool, e->aux);
2607 inline_summary (node)->self_time = time;
2608 inline_summary (node)->self_size = size;
2609 nonconstant_names.release ();
2610 if (optimize && !early)
2612 loop_optimizer_finalize ();
2613 free_dominance_info (CDI_DOMINATORS);
2617 fprintf (dump_file, "\n");
2618 dump_inline_summary (dump_file, node);
2623 /* Compute parameters of functions used by inliner.
2624 EARLY is true when we compute parameters for the early inliner */
2627 compute_inline_parameters (struct cgraph_node *node, bool early)
2629 HOST_WIDE_INT self_stack_size;
2630 struct cgraph_edge *e;
2631 struct inline_summary *info;
2633 gcc_assert (!node->global.inlined_to);
2635 inline_summary_alloc ();
2637 info = inline_summary (node);
2638 reset_inline_summary (node);
2640 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2641 Once this happen, we will need to more curefully predict call
2643 if (node->thunk.thunk_p)
2645 struct inline_edge_summary *es = inline_edge_summary (node->callees);
2646 struct predicate t = true_predicate ();
2648 info->inlinable = 0;
2649 node->callees->call_stmt_cannot_inline_p = true;
2650 node->local.can_change_signature = false;
2651 es->call_stmt_time = 1;
2652 es->call_stmt_size = 1;
2653 account_size_time (info, 0, 0, &t);
2657 /* Even is_gimple_min_invariant rely on current_function_decl. */
2658 push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
2660 /* Estimate the stack size for the function if we're optimizing. */
2661 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
2662 info->estimated_self_stack_size = self_stack_size;
2663 info->estimated_stack_size = self_stack_size;
2664 info->stack_frame_offset = 0;
2666 /* Can this function be inlined at all? */
2667 info->inlinable = tree_inlinable_function_p (node->symbol.decl);
2669 /* Type attributes can use parameter indices to describe them. */
2670 if (TYPE_ATTRIBUTES (TREE_TYPE (node->symbol.decl)))
2671 node->local.can_change_signature = false;
2674 /* Otherwise, inlinable functions always can change signature. */
2675 if (info->inlinable)
2676 node->local.can_change_signature = true;
2679 /* Functions calling builtin_apply can not change signature. */
2680 for (e = node->callees; e; e = e->next_callee)
2682 tree cdecl = e->callee->symbol.decl;
2683 if (DECL_BUILT_IN (cdecl)
2684 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2685 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2686 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
2689 node->local.can_change_signature = !e;
2692 estimate_function_body_sizes (node, early);
2694 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2695 info->time = info->self_time;
2696 info->size = info->self_size;
2697 info->stack_frame_offset = 0;
2698 info->estimated_stack_size = info->estimated_self_stack_size;
2699 #ifdef ENABLE_CHECKING
2700 inline_update_overall_summary (node);
2701 gcc_assert (info->time == info->self_time && info->size == info->self_size);
2708 /* Compute parameters of functions used by inliner using
2709 current_function_decl. */
2712 compute_inline_parameters_for_current (void)
2714 compute_inline_parameters (cgraph_get_node (current_function_decl), true);
2718 struct gimple_opt_pass pass_inline_parameters =
2722 "inline_param", /* name */
2723 OPTGROUP_INLINE, /* optinfo_flags */
2725 compute_inline_parameters_for_current, /* execute */
2728 0, /* static_pass_number */
2729 TV_INLINE_PARAMETERS, /* tv_id */
2730 0, /* properties_required */
2731 0, /* properties_provided */
2732 0, /* properties_destroyed */
2733 0, /* todo_flags_start */
2734 0 /* todo_flags_finish */
2739 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2743 estimate_edge_devirt_benefit (struct cgraph_edge *ie,
2744 int *size, int *time,
2745 vec<tree> known_vals,
2746 vec<tree> known_binfos,
2747 vec<ipa_agg_jump_function_p> known_aggs)
2750 struct cgraph_node *callee;
2751 struct inline_summary *isummary;
2753 if (!known_vals.exists () && !known_binfos.exists ())
2755 if (!flag_indirect_inlining)
2758 target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos,
2763 /* Account for difference in cost between indirect and direct calls. */
2764 *size -= (eni_size_weights.indirect_call_cost - eni_size_weights.call_cost);
2765 *time -= (eni_time_weights.indirect_call_cost - eni_time_weights.call_cost);
2766 gcc_checking_assert (*time >= 0);
2767 gcc_checking_assert (*size >= 0);
2769 callee = cgraph_get_node (target);
2770 if (!callee || !callee->analyzed)
2772 isummary = inline_summary (callee);
2773 return isummary->inlinable;
2776 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2779 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
2781 vec<tree> known_vals,
2782 vec<tree> known_binfos,
2783 vec<ipa_agg_jump_function_p> known_aggs,
2784 inline_hints *hints)
2786 struct inline_edge_summary *es = inline_edge_summary (e);
2787 int call_size = es->call_stmt_size;
2788 int call_time = es->call_stmt_time;
2790 && estimate_edge_devirt_benefit (e, &call_size, &call_time,
2791 known_vals, known_binfos, known_aggs)
2792 && hints && cgraph_maybe_hot_edge_p (e))
2793 *hints |= INLINE_HINT_indirect_call;
2794 *size += call_size * INLINE_SIZE_SCALE;
2795 *time += call_time * prob / REG_BR_PROB_BASE
2796 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE);
2797 if (*time > MAX_TIME * INLINE_TIME_SCALE)
2798 *time = MAX_TIME * INLINE_TIME_SCALE;
2803 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
2804 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
2808 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
2809 inline_hints *hints,
2810 clause_t possible_truths,
2811 vec<tree> known_vals,
2812 vec<tree> known_binfos,
2813 vec<ipa_agg_jump_function_p> known_aggs)
2815 struct cgraph_edge *e;
2816 for (e = node->callees; e; e = e->next_callee)
2818 struct inline_edge_summary *es = inline_edge_summary (e);
2820 || evaluate_predicate (es->predicate, possible_truths))
2822 if (e->inline_failed)
2824 /* Predicates of calls shall not use NOT_CHANGED codes,
2825 sowe do not need to compute probabilities. */
2826 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE,
2827 known_vals, known_binfos,
2831 estimate_calls_size_and_time (e->callee, size, time, hints,
2833 known_vals, known_binfos,
2837 for (e = node->indirect_calls; e; e = e->next_callee)
2839 struct inline_edge_summary *es = inline_edge_summary (e);
2841 || evaluate_predicate (es->predicate, possible_truths))
2842 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE,
2843 known_vals, known_binfos, known_aggs,
2849 /* Estimate size and time needed to execute NODE assuming
2850 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
2851 about NODE's arguments. */
2854 estimate_node_size_and_time (struct cgraph_node *node,
2855 clause_t possible_truths,
2856 vec<tree> known_vals,
2857 vec<tree> known_binfos,
2858 vec<ipa_agg_jump_function_p> known_aggs,
2859 int *ret_size, int *ret_time,
2860 inline_hints *ret_hints,
2861 vec<inline_param_summary_t>
2862 inline_param_summary)
2864 struct inline_summary *info = inline_summary (node);
2868 inline_hints hints = 0;
2871 if (dump_file && (dump_flags & TDF_DETAILS))
2874 fprintf (dump_file, " Estimating body: %s/%i\n"
2875 " Known to be false: ", cgraph_node_name (node), node->uid);
2877 for (i = predicate_not_inlined_condition;
2878 i < (predicate_first_dynamic_condition
2879 + (int) vec_safe_length (info->conds)); i++)
2880 if (!(possible_truths & (1 << i)))
2883 fprintf (dump_file, ", ");
2885 dump_condition (dump_file, info->conds, i);
2889 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
2890 if (evaluate_predicate (&e->predicate, possible_truths))
2893 gcc_checking_assert (e->time >= 0);
2894 gcc_checking_assert (time >= 0);
2895 if (!inline_param_summary.exists ())
2899 int prob = predicate_probability (info->conds,
2902 inline_param_summary);
2903 gcc_checking_assert (prob >= 0);
2904 gcc_checking_assert (prob <= REG_BR_PROB_BASE);
2905 time += ((gcov_type) e->time * prob) / REG_BR_PROB_BASE;
2907 if (time > MAX_TIME * INLINE_TIME_SCALE)
2908 time = MAX_TIME * INLINE_TIME_SCALE;
2909 gcc_checking_assert (time >= 0);
2912 gcc_checking_assert (size >= 0);
2913 gcc_checking_assert (time >= 0);
2915 if (info->loop_iterations
2916 && !evaluate_predicate (info->loop_iterations, possible_truths))
2917 hints |= INLINE_HINT_loop_iterations;
2918 if (info->loop_stride
2919 && !evaluate_predicate (info->loop_stride, possible_truths))
2920 hints |= INLINE_HINT_loop_stride;
2921 if (info->array_index
2922 && !evaluate_predicate (info->array_index, possible_truths))
2923 hints |= INLINE_HINT_array_index;
2925 hints |= INLINE_HINT_in_scc;
2926 if (DECL_DECLARED_INLINE_P (node->symbol.decl))
2927 hints |= INLINE_HINT_declared_inline;
2929 estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
2930 known_vals, known_binfos, known_aggs);
2931 gcc_checking_assert (size >= 0);
2932 gcc_checking_assert (time >= 0);
2933 time = RDIV (time, INLINE_TIME_SCALE);
2934 size = RDIV (size, INLINE_SIZE_SCALE);
2936 if (dump_file && (dump_flags & TDF_DETAILS))
2937 fprintf (dump_file, "\n size:%i time:%i\n", (int) size, (int) time);
2948 /* Estimate size and time needed to execute callee of EDGE assuming that
2949 parameters known to be constant at caller of EDGE are propagated.
2950 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
2951 and types for parameters. */
2954 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
2955 vec<tree> known_vals,
2956 vec<tree> known_binfos,
2957 vec<ipa_agg_jump_function_p> known_aggs,
2958 int *ret_size, int *ret_time,
2959 inline_hints *hints)
2963 clause = evaluate_conditions_for_known_args (node, false, known_vals,
2965 estimate_node_size_and_time (node, clause, known_vals, known_binfos,
2966 known_aggs, ret_size, ret_time, hints, vNULL);
2969 /* Translate all conditions from callee representation into caller
2970 representation and symbolically evaluate predicate P into new predicate.
2972 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
2973 is summary of function predicate P is from. OPERAND_MAP is array giving
2974 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
2975 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
2976 predicate under which callee is executed. OFFSET_MAP is an array of of
2977 offsets that need to be added to conditions, negative offset means that
2978 conditions relying on values passed by reference have to be discarded
2979 because they might not be preserved (and should be considered offset zero
2980 for other purposes). */
2982 static struct predicate
2983 remap_predicate (struct inline_summary *info,
2984 struct inline_summary *callee_info,
2985 struct predicate *p,
2986 vec<int> operand_map,
2987 vec<int> offset_map,
2988 clause_t possible_truths, struct predicate *toplev_predicate)
2991 struct predicate out = true_predicate ();
2993 /* True predicate is easy. */
2994 if (true_predicate_p (p))
2995 return *toplev_predicate;
2996 for (i = 0; p->clause[i]; i++)
2998 clause_t clause = p->clause[i];
3000 struct predicate clause_predicate = false_predicate ();
3002 gcc_assert (i < MAX_CLAUSES);
3004 for (cond = 0; cond < NUM_CONDITIONS; cond++)
3005 /* Do we have condition we can't disprove? */
3006 if (clause & possible_truths & (1 << cond))
3008 struct predicate cond_predicate;
3009 /* Work out if the condition can translate to predicate in the
3010 inlined function. */
3011 if (cond >= predicate_first_dynamic_condition)
3013 struct condition *c;
3015 c = &(*callee_info->conds)[cond
3017 predicate_first_dynamic_condition];
3018 /* See if we can remap condition operand to caller's operand.
3019 Otherwise give up. */
3020 if (!operand_map.exists ()
3021 || (int) operand_map.length () <= c->operand_num
3022 || operand_map[c->operand_num] == -1
3023 /* TODO: For non-aggregate conditions, adding an offset is
3024 basically an arithmetic jump function processing which
3025 we should support in future. */
3026 || ((!c->agg_contents || !c->by_ref)
3027 && offset_map[c->operand_num] > 0)
3028 || (c->agg_contents && c->by_ref
3029 && offset_map[c->operand_num] < 0))
3030 cond_predicate = true_predicate ();
3033 struct agg_position_info ap;
3034 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
3035 if (offset_delta < 0)
3037 gcc_checking_assert (!c->agg_contents || !c->by_ref);
3040 gcc_assert (!c->agg_contents
3041 || c->by_ref || offset_delta == 0);
3042 ap.offset = c->offset + offset_delta;
3043 ap.agg_contents = c->agg_contents;
3044 ap.by_ref = c->by_ref;
3045 cond_predicate = add_condition (info,
3046 operand_map[c->operand_num],
3047 &ap, c->code, c->val);
3050 /* Fixed conditions remains same, construct single
3051 condition predicate. */
3054 cond_predicate.clause[0] = 1 << cond;
3055 cond_predicate.clause[1] = 0;
3057 clause_predicate = or_predicates (info->conds, &clause_predicate,
3060 out = and_predicates (info->conds, &out, &clause_predicate);
3062 return and_predicates (info->conds, &out, toplev_predicate);
3066 /* Update summary information of inline clones after inlining.
3067 Compute peak stack usage. */
3070 inline_update_callee_summaries (struct cgraph_node *node, int depth)
3072 struct cgraph_edge *e;
3073 struct inline_summary *callee_info = inline_summary (node);
3074 struct inline_summary *caller_info = inline_summary (node->callers->caller);
3077 callee_info->stack_frame_offset
3078 = caller_info->stack_frame_offset
3079 + caller_info->estimated_self_stack_size;
3080 peak = callee_info->stack_frame_offset
3081 + callee_info->estimated_self_stack_size;
3082 if (inline_summary (node->global.inlined_to)->estimated_stack_size < peak)
3083 inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
3084 cgraph_propagate_frequency (node);
3085 for (e = node->callees; e; e = e->next_callee)
3087 if (!e->inline_failed)
3088 inline_update_callee_summaries (e->callee, depth);
3089 inline_edge_summary (e)->loop_depth += depth;
3091 for (e = node->indirect_calls; e; e = e->next_callee)
3092 inline_edge_summary (e)->loop_depth += depth;
3095 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3096 When functoin A is inlined in B and A calls C with parameter that
3097 changes with probability PROB1 and C is known to be passthroug
3098 of argument if B that change with probability PROB2, the probability
3099 of change is now PROB1*PROB2. */
3102 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
3103 struct cgraph_edge *edge)
3105 if (ipa_node_params_vector.exists ())
3108 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
3109 struct inline_edge_summary *es = inline_edge_summary (edge);
3110 struct inline_edge_summary *inlined_es
3111 = inline_edge_summary (inlined_edge);
3113 for (i = 0; i < ipa_get_cs_argument_count (args); i++)
3115 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
3116 if (jfunc->type == IPA_JF_PASS_THROUGH
3117 && (ipa_get_jf_pass_through_formal_id (jfunc)
3118 < (int) inlined_es->param.length ()))
3120 int jf_formal_id = ipa_get_jf_pass_through_formal_id (jfunc);
3121 int prob1 = es->param[i].change_prob;
3122 int prob2 = inlined_es->param[jf_formal_id].change_prob;
3123 int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2)
3124 / REG_BR_PROB_BASE);
3126 if (prob1 && prob2 && !prob)
3129 es->param[i].change_prob = prob;
3135 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3137 Remap predicates of callees of NODE. Rest of arguments match
3140 Also update change probabilities. */
3143 remap_edge_summaries (struct cgraph_edge *inlined_edge,
3144 struct cgraph_node *node,
3145 struct inline_summary *info,
3146 struct inline_summary *callee_info,
3147 vec<int> operand_map,
3148 vec<int> offset_map,
3149 clause_t possible_truths,
3150 struct predicate *toplev_predicate)
3152 struct cgraph_edge *e;
3153 for (e = node->callees; e; e = e->next_callee)
3155 struct inline_edge_summary *es = inline_edge_summary (e);
3158 if (e->inline_failed)
3160 remap_edge_change_prob (inlined_edge, e);
3164 p = remap_predicate (info, callee_info,
3165 es->predicate, operand_map, offset_map,
3166 possible_truths, toplev_predicate);
3167 edge_set_predicate (e, &p);
3168 /* TODO: We should remove the edge for code that will be
3169 optimized out, but we need to keep verifiers and tree-inline
3170 happy. Make it cold for now. */
3171 if (false_predicate_p (&p))
3178 edge_set_predicate (e, toplev_predicate);
3181 remap_edge_summaries (inlined_edge, e->callee, info, callee_info,
3182 operand_map, offset_map, possible_truths,
3185 for (e = node->indirect_calls; e; e = e->next_callee)
3187 struct inline_edge_summary *es = inline_edge_summary (e);
3190 remap_edge_change_prob (inlined_edge, e);
3193 p = remap_predicate (info, callee_info,
3194 es->predicate, operand_map, offset_map,
3195 possible_truths, toplev_predicate);
3196 edge_set_predicate (e, &p);
3197 /* TODO: We should remove the edge for code that will be optimized
3198 out, but we need to keep verifiers and tree-inline happy.
3199 Make it cold for now. */
3200 if (false_predicate_p (&p))
3207 edge_set_predicate (e, toplev_predicate);
3211 /* Same as remap_predicate, but set result into hint *HINT. */
3214 remap_hint_predicate (struct inline_summary *info,
3215 struct inline_summary *callee_info,
3216 struct predicate **hint,
3217 vec<int> operand_map,
3218 vec<int> offset_map,
3219 clause_t possible_truths,
3220 struct predicate *toplev_predicate)
3226 p = remap_predicate (info, callee_info,
3228 operand_map, offset_map,
3229 possible_truths, toplev_predicate);
3230 if (!false_predicate_p (&p) && !true_predicate_p (&p))
3233 set_hint_predicate (hint, p);
3235 **hint = and_predicates (info->conds, *hint, &p);
3239 /* We inlined EDGE. Update summary of the function we inlined into. */
3242 inline_merge_summary (struct cgraph_edge *edge)
3244 struct inline_summary *callee_info = inline_summary (edge->callee);
3245 struct cgraph_node *to = (edge->caller->global.inlined_to
3246 ? edge->caller->global.inlined_to : edge->caller);
3247 struct inline_summary *info = inline_summary (to);
3248 clause_t clause = 0; /* not_inline is known to be false. */
3250 vec<int> operand_map = vNULL;
3251 vec<int> offset_map = vNULL;
3253 struct predicate toplev_predicate;
3254 struct predicate true_p = true_predicate ();
3255 struct inline_edge_summary *es = inline_edge_summary (edge);
3258 toplev_predicate = *es->predicate;
3260 toplev_predicate = true_predicate ();
3262 if (ipa_node_params_vector.exists () && callee_info->conds)
3264 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
3265 int count = ipa_get_cs_argument_count (args);
3268 evaluate_properties_for_edge (edge, true, &clause, NULL, NULL, NULL);
3271 operand_map.safe_grow_cleared (count);
3272 offset_map.safe_grow_cleared (count);
3274 for (i = 0; i < count; i++)
3276 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
3279 /* TODO: handle non-NOPs when merging. */
3280 if (jfunc->type == IPA_JF_PASS_THROUGH)
3282 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3283 map = ipa_get_jf_pass_through_formal_id (jfunc);
3284 if (!ipa_get_jf_pass_through_agg_preserved (jfunc))
3287 else if (jfunc->type == IPA_JF_ANCESTOR)
3289 HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc);
3290 if (offset >= 0 && offset < INT_MAX)
3292 map = ipa_get_jf_ancestor_formal_id (jfunc);
3293 if (!ipa_get_jf_ancestor_agg_preserved (jfunc))
3295 offset_map[i] = offset;
3298 operand_map[i] = map;
3299 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
3302 for (i = 0; vec_safe_iterate (callee_info->entry, i, &e); i++)
3304 struct predicate p = remap_predicate (info, callee_info,
3305 &e->predicate, operand_map,
3308 if (!false_predicate_p (&p))
3310 gcov_type add_time = ((gcov_type) e->time * edge->frequency
3311 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
3312 int prob = predicate_probability (callee_info->conds,
3315 add_time = ((gcov_type) add_time * prob) / REG_BR_PROB_BASE;
3316 if (add_time > MAX_TIME * INLINE_TIME_SCALE)
3317 add_time = MAX_TIME * INLINE_TIME_SCALE;
3318 if (prob != REG_BR_PROB_BASE
3319 && dump_file && (dump_flags & TDF_DETAILS))
3321 fprintf (dump_file, "\t\tScaling time by probability:%f\n",
3322 (double) prob / REG_BR_PROB_BASE);
3324 account_size_time (info, e->size, add_time, &p);
3327 remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
3328 offset_map, clause, &toplev_predicate);
3329 remap_hint_predicate (info, callee_info,
3330 &callee_info->loop_iterations,
3331 operand_map, offset_map, clause, &toplev_predicate);
3332 remap_hint_predicate (info, callee_info,
3333 &callee_info->loop_stride,
3334 operand_map, offset_map, clause, &toplev_predicate);
3335 remap_hint_predicate (info, callee_info,
3336 &callee_info->array_index,
3337 operand_map, offset_map, clause, &toplev_predicate);
3339 inline_update_callee_summaries (edge->callee,
3340 inline_edge_summary (edge)->loop_depth);
3342 /* We do not maintain predicates of inlined edges, free it. */
3343 edge_set_predicate (edge, &true_p);
3344 /* Similarly remove param summaries. */
3345 es->param.release ();
3346 operand_map.release ();
3347 offset_map.release ();
3350 /* For performance reasons inline_merge_summary is not updating overall size
3351 and time. Recompute it. */
3354 inline_update_overall_summary (struct cgraph_node *node)
3356 struct inline_summary *info = inline_summary (node);
3362 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
3364 info->size += e->size, info->time += e->time;
3365 if (info->time > MAX_TIME * INLINE_TIME_SCALE)
3366 info->time = MAX_TIME * INLINE_TIME_SCALE;
3368 estimate_calls_size_and_time (node, &info->size, &info->time, NULL,
3369 ~(clause_t) (1 << predicate_false_condition),
3370 vNULL, vNULL, vNULL);
3371 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
3372 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
3375 /* Return hints derrived from EDGE. */
3377 simple_edge_hints (struct cgraph_edge *edge)
3380 struct cgraph_node *to = (edge->caller->global.inlined_to
3381 ? edge->caller->global.inlined_to : edge->caller);
3382 if (inline_summary (to)->scc_no
3383 && inline_summary (to)->scc_no == inline_summary (edge->callee)->scc_no
3384 && !cgraph_edge_recursive_p (edge))
3385 hints |= INLINE_HINT_same_scc;
3387 if (to->symbol.lto_file_data && edge->callee->symbol.lto_file_data
3388 && to->symbol.lto_file_data != edge->callee->symbol.lto_file_data)
3389 hints |= INLINE_HINT_cross_module;
3394 /* Estimate the time cost for the caller when inlining EDGE.
3395 Only to be called via estimate_edge_time, that handles the
3398 When caching, also update the cache entry. Compute both time and
3399 size, since we always need both metrics eventually. */
3402 do_estimate_edge_time (struct cgraph_edge *edge)
3407 struct cgraph_node *callee;
3409 vec<tree> known_vals;
3410 vec<tree> known_binfos;
3411 vec<ipa_agg_jump_function_p> known_aggs;
3412 struct inline_edge_summary *es = inline_edge_summary (edge);
3414 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3416 gcc_checking_assert (edge->inline_failed);
3417 evaluate_properties_for_edge (edge, true,
3418 &clause, &known_vals, &known_binfos,
3420 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3421 known_aggs, &size, &time, &hints, es->param);
3422 known_vals.release ();
3423 known_binfos.release ();
3424 known_aggs.release ();
3425 gcc_checking_assert (size >= 0);
3426 gcc_checking_assert (time >= 0);
3428 /* When caching, update the cache entry. */
3429 if (edge_growth_cache.exists ())
3431 if ((int) edge_growth_cache.length () <= edge->uid)
3432 edge_growth_cache.safe_grow_cleared (cgraph_edge_max_uid);
3433 edge_growth_cache[edge->uid].time = time + (time >= 0);
3435 edge_growth_cache[edge->uid].size = size + (size >= 0);
3436 hints |= simple_edge_hints (edge);
3437 edge_growth_cache[edge->uid].hints = hints + 1;
3443 /* Return estimated callee growth after inlining EDGE.
3444 Only to be called via estimate_edge_size. */
3447 do_estimate_edge_size (struct cgraph_edge *edge)
3450 struct cgraph_node *callee;
3452 vec<tree> known_vals;
3453 vec<tree> known_binfos;
3454 vec<ipa_agg_jump_function_p> known_aggs;
3456 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3458 if (edge_growth_cache.exists ())
3460 do_estimate_edge_time (edge);
3461 size = edge_growth_cache[edge->uid].size;
3462 gcc_checking_assert (size);
3463 return size - (size > 0);
3466 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3468 /* Early inliner runs without caching, go ahead and do the dirty work. */
3469 gcc_checking_assert (edge->inline_failed);
3470 evaluate_properties_for_edge (edge, true,
3471 &clause, &known_vals, &known_binfos,
3473 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3474 known_aggs, &size, NULL, NULL, vNULL);
3475 known_vals.release ();
3476 known_binfos.release ();
3477 known_aggs.release ();
3482 /* Estimate the growth of the caller when inlining EDGE.
3483 Only to be called via estimate_edge_size. */
3486 do_estimate_edge_hints (struct cgraph_edge *edge)
3489 struct cgraph_node *callee;
3491 vec<tree> known_vals;
3492 vec<tree> known_binfos;
3493 vec<ipa_agg_jump_function_p> known_aggs;
3495 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3497 if (edge_growth_cache.exists ())
3499 do_estimate_edge_time (edge);
3500 hints = edge_growth_cache[edge->uid].hints;
3501 gcc_checking_assert (hints);
3505 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3507 /* Early inliner runs without caching, go ahead and do the dirty work. */
3508 gcc_checking_assert (edge->inline_failed);
3509 evaluate_properties_for_edge (edge, true,
3510 &clause, &known_vals, &known_binfos,
3512 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3513 known_aggs, NULL, NULL, &hints, vNULL);
3514 known_vals.release ();
3515 known_binfos.release ();
3516 known_aggs.release ();
3517 hints |= simple_edge_hints (edge);
3522 /* Estimate self time of the function NODE after inlining EDGE. */
3525 estimate_time_after_inlining (struct cgraph_node *node,
3526 struct cgraph_edge *edge)
3528 struct inline_edge_summary *es = inline_edge_summary (edge);
3529 if (!es->predicate || !false_predicate_p (es->predicate))
3532 inline_summary (node)->time + estimate_edge_time (edge);
3535 if (time > MAX_TIME)
3539 return inline_summary (node)->time;
3543 /* Estimate the size of NODE after inlining EDGE which should be an
3544 edge to either NODE or a call inlined into NODE. */
3547 estimate_size_after_inlining (struct cgraph_node *node,
3548 struct cgraph_edge *edge)
3550 struct inline_edge_summary *es = inline_edge_summary (edge);
3551 if (!es->predicate || !false_predicate_p (es->predicate))
3553 int size = inline_summary (node)->size + estimate_edge_growth (edge);
3554 gcc_assert (size >= 0);
3557 return inline_summary (node)->size;
3563 bool self_recursive;
3568 /* Worker for do_estimate_growth. Collect growth for all callers. */
3571 do_estimate_growth_1 (struct cgraph_node *node, void *data)
3573 struct cgraph_edge *e;
3574 struct growth_data *d = (struct growth_data *) data;
3576 for (e = node->callers; e; e = e->next_caller)
3578 gcc_checking_assert (e->inline_failed);
3580 if (e->caller == node
3581 || (e->caller->global.inlined_to
3582 && e->caller->global.inlined_to == node))
3583 d->self_recursive = true;
3584 d->growth += estimate_edge_growth (e);
3590 /* Estimate the growth caused by inlining NODE into all callees. */
3593 do_estimate_growth (struct cgraph_node *node)
3595 struct growth_data d = { 0, false };
3596 struct inline_summary *info = inline_summary (node);
3598 cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
3600 /* For self recursive functions the growth estimation really should be
3601 infinity. We don't want to return very large values because the growth
3602 plays various roles in badness computation fractions. Be sure to not
3603 return zero or negative growths. */
3604 if (d.self_recursive)
3605 d.growth = d.growth < info->size ? info->size : d.growth;
3606 else if (DECL_EXTERNAL (node->symbol.decl))
3610 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node))
3611 d.growth -= info->size;
3612 /* COMDAT functions are very often not shared across multiple units
3613 since they come from various template instantiations.
3614 Take this into account. */
3615 else if (DECL_COMDAT (node->symbol.decl)
3616 && cgraph_can_remove_if_no_direct_calls_p (node))
3617 d.growth -= (info->size
3618 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
3622 if (node_growth_cache.exists ())
3624 if ((int) node_growth_cache.length () <= node->uid)
3625 node_growth_cache.safe_grow_cleared (cgraph_max_uid);
3626 node_growth_cache[node->uid] = d.growth + (d.growth >= 0);
3632 /* This function performs intraprocedural analysis in NODE that is required to
3633 inline indirect calls. */
3636 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
3638 ipa_analyze_node (node);
3639 if (dump_file && (dump_flags & TDF_DETAILS))
3641 ipa_print_node_params (dump_file, node);
3642 ipa_print_node_jump_functions (dump_file, node);
3647 /* Note function body size. */
3650 inline_analyze_function (struct cgraph_node *node)
3652 push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
3655 fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
3656 cgraph_node_name (node), node->uid);
3657 if (optimize && !node->thunk.thunk_p)
3658 inline_indirect_intraprocedural_analysis (node);
3659 compute_inline_parameters (node, false);
3665 /* Called when new function is inserted to callgraph late. */
3668 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
3670 inline_analyze_function (node);
3674 /* Note function body size. */
3677 inline_generate_summary (void)
3679 struct cgraph_node *node;
3681 function_insertion_hook_holder =
3682 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3684 ipa_register_cgraph_hooks ();
3685 inline_free_summary ();
3687 FOR_EACH_DEFINED_FUNCTION (node)
3689 inline_analyze_function (node);
3693 /* Read predicate from IB. */
3695 static struct predicate
3696 read_predicate (struct lto_input_block *ib)
3698 struct predicate out;
3704 gcc_assert (k <= MAX_CLAUSES);
3705 clause = out.clause[k++] = streamer_read_uhwi (ib);
3709 /* Zero-initialize the remaining clauses in OUT. */
3710 while (k <= MAX_CLAUSES)
3711 out.clause[k++] = 0;
3717 /* Write inline summary for edge E to OB. */
3720 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
3722 struct inline_edge_summary *es = inline_edge_summary (e);
3726 es->call_stmt_size = streamer_read_uhwi (ib);
3727 es->call_stmt_time = streamer_read_uhwi (ib);
3728 es->loop_depth = streamer_read_uhwi (ib);
3729 p = read_predicate (ib);
3730 edge_set_predicate (e, &p);
3731 length = streamer_read_uhwi (ib);
3734 es->param.safe_grow_cleared (length);
3735 for (i = 0; i < length; i++)
3736 es->param[i].change_prob = streamer_read_uhwi (ib);
3741 /* Stream in inline summaries from the section. */
3744 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
3747 const struct lto_function_header *header =
3748 (const struct lto_function_header *) data;
3749 const int cfg_offset = sizeof (struct lto_function_header);
3750 const int main_offset = cfg_offset + header->cfg_size;
3751 const int string_offset = main_offset + header->main_size;
3752 struct data_in *data_in;
3753 struct lto_input_block ib;
3754 unsigned int i, count2, j;
3755 unsigned int f_count;
3757 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
3761 lto_data_in_create (file_data, (const char *) data + string_offset,
3762 header->string_size, vNULL);
3763 f_count = streamer_read_uhwi (&ib);
3764 for (i = 0; i < f_count; i++)
3767 struct cgraph_node *node;
3768 struct inline_summary *info;
3769 lto_symtab_encoder_t encoder;
3770 struct bitpack_d bp;
3771 struct cgraph_edge *e;
3774 index = streamer_read_uhwi (&ib);
3775 encoder = file_data->symtab_node_encoder;
3776 node = cgraph (lto_symtab_encoder_deref (encoder, index));
3777 info = inline_summary (node);
3779 info->estimated_stack_size
3780 = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
3781 info->size = info->self_size = streamer_read_uhwi (&ib);
3782 info->time = info->self_time = streamer_read_uhwi (&ib);
3784 bp = streamer_read_bitpack (&ib);
3785 info->inlinable = bp_unpack_value (&bp, 1);
3787 count2 = streamer_read_uhwi (&ib);
3788 gcc_assert (!info->conds);
3789 for (j = 0; j < count2; j++)
3792 c.operand_num = streamer_read_uhwi (&ib);
3793 c.code = (enum tree_code) streamer_read_uhwi (&ib);
3794 c.val = stream_read_tree (&ib, data_in);
3795 bp = streamer_read_bitpack (&ib);
3796 c.agg_contents = bp_unpack_value (&bp, 1);
3797 c.by_ref = bp_unpack_value (&bp, 1);
3799 c.offset = streamer_read_uhwi (&ib);
3800 vec_safe_push (info->conds, c);
3802 count2 = streamer_read_uhwi (&ib);
3803 gcc_assert (!info->entry);
3804 for (j = 0; j < count2; j++)
3806 struct size_time_entry e;
3808 e.size = streamer_read_uhwi (&ib);
3809 e.time = streamer_read_uhwi (&ib);
3810 e.predicate = read_predicate (&ib);
3812 vec_safe_push (info->entry, e);
3815 p = read_predicate (&ib);
3816 set_hint_predicate (&info->loop_iterations, p);
3817 p = read_predicate (&ib);
3818 set_hint_predicate (&info->loop_stride, p);
3819 p = read_predicate (&ib);
3820 set_hint_predicate (&info->array_index, p);
3821 for (e = node->callees; e; e = e->next_callee)
3822 read_inline_edge_summary (&ib, e);
3823 for (e = node->indirect_calls; e; e = e->next_callee)
3824 read_inline_edge_summary (&ib, e);
3827 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
3829 lto_data_in_delete (data_in);
3833 /* Read inline summary. Jump functions are shared among ipa-cp
3834 and inliner, so when ipa-cp is active, we don't need to write them
3838 inline_read_summary (void)
3840 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
3841 struct lto_file_decl_data *file_data;
3844 inline_summary_alloc ();
3846 while ((file_data = file_data_vec[j++]))
3849 const char *data = lto_get_section_data (file_data,
3850 LTO_section_inline_summary,
3853 inline_read_section (file_data, data, len);
3855 /* Fatal error here. We do not want to support compiling ltrans units
3856 with different version of compiler or different flags than the WPA
3857 unit, so this should never happen. */
3858 fatal_error ("ipa inline summary is missing in input file");
3862 ipa_register_cgraph_hooks ();
3864 ipa_prop_read_jump_functions ();
3866 function_insertion_hook_holder =
3867 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3871 /* Write predicate P to OB. */
3874 write_predicate (struct output_block *ob, struct predicate *p)
3878 for (j = 0; p->clause[j]; j++)
3880 gcc_assert (j < MAX_CLAUSES);
3881 streamer_write_uhwi (ob, p->clause[j]);
3883 streamer_write_uhwi (ob, 0);
3887 /* Write inline summary for edge E to OB. */
3890 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
3892 struct inline_edge_summary *es = inline_edge_summary (e);
3895 streamer_write_uhwi (ob, es->call_stmt_size);
3896 streamer_write_uhwi (ob, es->call_stmt_time);
3897 streamer_write_uhwi (ob, es->loop_depth);
3898 write_predicate (ob, es->predicate);
3899 streamer_write_uhwi (ob, es->param.length ());
3900 for (i = 0; i < (int) es->param.length (); i++)
3901 streamer_write_uhwi (ob, es->param[i].change_prob);
3905 /* Write inline summary for node in SET.
3906 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3907 active, we don't need to write them twice. */
3910 inline_write_summary (void)
3912 struct cgraph_node *node;
3913 struct output_block *ob = create_output_block (LTO_section_inline_summary);
3914 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
3915 unsigned int count = 0;
3918 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
3920 symtab_node snode = lto_symtab_encoder_deref (encoder, i);
3921 cgraph_node *cnode = dyn_cast <cgraph_node> (snode);
3922 if (cnode && cnode->analyzed)
3925 streamer_write_uhwi (ob, count);
3927 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
3929 symtab_node snode = lto_symtab_encoder_deref (encoder, i);
3930 cgraph_node *cnode = dyn_cast <cgraph_node> (snode);
3931 if (cnode && (node = cnode)->analyzed)
3933 struct inline_summary *info = inline_summary (node);
3934 struct bitpack_d bp;
3935 struct cgraph_edge *edge;
3938 struct condition *c;
3940 streamer_write_uhwi (ob,
3941 lto_symtab_encoder_encode (encoder,
3944 streamer_write_hwi (ob, info->estimated_self_stack_size);
3945 streamer_write_hwi (ob, info->self_size);
3946 streamer_write_hwi (ob, info->self_time);
3947 bp = bitpack_create (ob->main_stream);
3948 bp_pack_value (&bp, info->inlinable, 1);
3949 streamer_write_bitpack (&bp);
3950 streamer_write_uhwi (ob, vec_safe_length (info->conds));
3951 for (i = 0; vec_safe_iterate (info->conds, i, &c); i++)
3953 streamer_write_uhwi (ob, c->operand_num);
3954 streamer_write_uhwi (ob, c->code);
3955 stream_write_tree (ob, c->val, true);
3956 bp = bitpack_create (ob->main_stream);
3957 bp_pack_value (&bp, c->agg_contents, 1);
3958 bp_pack_value (&bp, c->by_ref, 1);
3959 streamer_write_bitpack (&bp);
3960 if (c->agg_contents)
3961 streamer_write_uhwi (ob, c->offset);
3963 streamer_write_uhwi (ob, vec_safe_length (info->entry));
3964 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
3966 streamer_write_uhwi (ob, e->size);
3967 streamer_write_uhwi (ob, e->time);
3968 write_predicate (ob, &e->predicate);
3970 write_predicate (ob, info->loop_iterations);
3971 write_predicate (ob, info->loop_stride);
3972 write_predicate (ob, info->array_index);
3973 for (edge = node->callees; edge; edge = edge->next_callee)
3974 write_inline_edge_summary (ob, edge);
3975 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
3976 write_inline_edge_summary (ob, edge);
3979 streamer_write_char_stream (ob->main_stream, 0);
3980 produce_asm (ob, NULL);
3981 destroy_output_block (ob);
3983 if (optimize && !flag_ipa_cp)
3984 ipa_prop_write_jump_functions ();
3988 /* Release inline summary. */
3991 inline_free_summary (void)
3993 struct cgraph_node *node;
3994 if (!inline_edge_summary_vec.exists ())
3996 FOR_EACH_DEFINED_FUNCTION (node)
3997 reset_inline_summary (node);
3998 if (function_insertion_hook_holder)
3999 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
4000 function_insertion_hook_holder = NULL;
4001 if (node_removal_hook_holder)
4002 cgraph_remove_node_removal_hook (node_removal_hook_holder);
4003 node_removal_hook_holder = NULL;
4004 if (edge_removal_hook_holder)
4005 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
4006 edge_removal_hook_holder = NULL;
4007 if (node_duplication_hook_holder)
4008 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
4009 node_duplication_hook_holder = NULL;
4010 if (edge_duplication_hook_holder)
4011 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
4012 edge_duplication_hook_holder = NULL;
4013 vec_free (inline_summary_vec);
4014 inline_edge_summary_vec.release ();
4015 if (edge_predicate_pool)
4016 free_alloc_pool (edge_predicate_pool);
4017 edge_predicate_pool = 0;