1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 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 "symbol-summary.h"
114 #include "ipa-prop.h"
115 #include "lto-streamer.h"
116 #include "data-streamer.h"
117 #include "tree-streamer.h"
118 #include "ipa-inline.h"
120 #include "tree-scalar-evolution.h"
121 #include "ipa-utils.h"
123 #include "cfgexpand.h"
125 /* Estimate runtime of function can easilly run into huge numbers with many
126 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
127 integer. For anything larger we use gcov_type. */
128 #define MAX_TIME 500000
130 /* Number of bits in integer, but we really want to be stable across different
132 #define NUM_CONDITIONS 32
134 enum predicate_conditions
136 predicate_false_condition
= 0,
137 predicate_not_inlined_condition
= 1,
138 predicate_first_dynamic_condition
= 2
141 /* Special condition code we use to represent test that operand is compile time
143 #define IS_NOT_CONSTANT ERROR_MARK
144 /* Special condition code we use to represent test that operand is not changed
145 across invocation of the function. When operand IS_NOT_CONSTANT it is always
146 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
147 of executions even when they are not compile time constants. */
148 #define CHANGED IDENTIFIER_NODE
150 /* Holders of ipa cgraph hooks: */
151 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
152 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
153 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
154 static void inline_edge_duplication_hook (struct cgraph_edge
*,
155 struct cgraph_edge
*, void *);
157 /* VECtor holding inline summaries.
158 In GGC memory because conditions might point to constant trees. */
159 function_summary
<inline_summary
*> *inline_summaries
;
160 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
162 /* Cached node/edge growths. */
163 vec
<int> node_growth_cache
;
164 vec
<edge_growth_cache_entry
> edge_growth_cache
;
166 /* Edge predicates goes here. */
167 static alloc_pool edge_predicate_pool
;
169 /* Return true predicate (tautology).
170 We represent it by empty list of clauses. */
172 static inline struct predicate
173 true_predicate (void)
181 /* Return predicate testing single condition number COND. */
183 static inline struct predicate
184 single_cond_predicate (int cond
)
187 p
.clause
[0] = 1 << cond
;
193 /* Return false predicate. First clause require false condition. */
195 static inline struct predicate
196 false_predicate (void)
198 return single_cond_predicate (predicate_false_condition
);
202 /* Return true if P is (true). */
205 true_predicate_p (struct predicate
*p
)
207 return !p
->clause
[0];
211 /* Return true if P is (false). */
214 false_predicate_p (struct predicate
*p
)
216 if (p
->clause
[0] == (1 << predicate_false_condition
))
218 gcc_checking_assert (!p
->clause
[1]
219 && p
->clause
[0] == 1 << predicate_false_condition
);
226 /* Return predicate that is set true when function is not inlined. */
228 static inline struct predicate
229 not_inlined_predicate (void)
231 return single_cond_predicate (predicate_not_inlined_condition
);
234 /* Simple description of whether a memory load or a condition refers to a load
235 from an aggregate and if so, how and where from in the aggregate.
236 Individual fields have the same meaning like fields with the same name in
239 struct agg_position_info
241 HOST_WIDE_INT offset
;
246 /* Add condition to condition list CONDS. AGGPOS describes whether the used
247 oprand is loaded from an aggregate and where in the aggregate it is. It can
248 be NULL, which means this not a load from an aggregate. */
250 static struct predicate
251 add_condition (struct inline_summary
*summary
, int operand_num
,
252 struct agg_position_info
*aggpos
,
253 enum tree_code code
, tree val
)
257 struct condition new_cond
;
258 HOST_WIDE_INT offset
;
259 bool agg_contents
, by_ref
;
263 offset
= aggpos
->offset
;
264 agg_contents
= aggpos
->agg_contents
;
265 by_ref
= aggpos
->by_ref
;
270 agg_contents
= false;
274 gcc_checking_assert (operand_num
>= 0);
275 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
277 if (c
->operand_num
== operand_num
280 && c
->agg_contents
== agg_contents
281 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
282 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
284 /* Too many conditions. Give up and return constant true. */
285 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
286 return true_predicate ();
288 new_cond
.operand_num
= operand_num
;
289 new_cond
.code
= code
;
291 new_cond
.agg_contents
= agg_contents
;
292 new_cond
.by_ref
= by_ref
;
293 new_cond
.offset
= offset
;
294 vec_safe_push (summary
->conds
, new_cond
);
295 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
299 /* Add clause CLAUSE into the predicate P. */
302 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
306 int insert_here
= -1;
313 /* False clause makes the whole predicate false. Kill the other variants. */
314 if (clause
== (1 << predicate_false_condition
))
316 p
->clause
[0] = (1 << predicate_false_condition
);
320 if (false_predicate_p (p
))
323 /* No one should be silly enough to add false into nontrivial clauses. */
324 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
326 /* Look where to insert the clause. At the same time prune out
327 clauses of P that are implied by the new clause and thus
329 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
331 p
->clause
[i2
] = p
->clause
[i
];
336 /* If p->clause[i] implies clause, there is nothing to add. */
337 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
339 /* We had nothing to add, none of clauses should've become
341 gcc_checking_assert (i
== i2
);
345 if (p
->clause
[i
] < clause
&& insert_here
< 0)
348 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
349 Otherwise the p->clause[i] has to stay. */
350 if ((p
->clause
[i
] & clause
) != clause
)
354 /* Look for clauses that are obviously true. I.e.
355 op0 == 5 || op0 != 5. */
356 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
359 if (!(clause
& (1 << c1
)))
361 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
362 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
363 and thus there is no point for looking for them. */
364 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
366 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
367 if (clause
& (1 << c2
))
370 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
372 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
373 if (cc1
->operand_num
== cc2
->operand_num
374 && cc1
->val
== cc2
->val
375 && cc2
->code
!= IS_NOT_CONSTANT
376 && cc2
->code
!= CHANGED
377 && cc1
->code
== invert_tree_comparison (cc2
->code
,
378 HONOR_NANS (cc1
->val
)))
384 /* We run out of variants. Be conservative in positive direction. */
385 if (i2
== MAX_CLAUSES
)
387 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
388 p
->clause
[i2
+ 1] = 0;
389 if (insert_here
>= 0)
390 for (; i2
> insert_here
; i2
--)
391 p
->clause
[i2
] = p
->clause
[i2
- 1];
394 p
->clause
[insert_here
] = clause
;
400 static struct predicate
401 and_predicates (conditions conditions
,
402 struct predicate
*p
, struct predicate
*p2
)
404 struct predicate out
= *p
;
407 /* Avoid busy work. */
408 if (false_predicate_p (p2
) || true_predicate_p (p
))
410 if (false_predicate_p (p
) || true_predicate_p (p2
))
413 /* See how far predicates match. */
414 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
416 gcc_checking_assert (i
< MAX_CLAUSES
);
419 /* Combine the predicates rest. */
420 for (; p2
->clause
[i
]; i
++)
422 gcc_checking_assert (i
< MAX_CLAUSES
);
423 add_clause (conditions
, &out
, p2
->clause
[i
]);
429 /* Return true if predicates are obviously equal. */
432 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
435 for (i
= 0; p
->clause
[i
]; i
++)
437 gcc_checking_assert (i
< MAX_CLAUSES
);
438 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
439 gcc_checking_assert (!p2
->clause
[i
]
440 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
441 if (p
->clause
[i
] != p2
->clause
[i
])
444 return !p2
->clause
[i
];
450 static struct predicate
451 or_predicates (conditions conditions
,
452 struct predicate
*p
, struct predicate
*p2
)
454 struct predicate out
= true_predicate ();
457 /* Avoid busy work. */
458 if (false_predicate_p (p2
) || true_predicate_p (p
))
460 if (false_predicate_p (p
) || true_predicate_p (p2
))
462 if (predicates_equal_p (p
, p2
))
465 /* OK, combine the predicates. */
466 for (i
= 0; p
->clause
[i
]; i
++)
467 for (j
= 0; p2
->clause
[j
]; j
++)
469 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
470 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
476 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
477 if predicate P is known to be false. */
480 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
484 /* True remains true. */
485 if (true_predicate_p (p
))
488 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
490 /* See if we can find clause we can disprove. */
491 for (i
= 0; p
->clause
[i
]; i
++)
493 gcc_checking_assert (i
< MAX_CLAUSES
);
494 if (!(p
->clause
[i
] & possible_truths
))
500 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
501 instruction will be recomputed per invocation of the inlined call. */
504 predicate_probability (conditions conds
,
505 struct predicate
*p
, clause_t possible_truths
,
506 vec
<inline_param_summary
> inline_param_summary
)
509 int combined_prob
= REG_BR_PROB_BASE
;
511 /* True remains true. */
512 if (true_predicate_p (p
))
513 return REG_BR_PROB_BASE
;
515 if (false_predicate_p (p
))
518 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
520 /* See if we can find clause we can disprove. */
521 for (i
= 0; p
->clause
[i
]; i
++)
523 gcc_checking_assert (i
< MAX_CLAUSES
);
524 if (!(p
->clause
[i
] & possible_truths
))
530 if (!inline_param_summary
.exists ())
531 return REG_BR_PROB_BASE
;
532 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
533 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
535 if (i2
>= predicate_first_dynamic_condition
)
538 &(*conds
)[i2
- predicate_first_dynamic_condition
];
539 if (c
->code
== CHANGED
541 (int) inline_param_summary
.length ()))
544 inline_param_summary
[c
->operand_num
].change_prob
;
545 this_prob
= MAX (this_prob
, iprob
);
548 this_prob
= REG_BR_PROB_BASE
;
551 this_prob
= REG_BR_PROB_BASE
;
553 combined_prob
= MIN (this_prob
, combined_prob
);
558 return combined_prob
;
562 /* Dump conditional COND. */
565 dump_condition (FILE *f
, conditions conditions
, int cond
)
568 if (cond
== predicate_false_condition
)
569 fprintf (f
, "false");
570 else if (cond
== predicate_not_inlined_condition
)
571 fprintf (f
, "not inlined");
574 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
575 fprintf (f
, "op%i", c
->operand_num
);
577 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
578 c
->by_ref
? "ref " : "", c
->offset
);
579 if (c
->code
== IS_NOT_CONSTANT
)
581 fprintf (f
, " not constant");
584 if (c
->code
== CHANGED
)
586 fprintf (f
, " changed");
589 fprintf (f
, " %s ", op_symbol_code (c
->code
));
590 print_generic_expr (f
, c
->val
, 1);
595 /* Dump clause CLAUSE. */
598 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
605 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
606 if (clause
& (1 << i
))
611 dump_condition (f
, conds
, i
);
617 /* Dump predicate PREDICATE. */
620 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
623 if (true_predicate_p (pred
))
624 dump_clause (f
, conds
, 0);
626 for (i
= 0; pred
->clause
[i
]; i
++)
630 dump_clause (f
, conds
, pred
->clause
[i
]);
636 /* Dump inline hints. */
638 dump_inline_hints (FILE *f
, inline_hints hints
)
642 fprintf (f
, "inline hints:");
643 if (hints
& INLINE_HINT_indirect_call
)
645 hints
&= ~INLINE_HINT_indirect_call
;
646 fprintf (f
, " indirect_call");
648 if (hints
& INLINE_HINT_loop_iterations
)
650 hints
&= ~INLINE_HINT_loop_iterations
;
651 fprintf (f
, " loop_iterations");
653 if (hints
& INLINE_HINT_loop_stride
)
655 hints
&= ~INLINE_HINT_loop_stride
;
656 fprintf (f
, " loop_stride");
658 if (hints
& INLINE_HINT_same_scc
)
660 hints
&= ~INLINE_HINT_same_scc
;
661 fprintf (f
, " same_scc");
663 if (hints
& INLINE_HINT_in_scc
)
665 hints
&= ~INLINE_HINT_in_scc
;
666 fprintf (f
, " in_scc");
668 if (hints
& INLINE_HINT_cross_module
)
670 hints
&= ~INLINE_HINT_cross_module
;
671 fprintf (f
, " cross_module");
673 if (hints
& INLINE_HINT_declared_inline
)
675 hints
&= ~INLINE_HINT_declared_inline
;
676 fprintf (f
, " declared_inline");
678 if (hints
& INLINE_HINT_array_index
)
680 hints
&= ~INLINE_HINT_array_index
;
681 fprintf (f
, " array_index");
683 if (hints
& INLINE_HINT_known_hot
)
685 hints
&= ~INLINE_HINT_known_hot
;
686 fprintf (f
, " known_hot");
692 /* Record SIZE and TIME under condition PRED into the inline summary. */
695 account_size_time (struct inline_summary
*summary
, int size
, int time
,
696 struct predicate
*pred
)
702 if (false_predicate_p (pred
))
705 /* We need to create initial empty unconitional clause, but otherwie
706 we don't need to account empty times and sizes. */
707 if (!size
&& !time
&& summary
->entry
)
710 /* Watch overflow that might result from insane profiles. */
711 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
712 time
= MAX_TIME
* INLINE_TIME_SCALE
;
713 gcc_assert (time
>= 0);
715 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
716 if (predicates_equal_p (&e
->predicate
, pred
))
725 e
= &(*summary
->entry
)[0];
726 gcc_assert (!e
->predicate
.clause
[0]);
727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
729 "\t\tReached limit on number of entries, "
730 "ignoring the predicate.");
732 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
735 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
736 ((double) size
) / INLINE_SIZE_SCALE
,
737 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
738 dump_predicate (dump_file
, summary
->conds
, pred
);
742 struct size_time_entry new_entry
;
743 new_entry
.size
= size
;
744 new_entry
.time
= time
;
745 new_entry
.predicate
= *pred
;
746 vec_safe_push (summary
->entry
, new_entry
);
752 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
753 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
757 /* Set predicate for edge E. */
760 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
762 struct inline_edge_summary
*es
= inline_edge_summary (e
);
764 /* If the edge is determined to be never executed, redirect it
765 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
766 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
768 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
770 e
->redirect_callee (cgraph_node::get_create
771 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
772 e
->inline_failed
= CIF_UNREACHABLE
;
773 es
->call_stmt_size
= 0;
774 es
->call_stmt_time
= 0;
776 callee
->remove_symbol_and_inline_clones ();
778 if (predicate
&& !true_predicate_p (predicate
))
781 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
782 *es
->predicate
= *predicate
;
787 pool_free (edge_predicate_pool
, es
->predicate
);
788 es
->predicate
= NULL
;
792 /* Set predicate for hint *P. */
795 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
797 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
800 pool_free (edge_predicate_pool
, *p
);
806 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
812 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
813 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
814 Return clause of possible truths. When INLINE_P is true, assume that we are
817 ERROR_MARK means compile time invariant. */
820 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
822 vec
<tree
> known_vals
,
823 vec
<ipa_agg_jump_function_p
>
826 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
827 struct inline_summary
*info
= inline_summaries
->get (node
);
831 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
836 /* We allow call stmt to have fewer arguments than the callee function
837 (especially for K&R style programs). So bound check here (we assume
838 known_aggs vector, if non-NULL, has the same length as
840 gcc_checking_assert (!known_aggs
.exists ()
841 || (known_vals
.length () == known_aggs
.length ()));
842 if (c
->operand_num
>= (int) known_vals
.length ())
844 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
850 struct ipa_agg_jump_function
*agg
;
852 if (c
->code
== CHANGED
854 && (known_vals
[c
->operand_num
] == error_mark_node
))
857 if (known_aggs
.exists ())
859 agg
= known_aggs
[c
->operand_num
];
860 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
867 val
= known_vals
[c
->operand_num
];
868 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
874 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
877 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
880 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
881 TYPE_SIZE (TREE_TYPE (val
)), 0))
883 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
886 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
889 if (res
&& integer_zerop (res
))
892 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
898 /* Work out what conditions might be true at invocation of E. */
901 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
902 clause_t
*clause_ptr
,
903 vec
<tree
> *known_vals_ptr
,
904 vec
<ipa_polymorphic_call_context
>
906 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
908 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
909 struct inline_summary
*info
= inline_summaries
->get (callee
);
910 vec
<tree
> known_vals
= vNULL
;
911 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
914 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
916 known_vals_ptr
->create (0);
917 if (known_contexts_ptr
)
918 known_contexts_ptr
->create (0);
920 if (ipa_node_params_sum
921 && !e
->call_stmt_cannot_inline_p
922 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
924 struct ipa_node_params
*parms_info
;
925 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
926 struct inline_edge_summary
*es
= inline_edge_summary (e
);
927 int i
, count
= ipa_get_cs_argument_count (args
);
929 if (e
->caller
->global
.inlined_to
)
930 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
932 parms_info
= IPA_NODE_REF (e
->caller
);
934 if (count
&& (info
->conds
|| known_vals_ptr
))
935 known_vals
.safe_grow_cleared (count
);
936 if (count
&& (info
->conds
|| known_aggs_ptr
))
937 known_aggs
.safe_grow_cleared (count
);
938 if (count
&& known_contexts_ptr
)
939 known_contexts_ptr
->safe_grow_cleared (count
);
941 for (i
= 0; i
< count
; i
++)
943 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
944 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
946 if (!cst
&& e
->call_stmt
947 && i
< (int)gimple_call_num_args (e
->call_stmt
))
949 cst
= gimple_call_arg (e
->call_stmt
, i
);
950 if (!is_gimple_min_invariant (cst
))
955 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
956 if (known_vals
.exists ())
959 else if (inline_p
&& !es
->param
[i
].change_prob
)
960 known_vals
[i
] = error_mark_node
;
962 if (known_contexts_ptr
)
963 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
965 /* TODO: When IPA-CP starts propagating and merging aggregate jump
966 functions, use its knowledge of the caller too, just like the
967 scalar case above. */
968 known_aggs
[i
] = &jf
->agg
;
971 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
972 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
974 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
976 if (count
&& (info
->conds
|| known_vals_ptr
))
977 known_vals
.safe_grow_cleared (count
);
978 for (i
= 0; i
< count
; i
++)
980 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
981 if (!is_gimple_min_invariant (cst
))
989 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
990 known_vals
, known_aggs
);
993 *known_vals_ptr
= known_vals
;
995 known_vals
.release ();
998 *known_aggs_ptr
= known_aggs
;
1000 known_aggs
.release ();
1004 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1007 inline_summary_alloc (void)
1009 if (!edge_removal_hook_holder
)
1010 edge_removal_hook_holder
=
1011 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1012 if (!edge_duplication_hook_holder
)
1013 edge_duplication_hook_holder
=
1014 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1016 if (!inline_summaries
)
1017 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1019 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1020 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1021 if (!edge_predicate_pool
)
1022 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1023 sizeof (struct predicate
), 10);
1026 /* We are called multiple time for given function; clear
1027 data from previous run so they are not cumulated. */
1030 reset_inline_edge_summary (struct cgraph_edge
*e
)
1032 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1034 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1036 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1038 pool_free (edge_predicate_pool
, es
->predicate
);
1039 es
->predicate
= NULL
;
1040 es
->param
.release ();
1044 /* We are called multiple time for given function; clear
1045 data from previous run so they are not cumulated. */
1048 reset_inline_summary (struct cgraph_node
*node
,
1049 inline_summary
*info
)
1051 struct cgraph_edge
*e
;
1053 info
->self_size
= info
->self_time
= 0;
1054 info
->estimated_stack_size
= 0;
1055 info
->estimated_self_stack_size
= 0;
1056 info
->stack_frame_offset
= 0;
1061 if (info
->loop_iterations
)
1063 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1064 info
->loop_iterations
= NULL
;
1066 if (info
->loop_stride
)
1068 pool_free (edge_predicate_pool
, info
->loop_stride
);
1069 info
->loop_stride
= NULL
;
1071 if (info
->array_index
)
1073 pool_free (edge_predicate_pool
, info
->array_index
);
1074 info
->array_index
= NULL
;
1076 vec_free (info
->conds
);
1077 vec_free (info
->entry
);
1078 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1079 reset_inline_edge_summary (e
);
1080 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1081 reset_inline_edge_summary (e
);
1084 /* Hook that is called by cgraph.c when a node is removed. */
1087 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1089 reset_inline_summary (node
, info
);
1092 /* Remap predicate P of former function to be predicate of duplicated function.
1093 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1094 INFO is inline summary of the duplicated node. */
1096 static struct predicate
1097 remap_predicate_after_duplication (struct predicate
*p
,
1098 clause_t possible_truths
,
1099 struct inline_summary
*info
)
1101 struct predicate new_predicate
= true_predicate ();
1103 for (j
= 0; p
->clause
[j
]; j
++)
1104 if (!(possible_truths
& p
->clause
[j
]))
1106 new_predicate
= false_predicate ();
1110 add_clause (info
->conds
, &new_predicate
,
1111 possible_truths
& p
->clause
[j
]);
1112 return new_predicate
;
1115 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1116 Additionally care about allocating new memory slot for updated predicate
1117 and set it to NULL when it becomes true or false (and thus uninteresting).
1121 remap_hint_predicate_after_duplication (struct predicate
**p
,
1122 clause_t possible_truths
,
1123 struct inline_summary
*info
)
1125 struct predicate new_predicate
;
1130 new_predicate
= remap_predicate_after_duplication (*p
,
1131 possible_truths
, info
);
1132 /* We do not want to free previous predicate; it is used by node origin. */
1134 set_hint_predicate (p
, new_predicate
);
1138 /* Hook that is called by cgraph.c when a node is duplicated. */
1140 inline_summary_t::duplicate (cgraph_node
*src
,
1143 inline_summary
*info
)
1145 inline_summary_alloc ();
1146 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1147 /* TODO: as an optimization, we may avoid copying conditions
1148 that are known to be false or true. */
1149 info
->conds
= vec_safe_copy (info
->conds
);
1151 /* When there are any replacements in the function body, see if we can figure
1152 out that something was optimized out. */
1153 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1155 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1156 /* Use SRC parm info since it may not be copied yet. */
1157 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1158 vec
<tree
> known_vals
= vNULL
;
1159 int count
= ipa_get_param_count (parms_info
);
1161 clause_t possible_truths
;
1162 struct predicate true_pred
= true_predicate ();
1164 int optimized_out_size
= 0;
1165 bool inlined_to_p
= false;
1166 struct cgraph_edge
*edge
;
1169 known_vals
.safe_grow_cleared (count
);
1170 for (i
= 0; i
< count
; i
++)
1172 struct ipa_replace_map
*r
;
1174 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1176 if (((!r
->old_tree
&& r
->parm_num
== i
)
1177 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1178 && r
->replace_p
&& !r
->ref_p
)
1180 known_vals
[i
] = r
->new_tree
;
1185 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1188 known_vals
.release ();
1190 account_size_time (info
, 0, 0, &true_pred
);
1192 /* Remap size_time vectors.
1193 Simplify the predicate by prunning out alternatives that are known
1195 TODO: as on optimization, we can also eliminate conditions known
1197 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1199 struct predicate new_predicate
;
1200 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1203 if (false_predicate_p (&new_predicate
))
1204 optimized_out_size
+= e
->size
;
1206 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1209 /* Remap edge predicates with the same simplification as above.
1210 Also copy constantness arrays. */
1211 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1213 struct predicate new_predicate
;
1214 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1216 if (!edge
->inline_failed
)
1217 inlined_to_p
= true;
1220 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1223 if (false_predicate_p (&new_predicate
)
1224 && !false_predicate_p (es
->predicate
))
1226 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1227 edge
->frequency
= 0;
1229 edge_set_predicate (edge
, &new_predicate
);
1232 /* Remap indirect edge predicates with the same simplificaiton as above.
1233 Also copy constantness arrays. */
1234 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1236 struct predicate new_predicate
;
1237 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1239 gcc_checking_assert (edge
->inline_failed
);
1242 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1245 if (false_predicate_p (&new_predicate
)
1246 && !false_predicate_p (es
->predicate
))
1248 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1249 edge
->frequency
= 0;
1251 edge_set_predicate (edge
, &new_predicate
);
1253 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1254 possible_truths
, info
);
1255 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1256 possible_truths
, info
);
1257 remap_hint_predicate_after_duplication (&info
->array_index
,
1258 possible_truths
, info
);
1260 /* If inliner or someone after inliner will ever start producing
1261 non-trivial clones, we will get trouble with lack of information
1262 about updating self sizes, because size vectors already contains
1263 sizes of the calees. */
1264 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1268 info
->entry
= vec_safe_copy (info
->entry
);
1269 if (info
->loop_iterations
)
1271 predicate p
= *info
->loop_iterations
;
1272 info
->loop_iterations
= NULL
;
1273 set_hint_predicate (&info
->loop_iterations
, p
);
1275 if (info
->loop_stride
)
1277 predicate p
= *info
->loop_stride
;
1278 info
->loop_stride
= NULL
;
1279 set_hint_predicate (&info
->loop_stride
, p
);
1281 if (info
->array_index
)
1283 predicate p
= *info
->array_index
;
1284 info
->array_index
= NULL
;
1285 set_hint_predicate (&info
->array_index
, p
);
1288 inline_update_overall_summary (dst
);
1292 /* Hook that is called by cgraph.c when a node is duplicated. */
1295 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1296 struct cgraph_edge
*dst
,
1297 ATTRIBUTE_UNUSED
void *data
)
1299 struct inline_edge_summary
*info
;
1300 struct inline_edge_summary
*srcinfo
;
1301 inline_summary_alloc ();
1302 info
= inline_edge_summary (dst
);
1303 srcinfo
= inline_edge_summary (src
);
1304 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1305 info
->predicate
= NULL
;
1306 edge_set_predicate (dst
, srcinfo
->predicate
);
1307 info
->param
= srcinfo
->param
.copy ();
1311 /* Keep edge cache consistent across edge removal. */
1314 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1315 void *data ATTRIBUTE_UNUSED
)
1317 if (edge_growth_cache
.exists ())
1318 reset_edge_growth_cache (edge
);
1319 reset_inline_edge_summary (edge
);
1323 /* Initialize growth caches. */
1326 initialize_growth_caches (void)
1328 if (symtab
->edges_max_uid
)
1329 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1330 if (symtab
->cgraph_max_uid
)
1331 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1335 /* Free growth caches. */
1338 free_growth_caches (void)
1340 edge_growth_cache
.release ();
1341 node_growth_cache
.release ();
1345 /* Dump edge summaries associated to NODE and recursively to all clones.
1346 Indent by INDENT. */
1349 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1350 struct inline_summary
*info
)
1352 struct cgraph_edge
*edge
;
1353 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1355 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1356 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1360 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1361 " time: %2i callee size:%2i stack:%2i",
1362 indent
, "", callee
->name (), callee
->order
,
1363 !edge
->inline_failed
1364 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1365 indent
, "", es
->loop_depth
, edge
->frequency
,
1366 es
->call_stmt_size
, es
->call_stmt_time
,
1367 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1368 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1372 fprintf (f
, " predicate: ");
1373 dump_predicate (f
, info
->conds
, es
->predicate
);
1377 if (es
->param
.exists ())
1378 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1380 int prob
= es
->param
[i
].change_prob
;
1383 fprintf (f
, "%*s op%i is compile time invariant\n",
1385 else if (prob
!= REG_BR_PROB_BASE
)
1386 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1387 prob
* 100.0 / REG_BR_PROB_BASE
);
1389 if (!edge
->inline_failed
)
1391 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1392 " callee size %i\n",
1394 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1395 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1396 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1397 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1400 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1402 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1403 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1407 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1410 fprintf (f
, "predicate: ");
1411 dump_predicate (f
, info
->conds
, es
->predicate
);
1420 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1422 if (node
->definition
)
1424 struct inline_summary
*s
= inline_summaries
->get (node
);
1427 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1429 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1430 fprintf (f
, " always_inline");
1432 fprintf (f
, " inlinable");
1433 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1434 fprintf (f
, " global time: %i\n", s
->time
);
1435 fprintf (f
, " self size: %i\n", s
->self_size
);
1436 fprintf (f
, " global size: %i\n", s
->size
);
1437 fprintf (f
, " min size: %i\n", s
->min_size
);
1438 fprintf (f
, " self stack: %i\n",
1439 (int) s
->estimated_self_stack_size
);
1440 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1442 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1444 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1445 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1447 fprintf (f
, " size:%f, time:%f, predicate:",
1448 (double) e
->size
/ INLINE_SIZE_SCALE
,
1449 (double) e
->time
/ INLINE_TIME_SCALE
);
1450 dump_predicate (f
, s
->conds
, &e
->predicate
);
1452 if (s
->loop_iterations
)
1454 fprintf (f
, " loop iterations:");
1455 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1459 fprintf (f
, " loop stride:");
1460 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1464 fprintf (f
, " array index:");
1465 dump_predicate (f
, s
->conds
, s
->array_index
);
1467 fprintf (f
, " calls:\n");
1468 dump_inline_edge_summary (f
, 4, node
, s
);
1474 debug_inline_summary (struct cgraph_node
*node
)
1476 dump_inline_summary (stderr
, node
);
1480 dump_inline_summaries (FILE *f
)
1482 struct cgraph_node
*node
;
1484 FOR_EACH_DEFINED_FUNCTION (node
)
1485 if (!node
->global
.inlined_to
)
1486 dump_inline_summary (f
, node
);
1489 /* Give initial reasons why inlining would fail on EDGE. This gets either
1490 nullified or usually overwritten by more precise reasons later. */
1493 initialize_inline_failed (struct cgraph_edge
*e
)
1495 struct cgraph_node
*callee
= e
->callee
;
1497 if (e
->indirect_unknown_callee
)
1498 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1499 else if (!callee
->definition
)
1500 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1501 else if (callee
->local
.redefined_extern_inline
)
1502 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1503 else if (e
->call_stmt_cannot_inline_p
)
1504 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1505 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1506 /* We can't inline if the function is spawing a function. */
1507 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1509 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1512 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1513 boolean variable pointed to by DATA. */
1516 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1519 bool *b
= (bool *) data
;
1524 /* If OP refers to value of function parameter, return the corresponding
1528 unmodified_parm_1 (gimple stmt
, tree op
)
1530 /* SSA_NAME referring to parm default def? */
1531 if (TREE_CODE (op
) == SSA_NAME
1532 && SSA_NAME_IS_DEFAULT_DEF (op
)
1533 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1534 return SSA_NAME_VAR (op
);
1535 /* Non-SSA parm reference? */
1536 if (TREE_CODE (op
) == PARM_DECL
)
1538 bool modified
= false;
1541 ao_ref_init (&refd
, op
);
1542 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1550 /* If OP refers to value of function parameter, return the corresponding
1551 parameter. Also traverse chains of SSA register assignments. */
1554 unmodified_parm (gimple stmt
, tree op
)
1556 tree res
= unmodified_parm_1 (stmt
, op
);
1560 if (TREE_CODE (op
) == SSA_NAME
1561 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1562 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1563 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1564 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1568 /* If OP refers to a value of a function parameter or value loaded from an
1569 aggregate passed to a parameter (either by value or reference), return TRUE
1570 and store the number of the parameter to *INDEX_P and information whether
1571 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1572 the function parameters, STMT is the statement in which OP is used or
1576 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1577 gimple stmt
, tree op
, int *index_p
,
1578 struct agg_position_info
*aggpos
)
1580 tree res
= unmodified_parm_1 (stmt
, op
);
1582 gcc_checking_assert (aggpos
);
1585 *index_p
= ipa_get_param_decl_index (info
, res
);
1588 aggpos
->agg_contents
= false;
1589 aggpos
->by_ref
= false;
1593 if (TREE_CODE (op
) == SSA_NAME
)
1595 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1596 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1598 stmt
= SSA_NAME_DEF_STMT (op
);
1599 op
= gimple_assign_rhs1 (stmt
);
1600 if (!REFERENCE_CLASS_P (op
))
1601 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1605 aggpos
->agg_contents
= true;
1606 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1610 /* See if statement might disappear after inlining.
1611 0 - means not eliminated
1612 1 - half of statements goes away
1613 2 - for sure it is eliminated.
1614 We are not terribly sophisticated, basically looking for simple abstraction
1615 penalty wrappers. */
1618 eliminated_by_inlining_prob (gimple stmt
)
1620 enum gimple_code code
= gimple_code (stmt
);
1621 enum tree_code rhs_code
;
1631 if (gimple_num_ops (stmt
) != 2)
1634 rhs_code
= gimple_assign_rhs_code (stmt
);
1636 /* Casts of parameters, loads from parameters passed by reference
1637 and stores to return value or parameters are often free after
1638 inlining dua to SRA and further combining.
1639 Assume that half of statements goes away. */
1640 if (CONVERT_EXPR_CODE_P (rhs_code
)
1641 || rhs_code
== VIEW_CONVERT_EXPR
1642 || rhs_code
== ADDR_EXPR
1643 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1645 tree rhs
= gimple_assign_rhs1 (stmt
);
1646 tree lhs
= gimple_assign_lhs (stmt
);
1647 tree inner_rhs
= get_base_address (rhs
);
1648 tree inner_lhs
= get_base_address (lhs
);
1649 bool rhs_free
= false;
1650 bool lhs_free
= false;
1657 /* Reads of parameter are expected to be free. */
1658 if (unmodified_parm (stmt
, inner_rhs
))
1660 /* Match expressions of form &this->field. Those will most likely
1661 combine with something upstream after inlining. */
1662 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1664 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1665 if (TREE_CODE (op
) == PARM_DECL
)
1667 else if (TREE_CODE (op
) == MEM_REF
1668 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1672 /* When parameter is not SSA register because its address is taken
1673 and it is just copied into one, the statement will be completely
1674 free after inlining (we will copy propagate backward). */
1675 if (rhs_free
&& is_gimple_reg (lhs
))
1678 /* Reads of parameters passed by reference
1679 expected to be free (i.e. optimized out after inlining). */
1680 if (TREE_CODE (inner_rhs
) == MEM_REF
1681 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1684 /* Copying parameter passed by reference into gimple register is
1685 probably also going to copy propagate, but we can't be quite
1687 if (rhs_free
&& is_gimple_reg (lhs
))
1690 /* Writes to parameters, parameters passed by value and return value
1691 (either dirrectly or passed via invisible reference) are free.
1693 TODO: We ought to handle testcase like
1694 struct a {int a,b;};
1696 retrurnsturct (void)
1702 This translate into:
1717 For that we either need to copy ipa-split logic detecting writes
1719 if (TREE_CODE (inner_lhs
) == PARM_DECL
1720 || TREE_CODE (inner_lhs
) == RESULT_DECL
1721 || (TREE_CODE (inner_lhs
) == MEM_REF
1722 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1723 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1724 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1725 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1727 0))) == RESULT_DECL
))))
1730 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1732 if (lhs_free
&& rhs_free
)
1742 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1743 predicates to the CFG edges. */
1746 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1747 struct inline_summary
*summary
,
1753 struct agg_position_info aggpos
;
1754 enum tree_code code
, inverted_code
;
1760 last
= last_stmt (bb
);
1761 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1763 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1765 op
= gimple_cond_lhs (last
);
1766 /* TODO: handle conditionals like
1769 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1771 code
= gimple_cond_code (last
);
1772 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1774 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1776 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1777 ? code
: inverted_code
);
1778 /* invert_tree_comparison will return ERROR_MARK on FP
1779 comparsions that are not EQ/NE instead of returning proper
1780 unordered one. Be sure it is not confused with NON_CONSTANT. */
1781 if (this_code
!= ERROR_MARK
)
1783 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1785 gimple_cond_rhs (last
));
1786 e
->aux
= pool_alloc (edge_predicate_pool
);
1787 *(struct predicate
*) e
->aux
= p
;
1792 if (TREE_CODE (op
) != SSA_NAME
)
1795 if (builtin_constant_p (op))
1799 Here we can predicate nonconstant_code. We can't
1800 really handle constant_code since we have no predicate
1801 for this and also the constant code is not known to be
1802 optimized away when inliner doen't see operand is constant.
1803 Other optimizers might think otherwise. */
1804 if (gimple_cond_code (last
) != NE_EXPR
1805 || !integer_zerop (gimple_cond_rhs (last
)))
1807 set_stmt
= SSA_NAME_DEF_STMT (op
);
1808 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1809 || gimple_call_num_args (set_stmt
) != 1)
1811 op2
= gimple_call_arg (set_stmt
, 0);
1812 if (!unmodified_parm_or_parm_agg_item
1813 (info
, set_stmt
, op2
, &index
, &aggpos
))
1815 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1817 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1818 IS_NOT_CONSTANT
, NULL_TREE
);
1819 e
->aux
= pool_alloc (edge_predicate_pool
);
1820 *(struct predicate
*) e
->aux
= p
;
1825 /* If BB ends by a switch we can turn into predicates, attach corresponding
1826 predicates to the CFG edges. */
1829 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1830 struct inline_summary
*summary
,
1836 struct agg_position_info aggpos
;
1842 lastg
= last_stmt (bb
);
1843 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1845 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1846 op
= gimple_switch_index (last
);
1847 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1850 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1852 e
->aux
= pool_alloc (edge_predicate_pool
);
1853 *(struct predicate
*) e
->aux
= false_predicate ();
1855 n
= gimple_switch_num_labels (last
);
1856 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1858 tree cl
= gimple_switch_label (last
, case_idx
);
1862 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1863 min
= CASE_LOW (cl
);
1864 max
= CASE_HIGH (cl
);
1866 /* For default we might want to construct predicate that none
1867 of cases is met, but it is bit hard to do not having negations
1868 of conditionals handy. */
1870 p
= true_predicate ();
1872 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1875 struct predicate p1
, p2
;
1876 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1877 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1878 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1880 *(struct predicate
*) e
->aux
1881 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1886 /* For each BB in NODE attach to its AUX pointer predicate under
1887 which it is executable. */
1890 compute_bb_predicates (struct cgraph_node
*node
,
1891 struct ipa_node_params
*parms_info
,
1892 struct inline_summary
*summary
)
1894 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1898 FOR_EACH_BB_FN (bb
, my_function
)
1900 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1901 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1904 /* Entry block is always executable. */
1905 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1906 = pool_alloc (edge_predicate_pool
);
1907 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1908 = true_predicate ();
1910 /* A simple dataflow propagation of predicates forward in the CFG.
1911 TODO: work in reverse postorder. */
1915 FOR_EACH_BB_FN (bb
, my_function
)
1917 struct predicate p
= false_predicate ();
1920 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1924 struct predicate this_bb_predicate
1925 = *(struct predicate
*) e
->src
->aux
;
1928 = and_predicates (summary
->conds
, &this_bb_predicate
,
1929 (struct predicate
*) e
->aux
);
1930 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1931 if (true_predicate_p (&p
))
1935 if (false_predicate_p (&p
))
1936 gcc_assert (!bb
->aux
);
1942 bb
->aux
= pool_alloc (edge_predicate_pool
);
1943 *((struct predicate
*) bb
->aux
) = p
;
1945 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1947 /* This OR operation is needed to ensure monotonous data flow
1948 in the case we hit the limit on number of clauses and the
1949 and/or operations above give approximate answers. */
1950 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1951 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1954 *((struct predicate
*) bb
->aux
) = p
;
1963 /* We keep info about constantness of SSA names. */
1965 typedef struct predicate predicate_t
;
1966 /* Return predicate specifying when the STMT might have result that is not
1967 a compile time constant. */
1969 static struct predicate
1970 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1971 struct inline_summary
*summary
,
1973 vec
<predicate_t
> nonconstant_names
)
1978 while (UNARY_CLASS_P (expr
))
1979 expr
= TREE_OPERAND (expr
, 0);
1981 parm
= unmodified_parm (NULL
, expr
);
1982 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1983 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1984 if (is_gimple_min_invariant (expr
))
1985 return false_predicate ();
1986 if (TREE_CODE (expr
) == SSA_NAME
)
1987 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1988 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1990 struct predicate p1
= will_be_nonconstant_expr_predicate
1991 (info
, summary
, TREE_OPERAND (expr
, 0),
1993 struct predicate p2
;
1994 if (true_predicate_p (&p1
))
1996 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1997 TREE_OPERAND (expr
, 1),
1999 return or_predicates (summary
->conds
, &p1
, &p2
);
2001 else if (TREE_CODE (expr
) == COND_EXPR
)
2003 struct predicate p1
= will_be_nonconstant_expr_predicate
2004 (info
, summary
, TREE_OPERAND (expr
, 0),
2006 struct predicate p2
;
2007 if (true_predicate_p (&p1
))
2009 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2010 TREE_OPERAND (expr
, 1),
2012 if (true_predicate_p (&p2
))
2014 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2015 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2016 TREE_OPERAND (expr
, 2),
2018 return or_predicates (summary
->conds
, &p1
, &p2
);
2025 return false_predicate ();
2029 /* Return predicate specifying when the STMT might have result that is not
2030 a compile time constant. */
2032 static struct predicate
2033 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2034 struct inline_summary
*summary
,
2036 vec
<predicate_t
> nonconstant_names
)
2038 struct predicate p
= true_predicate ();
2041 struct predicate op_non_const
;
2044 struct agg_position_info aggpos
;
2046 /* What statments might be optimized away
2047 when their arguments are constant. */
2048 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2049 && gimple_code (stmt
) != GIMPLE_COND
2050 && gimple_code (stmt
) != GIMPLE_SWITCH
2051 && (gimple_code (stmt
) != GIMPLE_CALL
2052 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2055 /* Stores will stay anyway. */
2056 if (gimple_store_p (stmt
))
2059 is_load
= gimple_assign_load_p (stmt
);
2061 /* Loads can be optimized when the value is known. */
2065 gcc_assert (gimple_assign_single_p (stmt
));
2066 op
= gimple_assign_rhs1 (stmt
);
2067 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2074 /* See if we understand all operands before we start
2075 adding conditionals. */
2076 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2078 tree parm
= unmodified_parm (stmt
, use
);
2079 /* For arguments we can build a condition. */
2080 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2082 if (TREE_CODE (use
) != SSA_NAME
)
2084 /* If we know when operand is constant,
2085 we still can say something useful. */
2086 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2093 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2095 op_non_const
= false_predicate ();
2096 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2098 tree parm
= unmodified_parm (stmt
, use
);
2101 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2103 if (index
!= base_index
)
2104 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2109 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2110 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2112 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2113 && gimple_op (stmt
, 0)
2114 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2115 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2117 return op_non_const
;
2120 struct record_modified_bb_info
2126 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2127 set except for info->stmt. */
2130 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2132 struct record_modified_bb_info
*info
=
2133 (struct record_modified_bb_info
*) data
;
2134 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2136 bitmap_set_bit (info
->bb_set
,
2137 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2138 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2139 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2143 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2144 will change since last invocation of STMT.
2146 Value 0 is reserved for compile time invariants.
2147 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2148 ought to be REG_BR_PROB_BASE / estimated_iters. */
2151 param_change_prob (gimple stmt
, int i
)
2153 tree op
= gimple_call_arg (stmt
, i
);
2154 basic_block bb
= gimple_bb (stmt
);
2157 /* Global invariants neve change. */
2158 if (is_gimple_min_invariant (op
))
2160 /* We would have to do non-trivial analysis to really work out what
2161 is the probability of value to change (i.e. when init statement
2162 is in a sibling loop of the call).
2164 We do an conservative estimate: when call is executed N times more often
2165 than the statement defining value, we take the frequency 1/N. */
2166 if (TREE_CODE (op
) == SSA_NAME
)
2171 return REG_BR_PROB_BASE
;
2173 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2174 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2176 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2180 if (init_freq
< bb
->frequency
)
2181 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2183 return REG_BR_PROB_BASE
;
2186 base
= get_base_address (op
);
2191 struct record_modified_bb_info info
;
2194 tree init
= ctor_for_folding (base
);
2196 if (init
!= error_mark_node
)
2199 return REG_BR_PROB_BASE
;
2200 ao_ref_init (&refd
, op
);
2202 info
.bb_set
= BITMAP_ALLOC (NULL
);
2203 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2205 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2207 BITMAP_FREE (info
.bb_set
);
2208 return REG_BR_PROB_BASE
;
2211 /* Assume that every memory is initialized at entry.
2212 TODO: Can we easilly determine if value is always defined
2213 and thus we may skip entry block? */
2214 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2215 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2219 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2220 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2222 BITMAP_FREE (info
.bb_set
);
2223 if (max
< bb
->frequency
)
2224 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2226 return REG_BR_PROB_BASE
;
2228 return REG_BR_PROB_BASE
;
2231 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2232 sub-graph and if the predicate the condition depends on is known. If so,
2233 return true and store the pointer the predicate in *P. */
2236 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2237 inline_summary
*summary
, basic_block bb
,
2238 struct predicate
*p
,
2239 vec
<predicate_t
> nonconstant_names
)
2243 basic_block first_bb
= NULL
;
2246 if (single_pred_p (bb
))
2248 *p
= false_predicate ();
2252 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2254 if (single_succ_p (e
->src
))
2256 if (!single_pred_p (e
->src
))
2259 first_bb
= single_pred (e
->src
);
2260 else if (single_pred (e
->src
) != first_bb
)
2267 else if (e
->src
!= first_bb
)
2275 stmt
= last_stmt (first_bb
);
2277 || gimple_code (stmt
) != GIMPLE_COND
2278 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2281 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2282 gimple_cond_lhs (stmt
),
2284 if (true_predicate_p (p
))
2290 /* Given a PHI statement in a function described by inline properties SUMMARY
2291 and *P being the predicate describing whether the selected PHI argument is
2292 known, store a predicate for the result of the PHI statement into
2293 NONCONSTANT_NAMES, if possible. */
2296 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2297 struct predicate
*p
,
2298 vec
<predicate_t
> nonconstant_names
)
2302 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2304 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2305 if (!is_gimple_min_invariant (arg
))
2307 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2308 *p
= or_predicates (summary
->conds
, p
,
2309 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2310 if (true_predicate_p (p
))
2315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2317 fprintf (dump_file
, "\t\tphi predicate: ");
2318 dump_predicate (dump_file
, summary
->conds
, p
);
2320 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2323 /* Return predicate specifying when array index in access OP becomes non-constant. */
2325 static struct predicate
2326 array_index_predicate (inline_summary
*info
,
2327 vec
< predicate_t
> nonconstant_names
, tree op
)
2329 struct predicate p
= false_predicate ();
2330 while (handled_component_p (op
))
2332 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2334 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2335 p
= or_predicates (info
->conds
, &p
,
2336 &nonconstant_names
[SSA_NAME_VERSION
2337 (TREE_OPERAND (op
, 1))]);
2339 op
= TREE_OPERAND (op
, 0);
2344 /* For a typical usage of __builtin_expect (a<b, 1), we
2345 may introduce an extra relation stmt:
2346 With the builtin, we have
2349 t3 = __builtin_expect (t2, 1);
2352 Without the builtin, we have
2355 This affects the size/time estimation and may have
2356 an impact on the earlier inlining.
2357 Here find this pattern and fix it up later. */
2360 find_foldable_builtin_expect (basic_block bb
)
2362 gimple_stmt_iterator bsi
;
2364 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2366 gimple stmt
= gsi_stmt (bsi
);
2367 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2368 || (is_gimple_call (stmt
)
2369 && gimple_call_internal_p (stmt
)
2370 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2372 tree var
= gimple_call_lhs (stmt
);
2373 tree arg
= gimple_call_arg (stmt
, 0);
2374 use_operand_p use_p
;
2381 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2383 while (TREE_CODE (arg
) == SSA_NAME
)
2385 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2386 if (!is_gimple_assign (stmt_tmp
))
2388 switch (gimple_assign_rhs_code (stmt_tmp
))
2407 arg
= gimple_assign_rhs1 (stmt_tmp
);
2410 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2411 && gimple_code (use_stmt
) == GIMPLE_COND
)
2418 /* Return true when the basic blocks contains only clobbers followed by RESX.
2419 Such BBs are kept around to make removal of dead stores possible with
2420 presence of EH and will be optimized out by optimize_clobbers later in the
2423 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2424 that can be clobber only, too.. When it is false, the RESX is not necessary
2425 on the end of basic block. */
2428 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2430 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2436 if (gsi_end_p (gsi
))
2438 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2442 else if (!single_succ_p (bb
))
2445 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2447 gimple stmt
= gsi_stmt (gsi
);
2448 if (is_gimple_debug (stmt
))
2450 if (gimple_clobber_p (stmt
))
2452 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2457 /* See if all predecestors are either throws or clobber only BBs. */
2458 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2459 if (!(e
->flags
& EDGE_EH
)
2460 && !clobber_only_eh_bb_p (e
->src
, false))
2466 /* Compute function body size parameters for NODE.
2467 When EARLY is true, we compute only simple summaries without
2468 non-trivial predicates to drive the early inliner. */
2471 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2474 /* Estimate static overhead for function prologue/epilogue and alignment. */
2476 /* Benefits are scaled by probability of elimination that is in range
2479 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2481 struct inline_summary
*info
= inline_summaries
->get (node
);
2482 struct predicate bb_predicate
;
2483 struct ipa_node_params
*parms_info
= NULL
;
2484 vec
<predicate_t
> nonconstant_names
= vNULL
;
2487 predicate array_index
= true_predicate ();
2488 gimple fix_builtin_expect_stmt
;
2493 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2494 so we can produce proper inline hints.
2496 When optimizing and analyzing for early inliner, initialize node params
2497 so we can produce correct BB predicates. */
2499 if (opt_for_fn (node
->decl
, optimize
))
2501 calculate_dominance_info (CDI_DOMINATORS
);
2503 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2506 ipa_check_create_node_params ();
2507 ipa_initialize_node_params (node
);
2510 if (ipa_node_params_sum
)
2512 parms_info
= IPA_NODE_REF (node
);
2513 nonconstant_names
.safe_grow_cleared
2514 (SSANAMES (my_function
)->length ());
2519 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2522 /* When we run into maximal number of entries, we assign everything to the
2523 constant truth case. Be sure to have it in list. */
2524 bb_predicate
= true_predicate ();
2525 account_size_time (info
, 0, 0, &bb_predicate
);
2527 bb_predicate
= not_inlined_predicate ();
2528 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2530 gcc_assert (my_function
&& my_function
->cfg
);
2532 compute_bb_predicates (node
, parms_info
, info
);
2533 gcc_assert (cfun
== my_function
);
2534 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2535 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2536 for (n
= 0; n
< nblocks
; n
++)
2538 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2539 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2540 if (clobber_only_eh_bb_p (bb
))
2542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2543 fprintf (dump_file
, "\n Ignoring BB %i;"
2544 " it will be optimized away by cleanup_clobbers\n",
2549 /* TODO: Obviously predicates can be propagated down across CFG. */
2553 bb_predicate
= *(struct predicate
*) bb
->aux
;
2555 bb_predicate
= false_predicate ();
2558 bb_predicate
= true_predicate ();
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2562 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2563 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2566 if (parms_info
&& nonconstant_names
.exists ())
2568 struct predicate phi_predicate
;
2569 bool first_phi
= true;
2571 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2575 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2582 fprintf (dump_file
, " ");
2583 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2585 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2590 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2592 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2595 gimple stmt
= gsi_stmt (bsi
);
2596 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2597 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2599 struct predicate will_be_nonconstant
;
2601 /* This relation stmt should be folded after we remove
2602 buildin_expect call. Adjust the cost here. */
2603 if (stmt
== fix_builtin_expect_stmt
)
2609 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2611 fprintf (dump_file
, " ");
2612 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2613 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2614 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2618 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2620 struct predicate this_array_index
;
2622 array_index_predicate (info
, nonconstant_names
,
2623 gimple_assign_rhs1 (stmt
));
2624 if (!false_predicate_p (&this_array_index
))
2626 and_predicates (info
->conds
, &array_index
,
2629 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2631 struct predicate this_array_index
;
2633 array_index_predicate (info
, nonconstant_names
,
2634 gimple_get_lhs (stmt
));
2635 if (!false_predicate_p (&this_array_index
))
2637 and_predicates (info
->conds
, &array_index
,
2642 if (is_gimple_call (stmt
)
2643 && !gimple_call_internal_p (stmt
))
2645 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2646 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2648 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2649 resolved as constant. We however don't want to optimize
2650 out the cgraph edges. */
2651 if (nonconstant_names
.exists ()
2652 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2653 && gimple_call_lhs (stmt
)
2654 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2656 struct predicate false_p
= false_predicate ();
2657 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2660 if (ipa_node_params_sum
)
2662 int count
= gimple_call_num_args (stmt
);
2666 es
->param
.safe_grow_cleared (count
);
2667 for (i
= 0; i
< count
; i
++)
2669 int prob
= param_change_prob (stmt
, i
);
2670 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2671 es
->param
[i
].change_prob
= prob
;
2675 es
->call_stmt_size
= this_size
;
2676 es
->call_stmt_time
= this_time
;
2677 es
->loop_depth
= bb_loop_depth (bb
);
2678 edge_set_predicate (edge
, &bb_predicate
);
2681 /* TODO: When conditional jump or swithc is known to be constant, but
2682 we did not translate it into the predicates, we really can account
2683 just maximum of the possible paths. */
2686 = will_be_nonconstant_predicate (parms_info
, info
,
2687 stmt
, nonconstant_names
);
2688 if (this_time
|| this_size
)
2694 prob
= eliminated_by_inlining_prob (stmt
);
2695 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2697 "\t\t50%% will be eliminated by inlining\n");
2698 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2699 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2702 p
= and_predicates (info
->conds
, &bb_predicate
,
2703 &will_be_nonconstant
);
2705 p
= true_predicate ();
2707 if (!false_predicate_p (&p
)
2708 || (is_gimple_call (stmt
)
2709 && !false_predicate_p (&bb_predicate
)))
2713 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2714 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2717 /* We account everything but the calls. Calls have their own
2718 size/time info attached to cgraph edges. This is necessary
2719 in order to make the cost disappear after inlining. */
2720 if (!is_gimple_call (stmt
))
2724 struct predicate ip
= not_inlined_predicate ();
2725 ip
= and_predicates (info
->conds
, &ip
, &p
);
2726 account_size_time (info
, this_size
* prob
,
2727 this_time
* prob
, &ip
);
2730 account_size_time (info
, this_size
* (2 - prob
),
2731 this_time
* (2 - prob
), &p
);
2734 gcc_assert (time
>= 0);
2735 gcc_assert (size
>= 0);
2739 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2740 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2741 if (time
> MAX_TIME
)
2745 if (nonconstant_names
.exists () && !early
)
2748 predicate loop_iterations
= true_predicate ();
2749 predicate loop_stride
= true_predicate ();
2751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2752 flow_loops_dump (dump_file
, NULL
, 0);
2754 FOR_EACH_LOOP (loop
, 0)
2759 struct tree_niter_desc niter_desc
;
2760 basic_block
*body
= get_loop_body (loop
);
2761 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2763 exits
= get_loop_exit_edges (loop
);
2764 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2765 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2766 && !is_gimple_min_invariant (niter_desc
.niter
))
2768 predicate will_be_nonconstant
2769 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2772 if (!true_predicate_p (&will_be_nonconstant
))
2773 will_be_nonconstant
= and_predicates (info
->conds
,
2775 &will_be_nonconstant
);
2776 if (!true_predicate_p (&will_be_nonconstant
)
2777 && !false_predicate_p (&will_be_nonconstant
))
2778 /* This is slightly inprecise. We may want to represent each
2779 loop with independent predicate. */
2781 and_predicates (info
->conds
, &loop_iterations
,
2782 &will_be_nonconstant
);
2786 for (i
= 0; i
< loop
->num_nodes
; i
++)
2788 gimple_stmt_iterator gsi
;
2789 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2790 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2793 gimple stmt
= gsi_stmt (gsi
);
2798 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2800 predicate will_be_nonconstant
;
2803 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2804 || is_gimple_min_invariant (iv
.step
))
2807 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2810 if (!true_predicate_p (&will_be_nonconstant
))
2812 = and_predicates (info
->conds
,
2814 &will_be_nonconstant
);
2815 if (!true_predicate_p (&will_be_nonconstant
)
2816 && !false_predicate_p (&will_be_nonconstant
))
2817 /* This is slightly inprecise. We may want to represent
2818 each loop with independent predicate. */
2820 and_predicates (info
->conds
, &loop_stride
,
2821 &will_be_nonconstant
);
2827 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2829 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2832 FOR_ALL_BB_FN (bb
, my_function
)
2838 pool_free (edge_predicate_pool
, bb
->aux
);
2840 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2843 pool_free (edge_predicate_pool
, e
->aux
);
2847 inline_summaries
->get (node
)->self_time
= time
;
2848 inline_summaries
->get (node
)->self_size
= size
;
2849 nonconstant_names
.release ();
2850 if (opt_for_fn (node
->decl
, optimize
))
2853 loop_optimizer_finalize ();
2854 else if (!ipa_edge_args_vector
)
2855 ipa_free_all_node_params ();
2856 free_dominance_info (CDI_DOMINATORS
);
2860 fprintf (dump_file
, "\n");
2861 dump_inline_summary (dump_file
, node
);
2866 /* Compute parameters of functions used by inliner.
2867 EARLY is true when we compute parameters for the early inliner */
2870 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2872 HOST_WIDE_INT self_stack_size
;
2873 struct cgraph_edge
*e
;
2874 struct inline_summary
*info
;
2876 gcc_assert (!node
->global
.inlined_to
);
2878 inline_summary_alloc ();
2880 info
= inline_summaries
->get (node
);
2881 reset_inline_summary (node
, info
);
2883 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2884 Once this happen, we will need to more curefully predict call
2886 if (node
->thunk
.thunk_p
)
2888 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2889 struct predicate t
= true_predicate ();
2891 info
->inlinable
= 0;
2892 node
->callees
->call_stmt_cannot_inline_p
= true;
2893 node
->local
.can_change_signature
= false;
2894 es
->call_stmt_time
= 1;
2895 es
->call_stmt_size
= 1;
2896 account_size_time (info
, 0, 0, &t
);
2900 /* Even is_gimple_min_invariant rely on current_function_decl. */
2901 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2903 /* Estimate the stack size for the function if we're optimizing. */
2904 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2905 info
->estimated_self_stack_size
= self_stack_size
;
2906 info
->estimated_stack_size
= self_stack_size
;
2907 info
->stack_frame_offset
= 0;
2909 /* Can this function be inlined at all? */
2910 if (!opt_for_fn (node
->decl
, optimize
)
2911 && !lookup_attribute ("always_inline",
2912 DECL_ATTRIBUTES (node
->decl
)))
2913 info
->inlinable
= false;
2915 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2917 /* Type attributes can use parameter indices to describe them. */
2918 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2919 node
->local
.can_change_signature
= false;
2922 /* Otherwise, inlinable functions always can change signature. */
2923 if (info
->inlinable
)
2924 node
->local
.can_change_signature
= true;
2927 /* Functions calling builtin_apply can not change signature. */
2928 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2930 tree
cdecl = e
->callee
->decl
;
2931 if (DECL_BUILT_IN (cdecl)
2932 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2933 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2934 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2937 node
->local
.can_change_signature
= !e
;
2940 estimate_function_body_sizes (node
, early
);
2942 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2943 if (e
->callee
->comdat_local_p ())
2945 node
->calls_comdat_local
= (e
!= NULL
);
2947 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2948 info
->time
= info
->self_time
;
2949 info
->size
= info
->self_size
;
2950 info
->stack_frame_offset
= 0;
2951 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2952 #ifdef ENABLE_CHECKING
2953 inline_update_overall_summary (node
);
2954 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2961 /* Compute parameters of functions used by inliner using
2962 current_function_decl. */
2965 compute_inline_parameters_for_current (void)
2967 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2973 const pass_data pass_data_inline_parameters
=
2975 GIMPLE_PASS
, /* type */
2976 "inline_param", /* name */
2977 OPTGROUP_INLINE
, /* optinfo_flags */
2978 TV_INLINE_PARAMETERS
, /* tv_id */
2979 0, /* properties_required */
2980 0, /* properties_provided */
2981 0, /* properties_destroyed */
2982 0, /* todo_flags_start */
2983 0, /* todo_flags_finish */
2986 class pass_inline_parameters
: public gimple_opt_pass
2989 pass_inline_parameters (gcc::context
*ctxt
)
2990 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2993 /* opt_pass methods: */
2994 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2995 virtual unsigned int execute (function
*)
2997 return compute_inline_parameters_for_current ();
3000 }; // class pass_inline_parameters
3005 make_pass_inline_parameters (gcc::context
*ctxt
)
3007 return new pass_inline_parameters (ctxt
);
3011 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3012 KNOWN_CONTEXTS and KNOWN_AGGS. */
3015 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3016 int *size
, int *time
,
3017 vec
<tree
> known_vals
,
3018 vec
<ipa_polymorphic_call_context
> known_contexts
,
3019 vec
<ipa_agg_jump_function_p
> known_aggs
)
3022 struct cgraph_node
*callee
;
3023 struct inline_summary
*isummary
;
3024 enum availability avail
;
3027 if (!known_vals
.exists () && !known_contexts
.exists ())
3029 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3032 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3033 known_aggs
, &speculative
);
3034 if (!target
|| speculative
)
3037 /* Account for difference in cost between indirect and direct calls. */
3038 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3039 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3040 gcc_checking_assert (*time
>= 0);
3041 gcc_checking_assert (*size
>= 0);
3043 callee
= cgraph_node::get (target
);
3044 if (!callee
|| !callee
->definition
)
3046 callee
= callee
->function_symbol (&avail
);
3047 if (avail
< AVAIL_AVAILABLE
)
3049 isummary
= inline_summaries
->get (callee
);
3050 return isummary
->inlinable
;
3053 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3054 handle edge E with probability PROB.
3055 Set HINTS if edge may be devirtualized.
3056 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3060 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3063 vec
<tree
> known_vals
,
3064 vec
<ipa_polymorphic_call_context
> known_contexts
,
3065 vec
<ipa_agg_jump_function_p
> known_aggs
,
3066 inline_hints
*hints
)
3068 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3069 int call_size
= es
->call_stmt_size
;
3070 int call_time
= es
->call_stmt_time
;
3073 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3074 known_vals
, known_contexts
, known_aggs
)
3075 && hints
&& e
->maybe_hot_p ())
3076 *hints
|= INLINE_HINT_indirect_call
;
3077 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3080 *min_size
+= cur_size
;
3081 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3082 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3083 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3084 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3089 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3090 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3091 describe context of the call site. */
3094 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3095 int *min_size
, int *time
,
3096 inline_hints
*hints
,
3097 clause_t possible_truths
,
3098 vec
<tree
> known_vals
,
3099 vec
<ipa_polymorphic_call_context
> known_contexts
,
3100 vec
<ipa_agg_jump_function_p
> known_aggs
)
3102 struct cgraph_edge
*e
;
3103 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3105 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3107 /* Do not care about zero sized builtins. */
3108 if (e
->inline_failed
&& !es
->call_stmt_size
)
3110 gcc_checking_assert (!es
->call_stmt_time
);
3114 || evaluate_predicate (es
->predicate
, possible_truths
))
3116 if (e
->inline_failed
)
3118 /* Predicates of calls shall not use NOT_CHANGED codes,
3119 sowe do not need to compute probabilities. */
3120 estimate_edge_size_and_time (e
, size
,
3121 es
->predicate
? NULL
: min_size
,
3122 time
, REG_BR_PROB_BASE
,
3123 known_vals
, known_contexts
,
3127 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3130 known_vals
, known_contexts
,
3134 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3136 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3138 || evaluate_predicate (es
->predicate
, possible_truths
))
3139 estimate_edge_size_and_time (e
, size
,
3140 es
->predicate
? NULL
: min_size
,
3141 time
, REG_BR_PROB_BASE
,
3142 known_vals
, known_contexts
, known_aggs
,
3148 /* Estimate size and time needed to execute NODE assuming
3149 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3150 information about NODE's arguments. If non-NULL use also probability
3151 information present in INLINE_PARAM_SUMMARY vector.
3152 Additionally detemine hints determined by the context. Finally compute
3153 minimal size needed for the call that is independent on the call context and
3154 can be used for fast estimates. Return the values in RET_SIZE,
3155 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3158 estimate_node_size_and_time (struct cgraph_node
*node
,
3159 clause_t possible_truths
,
3160 vec
<tree
> known_vals
,
3161 vec
<ipa_polymorphic_call_context
> known_contexts
,
3162 vec
<ipa_agg_jump_function_p
> known_aggs
,
3163 int *ret_size
, int *ret_min_size
, int *ret_time
,
3164 inline_hints
*ret_hints
,
3165 vec
<inline_param_summary
>
3166 inline_param_summary
)
3168 struct inline_summary
*info
= inline_summaries
->get (node
);
3173 inline_hints hints
= 0;
3176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3179 fprintf (dump_file
, " Estimating body: %s/%i\n"
3180 " Known to be false: ", node
->name (),
3183 for (i
= predicate_not_inlined_condition
;
3184 i
< (predicate_first_dynamic_condition
3185 + (int) vec_safe_length (info
->conds
)); i
++)
3186 if (!(possible_truths
& (1 << i
)))
3189 fprintf (dump_file
, ", ");
3191 dump_condition (dump_file
, info
->conds
, i
);
3195 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3196 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3199 gcc_checking_assert (e
->time
>= 0);
3200 gcc_checking_assert (time
>= 0);
3201 if (!inline_param_summary
.exists ())
3205 int prob
= predicate_probability (info
->conds
,
3208 inline_param_summary
);
3209 gcc_checking_assert (prob
>= 0);
3210 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3211 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3213 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3214 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3215 gcc_checking_assert (time
>= 0);
3218 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3219 min_size
= (*info
->entry
)[0].size
;
3220 gcc_checking_assert (size
>= 0);
3221 gcc_checking_assert (time
>= 0);
3223 if (info
->loop_iterations
3224 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3225 hints
|= INLINE_HINT_loop_iterations
;
3226 if (info
->loop_stride
3227 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3228 hints
|= INLINE_HINT_loop_stride
;
3229 if (info
->array_index
3230 && !evaluate_predicate (info
->array_index
, possible_truths
))
3231 hints
|= INLINE_HINT_array_index
;
3233 hints
|= INLINE_HINT_in_scc
;
3234 if (DECL_DECLARED_INLINE_P (node
->decl
))
3235 hints
|= INLINE_HINT_declared_inline
;
3237 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3238 known_vals
, known_contexts
, known_aggs
);
3239 gcc_checking_assert (size
>= 0);
3240 gcc_checking_assert (time
>= 0);
3241 time
= RDIV (time
, INLINE_TIME_SCALE
);
3242 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3243 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3246 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3252 *ret_min_size
= min_size
;
3259 /* Estimate size and time needed to execute callee of EDGE assuming that
3260 parameters known to be constant at caller of EDGE are propagated.
3261 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3262 and types for parameters. */
3265 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3266 vec
<tree
> known_vals
,
3267 vec
<ipa_polymorphic_call_context
>
3269 vec
<ipa_agg_jump_function_p
> known_aggs
,
3270 int *ret_size
, int *ret_time
,
3271 inline_hints
*hints
)
3275 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3277 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3278 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3281 /* Translate all conditions from callee representation into caller
3282 representation and symbolically evaluate predicate P into new predicate.
3284 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3285 is summary of function predicate P is from. OPERAND_MAP is array giving
3286 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3287 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3288 predicate under which callee is executed. OFFSET_MAP is an array of of
3289 offsets that need to be added to conditions, negative offset means that
3290 conditions relying on values passed by reference have to be discarded
3291 because they might not be preserved (and should be considered offset zero
3292 for other purposes). */
3294 static struct predicate
3295 remap_predicate (struct inline_summary
*info
,
3296 struct inline_summary
*callee_info
,
3297 struct predicate
*p
,
3298 vec
<int> operand_map
,
3299 vec
<int> offset_map
,
3300 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3303 struct predicate out
= true_predicate ();
3305 /* True predicate is easy. */
3306 if (true_predicate_p (p
))
3307 return *toplev_predicate
;
3308 for (i
= 0; p
->clause
[i
]; i
++)
3310 clause_t clause
= p
->clause
[i
];
3312 struct predicate clause_predicate
= false_predicate ();
3314 gcc_assert (i
< MAX_CLAUSES
);
3316 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3317 /* Do we have condition we can't disprove? */
3318 if (clause
& possible_truths
& (1 << cond
))
3320 struct predicate cond_predicate
;
3321 /* Work out if the condition can translate to predicate in the
3322 inlined function. */
3323 if (cond
>= predicate_first_dynamic_condition
)
3325 struct condition
*c
;
3327 c
= &(*callee_info
->conds
)[cond
3329 predicate_first_dynamic_condition
];
3330 /* See if we can remap condition operand to caller's operand.
3331 Otherwise give up. */
3332 if (!operand_map
.exists ()
3333 || (int) operand_map
.length () <= c
->operand_num
3334 || operand_map
[c
->operand_num
] == -1
3335 /* TODO: For non-aggregate conditions, adding an offset is
3336 basically an arithmetic jump function processing which
3337 we should support in future. */
3338 || ((!c
->agg_contents
|| !c
->by_ref
)
3339 && offset_map
[c
->operand_num
] > 0)
3340 || (c
->agg_contents
&& c
->by_ref
3341 && offset_map
[c
->operand_num
] < 0))
3342 cond_predicate
= true_predicate ();
3345 struct agg_position_info ap
;
3346 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3347 if (offset_delta
< 0)
3349 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3352 gcc_assert (!c
->agg_contents
3353 || c
->by_ref
|| offset_delta
== 0);
3354 ap
.offset
= c
->offset
+ offset_delta
;
3355 ap
.agg_contents
= c
->agg_contents
;
3356 ap
.by_ref
= c
->by_ref
;
3357 cond_predicate
= add_condition (info
,
3358 operand_map
[c
->operand_num
],
3359 &ap
, c
->code
, c
->val
);
3362 /* Fixed conditions remains same, construct single
3363 condition predicate. */
3366 cond_predicate
.clause
[0] = 1 << cond
;
3367 cond_predicate
.clause
[1] = 0;
3369 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3372 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3374 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3378 /* Update summary information of inline clones after inlining.
3379 Compute peak stack usage. */
3382 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3384 struct cgraph_edge
*e
;
3385 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3386 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3389 callee_info
->stack_frame_offset
3390 = caller_info
->stack_frame_offset
3391 + caller_info
->estimated_self_stack_size
;
3392 peak
= callee_info
->stack_frame_offset
3393 + callee_info
->estimated_self_stack_size
;
3394 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3395 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3396 ipa_propagate_frequency (node
);
3397 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3399 if (!e
->inline_failed
)
3400 inline_update_callee_summaries (e
->callee
, depth
);
3401 inline_edge_summary (e
)->loop_depth
+= depth
;
3403 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3404 inline_edge_summary (e
)->loop_depth
+= depth
;
3407 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3408 When functoin A is inlined in B and A calls C with parameter that
3409 changes with probability PROB1 and C is known to be passthroug
3410 of argument if B that change with probability PROB2, the probability
3411 of change is now PROB1*PROB2. */
3414 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3415 struct cgraph_edge
*edge
)
3417 if (ipa_node_params_sum
)
3420 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3421 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3422 struct inline_edge_summary
*inlined_es
3423 = inline_edge_summary (inlined_edge
);
3425 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3427 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3428 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3429 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3430 < (int) inlined_es
->param
.length ()))
3432 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3433 int prob1
= es
->param
[i
].change_prob
;
3434 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3435 int prob
= combine_probabilities (prob1
, prob2
);
3437 if (prob1
&& prob2
&& !prob
)
3440 es
->param
[i
].change_prob
= prob
;
3446 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3448 Remap predicates of callees of NODE. Rest of arguments match
3451 Also update change probabilities. */
3454 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3455 struct cgraph_node
*node
,
3456 struct inline_summary
*info
,
3457 struct inline_summary
*callee_info
,
3458 vec
<int> operand_map
,
3459 vec
<int> offset_map
,
3460 clause_t possible_truths
,
3461 struct predicate
*toplev_predicate
)
3463 struct cgraph_edge
*e
;
3464 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3466 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3469 if (e
->inline_failed
)
3471 remap_edge_change_prob (inlined_edge
, e
);
3475 p
= remap_predicate (info
, callee_info
,
3476 es
->predicate
, operand_map
, offset_map
,
3477 possible_truths
, toplev_predicate
);
3478 edge_set_predicate (e
, &p
);
3479 /* TODO: We should remove the edge for code that will be
3480 optimized out, but we need to keep verifiers and tree-inline
3481 happy. Make it cold for now. */
3482 if (false_predicate_p (&p
))
3489 edge_set_predicate (e
, toplev_predicate
);
3492 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3493 operand_map
, offset_map
, possible_truths
,
3496 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3498 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3501 remap_edge_change_prob (inlined_edge
, e
);
3504 p
= remap_predicate (info
, callee_info
,
3505 es
->predicate
, operand_map
, offset_map
,
3506 possible_truths
, toplev_predicate
);
3507 edge_set_predicate (e
, &p
);
3508 /* TODO: We should remove the edge for code that will be optimized
3509 out, but we need to keep verifiers and tree-inline happy.
3510 Make it cold for now. */
3511 if (false_predicate_p (&p
))
3518 edge_set_predicate (e
, toplev_predicate
);
3522 /* Same as remap_predicate, but set result into hint *HINT. */
3525 remap_hint_predicate (struct inline_summary
*info
,
3526 struct inline_summary
*callee_info
,
3527 struct predicate
**hint
,
3528 vec
<int> operand_map
,
3529 vec
<int> offset_map
,
3530 clause_t possible_truths
,
3531 struct predicate
*toplev_predicate
)
3537 p
= remap_predicate (info
, callee_info
,
3539 operand_map
, offset_map
,
3540 possible_truths
, toplev_predicate
);
3541 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3544 set_hint_predicate (hint
, p
);
3546 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3550 /* We inlined EDGE. Update summary of the function we inlined into. */
3553 inline_merge_summary (struct cgraph_edge
*edge
)
3555 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3556 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3557 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3558 struct inline_summary
*info
= inline_summaries
->get (to
);
3559 clause_t clause
= 0; /* not_inline is known to be false. */
3561 vec
<int> operand_map
= vNULL
;
3562 vec
<int> offset_map
= vNULL
;
3564 struct predicate toplev_predicate
;
3565 struct predicate true_p
= true_predicate ();
3566 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3569 toplev_predicate
= *es
->predicate
;
3571 toplev_predicate
= true_predicate ();
3573 if (callee_info
->conds
)
3574 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3575 if (ipa_node_params_sum
&& callee_info
->conds
)
3577 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3578 int count
= ipa_get_cs_argument_count (args
);
3583 operand_map
.safe_grow_cleared (count
);
3584 offset_map
.safe_grow_cleared (count
);
3586 for (i
= 0; i
< count
; i
++)
3588 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3591 /* TODO: handle non-NOPs when merging. */
3592 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3594 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3595 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3596 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3599 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3601 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3602 if (offset
>= 0 && offset
< INT_MAX
)
3604 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3605 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3607 offset_map
[i
] = offset
;
3610 operand_map
[i
] = map
;
3611 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3614 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3616 struct predicate p
= remap_predicate (info
, callee_info
,
3617 &e
->predicate
, operand_map
,
3620 if (!false_predicate_p (&p
))
3622 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3623 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3624 int prob
= predicate_probability (callee_info
->conds
,
3627 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3628 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3629 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3630 if (prob
!= REG_BR_PROB_BASE
3631 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3633 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3634 (double) prob
/ REG_BR_PROB_BASE
);
3636 account_size_time (info
, e
->size
, add_time
, &p
);
3639 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3640 offset_map
, clause
, &toplev_predicate
);
3641 remap_hint_predicate (info
, callee_info
,
3642 &callee_info
->loop_iterations
,
3643 operand_map
, offset_map
, clause
, &toplev_predicate
);
3644 remap_hint_predicate (info
, callee_info
,
3645 &callee_info
->loop_stride
,
3646 operand_map
, offset_map
, clause
, &toplev_predicate
);
3647 remap_hint_predicate (info
, callee_info
,
3648 &callee_info
->array_index
,
3649 operand_map
, offset_map
, clause
, &toplev_predicate
);
3651 inline_update_callee_summaries (edge
->callee
,
3652 inline_edge_summary (edge
)->loop_depth
);
3654 /* We do not maintain predicates of inlined edges, free it. */
3655 edge_set_predicate (edge
, &true_p
);
3656 /* Similarly remove param summaries. */
3657 es
->param
.release ();
3658 operand_map
.release ();
3659 offset_map
.release ();
3662 /* For performance reasons inline_merge_summary is not updating overall size
3663 and time. Recompute it. */
3666 inline_update_overall_summary (struct cgraph_node
*node
)
3668 struct inline_summary
*info
= inline_summaries
->get (node
);
3674 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3676 info
->size
+= e
->size
, info
->time
+= e
->time
;
3677 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3678 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3680 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3682 ~(clause_t
) (1 << predicate_false_condition
),
3683 vNULL
, vNULL
, vNULL
);
3684 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3685 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3688 /* Return hints derrived from EDGE. */
3690 simple_edge_hints (struct cgraph_edge
*edge
)
3693 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3694 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3695 if (inline_summaries
->get (to
)->scc_no
3696 && inline_summaries
->get (to
)->scc_no
== inline_summaries
->get (edge
->callee
)->scc_no
3697 && !edge
->recursive_p ())
3698 hints
|= INLINE_HINT_same_scc
;
3700 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3701 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3702 hints
|= INLINE_HINT_cross_module
;
3707 /* Estimate the time cost for the caller when inlining EDGE.
3708 Only to be called via estimate_edge_time, that handles the
3711 When caching, also update the cache entry. Compute both time and
3712 size, since we always need both metrics eventually. */
3715 do_estimate_edge_time (struct cgraph_edge
*edge
)
3720 struct cgraph_node
*callee
;
3722 vec
<tree
> known_vals
;
3723 vec
<ipa_polymorphic_call_context
> known_contexts
;
3724 vec
<ipa_agg_jump_function_p
> known_aggs
;
3725 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3728 callee
= edge
->callee
->ultimate_alias_target ();
3730 gcc_checking_assert (edge
->inline_failed
);
3731 evaluate_properties_for_edge (edge
, true,
3732 &clause
, &known_vals
, &known_contexts
,
3734 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3735 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3737 /* When we have profile feedback, we can quite safely identify hot
3738 edges and for those we disable size limits. Don't do that when
3739 probability that caller will call the callee is low however, since it
3740 may hurt optimization of the caller's hot path. */
3741 if (edge
->count
&& edge
->maybe_hot_p ()
3743 > (edge
->caller
->global
.inlined_to
3744 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3745 hints
|= INLINE_HINT_known_hot
;
3747 known_vals
.release ();
3748 known_contexts
.release ();
3749 known_aggs
.release ();
3750 gcc_checking_assert (size
>= 0);
3751 gcc_checking_assert (time
>= 0);
3753 /* When caching, update the cache entry. */
3754 if (edge_growth_cache
.exists ())
3756 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3757 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3758 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3759 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3761 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3762 hints
|= simple_edge_hints (edge
);
3763 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3769 /* Return estimated callee growth after inlining EDGE.
3770 Only to be called via estimate_edge_size. */
3773 do_estimate_edge_size (struct cgraph_edge
*edge
)
3776 struct cgraph_node
*callee
;
3778 vec
<tree
> known_vals
;
3779 vec
<ipa_polymorphic_call_context
> known_contexts
;
3780 vec
<ipa_agg_jump_function_p
> known_aggs
;
3782 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3784 if (edge_growth_cache
.exists ())
3786 do_estimate_edge_time (edge
);
3787 size
= edge_growth_cache
[edge
->uid
].size
;
3788 gcc_checking_assert (size
);
3789 return size
- (size
> 0);
3792 callee
= edge
->callee
->ultimate_alias_target ();
3794 /* Early inliner runs without caching, go ahead and do the dirty work. */
3795 gcc_checking_assert (edge
->inline_failed
);
3796 evaluate_properties_for_edge (edge
, true,
3797 &clause
, &known_vals
, &known_contexts
,
3799 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3800 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3801 known_vals
.release ();
3802 known_contexts
.release ();
3803 known_aggs
.release ();
3808 /* Estimate the growth of the caller when inlining EDGE.
3809 Only to be called via estimate_edge_size. */
3812 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3815 struct cgraph_node
*callee
;
3817 vec
<tree
> known_vals
;
3818 vec
<ipa_polymorphic_call_context
> known_contexts
;
3819 vec
<ipa_agg_jump_function_p
> known_aggs
;
3821 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3823 if (edge_growth_cache
.exists ())
3825 do_estimate_edge_time (edge
);
3826 hints
= edge_growth_cache
[edge
->uid
].hints
;
3827 gcc_checking_assert (hints
);
3831 callee
= edge
->callee
->ultimate_alias_target ();
3833 /* Early inliner runs without caching, go ahead and do the dirty work. */
3834 gcc_checking_assert (edge
->inline_failed
);
3835 evaluate_properties_for_edge (edge
, true,
3836 &clause
, &known_vals
, &known_contexts
,
3838 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3839 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3840 known_vals
.release ();
3841 known_contexts
.release ();
3842 known_aggs
.release ();
3843 hints
|= simple_edge_hints (edge
);
3848 /* Estimate self time of the function NODE after inlining EDGE. */
3851 estimate_time_after_inlining (struct cgraph_node
*node
,
3852 struct cgraph_edge
*edge
)
3854 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3855 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3858 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3861 if (time
> MAX_TIME
)
3865 return inline_summaries
->get (node
)->time
;
3869 /* Estimate the size of NODE after inlining EDGE which should be an
3870 edge to either NODE or a call inlined into NODE. */
3873 estimate_size_after_inlining (struct cgraph_node
*node
,
3874 struct cgraph_edge
*edge
)
3876 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3877 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3879 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3880 gcc_assert (size
>= 0);
3883 return inline_summaries
->get (node
)->size
;
3889 struct cgraph_node
*node
;
3890 bool self_recursive
;
3895 /* Worker for do_estimate_growth. Collect growth for all callers. */
3898 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3900 struct cgraph_edge
*e
;
3901 struct growth_data
*d
= (struct growth_data
*) data
;
3903 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3905 gcc_checking_assert (e
->inline_failed
);
3907 if (e
->caller
== d
->node
3908 || (e
->caller
->global
.inlined_to
3909 && e
->caller
->global
.inlined_to
== d
->node
))
3910 d
->self_recursive
= true;
3911 d
->growth
+= estimate_edge_growth (e
);
3917 /* Estimate the growth caused by inlining NODE into all callees. */
3920 do_estimate_growth (struct cgraph_node
*node
)
3922 struct growth_data d
= { node
, 0, false };
3923 struct inline_summary
*info
= inline_summaries
->get (node
);
3925 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3927 /* For self recursive functions the growth estimation really should be
3928 infinity. We don't want to return very large values because the growth
3929 plays various roles in badness computation fractions. Be sure to not
3930 return zero or negative growths. */
3931 if (d
.self_recursive
)
3932 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3933 else if (DECL_EXTERNAL (node
->decl
))
3937 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3938 d
.growth
-= info
->size
;
3939 /* COMDAT functions are very often not shared across multiple units
3940 since they come from various template instantiations.
3941 Take this into account. */
3942 else if (DECL_COMDAT (node
->decl
)
3943 && node
->can_remove_if_no_direct_calls_p ())
3944 d
.growth
-= (info
->size
3945 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3949 if (node_growth_cache
.exists ())
3951 if ((int) node_growth_cache
.length () <= node
->uid
)
3952 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3953 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3959 /* Make cheap estimation if growth of NODE is likely positive knowing
3960 EDGE_GROWTH of one particular edge.
3961 We assume that most of other edges will have similar growth
3962 and skip computation if there are too many callers. */
3965 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3969 struct cgraph_edge
*e
;
3970 gcc_checking_assert (edge_growth
> 0);
3972 /* Unlike for functions called once, we play unsafe with
3973 COMDATs. We can allow that since we know functions
3974 in consideration are small (and thus risk is small) and
3975 moreover grow estimates already accounts that COMDAT
3976 functions may or may not disappear when eliminated from
3977 current unit. With good probability making aggressive
3978 choice in all units is going to make overall program
3981 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3983 cgraph_will_be_removed_from_program_if_no_direct_calls */
3984 if (DECL_EXTERNAL (node
->decl
)
3985 || !node
->can_remove_if_no_direct_calls_p ())
3988 /* If there is cached value, just go ahead. */
3989 if ((int)node_growth_cache
.length () > node
->uid
3990 && (ret
= node_growth_cache
[node
->uid
]))
3992 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
3993 && (!DECL_COMDAT (node
->decl
)
3994 || !node
->can_remove_if_no_direct_calls_p ()))
3996 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
3998 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4004 return estimate_growth (node
) > 0;
4008 /* This function performs intraprocedural analysis in NODE that is required to
4009 inline indirect calls. */
4012 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4014 ipa_analyze_node (node
);
4015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4017 ipa_print_node_params (dump_file
, node
);
4018 ipa_print_node_jump_functions (dump_file
, node
);
4023 /* Note function body size. */
4026 inline_analyze_function (struct cgraph_node
*node
)
4028 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4031 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4032 node
->name (), node
->order
);
4033 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4034 inline_indirect_intraprocedural_analysis (node
);
4035 compute_inline_parameters (node
, false);
4038 struct cgraph_edge
*e
;
4039 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4041 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4042 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4043 e
->call_stmt_cannot_inline_p
= true;
4045 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4047 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4048 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4049 e
->call_stmt_cannot_inline_p
= true;
4057 /* Called when new function is inserted to callgraph late. */
4060 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4062 inline_analyze_function (node
);
4065 /* Note function body size. */
4068 inline_generate_summary (void)
4070 struct cgraph_node
*node
;
4072 /* When not optimizing, do not bother to analyze. Inlining is still done
4073 because edge redirection needs to happen there. */
4074 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4077 if (!inline_summaries
)
4078 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4080 inline_summaries
->enable_insertion_hook ();
4082 ipa_register_cgraph_hooks ();
4083 inline_free_summary ();
4085 FOR_EACH_DEFINED_FUNCTION (node
)
4087 inline_analyze_function (node
);
4091 /* Read predicate from IB. */
4093 static struct predicate
4094 read_predicate (struct lto_input_block
*ib
)
4096 struct predicate out
;
4102 gcc_assert (k
<= MAX_CLAUSES
);
4103 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4107 /* Zero-initialize the remaining clauses in OUT. */
4108 while (k
<= MAX_CLAUSES
)
4109 out
.clause
[k
++] = 0;
4115 /* Write inline summary for edge E to OB. */
4118 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4120 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4124 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4125 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4126 es
->loop_depth
= streamer_read_uhwi (ib
);
4127 p
= read_predicate (ib
);
4128 edge_set_predicate (e
, &p
);
4129 length
= streamer_read_uhwi (ib
);
4132 es
->param
.safe_grow_cleared (length
);
4133 for (i
= 0; i
< length
; i
++)
4134 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4139 /* Stream in inline summaries from the section. */
4142 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4145 const struct lto_function_header
*header
=
4146 (const struct lto_function_header
*) data
;
4147 const int cfg_offset
= sizeof (struct lto_function_header
);
4148 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4149 const int string_offset
= main_offset
+ header
->main_size
;
4150 struct data_in
*data_in
;
4151 unsigned int i
, count2
, j
;
4152 unsigned int f_count
;
4154 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4157 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4158 header
->string_size
, vNULL
);
4159 f_count
= streamer_read_uhwi (&ib
);
4160 for (i
= 0; i
< f_count
; i
++)
4163 struct cgraph_node
*node
;
4164 struct inline_summary
*info
;
4165 lto_symtab_encoder_t encoder
;
4166 struct bitpack_d bp
;
4167 struct cgraph_edge
*e
;
4170 index
= streamer_read_uhwi (&ib
);
4171 encoder
= file_data
->symtab_node_encoder
;
4172 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4174 info
= inline_summaries
->get (node
);
4176 info
->estimated_stack_size
4177 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4178 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4179 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4181 bp
= streamer_read_bitpack (&ib
);
4182 info
->inlinable
= bp_unpack_value (&bp
, 1);
4184 count2
= streamer_read_uhwi (&ib
);
4185 gcc_assert (!info
->conds
);
4186 for (j
= 0; j
< count2
; j
++)
4189 c
.operand_num
= streamer_read_uhwi (&ib
);
4190 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4191 c
.val
= stream_read_tree (&ib
, data_in
);
4192 bp
= streamer_read_bitpack (&ib
);
4193 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4194 c
.by_ref
= bp_unpack_value (&bp
, 1);
4196 c
.offset
= streamer_read_uhwi (&ib
);
4197 vec_safe_push (info
->conds
, c
);
4199 count2
= streamer_read_uhwi (&ib
);
4200 gcc_assert (!info
->entry
);
4201 for (j
= 0; j
< count2
; j
++)
4203 struct size_time_entry e
;
4205 e
.size
= streamer_read_uhwi (&ib
);
4206 e
.time
= streamer_read_uhwi (&ib
);
4207 e
.predicate
= read_predicate (&ib
);
4209 vec_safe_push (info
->entry
, e
);
4212 p
= read_predicate (&ib
);
4213 set_hint_predicate (&info
->loop_iterations
, p
);
4214 p
= read_predicate (&ib
);
4215 set_hint_predicate (&info
->loop_stride
, p
);
4216 p
= read_predicate (&ib
);
4217 set_hint_predicate (&info
->array_index
, p
);
4218 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4219 read_inline_edge_summary (&ib
, e
);
4220 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4221 read_inline_edge_summary (&ib
, e
);
4224 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4226 lto_data_in_delete (data_in
);
4230 /* Read inline summary. Jump functions are shared among ipa-cp
4231 and inliner, so when ipa-cp is active, we don't need to write them
4235 inline_read_summary (void)
4237 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4238 struct lto_file_decl_data
*file_data
;
4241 inline_summary_alloc ();
4243 while ((file_data
= file_data_vec
[j
++]))
4246 const char *data
= lto_get_section_data (file_data
,
4247 LTO_section_inline_summary
,
4250 inline_read_section (file_data
, data
, len
);
4252 /* Fatal error here. We do not want to support compiling ltrans units
4253 with different version of compiler or different flags than the WPA
4254 unit, so this should never happen. */
4255 fatal_error ("ipa inline summary is missing in input file");
4259 ipa_register_cgraph_hooks ();
4261 ipa_prop_read_jump_functions ();
4264 gcc_assert (inline_summaries
);
4265 inline_summaries
->enable_insertion_hook ();
4269 /* Write predicate P to OB. */
4272 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4276 for (j
= 0; p
->clause
[j
]; j
++)
4278 gcc_assert (j
< MAX_CLAUSES
);
4279 streamer_write_uhwi (ob
, p
->clause
[j
]);
4281 streamer_write_uhwi (ob
, 0);
4285 /* Write inline summary for edge E to OB. */
4288 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4290 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4293 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4294 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4295 streamer_write_uhwi (ob
, es
->loop_depth
);
4296 write_predicate (ob
, es
->predicate
);
4297 streamer_write_uhwi (ob
, es
->param
.length ());
4298 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4299 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4303 /* Write inline summary for node in SET.
4304 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4305 active, we don't need to write them twice. */
4308 inline_write_summary (void)
4310 struct cgraph_node
*node
;
4311 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4312 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4313 unsigned int count
= 0;
4316 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4318 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4319 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4320 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4323 streamer_write_uhwi (ob
, count
);
4325 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4327 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4328 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4329 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4331 struct inline_summary
*info
= inline_summaries
->get (node
);
4332 struct bitpack_d bp
;
4333 struct cgraph_edge
*edge
;
4336 struct condition
*c
;
4338 streamer_write_uhwi (ob
,
4339 lto_symtab_encoder_encode (encoder
,
4342 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4343 streamer_write_hwi (ob
, info
->self_size
);
4344 streamer_write_hwi (ob
, info
->self_time
);
4345 bp
= bitpack_create (ob
->main_stream
);
4346 bp_pack_value (&bp
, info
->inlinable
, 1);
4347 streamer_write_bitpack (&bp
);
4348 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4349 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4351 streamer_write_uhwi (ob
, c
->operand_num
);
4352 streamer_write_uhwi (ob
, c
->code
);
4353 stream_write_tree (ob
, c
->val
, true);
4354 bp
= bitpack_create (ob
->main_stream
);
4355 bp_pack_value (&bp
, c
->agg_contents
, 1);
4356 bp_pack_value (&bp
, c
->by_ref
, 1);
4357 streamer_write_bitpack (&bp
);
4358 if (c
->agg_contents
)
4359 streamer_write_uhwi (ob
, c
->offset
);
4361 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4362 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4364 streamer_write_uhwi (ob
, e
->size
);
4365 streamer_write_uhwi (ob
, e
->time
);
4366 write_predicate (ob
, &e
->predicate
);
4368 write_predicate (ob
, info
->loop_iterations
);
4369 write_predicate (ob
, info
->loop_stride
);
4370 write_predicate (ob
, info
->array_index
);
4371 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4372 write_inline_edge_summary (ob
, edge
);
4373 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4374 write_inline_edge_summary (ob
, edge
);
4377 streamer_write_char_stream (ob
->main_stream
, 0);
4378 produce_asm (ob
, NULL
);
4379 destroy_output_block (ob
);
4381 if (optimize
&& !flag_ipa_cp
)
4382 ipa_prop_write_jump_functions ();
4386 /* Release inline summary. */
4389 inline_free_summary (void)
4391 struct cgraph_node
*node
;
4392 if (edge_removal_hook_holder
)
4393 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4394 edge_removal_hook_holder
= NULL
;
4395 if (edge_duplication_hook_holder
)
4396 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4397 edge_duplication_hook_holder
= NULL
;
4398 if (!inline_edge_summary_vec
.exists ())
4400 FOR_EACH_DEFINED_FUNCTION (node
)
4402 reset_inline_summary (node
, inline_summaries
->get (node
));
4403 inline_summaries
->release ();
4404 inline_summaries
= NULL
;
4405 inline_edge_summary_vec
.release ();
4406 if (edge_predicate_pool
)
4407 free_alloc_pool (edge_predicate_pool
);
4408 edge_predicate_pool
= 0;