1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2014 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 "stor-layout.h"
73 #include "stringpool.h"
74 #include "print-tree.h"
75 #include "tree-inline.h"
76 #include "langhooks.h"
78 #include "diagnostic.h"
79 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
88 #include "hard-reg-set.h"
91 #include "dominance.h"
94 #include "basic-block.h"
95 #include "tree-ssa-alias.h"
96 #include "internal-fn.h"
97 #include "gimple-expr.h"
100 #include "gimple-iterator.h"
101 #include "gimple-ssa.h"
102 #include "tree-cfg.h"
103 #include "tree-phinodes.h"
104 #include "ssa-iterators.h"
105 #include "tree-ssanames.h"
106 #include "tree-ssa-loop-niter.h"
107 #include "tree-ssa-loop.h"
108 #include "hash-map.h"
109 #include "plugin-api.h"
112 #include "alloc-pool.h"
113 #include "ipa-prop.h"
114 #include "lto-streamer.h"
115 #include "data-streamer.h"
116 #include "tree-streamer.h"
117 #include "ipa-inline.h"
119 #include "tree-scalar-evolution.h"
120 #include "ipa-utils.h"
122 #include "cfgexpand.h"
124 /* Estimate runtime of function can easilly run into huge numbers with many
125 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
126 integer. For anything larger we use gcov_type. */
127 #define MAX_TIME 500000
129 /* Number of bits in integer, but we really want to be stable across different
131 #define NUM_CONDITIONS 32
133 enum predicate_conditions
135 predicate_false_condition
= 0,
136 predicate_not_inlined_condition
= 1,
137 predicate_first_dynamic_condition
= 2
140 /* Special condition code we use to represent test that operand is compile time
142 #define IS_NOT_CONSTANT ERROR_MARK
143 /* Special condition code we use to represent test that operand is not changed
144 across invocation of the function. When operand IS_NOT_CONSTANT it is always
145 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
146 of executions even when they are not compile time constants. */
147 #define CHANGED IDENTIFIER_NODE
149 /* Holders of ipa cgraph hooks: */
150 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
151 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
152 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
153 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
154 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
155 static void inline_node_removal_hook (struct cgraph_node
*, void *);
156 static void inline_node_duplication_hook (struct cgraph_node
*,
157 struct cgraph_node
*, void *);
158 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
159 static void inline_edge_duplication_hook (struct cgraph_edge
*,
160 struct cgraph_edge
*, void *);
162 /* VECtor holding inline summaries.
163 In GGC memory because conditions might point to constant trees. */
164 vec
<inline_summary_t
, va_gc
> *inline_summary_vec
;
165 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
167 /* Cached node/edge growths. */
168 vec
<int> node_growth_cache
;
169 vec
<edge_growth_cache_entry
> edge_growth_cache
;
171 /* Edge predicates goes here. */
172 static alloc_pool edge_predicate_pool
;
174 /* Return true predicate (tautology).
175 We represent it by empty list of clauses. */
177 static inline struct predicate
178 true_predicate (void)
186 /* Return predicate testing single condition number COND. */
188 static inline struct predicate
189 single_cond_predicate (int cond
)
192 p
.clause
[0] = 1 << cond
;
198 /* Return false predicate. First clause require false condition. */
200 static inline struct predicate
201 false_predicate (void)
203 return single_cond_predicate (predicate_false_condition
);
207 /* Return true if P is (true). */
210 true_predicate_p (struct predicate
*p
)
212 return !p
->clause
[0];
216 /* Return true if P is (false). */
219 false_predicate_p (struct predicate
*p
)
221 if (p
->clause
[0] == (1 << predicate_false_condition
))
223 gcc_checking_assert (!p
->clause
[1]
224 && p
->clause
[0] == 1 << predicate_false_condition
);
231 /* Return predicate that is set true when function is not inlined. */
233 static inline struct predicate
234 not_inlined_predicate (void)
236 return single_cond_predicate (predicate_not_inlined_condition
);
239 /* Simple description of whether a memory load or a condition refers to a load
240 from an aggregate and if so, how and where from in the aggregate.
241 Individual fields have the same meaning like fields with the same name in
244 struct agg_position_info
246 HOST_WIDE_INT offset
;
251 /* Add condition to condition list CONDS. AGGPOS describes whether the used
252 oprand is loaded from an aggregate and where in the aggregate it is. It can
253 be NULL, which means this not a load from an aggregate. */
255 static struct predicate
256 add_condition (struct inline_summary
*summary
, int operand_num
,
257 struct agg_position_info
*aggpos
,
258 enum tree_code code
, tree val
)
262 struct condition new_cond
;
263 HOST_WIDE_INT offset
;
264 bool agg_contents
, by_ref
;
268 offset
= aggpos
->offset
;
269 agg_contents
= aggpos
->agg_contents
;
270 by_ref
= aggpos
->by_ref
;
275 agg_contents
= false;
279 gcc_checking_assert (operand_num
>= 0);
280 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
282 if (c
->operand_num
== operand_num
285 && c
->agg_contents
== agg_contents
286 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
287 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
289 /* Too many conditions. Give up and return constant true. */
290 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
291 return true_predicate ();
293 new_cond
.operand_num
= operand_num
;
294 new_cond
.code
= code
;
296 new_cond
.agg_contents
= agg_contents
;
297 new_cond
.by_ref
= by_ref
;
298 new_cond
.offset
= offset
;
299 vec_safe_push (summary
->conds
, new_cond
);
300 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
304 /* Add clause CLAUSE into the predicate P. */
307 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
311 int insert_here
= -1;
318 /* False clause makes the whole predicate false. Kill the other variants. */
319 if (clause
== (1 << predicate_false_condition
))
321 p
->clause
[0] = (1 << predicate_false_condition
);
325 if (false_predicate_p (p
))
328 /* No one should be silly enough to add false into nontrivial clauses. */
329 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
331 /* Look where to insert the clause. At the same time prune out
332 clauses of P that are implied by the new clause and thus
334 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
336 p
->clause
[i2
] = p
->clause
[i
];
341 /* If p->clause[i] implies clause, there is nothing to add. */
342 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
344 /* We had nothing to add, none of clauses should've become
346 gcc_checking_assert (i
== i2
);
350 if (p
->clause
[i
] < clause
&& insert_here
< 0)
353 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
354 Otherwise the p->clause[i] has to stay. */
355 if ((p
->clause
[i
] & clause
) != clause
)
359 /* Look for clauses that are obviously true. I.e.
360 op0 == 5 || op0 != 5. */
361 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
364 if (!(clause
& (1 << c1
)))
366 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
367 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
368 and thus there is no point for looking for them. */
369 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
371 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
372 if (clause
& (1 << c2
))
375 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
377 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
378 if (cc1
->operand_num
== cc2
->operand_num
379 && cc1
->val
== cc2
->val
380 && cc2
->code
!= IS_NOT_CONSTANT
381 && cc2
->code
!= CHANGED
382 && cc1
->code
== invert_tree_comparison
384 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1
->val
)))))
390 /* We run out of variants. Be conservative in positive direction. */
391 if (i2
== MAX_CLAUSES
)
393 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
394 p
->clause
[i2
+ 1] = 0;
395 if (insert_here
>= 0)
396 for (; i2
> insert_here
; i2
--)
397 p
->clause
[i2
] = p
->clause
[i2
- 1];
400 p
->clause
[insert_here
] = clause
;
406 static struct predicate
407 and_predicates (conditions conditions
,
408 struct predicate
*p
, struct predicate
*p2
)
410 struct predicate out
= *p
;
413 /* Avoid busy work. */
414 if (false_predicate_p (p2
) || true_predicate_p (p
))
416 if (false_predicate_p (p
) || true_predicate_p (p2
))
419 /* See how far predicates match. */
420 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
422 gcc_checking_assert (i
< MAX_CLAUSES
);
425 /* Combine the predicates rest. */
426 for (; p2
->clause
[i
]; i
++)
428 gcc_checking_assert (i
< MAX_CLAUSES
);
429 add_clause (conditions
, &out
, p2
->clause
[i
]);
435 /* Return true if predicates are obviously equal. */
438 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
441 for (i
= 0; p
->clause
[i
]; i
++)
443 gcc_checking_assert (i
< MAX_CLAUSES
);
444 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
445 gcc_checking_assert (!p2
->clause
[i
]
446 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
447 if (p
->clause
[i
] != p2
->clause
[i
])
450 return !p2
->clause
[i
];
456 static struct predicate
457 or_predicates (conditions conditions
,
458 struct predicate
*p
, struct predicate
*p2
)
460 struct predicate out
= true_predicate ();
463 /* Avoid busy work. */
464 if (false_predicate_p (p2
) || true_predicate_p (p
))
466 if (false_predicate_p (p
) || true_predicate_p (p2
))
468 if (predicates_equal_p (p
, p2
))
471 /* OK, combine the predicates. */
472 for (i
= 0; p
->clause
[i
]; i
++)
473 for (j
= 0; p2
->clause
[j
]; j
++)
475 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
476 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
482 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
483 if predicate P is known to be false. */
486 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
490 /* True remains true. */
491 if (true_predicate_p (p
))
494 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
496 /* See if we can find clause we can disprove. */
497 for (i
= 0; p
->clause
[i
]; i
++)
499 gcc_checking_assert (i
< MAX_CLAUSES
);
500 if (!(p
->clause
[i
] & possible_truths
))
506 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
507 instruction will be recomputed per invocation of the inlined call. */
510 predicate_probability (conditions conds
,
511 struct predicate
*p
, clause_t possible_truths
,
512 vec
<inline_param_summary
> inline_param_summary
)
515 int combined_prob
= REG_BR_PROB_BASE
;
517 /* True remains true. */
518 if (true_predicate_p (p
))
519 return REG_BR_PROB_BASE
;
521 if (false_predicate_p (p
))
524 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
526 /* See if we can find clause we can disprove. */
527 for (i
= 0; p
->clause
[i
]; i
++)
529 gcc_checking_assert (i
< MAX_CLAUSES
);
530 if (!(p
->clause
[i
] & possible_truths
))
536 if (!inline_param_summary
.exists ())
537 return REG_BR_PROB_BASE
;
538 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
539 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
541 if (i2
>= predicate_first_dynamic_condition
)
544 &(*conds
)[i2
- predicate_first_dynamic_condition
];
545 if (c
->code
== CHANGED
547 (int) inline_param_summary
.length ()))
550 inline_param_summary
[c
->operand_num
].change_prob
;
551 this_prob
= MAX (this_prob
, iprob
);
554 this_prob
= REG_BR_PROB_BASE
;
557 this_prob
= REG_BR_PROB_BASE
;
559 combined_prob
= MIN (this_prob
, combined_prob
);
564 return combined_prob
;
568 /* Dump conditional COND. */
571 dump_condition (FILE *f
, conditions conditions
, int cond
)
574 if (cond
== predicate_false_condition
)
575 fprintf (f
, "false");
576 else if (cond
== predicate_not_inlined_condition
)
577 fprintf (f
, "not inlined");
580 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
581 fprintf (f
, "op%i", c
->operand_num
);
583 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
584 c
->by_ref
? "ref " : "", c
->offset
);
585 if (c
->code
== IS_NOT_CONSTANT
)
587 fprintf (f
, " not constant");
590 if (c
->code
== CHANGED
)
592 fprintf (f
, " changed");
595 fprintf (f
, " %s ", op_symbol_code (c
->code
));
596 print_generic_expr (f
, c
->val
, 1);
601 /* Dump clause CLAUSE. */
604 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
611 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
612 if (clause
& (1 << i
))
617 dump_condition (f
, conds
, i
);
623 /* Dump predicate PREDICATE. */
626 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
629 if (true_predicate_p (pred
))
630 dump_clause (f
, conds
, 0);
632 for (i
= 0; pred
->clause
[i
]; i
++)
636 dump_clause (f
, conds
, pred
->clause
[i
]);
642 /* Dump inline hints. */
644 dump_inline_hints (FILE *f
, inline_hints hints
)
648 fprintf (f
, "inline hints:");
649 if (hints
& INLINE_HINT_indirect_call
)
651 hints
&= ~INLINE_HINT_indirect_call
;
652 fprintf (f
, " indirect_call");
654 if (hints
& INLINE_HINT_loop_iterations
)
656 hints
&= ~INLINE_HINT_loop_iterations
;
657 fprintf (f
, " loop_iterations");
659 if (hints
& INLINE_HINT_loop_stride
)
661 hints
&= ~INLINE_HINT_loop_stride
;
662 fprintf (f
, " loop_stride");
664 if (hints
& INLINE_HINT_same_scc
)
666 hints
&= ~INLINE_HINT_same_scc
;
667 fprintf (f
, " same_scc");
669 if (hints
& INLINE_HINT_in_scc
)
671 hints
&= ~INLINE_HINT_in_scc
;
672 fprintf (f
, " in_scc");
674 if (hints
& INLINE_HINT_cross_module
)
676 hints
&= ~INLINE_HINT_cross_module
;
677 fprintf (f
, " cross_module");
679 if (hints
& INLINE_HINT_declared_inline
)
681 hints
&= ~INLINE_HINT_declared_inline
;
682 fprintf (f
, " declared_inline");
684 if (hints
& INLINE_HINT_array_index
)
686 hints
&= ~INLINE_HINT_array_index
;
687 fprintf (f
, " array_index");
689 if (hints
& INLINE_HINT_known_hot
)
691 hints
&= ~INLINE_HINT_known_hot
;
692 fprintf (f
, " known_hot");
698 /* Record SIZE and TIME under condition PRED into the inline summary. */
701 account_size_time (struct inline_summary
*summary
, int size
, int time
,
702 struct predicate
*pred
)
708 if (false_predicate_p (pred
))
711 /* We need to create initial empty unconitional clause, but otherwie
712 we don't need to account empty times and sizes. */
713 if (!size
&& !time
&& summary
->entry
)
716 /* Watch overflow that might result from insane profiles. */
717 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
718 time
= MAX_TIME
* INLINE_TIME_SCALE
;
719 gcc_assert (time
>= 0);
721 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
722 if (predicates_equal_p (&e
->predicate
, pred
))
731 e
= &(*summary
->entry
)[0];
732 gcc_assert (!e
->predicate
.clause
[0]);
733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
735 "\t\tReached limit on number of entries, "
736 "ignoring the predicate.");
738 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
741 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
742 ((double) size
) / INLINE_SIZE_SCALE
,
743 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
744 dump_predicate (dump_file
, summary
->conds
, pred
);
748 struct size_time_entry new_entry
;
749 new_entry
.size
= size
;
750 new_entry
.time
= time
;
751 new_entry
.predicate
= *pred
;
752 vec_safe_push (summary
->entry
, new_entry
);
758 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
759 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
763 /* Set predicate for edge E. */
766 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
768 struct inline_edge_summary
*es
= inline_edge_summary (e
);
770 /* If the edge is determined to be never executed, redirect it
771 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
772 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
774 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
776 e
->redirect_callee (cgraph_node::get_create
777 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
778 e
->inline_failed
= CIF_UNREACHABLE
;
780 callee
->remove_symbol_and_inline_clones ();
782 if (predicate
&& !true_predicate_p (predicate
))
785 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
786 *es
->predicate
= *predicate
;
791 pool_free (edge_predicate_pool
, es
->predicate
);
792 es
->predicate
= NULL
;
796 /* Set predicate for hint *P. */
799 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
801 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
804 pool_free (edge_predicate_pool
, *p
);
810 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
816 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
817 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
818 Return clause of possible truths. When INLINE_P is true, assume that we are
821 ERROR_MARK means compile time invariant. */
824 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
826 vec
<tree
> known_vals
,
827 vec
<ipa_agg_jump_function_p
>
830 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
831 struct inline_summary
*info
= inline_summary (node
);
835 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
840 /* We allow call stmt to have fewer arguments than the callee function
841 (especially for K&R style programs). So bound check here (we assume
842 known_aggs vector, if non-NULL, has the same length as
844 gcc_checking_assert (!known_aggs
.exists ()
845 || (known_vals
.length () == known_aggs
.length ()));
846 if (c
->operand_num
>= (int) known_vals
.length ())
848 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
854 struct ipa_agg_jump_function
*agg
;
856 if (c
->code
== CHANGED
858 && (known_vals
[c
->operand_num
] == error_mark_node
))
861 if (known_aggs
.exists ())
863 agg
= known_aggs
[c
->operand_num
];
864 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
871 val
= known_vals
[c
->operand_num
];
872 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
878 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
881 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
883 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
884 if (res
&& integer_zerop (res
))
886 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
892 /* Work out what conditions might be true at invocation of E. */
895 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
896 clause_t
*clause_ptr
,
897 vec
<tree
> *known_vals_ptr
,
898 vec
<tree
> *known_binfos_ptr
,
899 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
901 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
902 struct inline_summary
*info
= inline_summary (callee
);
903 vec
<tree
> known_vals
= vNULL
;
904 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
907 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
909 known_vals_ptr
->create (0);
910 if (known_binfos_ptr
)
911 known_binfos_ptr
->create (0);
913 if (ipa_node_params_vector
.exists ()
914 && !e
->call_stmt_cannot_inline_p
915 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_binfos_ptr
))
917 struct ipa_node_params
*parms_info
;
918 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
919 struct inline_edge_summary
*es
= inline_edge_summary (e
);
920 int i
, count
= ipa_get_cs_argument_count (args
);
922 if (e
->caller
->global
.inlined_to
)
923 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
925 parms_info
= IPA_NODE_REF (e
->caller
);
927 if (count
&& (info
->conds
|| known_vals_ptr
))
928 known_vals
.safe_grow_cleared (count
);
929 if (count
&& (info
->conds
|| known_aggs_ptr
))
930 known_aggs
.safe_grow_cleared (count
);
931 if (count
&& known_binfos_ptr
)
932 known_binfos_ptr
->safe_grow_cleared (count
);
934 for (i
= 0; i
< count
; i
++)
936 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
937 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
940 if (known_vals
.exists () && TREE_CODE (cst
) != TREE_BINFO
)
942 else if (known_binfos_ptr
!= NULL
943 && TREE_CODE (cst
) == TREE_BINFO
)
944 (*known_binfos_ptr
)[i
] = cst
;
946 else if (inline_p
&& !es
->param
[i
].change_prob
)
947 known_vals
[i
] = error_mark_node
;
948 /* TODO: When IPA-CP starts propagating and merging aggregate jump
949 functions, use its knowledge of the caller too, just like the
950 scalar case above. */
951 known_aggs
[i
] = &jf
->agg
;
956 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
957 known_vals
, known_aggs
);
960 *known_vals_ptr
= known_vals
;
962 known_vals
.release ();
965 *known_aggs_ptr
= known_aggs
;
967 known_aggs
.release ();
971 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
974 inline_summary_alloc (void)
976 if (!node_removal_hook_holder
)
977 node_removal_hook_holder
=
978 symtab
->add_cgraph_removal_hook (&inline_node_removal_hook
, NULL
);
979 if (!edge_removal_hook_holder
)
980 edge_removal_hook_holder
=
981 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
982 if (!node_duplication_hook_holder
)
983 node_duplication_hook_holder
=
984 symtab
->add_cgraph_duplication_hook (&inline_node_duplication_hook
, NULL
);
985 if (!edge_duplication_hook_holder
)
986 edge_duplication_hook_holder
=
987 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
989 if (vec_safe_length (inline_summary_vec
) <= (unsigned) symtab
->cgraph_max_uid
)
990 vec_safe_grow_cleared (inline_summary_vec
, symtab
->cgraph_max_uid
+ 1);
991 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
992 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
993 if (!edge_predicate_pool
)
994 edge_predicate_pool
= create_alloc_pool ("edge predicates",
995 sizeof (struct predicate
), 10);
998 /* We are called multiple time for given function; clear
999 data from previous run so they are not cumulated. */
1002 reset_inline_edge_summary (struct cgraph_edge
*e
)
1004 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1006 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1008 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1010 pool_free (edge_predicate_pool
, es
->predicate
);
1011 es
->predicate
= NULL
;
1012 es
->param
.release ();
1016 /* We are called multiple time for given function; clear
1017 data from previous run so they are not cumulated. */
1020 reset_inline_summary (struct cgraph_node
*node
)
1022 struct inline_summary
*info
= inline_summary (node
);
1023 struct cgraph_edge
*e
;
1025 info
->self_size
= info
->self_time
= 0;
1026 info
->estimated_stack_size
= 0;
1027 info
->estimated_self_stack_size
= 0;
1028 info
->stack_frame_offset
= 0;
1033 if (info
->loop_iterations
)
1035 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1036 info
->loop_iterations
= NULL
;
1038 if (info
->loop_stride
)
1040 pool_free (edge_predicate_pool
, info
->loop_stride
);
1041 info
->loop_stride
= NULL
;
1043 if (info
->array_index
)
1045 pool_free (edge_predicate_pool
, info
->array_index
);
1046 info
->array_index
= NULL
;
1048 vec_free (info
->conds
);
1049 vec_free (info
->entry
);
1050 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1051 reset_inline_edge_summary (e
);
1052 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1053 reset_inline_edge_summary (e
);
1056 /* Hook that is called by cgraph.c when a node is removed. */
1059 inline_node_removal_hook (struct cgraph_node
*node
,
1060 void *data ATTRIBUTE_UNUSED
)
1062 struct inline_summary
*info
;
1063 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1065 info
= inline_summary (node
);
1066 reset_inline_summary (node
);
1067 memset (info
, 0, sizeof (inline_summary_t
));
1070 /* Remap predicate P of former function to be predicate of duplicated function.
1071 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1072 INFO is inline summary of the duplicated node. */
1074 static struct predicate
1075 remap_predicate_after_duplication (struct predicate
*p
,
1076 clause_t possible_truths
,
1077 struct inline_summary
*info
)
1079 struct predicate new_predicate
= true_predicate ();
1081 for (j
= 0; p
->clause
[j
]; j
++)
1082 if (!(possible_truths
& p
->clause
[j
]))
1084 new_predicate
= false_predicate ();
1088 add_clause (info
->conds
, &new_predicate
,
1089 possible_truths
& p
->clause
[j
]);
1090 return new_predicate
;
1093 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1094 Additionally care about allocating new memory slot for updated predicate
1095 and set it to NULL when it becomes true or false (and thus uninteresting).
1099 remap_hint_predicate_after_duplication (struct predicate
**p
,
1100 clause_t possible_truths
,
1101 struct inline_summary
*info
)
1103 struct predicate new_predicate
;
1108 new_predicate
= remap_predicate_after_duplication (*p
,
1109 possible_truths
, info
);
1110 /* We do not want to free previous predicate; it is used by node origin. */
1112 set_hint_predicate (p
, new_predicate
);
1116 /* Hook that is called by cgraph.c when a node is duplicated. */
1119 inline_node_duplication_hook (struct cgraph_node
*src
,
1120 struct cgraph_node
*dst
,
1121 ATTRIBUTE_UNUSED
void *data
)
1123 struct inline_summary
*info
;
1124 inline_summary_alloc ();
1125 info
= inline_summary (dst
);
1126 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1127 /* TODO: as an optimization, we may avoid copying conditions
1128 that are known to be false or true. */
1129 info
->conds
= vec_safe_copy (info
->conds
);
1131 /* When there are any replacements in the function body, see if we can figure
1132 out that something was optimized out. */
1133 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1135 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1136 /* Use SRC parm info since it may not be copied yet. */
1137 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1138 vec
<tree
> known_vals
= vNULL
;
1139 int count
= ipa_get_param_count (parms_info
);
1141 clause_t possible_truths
;
1142 struct predicate true_pred
= true_predicate ();
1144 int optimized_out_size
= 0;
1145 bool inlined_to_p
= false;
1146 struct cgraph_edge
*edge
;
1149 known_vals
.safe_grow_cleared (count
);
1150 for (i
= 0; i
< count
; i
++)
1152 struct ipa_replace_map
*r
;
1154 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1156 if (((!r
->old_tree
&& r
->parm_num
== i
)
1157 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1158 && r
->replace_p
&& !r
->ref_p
)
1160 known_vals
[i
] = r
->new_tree
;
1165 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1168 known_vals
.release ();
1170 account_size_time (info
, 0, 0, &true_pred
);
1172 /* Remap size_time vectors.
1173 Simplify the predicate by prunning out alternatives that are known
1175 TODO: as on optimization, we can also eliminate conditions known
1177 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1179 struct predicate new_predicate
;
1180 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1183 if (false_predicate_p (&new_predicate
))
1184 optimized_out_size
+= e
->size
;
1186 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1189 /* Remap edge predicates with the same simplification as above.
1190 Also copy constantness arrays. */
1191 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1193 struct predicate new_predicate
;
1194 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1196 if (!edge
->inline_failed
)
1197 inlined_to_p
= true;
1200 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1203 if (false_predicate_p (&new_predicate
)
1204 && !false_predicate_p (es
->predicate
))
1206 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1207 edge
->frequency
= 0;
1209 edge_set_predicate (edge
, &new_predicate
);
1212 /* Remap indirect edge predicates with the same simplificaiton as above.
1213 Also copy constantness arrays. */
1214 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1216 struct predicate new_predicate
;
1217 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1219 gcc_checking_assert (edge
->inline_failed
);
1222 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1225 if (false_predicate_p (&new_predicate
)
1226 && !false_predicate_p (es
->predicate
))
1228 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1229 edge
->frequency
= 0;
1231 edge_set_predicate (edge
, &new_predicate
);
1233 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1234 possible_truths
, info
);
1235 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1236 possible_truths
, info
);
1237 remap_hint_predicate_after_duplication (&info
->array_index
,
1238 possible_truths
, info
);
1240 /* If inliner or someone after inliner will ever start producing
1241 non-trivial clones, we will get trouble with lack of information
1242 about updating self sizes, because size vectors already contains
1243 sizes of the calees. */
1244 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1248 info
->entry
= vec_safe_copy (info
->entry
);
1249 if (info
->loop_iterations
)
1251 predicate p
= *info
->loop_iterations
;
1252 info
->loop_iterations
= NULL
;
1253 set_hint_predicate (&info
->loop_iterations
, p
);
1255 if (info
->loop_stride
)
1257 predicate p
= *info
->loop_stride
;
1258 info
->loop_stride
= NULL
;
1259 set_hint_predicate (&info
->loop_stride
, p
);
1261 if (info
->array_index
)
1263 predicate p
= *info
->array_index
;
1264 info
->array_index
= NULL
;
1265 set_hint_predicate (&info
->array_index
, p
);
1268 inline_update_overall_summary (dst
);
1272 /* Hook that is called by cgraph.c when a node is duplicated. */
1275 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1276 struct cgraph_edge
*dst
,
1277 ATTRIBUTE_UNUSED
void *data
)
1279 struct inline_edge_summary
*info
;
1280 struct inline_edge_summary
*srcinfo
;
1281 inline_summary_alloc ();
1282 info
= inline_edge_summary (dst
);
1283 srcinfo
= inline_edge_summary (src
);
1284 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1285 info
->predicate
= NULL
;
1286 edge_set_predicate (dst
, srcinfo
->predicate
);
1287 info
->param
= srcinfo
->param
.copy ();
1291 /* Keep edge cache consistent across edge removal. */
1294 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1295 void *data ATTRIBUTE_UNUSED
)
1297 if (edge_growth_cache
.exists ())
1298 reset_edge_growth_cache (edge
);
1299 reset_inline_edge_summary (edge
);
1303 /* Initialize growth caches. */
1306 initialize_growth_caches (void)
1308 if (symtab
->edges_max_uid
)
1309 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1310 if (symtab
->cgraph_max_uid
)
1311 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1315 /* Free growth caches. */
1318 free_growth_caches (void)
1320 edge_growth_cache
.release ();
1321 node_growth_cache
.release ();
1325 /* Dump edge summaries associated to NODE and recursively to all clones.
1326 Indent by INDENT. */
1329 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1330 struct inline_summary
*info
)
1332 struct cgraph_edge
*edge
;
1333 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1335 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1336 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1340 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1341 " time: %2i callee size:%2i stack:%2i",
1342 indent
, "", callee
->name (), callee
->order
,
1343 !edge
->inline_failed
1344 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1345 indent
, "", es
->loop_depth
, edge
->frequency
,
1346 es
->call_stmt_size
, es
->call_stmt_time
,
1347 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1348 (int) inline_summary (callee
)->estimated_stack_size
);
1352 fprintf (f
, " predicate: ");
1353 dump_predicate (f
, info
->conds
, es
->predicate
);
1357 if (es
->param
.exists ())
1358 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1360 int prob
= es
->param
[i
].change_prob
;
1363 fprintf (f
, "%*s op%i is compile time invariant\n",
1365 else if (prob
!= REG_BR_PROB_BASE
)
1366 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1367 prob
* 100.0 / REG_BR_PROB_BASE
);
1369 if (!edge
->inline_failed
)
1371 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1372 " callee size %i\n",
1374 (int) inline_summary (callee
)->stack_frame_offset
,
1375 (int) inline_summary (callee
)->estimated_self_stack_size
,
1376 (int) inline_summary (callee
)->estimated_stack_size
);
1377 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1380 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1382 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1383 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1387 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1390 fprintf (f
, "predicate: ");
1391 dump_predicate (f
, info
->conds
, es
->predicate
);
1400 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1402 if (node
->definition
)
1404 struct inline_summary
*s
= inline_summary (node
);
1407 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1409 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1410 fprintf (f
, " always_inline");
1412 fprintf (f
, " inlinable");
1413 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1414 fprintf (f
, " global time: %i\n", s
->time
);
1415 fprintf (f
, " self size: %i\n", s
->self_size
);
1416 fprintf (f
, " global size: %i\n", s
->size
);
1417 fprintf (f
, " min size: %i\n", s
->min_size
);
1418 fprintf (f
, " self stack: %i\n",
1419 (int) s
->estimated_self_stack_size
);
1420 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1422 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1424 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1425 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1427 fprintf (f
, " size:%f, time:%f, predicate:",
1428 (double) e
->size
/ INLINE_SIZE_SCALE
,
1429 (double) e
->time
/ INLINE_TIME_SCALE
);
1430 dump_predicate (f
, s
->conds
, &e
->predicate
);
1432 if (s
->loop_iterations
)
1434 fprintf (f
, " loop iterations:");
1435 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1439 fprintf (f
, " loop stride:");
1440 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1444 fprintf (f
, " array index:");
1445 dump_predicate (f
, s
->conds
, s
->array_index
);
1447 fprintf (f
, " calls:\n");
1448 dump_inline_edge_summary (f
, 4, node
, s
);
1454 debug_inline_summary (struct cgraph_node
*node
)
1456 dump_inline_summary (stderr
, node
);
1460 dump_inline_summaries (FILE *f
)
1462 struct cgraph_node
*node
;
1464 FOR_EACH_DEFINED_FUNCTION (node
)
1465 if (!node
->global
.inlined_to
)
1466 dump_inline_summary (f
, node
);
1469 /* Give initial reasons why inlining would fail on EDGE. This gets either
1470 nullified or usually overwritten by more precise reasons later. */
1473 initialize_inline_failed (struct cgraph_edge
*e
)
1475 struct cgraph_node
*callee
= e
->callee
;
1477 if (e
->indirect_unknown_callee
)
1478 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1479 else if (!callee
->definition
)
1480 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1481 else if (callee
->local
.redefined_extern_inline
)
1482 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1483 else if (e
->call_stmt_cannot_inline_p
)
1484 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1485 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1486 /* We can't inline if the function is spawing a function. */
1487 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1489 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1492 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1493 boolean variable pointed to by DATA. */
1496 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1499 bool *b
= (bool *) data
;
1504 /* If OP refers to value of function parameter, return the corresponding
1508 unmodified_parm_1 (gimple stmt
, tree op
)
1510 /* SSA_NAME referring to parm default def? */
1511 if (TREE_CODE (op
) == SSA_NAME
1512 && SSA_NAME_IS_DEFAULT_DEF (op
)
1513 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1514 return SSA_NAME_VAR (op
);
1515 /* Non-SSA parm reference? */
1516 if (TREE_CODE (op
) == PARM_DECL
)
1518 bool modified
= false;
1521 ao_ref_init (&refd
, op
);
1522 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1530 /* If OP refers to value of function parameter, return the corresponding
1531 parameter. Also traverse chains of SSA register assignments. */
1534 unmodified_parm (gimple stmt
, tree op
)
1536 tree res
= unmodified_parm_1 (stmt
, op
);
1540 if (TREE_CODE (op
) == SSA_NAME
1541 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1542 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1543 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1544 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1548 /* If OP refers to a value of a function parameter or value loaded from an
1549 aggregate passed to a parameter (either by value or reference), return TRUE
1550 and store the number of the parameter to *INDEX_P and information whether
1551 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1552 the function parameters, STMT is the statement in which OP is used or
1556 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1557 gimple stmt
, tree op
, int *index_p
,
1558 struct agg_position_info
*aggpos
)
1560 tree res
= unmodified_parm_1 (stmt
, op
);
1562 gcc_checking_assert (aggpos
);
1565 *index_p
= ipa_get_param_decl_index (info
, res
);
1568 aggpos
->agg_contents
= false;
1569 aggpos
->by_ref
= false;
1573 if (TREE_CODE (op
) == SSA_NAME
)
1575 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1576 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1578 stmt
= SSA_NAME_DEF_STMT (op
);
1579 op
= gimple_assign_rhs1 (stmt
);
1580 if (!REFERENCE_CLASS_P (op
))
1581 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1585 aggpos
->agg_contents
= true;
1586 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1590 /* See if statement might disappear after inlining.
1591 0 - means not eliminated
1592 1 - half of statements goes away
1593 2 - for sure it is eliminated.
1594 We are not terribly sophisticated, basically looking for simple abstraction
1595 penalty wrappers. */
1598 eliminated_by_inlining_prob (gimple stmt
)
1600 enum gimple_code code
= gimple_code (stmt
);
1601 enum tree_code rhs_code
;
1611 if (gimple_num_ops (stmt
) != 2)
1614 rhs_code
= gimple_assign_rhs_code (stmt
);
1616 /* Casts of parameters, loads from parameters passed by reference
1617 and stores to return value or parameters are often free after
1618 inlining dua to SRA and further combining.
1619 Assume that half of statements goes away. */
1620 if (rhs_code
== CONVERT_EXPR
1621 || rhs_code
== NOP_EXPR
1622 || rhs_code
== VIEW_CONVERT_EXPR
1623 || rhs_code
== ADDR_EXPR
1624 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1626 tree rhs
= gimple_assign_rhs1 (stmt
);
1627 tree lhs
= gimple_assign_lhs (stmt
);
1628 tree inner_rhs
= get_base_address (rhs
);
1629 tree inner_lhs
= get_base_address (lhs
);
1630 bool rhs_free
= false;
1631 bool lhs_free
= false;
1638 /* Reads of parameter are expected to be free. */
1639 if (unmodified_parm (stmt
, inner_rhs
))
1641 /* Match expressions of form &this->field. Those will most likely
1642 combine with something upstream after inlining. */
1643 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1645 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1646 if (TREE_CODE (op
) == PARM_DECL
)
1648 else if (TREE_CODE (op
) == MEM_REF
1649 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1653 /* When parameter is not SSA register because its address is taken
1654 and it is just copied into one, the statement will be completely
1655 free after inlining (we will copy propagate backward). */
1656 if (rhs_free
&& is_gimple_reg (lhs
))
1659 /* Reads of parameters passed by reference
1660 expected to be free (i.e. optimized out after inlining). */
1661 if (TREE_CODE (inner_rhs
) == MEM_REF
1662 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1665 /* Copying parameter passed by reference into gimple register is
1666 probably also going to copy propagate, but we can't be quite
1668 if (rhs_free
&& is_gimple_reg (lhs
))
1671 /* Writes to parameters, parameters passed by value and return value
1672 (either dirrectly or passed via invisible reference) are free.
1674 TODO: We ought to handle testcase like
1675 struct a {int a,b;};
1677 retrurnsturct (void)
1683 This translate into:
1698 For that we either need to copy ipa-split logic detecting writes
1700 if (TREE_CODE (inner_lhs
) == PARM_DECL
1701 || TREE_CODE (inner_lhs
) == RESULT_DECL
1702 || (TREE_CODE (inner_lhs
) == MEM_REF
1703 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1704 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1705 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1706 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1708 0))) == RESULT_DECL
))))
1711 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1713 if (lhs_free
&& rhs_free
)
1723 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1724 predicates to the CFG edges. */
1727 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1728 struct inline_summary
*summary
,
1734 struct agg_position_info aggpos
;
1735 enum tree_code code
, inverted_code
;
1741 last
= last_stmt (bb
);
1742 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1744 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1746 op
= gimple_cond_lhs (last
);
1747 /* TODO: handle conditionals like
1750 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1752 code
= gimple_cond_code (last
);
1754 = invert_tree_comparison (code
,
1755 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1759 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1760 ? code
: inverted_code
);
1761 /* invert_tree_comparison will return ERROR_MARK on FP
1762 comparsions that are not EQ/NE instead of returning proper
1763 unordered one. Be sure it is not confused with NON_CONSTANT. */
1764 if (this_code
!= ERROR_MARK
)
1766 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1768 gimple_cond_rhs (last
));
1769 e
->aux
= pool_alloc (edge_predicate_pool
);
1770 *(struct predicate
*) e
->aux
= p
;
1775 if (TREE_CODE (op
) != SSA_NAME
)
1778 if (builtin_constant_p (op))
1782 Here we can predicate nonconstant_code. We can't
1783 really handle constant_code since we have no predicate
1784 for this and also the constant code is not known to be
1785 optimized away when inliner doen't see operand is constant.
1786 Other optimizers might think otherwise. */
1787 if (gimple_cond_code (last
) != NE_EXPR
1788 || !integer_zerop (gimple_cond_rhs (last
)))
1790 set_stmt
= SSA_NAME_DEF_STMT (op
);
1791 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1792 || gimple_call_num_args (set_stmt
) != 1)
1794 op2
= gimple_call_arg (set_stmt
, 0);
1795 if (!unmodified_parm_or_parm_agg_item
1796 (info
, set_stmt
, op2
, &index
, &aggpos
))
1798 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1800 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1801 IS_NOT_CONSTANT
, NULL_TREE
);
1802 e
->aux
= pool_alloc (edge_predicate_pool
);
1803 *(struct predicate
*) e
->aux
= p
;
1808 /* If BB ends by a switch we can turn into predicates, attach corresponding
1809 predicates to the CFG edges. */
1812 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1813 struct inline_summary
*summary
,
1819 struct agg_position_info aggpos
;
1825 last
= last_stmt (bb
);
1826 if (!last
|| gimple_code (last
) != GIMPLE_SWITCH
)
1828 op
= gimple_switch_index (last
);
1829 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1832 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1834 e
->aux
= pool_alloc (edge_predicate_pool
);
1835 *(struct predicate
*) e
->aux
= false_predicate ();
1837 n
= gimple_switch_num_labels (last
);
1838 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1840 tree cl
= gimple_switch_label (last
, case_idx
);
1844 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1845 min
= CASE_LOW (cl
);
1846 max
= CASE_HIGH (cl
);
1848 /* For default we might want to construct predicate that none
1849 of cases is met, but it is bit hard to do not having negations
1850 of conditionals handy. */
1852 p
= true_predicate ();
1854 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1857 struct predicate p1
, p2
;
1858 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1859 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1860 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1862 *(struct predicate
*) e
->aux
1863 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1868 /* For each BB in NODE attach to its AUX pointer predicate under
1869 which it is executable. */
1872 compute_bb_predicates (struct cgraph_node
*node
,
1873 struct ipa_node_params
*parms_info
,
1874 struct inline_summary
*summary
)
1876 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1880 FOR_EACH_BB_FN (bb
, my_function
)
1882 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1883 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1886 /* Entry block is always executable. */
1887 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1888 = pool_alloc (edge_predicate_pool
);
1889 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1890 = true_predicate ();
1892 /* A simple dataflow propagation of predicates forward in the CFG.
1893 TODO: work in reverse postorder. */
1897 FOR_EACH_BB_FN (bb
, my_function
)
1899 struct predicate p
= false_predicate ();
1902 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1906 struct predicate this_bb_predicate
1907 = *(struct predicate
*) e
->src
->aux
;
1910 = and_predicates (summary
->conds
, &this_bb_predicate
,
1911 (struct predicate
*) e
->aux
);
1912 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1913 if (true_predicate_p (&p
))
1917 if (false_predicate_p (&p
))
1918 gcc_assert (!bb
->aux
);
1924 bb
->aux
= pool_alloc (edge_predicate_pool
);
1925 *((struct predicate
*) bb
->aux
) = p
;
1927 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1929 /* This OR operation is needed to ensure monotonous data flow
1930 in the case we hit the limit on number of clauses and the
1931 and/or operations above give approximate answers. */
1932 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1933 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1936 *((struct predicate
*) bb
->aux
) = p
;
1945 /* We keep info about constantness of SSA names. */
1947 typedef struct predicate predicate_t
;
1948 /* Return predicate specifying when the STMT might have result that is not
1949 a compile time constant. */
1951 static struct predicate
1952 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1953 struct inline_summary
*summary
,
1955 vec
<predicate_t
> nonconstant_names
)
1960 while (UNARY_CLASS_P (expr
))
1961 expr
= TREE_OPERAND (expr
, 0);
1963 parm
= unmodified_parm (NULL
, expr
);
1964 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1965 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1966 if (is_gimple_min_invariant (expr
))
1967 return false_predicate ();
1968 if (TREE_CODE (expr
) == SSA_NAME
)
1969 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1970 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1972 struct predicate p1
= will_be_nonconstant_expr_predicate
1973 (info
, summary
, TREE_OPERAND (expr
, 0),
1975 struct predicate p2
;
1976 if (true_predicate_p (&p1
))
1978 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1979 TREE_OPERAND (expr
, 1),
1981 return or_predicates (summary
->conds
, &p1
, &p2
);
1983 else if (TREE_CODE (expr
) == COND_EXPR
)
1985 struct predicate p1
= will_be_nonconstant_expr_predicate
1986 (info
, summary
, TREE_OPERAND (expr
, 0),
1988 struct predicate p2
;
1989 if (true_predicate_p (&p1
))
1991 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1992 TREE_OPERAND (expr
, 1),
1994 if (true_predicate_p (&p2
))
1996 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
1997 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1998 TREE_OPERAND (expr
, 2),
2000 return or_predicates (summary
->conds
, &p1
, &p2
);
2007 return false_predicate ();
2011 /* Return predicate specifying when the STMT might have result that is not
2012 a compile time constant. */
2014 static struct predicate
2015 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2016 struct inline_summary
*summary
,
2018 vec
<predicate_t
> nonconstant_names
)
2020 struct predicate p
= true_predicate ();
2023 struct predicate op_non_const
;
2026 struct agg_position_info aggpos
;
2028 /* What statments might be optimized away
2029 when their arguments are constant
2030 TODO: also trivial builtins.
2031 builtin_constant_p is already handled later. */
2032 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2033 && gimple_code (stmt
) != GIMPLE_COND
2034 && gimple_code (stmt
) != GIMPLE_SWITCH
)
2037 /* Stores will stay anyway. */
2038 if (gimple_store_p (stmt
))
2041 is_load
= gimple_assign_load_p (stmt
);
2043 /* Loads can be optimized when the value is known. */
2047 gcc_assert (gimple_assign_single_p (stmt
));
2048 op
= gimple_assign_rhs1 (stmt
);
2049 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2056 /* See if we understand all operands before we start
2057 adding conditionals. */
2058 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2060 tree parm
= unmodified_parm (stmt
, use
);
2061 /* For arguments we can build a condition. */
2062 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2064 if (TREE_CODE (use
) != SSA_NAME
)
2066 /* If we know when operand is constant,
2067 we still can say something useful. */
2068 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2075 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2077 op_non_const
= false_predicate ();
2078 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2080 tree parm
= unmodified_parm (stmt
, use
);
2083 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2085 if (index
!= base_index
)
2086 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2091 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2092 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2094 if (gimple_code (stmt
) == GIMPLE_ASSIGN
2095 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
2096 nonconstant_names
[SSA_NAME_VERSION (gimple_assign_lhs (stmt
))]
2098 return op_non_const
;
2101 struct record_modified_bb_info
2107 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2108 set except for info->stmt. */
2111 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2113 struct record_modified_bb_info
*info
=
2114 (struct record_modified_bb_info
*) data
;
2115 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2117 bitmap_set_bit (info
->bb_set
,
2118 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2119 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2120 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2124 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2125 will change since last invocation of STMT.
2127 Value 0 is reserved for compile time invariants.
2128 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2129 ought to be REG_BR_PROB_BASE / estimated_iters. */
2132 param_change_prob (gimple stmt
, int i
)
2134 tree op
= gimple_call_arg (stmt
, i
);
2135 basic_block bb
= gimple_bb (stmt
);
2138 /* Global invariants neve change. */
2139 if (is_gimple_min_invariant (op
))
2141 /* We would have to do non-trivial analysis to really work out what
2142 is the probability of value to change (i.e. when init statement
2143 is in a sibling loop of the call).
2145 We do an conservative estimate: when call is executed N times more often
2146 than the statement defining value, we take the frequency 1/N. */
2147 if (TREE_CODE (op
) == SSA_NAME
)
2152 return REG_BR_PROB_BASE
;
2154 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2155 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2157 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2161 if (init_freq
< bb
->frequency
)
2162 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2164 return REG_BR_PROB_BASE
;
2167 base
= get_base_address (op
);
2172 struct record_modified_bb_info info
;
2175 tree init
= ctor_for_folding (base
);
2177 if (init
!= error_mark_node
)
2180 return REG_BR_PROB_BASE
;
2181 ao_ref_init (&refd
, op
);
2183 info
.bb_set
= BITMAP_ALLOC (NULL
);
2184 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2186 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2188 BITMAP_FREE (info
.bb_set
);
2189 return REG_BR_PROB_BASE
;
2192 /* Assume that every memory is initialized at entry.
2193 TODO: Can we easilly determine if value is always defined
2194 and thus we may skip entry block? */
2195 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2196 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2200 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2201 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2203 BITMAP_FREE (info
.bb_set
);
2204 if (max
< bb
->frequency
)
2205 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2207 return REG_BR_PROB_BASE
;
2209 return REG_BR_PROB_BASE
;
2212 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2213 sub-graph and if the predicate the condition depends on is known. If so,
2214 return true and store the pointer the predicate in *P. */
2217 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2218 struct inline_summary
*summary
, basic_block bb
,
2219 struct predicate
*p
,
2220 vec
<predicate_t
> nonconstant_names
)
2224 basic_block first_bb
= NULL
;
2227 if (single_pred_p (bb
))
2229 *p
= false_predicate ();
2233 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2235 if (single_succ_p (e
->src
))
2237 if (!single_pred_p (e
->src
))
2240 first_bb
= single_pred (e
->src
);
2241 else if (single_pred (e
->src
) != first_bb
)
2248 else if (e
->src
!= first_bb
)
2256 stmt
= last_stmt (first_bb
);
2258 || gimple_code (stmt
) != GIMPLE_COND
2259 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2262 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2263 gimple_cond_lhs (stmt
),
2265 if (true_predicate_p (p
))
2271 /* Given a PHI statement in a function described by inline properties SUMMARY
2272 and *P being the predicate describing whether the selected PHI argument is
2273 known, store a predicate for the result of the PHI statement into
2274 NONCONSTANT_NAMES, if possible. */
2277 predicate_for_phi_result (struct inline_summary
*summary
, gimple phi
,
2278 struct predicate
*p
,
2279 vec
<predicate_t
> nonconstant_names
)
2283 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2285 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2286 if (!is_gimple_min_invariant (arg
))
2288 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2289 *p
= or_predicates (summary
->conds
, p
,
2290 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2291 if (true_predicate_p (p
))
2296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2298 fprintf (dump_file
, "\t\tphi predicate: ");
2299 dump_predicate (dump_file
, summary
->conds
, p
);
2301 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2304 /* Return predicate specifying when array index in access OP becomes non-constant. */
2306 static struct predicate
2307 array_index_predicate (struct inline_summary
*info
,
2308 vec
< predicate_t
> nonconstant_names
, tree op
)
2310 struct predicate p
= false_predicate ();
2311 while (handled_component_p (op
))
2313 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2315 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2316 p
= or_predicates (info
->conds
, &p
,
2317 &nonconstant_names
[SSA_NAME_VERSION
2318 (TREE_OPERAND (op
, 1))]);
2320 op
= TREE_OPERAND (op
, 0);
2325 /* For a typical usage of __builtin_expect (a<b, 1), we
2326 may introduce an extra relation stmt:
2327 With the builtin, we have
2330 t3 = __builtin_expect (t2, 1);
2333 Without the builtin, we have
2336 This affects the size/time estimation and may have
2337 an impact on the earlier inlining.
2338 Here find this pattern and fix it up later. */
2341 find_foldable_builtin_expect (basic_block bb
)
2343 gimple_stmt_iterator bsi
;
2345 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2347 gimple stmt
= gsi_stmt (bsi
);
2348 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2349 || (is_gimple_call (stmt
)
2350 && gimple_call_internal_p (stmt
)
2351 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2353 tree var
= gimple_call_lhs (stmt
);
2354 tree arg
= gimple_call_arg (stmt
, 0);
2355 use_operand_p use_p
;
2362 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2364 while (TREE_CODE (arg
) == SSA_NAME
)
2366 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2367 if (!is_gimple_assign (stmt_tmp
))
2369 switch (gimple_assign_rhs_code (stmt_tmp
))
2388 arg
= gimple_assign_rhs1 (stmt_tmp
);
2391 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2392 && gimple_code (use_stmt
) == GIMPLE_COND
)
2399 /* Return true when the basic blocks contains only clobbers followed by RESX.
2400 Such BBs are kept around to make removal of dead stores possible with
2401 presence of EH and will be optimized out by optimize_clobbers later in the
2404 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2405 that can be clobber only, too.. When it is false, the RESX is not necessary
2406 on the end of basic block. */
2409 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2411 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2417 if (gsi_end_p (gsi
))
2419 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2423 else if (!single_succ_p (bb
))
2426 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2428 gimple stmt
= gsi_stmt (gsi
);
2429 if (is_gimple_debug (stmt
))
2431 if (gimple_clobber_p (stmt
))
2433 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2438 /* See if all predecestors are either throws or clobber only BBs. */
2439 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2440 if (!(e
->flags
& EDGE_EH
)
2441 && !clobber_only_eh_bb_p (e
->src
, false))
2447 /* Compute function body size parameters for NODE.
2448 When EARLY is true, we compute only simple summaries without
2449 non-trivial predicates to drive the early inliner. */
2452 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2455 /* Estimate static overhead for function prologue/epilogue and alignment. */
2457 /* Benefits are scaled by probability of elimination that is in range
2460 gimple_stmt_iterator bsi
;
2461 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2463 struct inline_summary
*info
= inline_summary (node
);
2464 struct predicate bb_predicate
;
2465 struct ipa_node_params
*parms_info
= NULL
;
2466 vec
<predicate_t
> nonconstant_names
= vNULL
;
2469 predicate array_index
= true_predicate ();
2470 gimple fix_builtin_expect_stmt
;
2475 if (optimize
&& !early
)
2477 calculate_dominance_info (CDI_DOMINATORS
);
2478 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2480 if (ipa_node_params_vector
.exists ())
2482 parms_info
= IPA_NODE_REF (node
);
2483 nonconstant_names
.safe_grow_cleared
2484 (SSANAMES (my_function
)->length ());
2489 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2492 /* When we run into maximal number of entries, we assign everything to the
2493 constant truth case. Be sure to have it in list. */
2494 bb_predicate
= true_predicate ();
2495 account_size_time (info
, 0, 0, &bb_predicate
);
2497 bb_predicate
= not_inlined_predicate ();
2498 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2500 gcc_assert (my_function
&& my_function
->cfg
);
2502 compute_bb_predicates (node
, parms_info
, info
);
2503 gcc_assert (cfun
== my_function
);
2504 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2505 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2506 for (n
= 0; n
< nblocks
; n
++)
2508 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2509 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2510 if (clobber_only_eh_bb_p (bb
))
2512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2513 fprintf (dump_file
, "\n Ignoring BB %i;"
2514 " it will be optimized away by cleanup_clobbers\n",
2519 /* TODO: Obviously predicates can be propagated down across CFG. */
2523 bb_predicate
= *(struct predicate
*) bb
->aux
;
2525 bb_predicate
= false_predicate ();
2528 bb_predicate
= true_predicate ();
2530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2532 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2533 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2536 if (parms_info
&& nonconstant_names
.exists ())
2538 struct predicate phi_predicate
;
2539 bool first_phi
= true;
2541 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2544 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2551 fprintf (dump_file
, " ");
2552 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2554 predicate_for_phi_result (info
, gsi_stmt (bsi
), &phi_predicate
,
2559 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2561 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2563 gimple stmt
= gsi_stmt (bsi
);
2564 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2565 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2567 struct predicate will_be_nonconstant
;
2569 /* This relation stmt should be folded after we remove
2570 buildin_expect call. Adjust the cost here. */
2571 if (stmt
== fix_builtin_expect_stmt
)
2577 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2579 fprintf (dump_file
, " ");
2580 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2581 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2582 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2586 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2588 struct predicate this_array_index
;
2590 array_index_predicate (info
, nonconstant_names
,
2591 gimple_assign_rhs1 (stmt
));
2592 if (!false_predicate_p (&this_array_index
))
2594 and_predicates (info
->conds
, &array_index
,
2597 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2599 struct predicate this_array_index
;
2601 array_index_predicate (info
, nonconstant_names
,
2602 gimple_get_lhs (stmt
));
2603 if (!false_predicate_p (&this_array_index
))
2605 and_predicates (info
->conds
, &array_index
,
2610 if (is_gimple_call (stmt
)
2611 && !gimple_call_internal_p (stmt
))
2613 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2614 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2616 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2617 resolved as constant. We however don't want to optimize
2618 out the cgraph edges. */
2619 if (nonconstant_names
.exists ()
2620 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2621 && gimple_call_lhs (stmt
)
2622 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2624 struct predicate false_p
= false_predicate ();
2625 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2628 if (ipa_node_params_vector
.exists ())
2630 int count
= gimple_call_num_args (stmt
);
2634 es
->param
.safe_grow_cleared (count
);
2635 for (i
= 0; i
< count
; i
++)
2637 int prob
= param_change_prob (stmt
, i
);
2638 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2639 es
->param
[i
].change_prob
= prob
;
2643 es
->call_stmt_size
= this_size
;
2644 es
->call_stmt_time
= this_time
;
2645 es
->loop_depth
= bb_loop_depth (bb
);
2646 edge_set_predicate (edge
, &bb_predicate
);
2649 /* TODO: When conditional jump or swithc is known to be constant, but
2650 we did not translate it into the predicates, we really can account
2651 just maximum of the possible paths. */
2654 = will_be_nonconstant_predicate (parms_info
, info
,
2655 stmt
, nonconstant_names
);
2656 if (this_time
|| this_size
)
2662 prob
= eliminated_by_inlining_prob (stmt
);
2663 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2665 "\t\t50%% will be eliminated by inlining\n");
2666 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2667 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2670 p
= and_predicates (info
->conds
, &bb_predicate
,
2671 &will_be_nonconstant
);
2673 p
= true_predicate ();
2675 if (!false_predicate_p (&p
))
2679 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2680 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2683 /* We account everything but the calls. Calls have their own
2684 size/time info attached to cgraph edges. This is necessary
2685 in order to make the cost disappear after inlining. */
2686 if (!is_gimple_call (stmt
))
2690 struct predicate ip
= not_inlined_predicate ();
2691 ip
= and_predicates (info
->conds
, &ip
, &p
);
2692 account_size_time (info
, this_size
* prob
,
2693 this_time
* prob
, &ip
);
2696 account_size_time (info
, this_size
* (2 - prob
),
2697 this_time
* (2 - prob
), &p
);
2700 gcc_assert (time
>= 0);
2701 gcc_assert (size
>= 0);
2705 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2706 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2707 if (time
> MAX_TIME
)
2711 if (!early
&& nonconstant_names
.exists ())
2714 predicate loop_iterations
= true_predicate ();
2715 predicate loop_stride
= true_predicate ();
2717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2718 flow_loops_dump (dump_file
, NULL
, 0);
2720 FOR_EACH_LOOP (loop
, 0)
2725 struct tree_niter_desc niter_desc
;
2726 basic_block
*body
= get_loop_body (loop
);
2727 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2729 exits
= get_loop_exit_edges (loop
);
2730 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2731 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2732 && !is_gimple_min_invariant (niter_desc
.niter
))
2734 predicate will_be_nonconstant
2735 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2738 if (!true_predicate_p (&will_be_nonconstant
))
2739 will_be_nonconstant
= and_predicates (info
->conds
,
2741 &will_be_nonconstant
);
2742 if (!true_predicate_p (&will_be_nonconstant
)
2743 && !false_predicate_p (&will_be_nonconstant
))
2744 /* This is slightly inprecise. We may want to represent each
2745 loop with independent predicate. */
2747 and_predicates (info
->conds
, &loop_iterations
,
2748 &will_be_nonconstant
);
2752 for (i
= 0; i
< loop
->num_nodes
; i
++)
2754 gimple_stmt_iterator gsi
;
2755 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2756 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2759 gimple stmt
= gsi_stmt (gsi
);
2764 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2766 predicate will_be_nonconstant
;
2769 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2770 || is_gimple_min_invariant (iv
.step
))
2773 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2776 if (!true_predicate_p (&will_be_nonconstant
))
2778 = and_predicates (info
->conds
,
2780 &will_be_nonconstant
);
2781 if (!true_predicate_p (&will_be_nonconstant
)
2782 && !false_predicate_p (&will_be_nonconstant
))
2783 /* This is slightly inprecise. We may want to represent
2784 each loop with independent predicate. */
2786 and_predicates (info
->conds
, &loop_stride
,
2787 &will_be_nonconstant
);
2793 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2795 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2798 FOR_ALL_BB_FN (bb
, my_function
)
2804 pool_free (edge_predicate_pool
, bb
->aux
);
2806 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2809 pool_free (edge_predicate_pool
, e
->aux
);
2813 inline_summary (node
)->self_time
= time
;
2814 inline_summary (node
)->self_size
= size
;
2815 nonconstant_names
.release ();
2816 if (optimize
&& !early
)
2818 loop_optimizer_finalize ();
2819 free_dominance_info (CDI_DOMINATORS
);
2823 fprintf (dump_file
, "\n");
2824 dump_inline_summary (dump_file
, node
);
2829 /* Compute parameters of functions used by inliner.
2830 EARLY is true when we compute parameters for the early inliner */
2833 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2835 HOST_WIDE_INT self_stack_size
;
2836 struct cgraph_edge
*e
;
2837 struct inline_summary
*info
;
2839 gcc_assert (!node
->global
.inlined_to
);
2841 inline_summary_alloc ();
2843 info
= inline_summary (node
);
2844 reset_inline_summary (node
);
2846 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2847 Once this happen, we will need to more curefully predict call
2849 if (node
->thunk
.thunk_p
)
2851 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2852 struct predicate t
= true_predicate ();
2854 info
->inlinable
= 0;
2855 node
->callees
->call_stmt_cannot_inline_p
= true;
2856 node
->local
.can_change_signature
= false;
2857 es
->call_stmt_time
= 1;
2858 es
->call_stmt_size
= 1;
2859 account_size_time (info
, 0, 0, &t
);
2863 /* Even is_gimple_min_invariant rely on current_function_decl. */
2864 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2866 /* Estimate the stack size for the function if we're optimizing. */
2867 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2868 info
->estimated_self_stack_size
= self_stack_size
;
2869 info
->estimated_stack_size
= self_stack_size
;
2870 info
->stack_frame_offset
= 0;
2872 /* Can this function be inlined at all? */
2873 if (!optimize
&& !lookup_attribute ("always_inline",
2874 DECL_ATTRIBUTES (node
->decl
)))
2875 info
->inlinable
= false;
2877 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2879 /* Type attributes can use parameter indices to describe them. */
2880 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2881 node
->local
.can_change_signature
= false;
2884 /* Otherwise, inlinable functions always can change signature. */
2885 if (info
->inlinable
)
2886 node
->local
.can_change_signature
= true;
2889 /* Functions calling builtin_apply can not change signature. */
2890 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2892 tree
cdecl = e
->callee
->decl
;
2893 if (DECL_BUILT_IN (cdecl)
2894 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2895 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2896 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2899 node
->local
.can_change_signature
= !e
;
2902 estimate_function_body_sizes (node
, early
);
2904 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2905 if (e
->callee
->comdat_local_p ())
2907 node
->calls_comdat_local
= (e
!= NULL
);
2909 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2910 info
->time
= info
->self_time
;
2911 info
->size
= info
->self_size
;
2912 info
->stack_frame_offset
= 0;
2913 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2914 #ifdef ENABLE_CHECKING
2915 inline_update_overall_summary (node
);
2916 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2923 /* Compute parameters of functions used by inliner using
2924 current_function_decl. */
2927 compute_inline_parameters_for_current (void)
2929 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2935 const pass_data pass_data_inline_parameters
=
2937 GIMPLE_PASS
, /* type */
2938 "inline_param", /* name */
2939 OPTGROUP_INLINE
, /* optinfo_flags */
2940 TV_INLINE_PARAMETERS
, /* tv_id */
2941 0, /* properties_required */
2942 0, /* properties_provided */
2943 0, /* properties_destroyed */
2944 0, /* todo_flags_start */
2945 0, /* todo_flags_finish */
2948 class pass_inline_parameters
: public gimple_opt_pass
2951 pass_inline_parameters (gcc::context
*ctxt
)
2952 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2955 /* opt_pass methods: */
2956 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2957 virtual unsigned int execute (function
*)
2959 return compute_inline_parameters_for_current ();
2962 }; // class pass_inline_parameters
2967 make_pass_inline_parameters (gcc::context
*ctxt
)
2969 return new pass_inline_parameters (ctxt
);
2973 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2977 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2978 int *size
, int *time
,
2979 vec
<tree
> known_vals
,
2980 vec
<tree
> known_binfos
,
2981 vec
<ipa_agg_jump_function_p
> known_aggs
)
2984 struct cgraph_node
*callee
;
2985 struct inline_summary
*isummary
;
2986 enum availability avail
;
2988 if (!known_vals
.exists () && !known_binfos
.exists ())
2990 if (!flag_indirect_inlining
)
2993 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_binfos
,
2998 /* Account for difference in cost between indirect and direct calls. */
2999 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3000 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3001 gcc_checking_assert (*time
>= 0);
3002 gcc_checking_assert (*size
>= 0);
3004 callee
= cgraph_node::get (target
);
3005 if (!callee
|| !callee
->definition
)
3007 callee
= callee
->function_symbol (&avail
);
3008 if (avail
< AVAIL_AVAILABLE
)
3010 isummary
= inline_summary (callee
);
3011 return isummary
->inlinable
;
3014 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3015 handle edge E with probability PROB.
3016 Set HINTS if edge may be devirtualized.
3017 KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS describe context of the call
3021 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3024 vec
<tree
> known_vals
,
3025 vec
<tree
> known_binfos
,
3026 vec
<ipa_agg_jump_function_p
> known_aggs
,
3027 inline_hints
*hints
)
3029 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3030 int call_size
= es
->call_stmt_size
;
3031 int call_time
= es
->call_stmt_time
;
3034 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3035 known_vals
, known_binfos
, known_aggs
)
3036 && hints
&& e
->maybe_hot_p ())
3037 *hints
|= INLINE_HINT_indirect_call
;
3038 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3041 *min_size
+= cur_size
;
3042 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3043 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3044 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3045 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3050 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3052 POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS describe context of
3056 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3057 int *min_size
, int *time
,
3058 inline_hints
*hints
,
3059 clause_t possible_truths
,
3060 vec
<tree
> known_vals
,
3061 vec
<tree
> known_binfos
,
3062 vec
<ipa_agg_jump_function_p
> known_aggs
)
3064 struct cgraph_edge
*e
;
3065 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3067 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3069 || evaluate_predicate (es
->predicate
, possible_truths
))
3071 if (e
->inline_failed
)
3073 /* Predicates of calls shall not use NOT_CHANGED codes,
3074 sowe do not need to compute probabilities. */
3075 estimate_edge_size_and_time (e
, size
,
3076 es
->predicate
? NULL
: min_size
,
3077 time
, REG_BR_PROB_BASE
,
3078 known_vals
, known_binfos
,
3082 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3085 known_vals
, known_binfos
,
3089 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3091 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3093 || evaluate_predicate (es
->predicate
, possible_truths
))
3094 estimate_edge_size_and_time (e
, size
,
3095 es
->predicate
? NULL
: min_size
,
3096 time
, REG_BR_PROB_BASE
,
3097 known_vals
, known_binfos
, known_aggs
,
3103 /* Estimate size and time needed to execute NODE assuming
3104 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS
3105 information about NODE's arguments. If non-NULL use also probability
3106 information present in INLINE_PARAM_SUMMARY vector.
3107 Additionally detemine hints determined by the context. Finally compute
3108 minimal size needed for the call that is independent on the call context and
3109 can be used for fast estimates. Return the values in RET_SIZE,
3110 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3113 estimate_node_size_and_time (struct cgraph_node
*node
,
3114 clause_t possible_truths
,
3115 vec
<tree
> known_vals
,
3116 vec
<tree
> known_binfos
,
3117 vec
<ipa_agg_jump_function_p
> known_aggs
,
3118 int *ret_size
, int *ret_min_size
, int *ret_time
,
3119 inline_hints
*ret_hints
,
3120 vec
<inline_param_summary
>
3121 inline_param_summary
)
3123 struct inline_summary
*info
= inline_summary (node
);
3128 inline_hints hints
= 0;
3131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3134 fprintf (dump_file
, " Estimating body: %s/%i\n"
3135 " Known to be false: ", node
->name (),
3138 for (i
= predicate_not_inlined_condition
;
3139 i
< (predicate_first_dynamic_condition
3140 + (int) vec_safe_length (info
->conds
)); i
++)
3141 if (!(possible_truths
& (1 << i
)))
3144 fprintf (dump_file
, ", ");
3146 dump_condition (dump_file
, info
->conds
, i
);
3150 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3151 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3154 gcc_checking_assert (e
->time
>= 0);
3155 gcc_checking_assert (time
>= 0);
3156 if (!inline_param_summary
.exists ())
3160 int prob
= predicate_probability (info
->conds
,
3163 inline_param_summary
);
3164 gcc_checking_assert (prob
>= 0);
3165 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3166 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3168 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3169 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3170 gcc_checking_assert (time
>= 0);
3173 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3174 min_size
= (*info
->entry
)[0].size
;
3175 gcc_checking_assert (size
>= 0);
3176 gcc_checking_assert (time
>= 0);
3178 if (info
->loop_iterations
3179 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3180 hints
|= INLINE_HINT_loop_iterations
;
3181 if (info
->loop_stride
3182 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3183 hints
|= INLINE_HINT_loop_stride
;
3184 if (info
->array_index
3185 && !evaluate_predicate (info
->array_index
, possible_truths
))
3186 hints
|= INLINE_HINT_array_index
;
3188 hints
|= INLINE_HINT_in_scc
;
3189 if (DECL_DECLARED_INLINE_P (node
->decl
))
3190 hints
|= INLINE_HINT_declared_inline
;
3192 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3193 known_vals
, known_binfos
, known_aggs
);
3194 gcc_checking_assert (size
>= 0);
3195 gcc_checking_assert (time
>= 0);
3196 time
= RDIV (time
, INLINE_TIME_SCALE
);
3197 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3198 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3201 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3207 *ret_min_size
= min_size
;
3214 /* Estimate size and time needed to execute callee of EDGE assuming that
3215 parameters known to be constant at caller of EDGE are propagated.
3216 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
3217 and types for parameters. */
3220 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3221 vec
<tree
> known_vals
,
3222 vec
<tree
> known_binfos
,
3223 vec
<ipa_agg_jump_function_p
> known_aggs
,
3224 int *ret_size
, int *ret_time
,
3225 inline_hints
*hints
)
3229 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3231 estimate_node_size_and_time (node
, clause
, known_vals
, known_binfos
,
3232 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3235 /* Translate all conditions from callee representation into caller
3236 representation and symbolically evaluate predicate P into new predicate.
3238 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3239 is summary of function predicate P is from. OPERAND_MAP is array giving
3240 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3241 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3242 predicate under which callee is executed. OFFSET_MAP is an array of of
3243 offsets that need to be added to conditions, negative offset means that
3244 conditions relying on values passed by reference have to be discarded
3245 because they might not be preserved (and should be considered offset zero
3246 for other purposes). */
3248 static struct predicate
3249 remap_predicate (struct inline_summary
*info
,
3250 struct inline_summary
*callee_info
,
3251 struct predicate
*p
,
3252 vec
<int> operand_map
,
3253 vec
<int> offset_map
,
3254 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3257 struct predicate out
= true_predicate ();
3259 /* True predicate is easy. */
3260 if (true_predicate_p (p
))
3261 return *toplev_predicate
;
3262 for (i
= 0; p
->clause
[i
]; i
++)
3264 clause_t clause
= p
->clause
[i
];
3266 struct predicate clause_predicate
= false_predicate ();
3268 gcc_assert (i
< MAX_CLAUSES
);
3270 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3271 /* Do we have condition we can't disprove? */
3272 if (clause
& possible_truths
& (1 << cond
))
3274 struct predicate cond_predicate
;
3275 /* Work out if the condition can translate to predicate in the
3276 inlined function. */
3277 if (cond
>= predicate_first_dynamic_condition
)
3279 struct condition
*c
;
3281 c
= &(*callee_info
->conds
)[cond
3283 predicate_first_dynamic_condition
];
3284 /* See if we can remap condition operand to caller's operand.
3285 Otherwise give up. */
3286 if (!operand_map
.exists ()
3287 || (int) operand_map
.length () <= c
->operand_num
3288 || operand_map
[c
->operand_num
] == -1
3289 /* TODO: For non-aggregate conditions, adding an offset is
3290 basically an arithmetic jump function processing which
3291 we should support in future. */
3292 || ((!c
->agg_contents
|| !c
->by_ref
)
3293 && offset_map
[c
->operand_num
] > 0)
3294 || (c
->agg_contents
&& c
->by_ref
3295 && offset_map
[c
->operand_num
] < 0))
3296 cond_predicate
= true_predicate ();
3299 struct agg_position_info ap
;
3300 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3301 if (offset_delta
< 0)
3303 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3306 gcc_assert (!c
->agg_contents
3307 || c
->by_ref
|| offset_delta
== 0);
3308 ap
.offset
= c
->offset
+ offset_delta
;
3309 ap
.agg_contents
= c
->agg_contents
;
3310 ap
.by_ref
= c
->by_ref
;
3311 cond_predicate
= add_condition (info
,
3312 operand_map
[c
->operand_num
],
3313 &ap
, c
->code
, c
->val
);
3316 /* Fixed conditions remains same, construct single
3317 condition predicate. */
3320 cond_predicate
.clause
[0] = 1 << cond
;
3321 cond_predicate
.clause
[1] = 0;
3323 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3326 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3328 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3332 /* Update summary information of inline clones after inlining.
3333 Compute peak stack usage. */
3336 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3338 struct cgraph_edge
*e
;
3339 struct inline_summary
*callee_info
= inline_summary (node
);
3340 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3343 callee_info
->stack_frame_offset
3344 = caller_info
->stack_frame_offset
3345 + caller_info
->estimated_self_stack_size
;
3346 peak
= callee_info
->stack_frame_offset
3347 + callee_info
->estimated_self_stack_size
;
3348 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3349 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3350 ipa_propagate_frequency (node
);
3351 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3353 if (!e
->inline_failed
)
3354 inline_update_callee_summaries (e
->callee
, depth
);
3355 inline_edge_summary (e
)->loop_depth
+= depth
;
3357 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3358 inline_edge_summary (e
)->loop_depth
+= depth
;
3361 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3362 When functoin A is inlined in B and A calls C with parameter that
3363 changes with probability PROB1 and C is known to be passthroug
3364 of argument if B that change with probability PROB2, the probability
3365 of change is now PROB1*PROB2. */
3368 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3369 struct cgraph_edge
*edge
)
3371 if (ipa_node_params_vector
.exists ())
3374 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3375 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3376 struct inline_edge_summary
*inlined_es
3377 = inline_edge_summary (inlined_edge
);
3379 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3381 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3382 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3383 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3384 < (int) inlined_es
->param
.length ()))
3386 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3387 int prob1
= es
->param
[i
].change_prob
;
3388 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3389 int prob
= combine_probabilities (prob1
, prob2
);
3391 if (prob1
&& prob2
&& !prob
)
3394 es
->param
[i
].change_prob
= prob
;
3400 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3402 Remap predicates of callees of NODE. Rest of arguments match
3405 Also update change probabilities. */
3408 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3409 struct cgraph_node
*node
,
3410 struct inline_summary
*info
,
3411 struct inline_summary
*callee_info
,
3412 vec
<int> operand_map
,
3413 vec
<int> offset_map
,
3414 clause_t possible_truths
,
3415 struct predicate
*toplev_predicate
)
3417 struct cgraph_edge
*e
;
3418 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3420 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3423 if (e
->inline_failed
)
3425 remap_edge_change_prob (inlined_edge
, e
);
3429 p
= remap_predicate (info
, callee_info
,
3430 es
->predicate
, operand_map
, offset_map
,
3431 possible_truths
, toplev_predicate
);
3432 edge_set_predicate (e
, &p
);
3433 /* TODO: We should remove the edge for code that will be
3434 optimized out, but we need to keep verifiers and tree-inline
3435 happy. Make it cold for now. */
3436 if (false_predicate_p (&p
))
3443 edge_set_predicate (e
, toplev_predicate
);
3446 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3447 operand_map
, offset_map
, possible_truths
,
3450 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3452 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3455 remap_edge_change_prob (inlined_edge
, e
);
3458 p
= remap_predicate (info
, callee_info
,
3459 es
->predicate
, operand_map
, offset_map
,
3460 possible_truths
, toplev_predicate
);
3461 edge_set_predicate (e
, &p
);
3462 /* TODO: We should remove the edge for code that will be optimized
3463 out, but we need to keep verifiers and tree-inline happy.
3464 Make it cold for now. */
3465 if (false_predicate_p (&p
))
3472 edge_set_predicate (e
, toplev_predicate
);
3476 /* Same as remap_predicate, but set result into hint *HINT. */
3479 remap_hint_predicate (struct inline_summary
*info
,
3480 struct inline_summary
*callee_info
,
3481 struct predicate
**hint
,
3482 vec
<int> operand_map
,
3483 vec
<int> offset_map
,
3484 clause_t possible_truths
,
3485 struct predicate
*toplev_predicate
)
3491 p
= remap_predicate (info
, callee_info
,
3493 operand_map
, offset_map
,
3494 possible_truths
, toplev_predicate
);
3495 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3498 set_hint_predicate (hint
, p
);
3500 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3504 /* We inlined EDGE. Update summary of the function we inlined into. */
3507 inline_merge_summary (struct cgraph_edge
*edge
)
3509 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3510 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3511 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3512 struct inline_summary
*info
= inline_summary (to
);
3513 clause_t clause
= 0; /* not_inline is known to be false. */
3515 vec
<int> operand_map
= vNULL
;
3516 vec
<int> offset_map
= vNULL
;
3518 struct predicate toplev_predicate
;
3519 struct predicate true_p
= true_predicate ();
3520 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3523 toplev_predicate
= *es
->predicate
;
3525 toplev_predicate
= true_predicate ();
3527 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3529 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3530 int count
= ipa_get_cs_argument_count (args
);
3533 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3536 operand_map
.safe_grow_cleared (count
);
3537 offset_map
.safe_grow_cleared (count
);
3539 for (i
= 0; i
< count
; i
++)
3541 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3544 /* TODO: handle non-NOPs when merging. */
3545 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3547 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3548 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3549 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3552 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3554 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3555 if (offset
>= 0 && offset
< INT_MAX
)
3557 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3558 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3560 offset_map
[i
] = offset
;
3563 operand_map
[i
] = map
;
3564 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3567 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3569 struct predicate p
= remap_predicate (info
, callee_info
,
3570 &e
->predicate
, operand_map
,
3573 if (!false_predicate_p (&p
))
3575 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3576 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3577 int prob
= predicate_probability (callee_info
->conds
,
3580 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3581 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3582 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3583 if (prob
!= REG_BR_PROB_BASE
3584 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3586 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3587 (double) prob
/ REG_BR_PROB_BASE
);
3589 account_size_time (info
, e
->size
, add_time
, &p
);
3592 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3593 offset_map
, clause
, &toplev_predicate
);
3594 remap_hint_predicate (info
, callee_info
,
3595 &callee_info
->loop_iterations
,
3596 operand_map
, offset_map
, clause
, &toplev_predicate
);
3597 remap_hint_predicate (info
, callee_info
,
3598 &callee_info
->loop_stride
,
3599 operand_map
, offset_map
, clause
, &toplev_predicate
);
3600 remap_hint_predicate (info
, callee_info
,
3601 &callee_info
->array_index
,
3602 operand_map
, offset_map
, clause
, &toplev_predicate
);
3604 inline_update_callee_summaries (edge
->callee
,
3605 inline_edge_summary (edge
)->loop_depth
);
3607 /* We do not maintain predicates of inlined edges, free it. */
3608 edge_set_predicate (edge
, &true_p
);
3609 /* Similarly remove param summaries. */
3610 es
->param
.release ();
3611 operand_map
.release ();
3612 offset_map
.release ();
3615 /* For performance reasons inline_merge_summary is not updating overall size
3616 and time. Recompute it. */
3619 inline_update_overall_summary (struct cgraph_node
*node
)
3621 struct inline_summary
*info
= inline_summary (node
);
3627 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3629 info
->size
+= e
->size
, info
->time
+= e
->time
;
3630 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3631 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3633 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3635 ~(clause_t
) (1 << predicate_false_condition
),
3636 vNULL
, vNULL
, vNULL
);
3637 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3638 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3641 /* Return hints derrived from EDGE. */
3643 simple_edge_hints (struct cgraph_edge
*edge
)
3646 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3647 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3648 if (inline_summary (to
)->scc_no
3649 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3650 && !edge
->recursive_p ())
3651 hints
|= INLINE_HINT_same_scc
;
3653 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3654 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3655 hints
|= INLINE_HINT_cross_module
;
3660 /* Estimate the time cost for the caller when inlining EDGE.
3661 Only to be called via estimate_edge_time, that handles the
3664 When caching, also update the cache entry. Compute both time and
3665 size, since we always need both metrics eventually. */
3668 do_estimate_edge_time (struct cgraph_edge
*edge
)
3673 struct cgraph_node
*callee
;
3675 vec
<tree
> known_vals
;
3676 vec
<tree
> known_binfos
;
3677 vec
<ipa_agg_jump_function_p
> known_aggs
;
3678 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3681 callee
= edge
->callee
->ultimate_alias_target ();
3683 gcc_checking_assert (edge
->inline_failed
);
3684 evaluate_properties_for_edge (edge
, true,
3685 &clause
, &known_vals
, &known_binfos
,
3687 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3688 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3690 /* When we have profile feedback, we can quite safely identify hot
3691 edges and for those we disable size limits. Don't do that when
3692 probability that caller will call the callee is low however, since it
3693 may hurt optimization of the caller's hot path. */
3694 if (edge
->count
&& edge
->maybe_hot_p ()
3696 > (edge
->caller
->global
.inlined_to
3697 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3698 hints
|= INLINE_HINT_known_hot
;
3700 known_vals
.release ();
3701 known_binfos
.release ();
3702 known_aggs
.release ();
3703 gcc_checking_assert (size
>= 0);
3704 gcc_checking_assert (time
>= 0);
3706 /* When caching, update the cache entry. */
3707 if (edge_growth_cache
.exists ())
3709 inline_summary (edge
->callee
)->min_size
= min_size
;
3710 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3711 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3712 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3714 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3715 hints
|= simple_edge_hints (edge
);
3716 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3722 /* Return estimated callee growth after inlining EDGE.
3723 Only to be called via estimate_edge_size. */
3726 do_estimate_edge_size (struct cgraph_edge
*edge
)
3729 struct cgraph_node
*callee
;
3731 vec
<tree
> known_vals
;
3732 vec
<tree
> known_binfos
;
3733 vec
<ipa_agg_jump_function_p
> known_aggs
;
3735 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3737 if (edge_growth_cache
.exists ())
3739 do_estimate_edge_time (edge
);
3740 size
= edge_growth_cache
[edge
->uid
].size
;
3741 gcc_checking_assert (size
);
3742 return size
- (size
> 0);
3745 callee
= edge
->callee
->ultimate_alias_target ();
3747 /* Early inliner runs without caching, go ahead and do the dirty work. */
3748 gcc_checking_assert (edge
->inline_failed
);
3749 evaluate_properties_for_edge (edge
, true,
3750 &clause
, &known_vals
, &known_binfos
,
3752 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3753 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3754 known_vals
.release ();
3755 known_binfos
.release ();
3756 known_aggs
.release ();
3761 /* Estimate the growth of the caller when inlining EDGE.
3762 Only to be called via estimate_edge_size. */
3765 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3768 struct cgraph_node
*callee
;
3770 vec
<tree
> known_vals
;
3771 vec
<tree
> known_binfos
;
3772 vec
<ipa_agg_jump_function_p
> known_aggs
;
3774 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3776 if (edge_growth_cache
.exists ())
3778 do_estimate_edge_time (edge
);
3779 hints
= edge_growth_cache
[edge
->uid
].hints
;
3780 gcc_checking_assert (hints
);
3784 callee
= edge
->callee
->ultimate_alias_target ();
3786 /* Early inliner runs without caching, go ahead and do the dirty work. */
3787 gcc_checking_assert (edge
->inline_failed
);
3788 evaluate_properties_for_edge (edge
, true,
3789 &clause
, &known_vals
, &known_binfos
,
3791 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3792 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3793 known_vals
.release ();
3794 known_binfos
.release ();
3795 known_aggs
.release ();
3796 hints
|= simple_edge_hints (edge
);
3801 /* Estimate self time of the function NODE after inlining EDGE. */
3804 estimate_time_after_inlining (struct cgraph_node
*node
,
3805 struct cgraph_edge
*edge
)
3807 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3808 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3811 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3814 if (time
> MAX_TIME
)
3818 return inline_summary (node
)->time
;
3822 /* Estimate the size of NODE after inlining EDGE which should be an
3823 edge to either NODE or a call inlined into NODE. */
3826 estimate_size_after_inlining (struct cgraph_node
*node
,
3827 struct cgraph_edge
*edge
)
3829 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3830 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3832 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3833 gcc_assert (size
>= 0);
3836 return inline_summary (node
)->size
;
3842 struct cgraph_node
*node
;
3843 bool self_recursive
;
3848 /* Worker for do_estimate_growth. Collect growth for all callers. */
3851 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3853 struct cgraph_edge
*e
;
3854 struct growth_data
*d
= (struct growth_data
*) data
;
3856 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3858 gcc_checking_assert (e
->inline_failed
);
3860 if (e
->caller
== d
->node
3861 || (e
->caller
->global
.inlined_to
3862 && e
->caller
->global
.inlined_to
== d
->node
))
3863 d
->self_recursive
= true;
3864 d
->growth
+= estimate_edge_growth (e
);
3870 /* Estimate the growth caused by inlining NODE into all callees. */
3873 do_estimate_growth (struct cgraph_node
*node
)
3875 struct growth_data d
= { node
, 0, false };
3876 struct inline_summary
*info
= inline_summary (node
);
3878 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3880 /* For self recursive functions the growth estimation really should be
3881 infinity. We don't want to return very large values because the growth
3882 plays various roles in badness computation fractions. Be sure to not
3883 return zero or negative growths. */
3884 if (d
.self_recursive
)
3885 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3886 else if (DECL_EXTERNAL (node
->decl
))
3890 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3891 d
.growth
-= info
->size
;
3892 /* COMDAT functions are very often not shared across multiple units
3893 since they come from various template instantiations.
3894 Take this into account. */
3895 else if (DECL_COMDAT (node
->decl
)
3896 && node
->can_remove_if_no_direct_calls_p ())
3897 d
.growth
-= (info
->size
3898 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3902 if (node_growth_cache
.exists ())
3904 if ((int) node_growth_cache
.length () <= node
->uid
)
3905 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3906 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3912 /* Make cheap estimation if growth of NODE is likely positive knowing
3913 EDGE_GROWTH of one particular edge.
3914 We assume that most of other edges will have similar growth
3915 and skip computation if there are too many callers. */
3918 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3922 struct cgraph_edge
*e
;
3923 gcc_checking_assert (edge_growth
> 0);
3925 /* Unlike for functions called once, we play unsafe with
3926 COMDATs. We can allow that since we know functions
3927 in consideration are small (and thus risk is small) and
3928 moreover grow estimates already accounts that COMDAT
3929 functions may or may not disappear when eliminated from
3930 current unit. With good probability making aggressive
3931 choice in all units is going to make overall program
3934 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3936 cgraph_will_be_removed_from_program_if_no_direct_calls */
3937 if (DECL_EXTERNAL (node
->decl
)
3938 || !node
->can_remove_if_no_direct_calls_p ())
3941 /* If there is cached value, just go ahead. */
3942 if ((int)node_growth_cache
.length () > node
->uid
3943 && (ret
= node_growth_cache
[node
->uid
]))
3945 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
3946 && (!DECL_COMDAT (node
->decl
)
3947 || !node
->can_remove_if_no_direct_calls_p ()))
3949 max_callers
= inline_summary (node
)->size
* 4 / edge_growth
+ 2;
3951 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3957 return estimate_growth (node
) > 0;
3961 /* This function performs intraprocedural analysis in NODE that is required to
3962 inline indirect calls. */
3965 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3967 ipa_analyze_node (node
);
3968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3970 ipa_print_node_params (dump_file
, node
);
3971 ipa_print_node_jump_functions (dump_file
, node
);
3976 /* Note function body size. */
3979 inline_analyze_function (struct cgraph_node
*node
)
3981 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3984 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3985 node
->name (), node
->order
);
3986 if (optimize
&& !node
->thunk
.thunk_p
)
3987 inline_indirect_intraprocedural_analysis (node
);
3988 compute_inline_parameters (node
, false);
3991 struct cgraph_edge
*e
;
3992 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3994 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3995 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3996 e
->call_stmt_cannot_inline_p
= true;
3998 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4000 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4001 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4002 e
->call_stmt_cannot_inline_p
= true;
4010 /* Called when new function is inserted to callgraph late. */
4013 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
4015 inline_analyze_function (node
);
4019 /* Note function body size. */
4022 inline_generate_summary (void)
4024 struct cgraph_node
*node
;
4026 /* When not optimizing, do not bother to analyze. Inlining is still done
4027 because edge redirection needs to happen there. */
4028 if (!optimize
&& !flag_lto
&& !flag_wpa
)
4031 function_insertion_hook_holder
=
4032 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4034 ipa_register_cgraph_hooks ();
4035 inline_free_summary ();
4037 FOR_EACH_DEFINED_FUNCTION (node
)
4039 inline_analyze_function (node
);
4043 /* Read predicate from IB. */
4045 static struct predicate
4046 read_predicate (struct lto_input_block
*ib
)
4048 struct predicate out
;
4054 gcc_assert (k
<= MAX_CLAUSES
);
4055 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4059 /* Zero-initialize the remaining clauses in OUT. */
4060 while (k
<= MAX_CLAUSES
)
4061 out
.clause
[k
++] = 0;
4067 /* Write inline summary for edge E to OB. */
4070 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4072 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4076 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4077 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4078 es
->loop_depth
= streamer_read_uhwi (ib
);
4079 p
= read_predicate (ib
);
4080 edge_set_predicate (e
, &p
);
4081 length
= streamer_read_uhwi (ib
);
4084 es
->param
.safe_grow_cleared (length
);
4085 for (i
= 0; i
< length
; i
++)
4086 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4091 /* Stream in inline summaries from the section. */
4094 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4097 const struct lto_function_header
*header
=
4098 (const struct lto_function_header
*) data
;
4099 const int cfg_offset
= sizeof (struct lto_function_header
);
4100 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4101 const int string_offset
= main_offset
+ header
->main_size
;
4102 struct data_in
*data_in
;
4103 unsigned int i
, count2
, j
;
4104 unsigned int f_count
;
4106 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4109 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4110 header
->string_size
, vNULL
);
4111 f_count
= streamer_read_uhwi (&ib
);
4112 for (i
= 0; i
< f_count
; i
++)
4115 struct cgraph_node
*node
;
4116 struct inline_summary
*info
;
4117 lto_symtab_encoder_t encoder
;
4118 struct bitpack_d bp
;
4119 struct cgraph_edge
*e
;
4122 index
= streamer_read_uhwi (&ib
);
4123 encoder
= file_data
->symtab_node_encoder
;
4124 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4126 info
= inline_summary (node
);
4128 info
->estimated_stack_size
4129 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4130 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4131 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4133 bp
= streamer_read_bitpack (&ib
);
4134 info
->inlinable
= bp_unpack_value (&bp
, 1);
4136 count2
= streamer_read_uhwi (&ib
);
4137 gcc_assert (!info
->conds
);
4138 for (j
= 0; j
< count2
; j
++)
4141 c
.operand_num
= streamer_read_uhwi (&ib
);
4142 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4143 c
.val
= stream_read_tree (&ib
, data_in
);
4144 bp
= streamer_read_bitpack (&ib
);
4145 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4146 c
.by_ref
= bp_unpack_value (&bp
, 1);
4148 c
.offset
= streamer_read_uhwi (&ib
);
4149 vec_safe_push (info
->conds
, c
);
4151 count2
= streamer_read_uhwi (&ib
);
4152 gcc_assert (!info
->entry
);
4153 for (j
= 0; j
< count2
; j
++)
4155 struct size_time_entry e
;
4157 e
.size
= streamer_read_uhwi (&ib
);
4158 e
.time
= streamer_read_uhwi (&ib
);
4159 e
.predicate
= read_predicate (&ib
);
4161 vec_safe_push (info
->entry
, e
);
4164 p
= read_predicate (&ib
);
4165 set_hint_predicate (&info
->loop_iterations
, p
);
4166 p
= read_predicate (&ib
);
4167 set_hint_predicate (&info
->loop_stride
, p
);
4168 p
= read_predicate (&ib
);
4169 set_hint_predicate (&info
->array_index
, p
);
4170 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4171 read_inline_edge_summary (&ib
, e
);
4172 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4173 read_inline_edge_summary (&ib
, e
);
4176 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4178 lto_data_in_delete (data_in
);
4182 /* Read inline summary. Jump functions are shared among ipa-cp
4183 and inliner, so when ipa-cp is active, we don't need to write them
4187 inline_read_summary (void)
4189 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4190 struct lto_file_decl_data
*file_data
;
4193 inline_summary_alloc ();
4195 while ((file_data
= file_data_vec
[j
++]))
4198 const char *data
= lto_get_section_data (file_data
,
4199 LTO_section_inline_summary
,
4202 inline_read_section (file_data
, data
, len
);
4204 /* Fatal error here. We do not want to support compiling ltrans units
4205 with different version of compiler or different flags than the WPA
4206 unit, so this should never happen. */
4207 fatal_error ("ipa inline summary is missing in input file");
4211 ipa_register_cgraph_hooks ();
4213 ipa_prop_read_jump_functions ();
4215 function_insertion_hook_holder
=
4216 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4220 /* Write predicate P to OB. */
4223 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4227 for (j
= 0; p
->clause
[j
]; j
++)
4229 gcc_assert (j
< MAX_CLAUSES
);
4230 streamer_write_uhwi (ob
, p
->clause
[j
]);
4232 streamer_write_uhwi (ob
, 0);
4236 /* Write inline summary for edge E to OB. */
4239 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4241 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4244 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4245 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4246 streamer_write_uhwi (ob
, es
->loop_depth
);
4247 write_predicate (ob
, es
->predicate
);
4248 streamer_write_uhwi (ob
, es
->param
.length ());
4249 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4250 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4254 /* Write inline summary for node in SET.
4255 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4256 active, we don't need to write them twice. */
4259 inline_write_summary (void)
4261 struct cgraph_node
*node
;
4262 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4263 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4264 unsigned int count
= 0;
4267 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4269 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4270 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4271 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4274 streamer_write_uhwi (ob
, count
);
4276 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4278 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4279 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4280 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4282 struct inline_summary
*info
= inline_summary (node
);
4283 struct bitpack_d bp
;
4284 struct cgraph_edge
*edge
;
4287 struct condition
*c
;
4289 streamer_write_uhwi (ob
,
4290 lto_symtab_encoder_encode (encoder
,
4293 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4294 streamer_write_hwi (ob
, info
->self_size
);
4295 streamer_write_hwi (ob
, info
->self_time
);
4296 bp
= bitpack_create (ob
->main_stream
);
4297 bp_pack_value (&bp
, info
->inlinable
, 1);
4298 streamer_write_bitpack (&bp
);
4299 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4300 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4302 streamer_write_uhwi (ob
, c
->operand_num
);
4303 streamer_write_uhwi (ob
, c
->code
);
4304 stream_write_tree (ob
, c
->val
, true);
4305 bp
= bitpack_create (ob
->main_stream
);
4306 bp_pack_value (&bp
, c
->agg_contents
, 1);
4307 bp_pack_value (&bp
, c
->by_ref
, 1);
4308 streamer_write_bitpack (&bp
);
4309 if (c
->agg_contents
)
4310 streamer_write_uhwi (ob
, c
->offset
);
4312 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4313 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4315 streamer_write_uhwi (ob
, e
->size
);
4316 streamer_write_uhwi (ob
, e
->time
);
4317 write_predicate (ob
, &e
->predicate
);
4319 write_predicate (ob
, info
->loop_iterations
);
4320 write_predicate (ob
, info
->loop_stride
);
4321 write_predicate (ob
, info
->array_index
);
4322 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4323 write_inline_edge_summary (ob
, edge
);
4324 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4325 write_inline_edge_summary (ob
, edge
);
4328 streamer_write_char_stream (ob
->main_stream
, 0);
4329 produce_asm (ob
, NULL
);
4330 destroy_output_block (ob
);
4332 if (optimize
&& !flag_ipa_cp
)
4333 ipa_prop_write_jump_functions ();
4337 /* Release inline summary. */
4340 inline_free_summary (void)
4342 struct cgraph_node
*node
;
4343 if (!inline_edge_summary_vec
.exists ())
4345 FOR_EACH_DEFINED_FUNCTION (node
)
4347 reset_inline_summary (node
);
4348 if (function_insertion_hook_holder
)
4349 symtab
->remove_cgraph_insertion_hook (function_insertion_hook_holder
);
4350 function_insertion_hook_holder
= NULL
;
4351 if (node_removal_hook_holder
)
4352 symtab
->remove_cgraph_removal_hook (node_removal_hook_holder
);
4353 node_removal_hook_holder
= NULL
;
4354 if (edge_removal_hook_holder
)
4355 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4356 edge_removal_hook_holder
= NULL
;
4357 if (node_duplication_hook_holder
)
4358 symtab
->remove_cgraph_duplication_hook (node_duplication_hook_holder
);
4359 node_duplication_hook_holder
= NULL
;
4360 if (edge_duplication_hook_holder
)
4361 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4362 edge_duplication_hook_holder
= NULL
;
4363 vec_free (inline_summary_vec
);
4364 inline_edge_summary_vec
.release ();
4365 if (edge_predicate_pool
)
4366 free_alloc_pool (edge_predicate_pool
);
4367 edge_predicate_pool
= 0;