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"
74 #include "double-int.h"
82 #include "fold-const.h"
83 #include "stor-layout.h"
84 #include "stringpool.h"
85 #include "print-tree.h"
86 #include "tree-inline.h"
87 #include "langhooks.h"
89 #include "diagnostic.h"
90 #include "gimple-pretty-print.h"
92 #include "tree-pass.h"
95 #include "hard-reg-set.h"
98 #include "dominance.h"
101 #include "basic-block.h"
102 #include "tree-ssa-alias.h"
103 #include "internal-fn.h"
104 #include "gimple-expr.h"
107 #include "gimple-iterator.h"
108 #include "gimple-ssa.h"
109 #include "tree-cfg.h"
110 #include "tree-phinodes.h"
111 #include "ssa-iterators.h"
112 #include "tree-ssanames.h"
113 #include "tree-ssa-loop-niter.h"
114 #include "tree-ssa-loop.h"
115 #include "hash-map.h"
116 #include "plugin-api.h"
119 #include "alloc-pool.h"
120 #include "symbol-summary.h"
121 #include "ipa-prop.h"
122 #include "lto-streamer.h"
123 #include "data-streamer.h"
124 #include "tree-streamer.h"
125 #include "ipa-inline.h"
127 #include "tree-scalar-evolution.h"
128 #include "ipa-utils.h"
130 #include "cfgexpand.h"
132 /* Estimate runtime of function can easilly run into huge numbers with many
133 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
134 integer. For anything larger we use gcov_type. */
135 #define MAX_TIME 500000
137 /* Number of bits in integer, but we really want to be stable across different
139 #define NUM_CONDITIONS 32
141 enum predicate_conditions
143 predicate_false_condition
= 0,
144 predicate_not_inlined_condition
= 1,
145 predicate_first_dynamic_condition
= 2
148 /* Special condition code we use to represent test that operand is compile time
150 #define IS_NOT_CONSTANT ERROR_MARK
151 /* Special condition code we use to represent test that operand is not changed
152 across invocation of the function. When operand IS_NOT_CONSTANT it is always
153 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
154 of executions even when they are not compile time constants. */
155 #define CHANGED IDENTIFIER_NODE
157 /* Holders of ipa cgraph hooks: */
158 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
159 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
160 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
161 static void inline_edge_duplication_hook (struct cgraph_edge
*,
162 struct cgraph_edge
*, void *);
164 /* VECtor holding inline summaries.
165 In GGC memory because conditions might point to constant trees. */
166 function_summary
<inline_summary
*> *inline_summaries
;
167 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
169 /* Cached node/edge growths. */
170 vec
<edge_growth_cache_entry
> edge_growth_cache
;
172 /* Edge predicates goes here. */
173 static alloc_pool edge_predicate_pool
;
175 /* Return true predicate (tautology).
176 We represent it by empty list of clauses. */
178 static inline struct predicate
179 true_predicate (void)
187 /* Return predicate testing single condition number COND. */
189 static inline struct predicate
190 single_cond_predicate (int cond
)
193 p
.clause
[0] = 1 << cond
;
199 /* Return false predicate. First clause require false condition. */
201 static inline struct predicate
202 false_predicate (void)
204 return single_cond_predicate (predicate_false_condition
);
208 /* Return true if P is (true). */
211 true_predicate_p (struct predicate
*p
)
213 return !p
->clause
[0];
217 /* Return true if P is (false). */
220 false_predicate_p (struct predicate
*p
)
222 if (p
->clause
[0] == (1 << predicate_false_condition
))
224 gcc_checking_assert (!p
->clause
[1]
225 && p
->clause
[0] == 1 << predicate_false_condition
);
232 /* Return predicate that is set true when function is not inlined. */
234 static inline struct predicate
235 not_inlined_predicate (void)
237 return single_cond_predicate (predicate_not_inlined_condition
);
240 /* Simple description of whether a memory load or a condition refers to a load
241 from an aggregate and if so, how and where from in the aggregate.
242 Individual fields have the same meaning like fields with the same name in
245 struct agg_position_info
247 HOST_WIDE_INT offset
;
252 /* Add condition to condition list CONDS. AGGPOS describes whether the used
253 oprand is loaded from an aggregate and where in the aggregate it is. It can
254 be NULL, which means this not a load from an aggregate. */
256 static struct predicate
257 add_condition (struct inline_summary
*summary
, int operand_num
,
258 struct agg_position_info
*aggpos
,
259 enum tree_code code
, tree val
)
263 struct condition new_cond
;
264 HOST_WIDE_INT offset
;
265 bool agg_contents
, by_ref
;
269 offset
= aggpos
->offset
;
270 agg_contents
= aggpos
->agg_contents
;
271 by_ref
= aggpos
->by_ref
;
276 agg_contents
= false;
280 gcc_checking_assert (operand_num
>= 0);
281 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
283 if (c
->operand_num
== operand_num
286 && c
->agg_contents
== agg_contents
287 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
288 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
290 /* Too many conditions. Give up and return constant true. */
291 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
292 return true_predicate ();
294 new_cond
.operand_num
= operand_num
;
295 new_cond
.code
= code
;
297 new_cond
.agg_contents
= agg_contents
;
298 new_cond
.by_ref
= by_ref
;
299 new_cond
.offset
= offset
;
300 vec_safe_push (summary
->conds
, new_cond
);
301 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
305 /* Add clause CLAUSE into the predicate P. */
308 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
312 int insert_here
= -1;
319 /* False clause makes the whole predicate false. Kill the other variants. */
320 if (clause
== (1 << predicate_false_condition
))
322 p
->clause
[0] = (1 << predicate_false_condition
);
326 if (false_predicate_p (p
))
329 /* No one should be silly enough to add false into nontrivial clauses. */
330 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
332 /* Look where to insert the clause. At the same time prune out
333 clauses of P that are implied by the new clause and thus
335 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
337 p
->clause
[i2
] = p
->clause
[i
];
342 /* If p->clause[i] implies clause, there is nothing to add. */
343 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
345 /* We had nothing to add, none of clauses should've become
347 gcc_checking_assert (i
== i2
);
351 if (p
->clause
[i
] < clause
&& insert_here
< 0)
354 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
355 Otherwise the p->clause[i] has to stay. */
356 if ((p
->clause
[i
] & clause
) != clause
)
360 /* Look for clauses that are obviously true. I.e.
361 op0 == 5 || op0 != 5. */
362 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
365 if (!(clause
& (1 << c1
)))
367 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
368 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
369 and thus there is no point for looking for them. */
370 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
372 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
373 if (clause
& (1 << c2
))
376 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
378 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
379 if (cc1
->operand_num
== cc2
->operand_num
380 && cc1
->val
== cc2
->val
381 && cc2
->code
!= IS_NOT_CONSTANT
382 && cc2
->code
!= CHANGED
383 && cc1
->code
== invert_tree_comparison (cc2
->code
,
384 HONOR_NANS (cc1
->val
)))
390 /* We run out of variants. Be conservative in positive direction. */
391 if (i2
== MAX_CLAUSES
)
393 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
394 p
->clause
[i2
+ 1] = 0;
395 if (insert_here
>= 0)
396 for (; i2
> insert_here
; i2
--)
397 p
->clause
[i2
] = p
->clause
[i2
- 1];
400 p
->clause
[insert_here
] = clause
;
406 static struct predicate
407 and_predicates (conditions conditions
,
408 struct predicate
*p
, struct predicate
*p2
)
410 struct predicate out
= *p
;
413 /* Avoid busy work. */
414 if (false_predicate_p (p2
) || true_predicate_p (p
))
416 if (false_predicate_p (p
) || true_predicate_p (p2
))
419 /* See how far predicates match. */
420 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
422 gcc_checking_assert (i
< MAX_CLAUSES
);
425 /* Combine the predicates rest. */
426 for (; p2
->clause
[i
]; i
++)
428 gcc_checking_assert (i
< MAX_CLAUSES
);
429 add_clause (conditions
, &out
, p2
->clause
[i
]);
435 /* Return true if predicates are obviously equal. */
438 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
441 for (i
= 0; p
->clause
[i
]; i
++)
443 gcc_checking_assert (i
< MAX_CLAUSES
);
444 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
445 gcc_checking_assert (!p2
->clause
[i
]
446 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
447 if (p
->clause
[i
] != p2
->clause
[i
])
450 return !p2
->clause
[i
];
456 static struct predicate
457 or_predicates (conditions conditions
,
458 struct predicate
*p
, struct predicate
*p2
)
460 struct predicate out
= true_predicate ();
463 /* Avoid busy work. */
464 if (false_predicate_p (p2
) || true_predicate_p (p
))
466 if (false_predicate_p (p
) || true_predicate_p (p2
))
468 if (predicates_equal_p (p
, p2
))
471 /* OK, combine the predicates. */
472 for (i
= 0; p
->clause
[i
]; i
++)
473 for (j
= 0; p2
->clause
[j
]; j
++)
475 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
476 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
482 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
483 if predicate P is known to be false. */
486 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
490 /* True remains true. */
491 if (true_predicate_p (p
))
494 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
496 /* See if we can find clause we can disprove. */
497 for (i
= 0; p
->clause
[i
]; i
++)
499 gcc_checking_assert (i
< MAX_CLAUSES
);
500 if (!(p
->clause
[i
] & possible_truths
))
506 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
507 instruction will be recomputed per invocation of the inlined call. */
510 predicate_probability (conditions conds
,
511 struct predicate
*p
, clause_t possible_truths
,
512 vec
<inline_param_summary
> inline_param_summary
)
515 int combined_prob
= REG_BR_PROB_BASE
;
517 /* True remains true. */
518 if (true_predicate_p (p
))
519 return REG_BR_PROB_BASE
;
521 if (false_predicate_p (p
))
524 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
526 /* See if we can find clause we can disprove. */
527 for (i
= 0; p
->clause
[i
]; i
++)
529 gcc_checking_assert (i
< MAX_CLAUSES
);
530 if (!(p
->clause
[i
] & possible_truths
))
536 if (!inline_param_summary
.exists ())
537 return REG_BR_PROB_BASE
;
538 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
539 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
541 if (i2
>= predicate_first_dynamic_condition
)
544 &(*conds
)[i2
- predicate_first_dynamic_condition
];
545 if (c
->code
== CHANGED
547 (int) inline_param_summary
.length ()))
550 inline_param_summary
[c
->operand_num
].change_prob
;
551 this_prob
= MAX (this_prob
, iprob
);
554 this_prob
= REG_BR_PROB_BASE
;
557 this_prob
= REG_BR_PROB_BASE
;
559 combined_prob
= MIN (this_prob
, combined_prob
);
564 return combined_prob
;
568 /* Dump conditional COND. */
571 dump_condition (FILE *f
, conditions conditions
, int cond
)
574 if (cond
== predicate_false_condition
)
575 fprintf (f
, "false");
576 else if (cond
== predicate_not_inlined_condition
)
577 fprintf (f
, "not inlined");
580 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
581 fprintf (f
, "op%i", c
->operand_num
);
583 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
584 c
->by_ref
? "ref " : "", c
->offset
);
585 if (c
->code
== IS_NOT_CONSTANT
)
587 fprintf (f
, " not constant");
590 if (c
->code
== CHANGED
)
592 fprintf (f
, " changed");
595 fprintf (f
, " %s ", op_symbol_code (c
->code
));
596 print_generic_expr (f
, c
->val
, 1);
601 /* Dump clause CLAUSE. */
604 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
611 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
612 if (clause
& (1 << i
))
617 dump_condition (f
, conds
, i
);
623 /* Dump predicate PREDICATE. */
626 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
629 if (true_predicate_p (pred
))
630 dump_clause (f
, conds
, 0);
632 for (i
= 0; pred
->clause
[i
]; i
++)
636 dump_clause (f
, conds
, pred
->clause
[i
]);
642 /* Dump inline hints. */
644 dump_inline_hints (FILE *f
, inline_hints hints
)
648 fprintf (f
, "inline hints:");
649 if (hints
& INLINE_HINT_indirect_call
)
651 hints
&= ~INLINE_HINT_indirect_call
;
652 fprintf (f
, " indirect_call");
654 if (hints
& INLINE_HINT_loop_iterations
)
656 hints
&= ~INLINE_HINT_loop_iterations
;
657 fprintf (f
, " loop_iterations");
659 if (hints
& INLINE_HINT_loop_stride
)
661 hints
&= ~INLINE_HINT_loop_stride
;
662 fprintf (f
, " loop_stride");
664 if (hints
& INLINE_HINT_same_scc
)
666 hints
&= ~INLINE_HINT_same_scc
;
667 fprintf (f
, " same_scc");
669 if (hints
& INLINE_HINT_in_scc
)
671 hints
&= ~INLINE_HINT_in_scc
;
672 fprintf (f
, " in_scc");
674 if (hints
& INLINE_HINT_cross_module
)
676 hints
&= ~INLINE_HINT_cross_module
;
677 fprintf (f
, " cross_module");
679 if (hints
& INLINE_HINT_declared_inline
)
681 hints
&= ~INLINE_HINT_declared_inline
;
682 fprintf (f
, " declared_inline");
684 if (hints
& INLINE_HINT_array_index
)
686 hints
&= ~INLINE_HINT_array_index
;
687 fprintf (f
, " array_index");
689 if (hints
& INLINE_HINT_known_hot
)
691 hints
&= ~INLINE_HINT_known_hot
;
692 fprintf (f
, " known_hot");
698 /* Record SIZE and TIME under condition PRED into the inline summary. */
701 account_size_time (struct inline_summary
*summary
, int size
, int time
,
702 struct predicate
*pred
)
708 if (false_predicate_p (pred
))
711 /* We need to create initial empty unconitional clause, but otherwie
712 we don't need to account empty times and sizes. */
713 if (!size
&& !time
&& summary
->entry
)
716 /* Watch overflow that might result from insane profiles. */
717 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
718 time
= MAX_TIME
* INLINE_TIME_SCALE
;
719 gcc_assert (time
>= 0);
721 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
722 if (predicates_equal_p (&e
->predicate
, pred
))
731 e
= &(*summary
->entry
)[0];
732 gcc_assert (!e
->predicate
.clause
[0]);
733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
735 "\t\tReached limit on number of entries, "
736 "ignoring the predicate.");
738 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
741 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
742 ((double) size
) / INLINE_SIZE_SCALE
,
743 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
744 dump_predicate (dump_file
, summary
->conds
, pred
);
748 struct size_time_entry new_entry
;
749 new_entry
.size
= size
;
750 new_entry
.time
= time
;
751 new_entry
.predicate
= *pred
;
752 vec_safe_push (summary
->entry
, new_entry
);
758 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
759 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
763 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
766 redirect_to_unreachable (struct cgraph_edge
*e
)
768 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
769 struct inline_edge_summary
*es
= inline_edge_summary (e
);
772 e
->resolve_speculation (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
774 e
->make_direct (cgraph_node::get_create
775 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
777 e
->redirect_callee (cgraph_node::get_create
778 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
779 e
->inline_failed
= CIF_UNREACHABLE
;
782 es
->call_stmt_size
= 0;
783 es
->call_stmt_time
= 0;
785 callee
->remove_symbol_and_inline_clones ();
788 /* Set predicate for edge E. */
791 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
793 struct inline_edge_summary
*es
= inline_edge_summary (e
);
795 /* If the edge is determined to be never executed, redirect it
796 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
797 if (predicate
&& false_predicate_p (predicate
))
798 redirect_to_unreachable (e
);
799 if (predicate
&& !true_predicate_p (predicate
))
802 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
803 *es
->predicate
= *predicate
;
808 pool_free (edge_predicate_pool
, es
->predicate
);
809 es
->predicate
= NULL
;
813 /* Set predicate for hint *P. */
816 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
818 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
821 pool_free (edge_predicate_pool
, *p
);
827 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
833 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
834 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
835 Return clause of possible truths. When INLINE_P is true, assume that we are
838 ERROR_MARK means compile time invariant. */
841 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
843 vec
<tree
> known_vals
,
844 vec
<ipa_agg_jump_function_p
>
847 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
848 struct inline_summary
*info
= inline_summaries
->get (node
);
852 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
857 /* We allow call stmt to have fewer arguments than the callee function
858 (especially for K&R style programs). So bound check here (we assume
859 known_aggs vector, if non-NULL, has the same length as
861 gcc_checking_assert (!known_aggs
.exists ()
862 || (known_vals
.length () == known_aggs
.length ()));
863 if (c
->operand_num
>= (int) known_vals
.length ())
865 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
871 struct ipa_agg_jump_function
*agg
;
873 if (c
->code
== CHANGED
875 && (known_vals
[c
->operand_num
] == error_mark_node
))
878 if (known_aggs
.exists ())
880 agg
= known_aggs
[c
->operand_num
];
881 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
888 val
= known_vals
[c
->operand_num
];
889 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
895 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
898 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
901 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
902 TYPE_SIZE (TREE_TYPE (val
)), 0))
904 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
907 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
910 if (res
&& integer_zerop (res
))
913 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
919 /* Work out what conditions might be true at invocation of E. */
922 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
923 clause_t
*clause_ptr
,
924 vec
<tree
> *known_vals_ptr
,
925 vec
<ipa_polymorphic_call_context
>
927 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
929 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
930 struct inline_summary
*info
= inline_summaries
->get (callee
);
931 vec
<tree
> known_vals
= vNULL
;
932 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
935 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
937 known_vals_ptr
->create (0);
938 if (known_contexts_ptr
)
939 known_contexts_ptr
->create (0);
941 if (ipa_node_params_sum
942 && !e
->call_stmt_cannot_inline_p
943 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
945 struct ipa_node_params
*parms_info
;
946 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
947 struct inline_edge_summary
*es
= inline_edge_summary (e
);
948 int i
, count
= ipa_get_cs_argument_count (args
);
950 if (e
->caller
->global
.inlined_to
)
951 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
953 parms_info
= IPA_NODE_REF (e
->caller
);
955 if (count
&& (info
->conds
|| known_vals_ptr
))
956 known_vals
.safe_grow_cleared (count
);
957 if (count
&& (info
->conds
|| known_aggs_ptr
))
958 known_aggs
.safe_grow_cleared (count
);
959 if (count
&& known_contexts_ptr
)
960 known_contexts_ptr
->safe_grow_cleared (count
);
962 for (i
= 0; i
< count
; i
++)
964 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
965 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
967 if (!cst
&& e
->call_stmt
968 && i
< (int)gimple_call_num_args (e
->call_stmt
))
970 cst
= gimple_call_arg (e
->call_stmt
, i
);
971 if (!is_gimple_min_invariant (cst
))
976 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
977 if (known_vals
.exists ())
980 else if (inline_p
&& !es
->param
[i
].change_prob
)
981 known_vals
[i
] = error_mark_node
;
983 if (known_contexts_ptr
)
984 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
986 /* TODO: When IPA-CP starts propagating and merging aggregate jump
987 functions, use its knowledge of the caller too, just like the
988 scalar case above. */
989 known_aggs
[i
] = &jf
->agg
;
992 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
993 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
995 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
997 if (count
&& (info
->conds
|| known_vals_ptr
))
998 known_vals
.safe_grow_cleared (count
);
999 for (i
= 0; i
< count
; i
++)
1001 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
1002 if (!is_gimple_min_invariant (cst
))
1005 known_vals
[i
] = cst
;
1010 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
1011 known_vals
, known_aggs
);
1014 *known_vals_ptr
= known_vals
;
1016 known_vals
.release ();
1019 *known_aggs_ptr
= known_aggs
;
1021 known_aggs
.release ();
1025 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1028 inline_summary_alloc (void)
1030 if (!edge_removal_hook_holder
)
1031 edge_removal_hook_holder
=
1032 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1033 if (!edge_duplication_hook_holder
)
1034 edge_duplication_hook_holder
=
1035 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1037 if (!inline_summaries
)
1038 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1040 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1041 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1042 if (!edge_predicate_pool
)
1043 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1044 sizeof (struct predicate
), 10);
1047 /* We are called multiple time for given function; clear
1048 data from previous run so they are not cumulated. */
1051 reset_inline_edge_summary (struct cgraph_edge
*e
)
1053 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1055 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1057 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1059 pool_free (edge_predicate_pool
, es
->predicate
);
1060 es
->predicate
= NULL
;
1061 es
->param
.release ();
1065 /* We are called multiple time for given function; clear
1066 data from previous run so they are not cumulated. */
1069 reset_inline_summary (struct cgraph_node
*node
,
1070 inline_summary
*info
)
1072 struct cgraph_edge
*e
;
1074 info
->self_size
= info
->self_time
= 0;
1075 info
->estimated_stack_size
= 0;
1076 info
->estimated_self_stack_size
= 0;
1077 info
->stack_frame_offset
= 0;
1082 if (info
->loop_iterations
)
1084 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1085 info
->loop_iterations
= NULL
;
1087 if (info
->loop_stride
)
1089 pool_free (edge_predicate_pool
, info
->loop_stride
);
1090 info
->loop_stride
= NULL
;
1092 if (info
->array_index
)
1094 pool_free (edge_predicate_pool
, info
->array_index
);
1095 info
->array_index
= NULL
;
1097 vec_free (info
->conds
);
1098 vec_free (info
->entry
);
1099 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1100 reset_inline_edge_summary (e
);
1101 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1102 reset_inline_edge_summary (e
);
1105 /* Hook that is called by cgraph.c when a node is removed. */
1108 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1110 reset_inline_summary (node
, info
);
1113 /* Remap predicate P of former function to be predicate of duplicated function.
1114 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1115 INFO is inline summary of the duplicated node. */
1117 static struct predicate
1118 remap_predicate_after_duplication (struct predicate
*p
,
1119 clause_t possible_truths
,
1120 struct inline_summary
*info
)
1122 struct predicate new_predicate
= true_predicate ();
1124 for (j
= 0; p
->clause
[j
]; j
++)
1125 if (!(possible_truths
& p
->clause
[j
]))
1127 new_predicate
= false_predicate ();
1131 add_clause (info
->conds
, &new_predicate
,
1132 possible_truths
& p
->clause
[j
]);
1133 return new_predicate
;
1136 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1137 Additionally care about allocating new memory slot for updated predicate
1138 and set it to NULL when it becomes true or false (and thus uninteresting).
1142 remap_hint_predicate_after_duplication (struct predicate
**p
,
1143 clause_t possible_truths
,
1144 struct inline_summary
*info
)
1146 struct predicate new_predicate
;
1151 new_predicate
= remap_predicate_after_duplication (*p
,
1152 possible_truths
, info
);
1153 /* We do not want to free previous predicate; it is used by node origin. */
1155 set_hint_predicate (p
, new_predicate
);
1159 /* Hook that is called by cgraph.c when a node is duplicated. */
1161 inline_summary_t::duplicate (cgraph_node
*src
,
1164 inline_summary
*info
)
1166 inline_summary_alloc ();
1167 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1168 /* TODO: as an optimization, we may avoid copying conditions
1169 that are known to be false or true. */
1170 info
->conds
= vec_safe_copy (info
->conds
);
1172 /* When there are any replacements in the function body, see if we can figure
1173 out that something was optimized out. */
1174 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1176 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1177 /* Use SRC parm info since it may not be copied yet. */
1178 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1179 vec
<tree
> known_vals
= vNULL
;
1180 int count
= ipa_get_param_count (parms_info
);
1182 clause_t possible_truths
;
1183 struct predicate true_pred
= true_predicate ();
1185 int optimized_out_size
= 0;
1186 bool inlined_to_p
= false;
1187 struct cgraph_edge
*edge
;
1190 known_vals
.safe_grow_cleared (count
);
1191 for (i
= 0; i
< count
; i
++)
1193 struct ipa_replace_map
*r
;
1195 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1197 if (((!r
->old_tree
&& r
->parm_num
== i
)
1198 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1199 && r
->replace_p
&& !r
->ref_p
)
1201 known_vals
[i
] = r
->new_tree
;
1206 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1209 known_vals
.release ();
1211 account_size_time (info
, 0, 0, &true_pred
);
1213 /* Remap size_time vectors.
1214 Simplify the predicate by prunning out alternatives that are known
1216 TODO: as on optimization, we can also eliminate conditions known
1218 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1220 struct predicate new_predicate
;
1221 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1224 if (false_predicate_p (&new_predicate
))
1225 optimized_out_size
+= e
->size
;
1227 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1230 /* Remap edge predicates with the same simplification as above.
1231 Also copy constantness arrays. */
1232 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1234 struct predicate new_predicate
;
1235 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1237 if (!edge
->inline_failed
)
1238 inlined_to_p
= true;
1241 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1244 if (false_predicate_p (&new_predicate
)
1245 && !false_predicate_p (es
->predicate
))
1246 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1247 edge_set_predicate (edge
, &new_predicate
);
1250 /* Remap indirect edge predicates with the same simplificaiton as above.
1251 Also copy constantness arrays. */
1252 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1254 struct predicate new_predicate
;
1255 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1257 gcc_checking_assert (edge
->inline_failed
);
1260 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1263 if (false_predicate_p (&new_predicate
)
1264 && !false_predicate_p (es
->predicate
))
1265 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1266 edge_set_predicate (edge
, &new_predicate
);
1268 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1269 possible_truths
, info
);
1270 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1271 possible_truths
, info
);
1272 remap_hint_predicate_after_duplication (&info
->array_index
,
1273 possible_truths
, info
);
1275 /* If inliner or someone after inliner will ever start producing
1276 non-trivial clones, we will get trouble with lack of information
1277 about updating self sizes, because size vectors already contains
1278 sizes of the calees. */
1279 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1283 info
->entry
= vec_safe_copy (info
->entry
);
1284 if (info
->loop_iterations
)
1286 predicate p
= *info
->loop_iterations
;
1287 info
->loop_iterations
= NULL
;
1288 set_hint_predicate (&info
->loop_iterations
, p
);
1290 if (info
->loop_stride
)
1292 predicate p
= *info
->loop_stride
;
1293 info
->loop_stride
= NULL
;
1294 set_hint_predicate (&info
->loop_stride
, p
);
1296 if (info
->array_index
)
1298 predicate p
= *info
->array_index
;
1299 info
->array_index
= NULL
;
1300 set_hint_predicate (&info
->array_index
, p
);
1303 if (!dst
->global
.inlined_to
)
1304 inline_update_overall_summary (dst
);
1308 /* Hook that is called by cgraph.c when a node is duplicated. */
1311 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1312 struct cgraph_edge
*dst
,
1313 ATTRIBUTE_UNUSED
void *data
)
1315 struct inline_edge_summary
*info
;
1316 struct inline_edge_summary
*srcinfo
;
1317 inline_summary_alloc ();
1318 info
= inline_edge_summary (dst
);
1319 srcinfo
= inline_edge_summary (src
);
1320 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1321 info
->predicate
= NULL
;
1322 edge_set_predicate (dst
, srcinfo
->predicate
);
1323 info
->param
= srcinfo
->param
.copy ();
1324 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1326 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1327 - eni_size_weights
.call_cost
);
1328 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1329 - eni_time_weights
.call_cost
);
1334 /* Keep edge cache consistent across edge removal. */
1337 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1338 void *data ATTRIBUTE_UNUSED
)
1340 if (edge_growth_cache
.exists ())
1341 reset_edge_growth_cache (edge
);
1342 reset_inline_edge_summary (edge
);
1346 /* Initialize growth caches. */
1349 initialize_growth_caches (void)
1351 if (symtab
->edges_max_uid
)
1352 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1356 /* Free growth caches. */
1359 free_growth_caches (void)
1361 edge_growth_cache
.release ();
1365 /* Dump edge summaries associated to NODE and recursively to all clones.
1366 Indent by INDENT. */
1369 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1370 struct inline_summary
*info
)
1372 struct cgraph_edge
*edge
;
1373 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1375 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1376 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1380 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1381 " time: %2i callee size:%2i stack:%2i",
1382 indent
, "", callee
->name (), callee
->order
,
1383 !edge
->inline_failed
1384 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1385 indent
, "", es
->loop_depth
, edge
->frequency
,
1386 es
->call_stmt_size
, es
->call_stmt_time
,
1387 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1388 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1392 fprintf (f
, " predicate: ");
1393 dump_predicate (f
, info
->conds
, es
->predicate
);
1397 if (es
->param
.exists ())
1398 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1400 int prob
= es
->param
[i
].change_prob
;
1403 fprintf (f
, "%*s op%i is compile time invariant\n",
1405 else if (prob
!= REG_BR_PROB_BASE
)
1406 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1407 prob
* 100.0 / REG_BR_PROB_BASE
);
1409 if (!edge
->inline_failed
)
1411 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1412 " callee size %i\n",
1414 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1415 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1416 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1417 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1420 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1422 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1423 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1427 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1430 fprintf (f
, "predicate: ");
1431 dump_predicate (f
, info
->conds
, es
->predicate
);
1440 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1442 if (node
->definition
)
1444 struct inline_summary
*s
= inline_summaries
->get (node
);
1447 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1449 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1450 fprintf (f
, " always_inline");
1452 fprintf (f
, " inlinable");
1453 if (s
->contains_cilk_spawn
)
1454 fprintf (f
, " contains_cilk_spawn");
1455 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1456 fprintf (f
, " global time: %i\n", s
->time
);
1457 fprintf (f
, " self size: %i\n", s
->self_size
);
1458 fprintf (f
, " global size: %i\n", s
->size
);
1459 fprintf (f
, " min size: %i\n", s
->min_size
);
1460 fprintf (f
, " self stack: %i\n",
1461 (int) s
->estimated_self_stack_size
);
1462 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1464 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1466 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1467 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1469 fprintf (f
, " size:%f, time:%f, predicate:",
1470 (double) e
->size
/ INLINE_SIZE_SCALE
,
1471 (double) e
->time
/ INLINE_TIME_SCALE
);
1472 dump_predicate (f
, s
->conds
, &e
->predicate
);
1474 if (s
->loop_iterations
)
1476 fprintf (f
, " loop iterations:");
1477 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1481 fprintf (f
, " loop stride:");
1482 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1486 fprintf (f
, " array index:");
1487 dump_predicate (f
, s
->conds
, s
->array_index
);
1489 fprintf (f
, " calls:\n");
1490 dump_inline_edge_summary (f
, 4, node
, s
);
1496 debug_inline_summary (struct cgraph_node
*node
)
1498 dump_inline_summary (stderr
, node
);
1502 dump_inline_summaries (FILE *f
)
1504 struct cgraph_node
*node
;
1506 FOR_EACH_DEFINED_FUNCTION (node
)
1507 if (!node
->global
.inlined_to
)
1508 dump_inline_summary (f
, node
);
1511 /* Give initial reasons why inlining would fail on EDGE. This gets either
1512 nullified or usually overwritten by more precise reasons later. */
1515 initialize_inline_failed (struct cgraph_edge
*e
)
1517 struct cgraph_node
*callee
= e
->callee
;
1519 if (e
->indirect_unknown_callee
)
1520 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1521 else if (!callee
->definition
)
1522 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1523 else if (callee
->local
.redefined_extern_inline
)
1524 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1525 else if (e
->call_stmt_cannot_inline_p
)
1526 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1527 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1528 /* We can't inline if the function is spawing a function. */
1529 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1531 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1534 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1535 boolean variable pointed to by DATA. */
1538 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1541 bool *b
= (bool *) data
;
1546 /* If OP refers to value of function parameter, return the corresponding
1550 unmodified_parm_1 (gimple stmt
, tree op
)
1552 /* SSA_NAME referring to parm default def? */
1553 if (TREE_CODE (op
) == SSA_NAME
1554 && SSA_NAME_IS_DEFAULT_DEF (op
)
1555 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1556 return SSA_NAME_VAR (op
);
1557 /* Non-SSA parm reference? */
1558 if (TREE_CODE (op
) == PARM_DECL
)
1560 bool modified
= false;
1563 ao_ref_init (&refd
, op
);
1564 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1572 /* If OP refers to value of function parameter, return the corresponding
1573 parameter. Also traverse chains of SSA register assignments. */
1576 unmodified_parm (gimple stmt
, tree op
)
1578 tree res
= unmodified_parm_1 (stmt
, op
);
1582 if (TREE_CODE (op
) == SSA_NAME
1583 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1584 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1585 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1586 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1590 /* If OP refers to a value of a function parameter or value loaded from an
1591 aggregate passed to a parameter (either by value or reference), return TRUE
1592 and store the number of the parameter to *INDEX_P and information whether
1593 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1594 the function parameters, STMT is the statement in which OP is used or
1598 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1599 gimple stmt
, tree op
, int *index_p
,
1600 struct agg_position_info
*aggpos
)
1602 tree res
= unmodified_parm_1 (stmt
, op
);
1604 gcc_checking_assert (aggpos
);
1607 *index_p
= ipa_get_param_decl_index (info
, res
);
1610 aggpos
->agg_contents
= false;
1611 aggpos
->by_ref
= false;
1615 if (TREE_CODE (op
) == SSA_NAME
)
1617 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1618 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1620 stmt
= SSA_NAME_DEF_STMT (op
);
1621 op
= gimple_assign_rhs1 (stmt
);
1622 if (!REFERENCE_CLASS_P (op
))
1623 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1627 aggpos
->agg_contents
= true;
1628 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1632 /* See if statement might disappear after inlining.
1633 0 - means not eliminated
1634 1 - half of statements goes away
1635 2 - for sure it is eliminated.
1636 We are not terribly sophisticated, basically looking for simple abstraction
1637 penalty wrappers. */
1640 eliminated_by_inlining_prob (gimple stmt
)
1642 enum gimple_code code
= gimple_code (stmt
);
1643 enum tree_code rhs_code
;
1653 if (gimple_num_ops (stmt
) != 2)
1656 rhs_code
= gimple_assign_rhs_code (stmt
);
1658 /* Casts of parameters, loads from parameters passed by reference
1659 and stores to return value or parameters are often free after
1660 inlining dua to SRA and further combining.
1661 Assume that half of statements goes away. */
1662 if (CONVERT_EXPR_CODE_P (rhs_code
)
1663 || rhs_code
== VIEW_CONVERT_EXPR
1664 || rhs_code
== ADDR_EXPR
1665 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1667 tree rhs
= gimple_assign_rhs1 (stmt
);
1668 tree lhs
= gimple_assign_lhs (stmt
);
1669 tree inner_rhs
= get_base_address (rhs
);
1670 tree inner_lhs
= get_base_address (lhs
);
1671 bool rhs_free
= false;
1672 bool lhs_free
= false;
1679 /* Reads of parameter are expected to be free. */
1680 if (unmodified_parm (stmt
, inner_rhs
))
1682 /* Match expressions of form &this->field. Those will most likely
1683 combine with something upstream after inlining. */
1684 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1686 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1687 if (TREE_CODE (op
) == PARM_DECL
)
1689 else if (TREE_CODE (op
) == MEM_REF
1690 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1694 /* When parameter is not SSA register because its address is taken
1695 and it is just copied into one, the statement will be completely
1696 free after inlining (we will copy propagate backward). */
1697 if (rhs_free
&& is_gimple_reg (lhs
))
1700 /* Reads of parameters passed by reference
1701 expected to be free (i.e. optimized out after inlining). */
1702 if (TREE_CODE (inner_rhs
) == MEM_REF
1703 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1706 /* Copying parameter passed by reference into gimple register is
1707 probably also going to copy propagate, but we can't be quite
1709 if (rhs_free
&& is_gimple_reg (lhs
))
1712 /* Writes to parameters, parameters passed by value and return value
1713 (either dirrectly or passed via invisible reference) are free.
1715 TODO: We ought to handle testcase like
1716 struct a {int a,b;};
1718 retrurnsturct (void)
1724 This translate into:
1739 For that we either need to copy ipa-split logic detecting writes
1741 if (TREE_CODE (inner_lhs
) == PARM_DECL
1742 || TREE_CODE (inner_lhs
) == RESULT_DECL
1743 || (TREE_CODE (inner_lhs
) == MEM_REF
1744 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1745 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1746 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1747 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1749 0))) == RESULT_DECL
))))
1752 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1754 if (lhs_free
&& rhs_free
)
1764 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1765 predicates to the CFG edges. */
1768 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1769 struct inline_summary
*summary
,
1775 struct agg_position_info aggpos
;
1776 enum tree_code code
, inverted_code
;
1782 last
= last_stmt (bb
);
1783 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1785 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1787 op
= gimple_cond_lhs (last
);
1788 /* TODO: handle conditionals like
1791 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1793 code
= gimple_cond_code (last
);
1794 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1796 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1798 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1799 ? code
: inverted_code
);
1800 /* invert_tree_comparison will return ERROR_MARK on FP
1801 comparsions that are not EQ/NE instead of returning proper
1802 unordered one. Be sure it is not confused with NON_CONSTANT. */
1803 if (this_code
!= ERROR_MARK
)
1805 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1807 gimple_cond_rhs (last
));
1808 e
->aux
= pool_alloc (edge_predicate_pool
);
1809 *(struct predicate
*) e
->aux
= p
;
1814 if (TREE_CODE (op
) != SSA_NAME
)
1817 if (builtin_constant_p (op))
1821 Here we can predicate nonconstant_code. We can't
1822 really handle constant_code since we have no predicate
1823 for this and also the constant code is not known to be
1824 optimized away when inliner doen't see operand is constant.
1825 Other optimizers might think otherwise. */
1826 if (gimple_cond_code (last
) != NE_EXPR
1827 || !integer_zerop (gimple_cond_rhs (last
)))
1829 set_stmt
= SSA_NAME_DEF_STMT (op
);
1830 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1831 || gimple_call_num_args (set_stmt
) != 1)
1833 op2
= gimple_call_arg (set_stmt
, 0);
1834 if (!unmodified_parm_or_parm_agg_item
1835 (info
, set_stmt
, op2
, &index
, &aggpos
))
1837 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1839 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1840 IS_NOT_CONSTANT
, NULL_TREE
);
1841 e
->aux
= pool_alloc (edge_predicate_pool
);
1842 *(struct predicate
*) e
->aux
= p
;
1847 /* If BB ends by a switch we can turn into predicates, attach corresponding
1848 predicates to the CFG edges. */
1851 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1852 struct inline_summary
*summary
,
1858 struct agg_position_info aggpos
;
1864 lastg
= last_stmt (bb
);
1865 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1867 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1868 op
= gimple_switch_index (last
);
1869 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1872 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1874 e
->aux
= pool_alloc (edge_predicate_pool
);
1875 *(struct predicate
*) e
->aux
= false_predicate ();
1877 n
= gimple_switch_num_labels (last
);
1878 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1880 tree cl
= gimple_switch_label (last
, case_idx
);
1884 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1885 min
= CASE_LOW (cl
);
1886 max
= CASE_HIGH (cl
);
1888 /* For default we might want to construct predicate that none
1889 of cases is met, but it is bit hard to do not having negations
1890 of conditionals handy. */
1892 p
= true_predicate ();
1894 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1897 struct predicate p1
, p2
;
1898 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1899 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1900 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1902 *(struct predicate
*) e
->aux
1903 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1908 /* For each BB in NODE attach to its AUX pointer predicate under
1909 which it is executable. */
1912 compute_bb_predicates (struct cgraph_node
*node
,
1913 struct ipa_node_params
*parms_info
,
1914 struct inline_summary
*summary
)
1916 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1920 FOR_EACH_BB_FN (bb
, my_function
)
1922 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1923 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1926 /* Entry block is always executable. */
1927 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1928 = pool_alloc (edge_predicate_pool
);
1929 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1930 = true_predicate ();
1932 /* A simple dataflow propagation of predicates forward in the CFG.
1933 TODO: work in reverse postorder. */
1937 FOR_EACH_BB_FN (bb
, my_function
)
1939 struct predicate p
= false_predicate ();
1942 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1946 struct predicate this_bb_predicate
1947 = *(struct predicate
*) e
->src
->aux
;
1950 = and_predicates (summary
->conds
, &this_bb_predicate
,
1951 (struct predicate
*) e
->aux
);
1952 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1953 if (true_predicate_p (&p
))
1957 if (false_predicate_p (&p
))
1958 gcc_assert (!bb
->aux
);
1964 bb
->aux
= pool_alloc (edge_predicate_pool
);
1965 *((struct predicate
*) bb
->aux
) = p
;
1967 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1969 /* This OR operation is needed to ensure monotonous data flow
1970 in the case we hit the limit on number of clauses and the
1971 and/or operations above give approximate answers. */
1972 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1973 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1976 *((struct predicate
*) bb
->aux
) = p
;
1985 /* We keep info about constantness of SSA names. */
1987 typedef struct predicate predicate_t
;
1988 /* Return predicate specifying when the STMT might have result that is not
1989 a compile time constant. */
1991 static struct predicate
1992 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1993 struct inline_summary
*summary
,
1995 vec
<predicate_t
> nonconstant_names
)
2000 while (UNARY_CLASS_P (expr
))
2001 expr
= TREE_OPERAND (expr
, 0);
2003 parm
= unmodified_parm (NULL
, expr
);
2004 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2005 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2006 if (is_gimple_min_invariant (expr
))
2007 return false_predicate ();
2008 if (TREE_CODE (expr
) == SSA_NAME
)
2009 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
2010 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
2012 struct predicate p1
= will_be_nonconstant_expr_predicate
2013 (info
, summary
, TREE_OPERAND (expr
, 0),
2015 struct predicate p2
;
2016 if (true_predicate_p (&p1
))
2018 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2019 TREE_OPERAND (expr
, 1),
2021 return or_predicates (summary
->conds
, &p1
, &p2
);
2023 else if (TREE_CODE (expr
) == COND_EXPR
)
2025 struct predicate p1
= will_be_nonconstant_expr_predicate
2026 (info
, summary
, TREE_OPERAND (expr
, 0),
2028 struct predicate p2
;
2029 if (true_predicate_p (&p1
))
2031 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2032 TREE_OPERAND (expr
, 1),
2034 if (true_predicate_p (&p2
))
2036 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2037 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2038 TREE_OPERAND (expr
, 2),
2040 return or_predicates (summary
->conds
, &p1
, &p2
);
2047 return false_predicate ();
2051 /* Return predicate specifying when the STMT might have result that is not
2052 a compile time constant. */
2054 static struct predicate
2055 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2056 struct inline_summary
*summary
,
2058 vec
<predicate_t
> nonconstant_names
)
2060 struct predicate p
= true_predicate ();
2063 struct predicate op_non_const
;
2066 struct agg_position_info aggpos
;
2068 /* What statments might be optimized away
2069 when their arguments are constant. */
2070 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2071 && gimple_code (stmt
) != GIMPLE_COND
2072 && gimple_code (stmt
) != GIMPLE_SWITCH
2073 && (gimple_code (stmt
) != GIMPLE_CALL
2074 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2077 /* Stores will stay anyway. */
2078 if (gimple_store_p (stmt
))
2081 is_load
= gimple_assign_load_p (stmt
);
2083 /* Loads can be optimized when the value is known. */
2087 gcc_assert (gimple_assign_single_p (stmt
));
2088 op
= gimple_assign_rhs1 (stmt
);
2089 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2096 /* See if we understand all operands before we start
2097 adding conditionals. */
2098 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2100 tree parm
= unmodified_parm (stmt
, use
);
2101 /* For arguments we can build a condition. */
2102 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2104 if (TREE_CODE (use
) != SSA_NAME
)
2106 /* If we know when operand is constant,
2107 we still can say something useful. */
2108 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2115 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2117 op_non_const
= false_predicate ();
2118 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2120 tree parm
= unmodified_parm (stmt
, use
);
2123 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2125 if (index
!= base_index
)
2126 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2131 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2132 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2134 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2135 && gimple_op (stmt
, 0)
2136 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2137 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2139 return op_non_const
;
2142 struct record_modified_bb_info
2148 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2149 set except for info->stmt. */
2152 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2154 struct record_modified_bb_info
*info
=
2155 (struct record_modified_bb_info
*) data
;
2156 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2158 bitmap_set_bit (info
->bb_set
,
2159 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2160 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2161 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2165 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2166 will change since last invocation of STMT.
2168 Value 0 is reserved for compile time invariants.
2169 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2170 ought to be REG_BR_PROB_BASE / estimated_iters. */
2173 param_change_prob (gimple stmt
, int i
)
2175 tree op
= gimple_call_arg (stmt
, i
);
2176 basic_block bb
= gimple_bb (stmt
);
2179 /* Global invariants neve change. */
2180 if (is_gimple_min_invariant (op
))
2182 /* We would have to do non-trivial analysis to really work out what
2183 is the probability of value to change (i.e. when init statement
2184 is in a sibling loop of the call).
2186 We do an conservative estimate: when call is executed N times more often
2187 than the statement defining value, we take the frequency 1/N. */
2188 if (TREE_CODE (op
) == SSA_NAME
)
2193 return REG_BR_PROB_BASE
;
2195 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2196 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2198 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2202 if (init_freq
< bb
->frequency
)
2203 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2205 return REG_BR_PROB_BASE
;
2208 base
= get_base_address (op
);
2213 struct record_modified_bb_info info
;
2216 tree init
= ctor_for_folding (base
);
2218 if (init
!= error_mark_node
)
2221 return REG_BR_PROB_BASE
;
2222 ao_ref_init (&refd
, op
);
2224 info
.bb_set
= BITMAP_ALLOC (NULL
);
2225 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2227 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2229 BITMAP_FREE (info
.bb_set
);
2230 return REG_BR_PROB_BASE
;
2233 /* Assume that every memory is initialized at entry.
2234 TODO: Can we easilly determine if value is always defined
2235 and thus we may skip entry block? */
2236 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2237 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2241 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2242 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2244 BITMAP_FREE (info
.bb_set
);
2245 if (max
< bb
->frequency
)
2246 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2248 return REG_BR_PROB_BASE
;
2250 return REG_BR_PROB_BASE
;
2253 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2254 sub-graph and if the predicate the condition depends on is known. If so,
2255 return true and store the pointer the predicate in *P. */
2258 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2259 inline_summary
*summary
, basic_block bb
,
2260 struct predicate
*p
,
2261 vec
<predicate_t
> nonconstant_names
)
2265 basic_block first_bb
= NULL
;
2268 if (single_pred_p (bb
))
2270 *p
= false_predicate ();
2274 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2276 if (single_succ_p (e
->src
))
2278 if (!single_pred_p (e
->src
))
2281 first_bb
= single_pred (e
->src
);
2282 else if (single_pred (e
->src
) != first_bb
)
2289 else if (e
->src
!= first_bb
)
2297 stmt
= last_stmt (first_bb
);
2299 || gimple_code (stmt
) != GIMPLE_COND
2300 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2303 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2304 gimple_cond_lhs (stmt
),
2306 if (true_predicate_p (p
))
2312 /* Given a PHI statement in a function described by inline properties SUMMARY
2313 and *P being the predicate describing whether the selected PHI argument is
2314 known, store a predicate for the result of the PHI statement into
2315 NONCONSTANT_NAMES, if possible. */
2318 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2319 struct predicate
*p
,
2320 vec
<predicate_t
> nonconstant_names
)
2324 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2326 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2327 if (!is_gimple_min_invariant (arg
))
2329 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2330 *p
= or_predicates (summary
->conds
, p
,
2331 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2332 if (true_predicate_p (p
))
2337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2339 fprintf (dump_file
, "\t\tphi predicate: ");
2340 dump_predicate (dump_file
, summary
->conds
, p
);
2342 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2345 /* Return predicate specifying when array index in access OP becomes non-constant. */
2347 static struct predicate
2348 array_index_predicate (inline_summary
*info
,
2349 vec
< predicate_t
> nonconstant_names
, tree op
)
2351 struct predicate p
= false_predicate ();
2352 while (handled_component_p (op
))
2354 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2356 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2357 p
= or_predicates (info
->conds
, &p
,
2358 &nonconstant_names
[SSA_NAME_VERSION
2359 (TREE_OPERAND (op
, 1))]);
2361 op
= TREE_OPERAND (op
, 0);
2366 /* For a typical usage of __builtin_expect (a<b, 1), we
2367 may introduce an extra relation stmt:
2368 With the builtin, we have
2371 t3 = __builtin_expect (t2, 1);
2374 Without the builtin, we have
2377 This affects the size/time estimation and may have
2378 an impact on the earlier inlining.
2379 Here find this pattern and fix it up later. */
2382 find_foldable_builtin_expect (basic_block bb
)
2384 gimple_stmt_iterator bsi
;
2386 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2388 gimple stmt
= gsi_stmt (bsi
);
2389 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2390 || (is_gimple_call (stmt
)
2391 && gimple_call_internal_p (stmt
)
2392 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2394 tree var
= gimple_call_lhs (stmt
);
2395 tree arg
= gimple_call_arg (stmt
, 0);
2396 use_operand_p use_p
;
2403 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2405 while (TREE_CODE (arg
) == SSA_NAME
)
2407 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2408 if (!is_gimple_assign (stmt_tmp
))
2410 switch (gimple_assign_rhs_code (stmt_tmp
))
2429 arg
= gimple_assign_rhs1 (stmt_tmp
);
2432 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2433 && gimple_code (use_stmt
) == GIMPLE_COND
)
2440 /* Return true when the basic blocks contains only clobbers followed by RESX.
2441 Such BBs are kept around to make removal of dead stores possible with
2442 presence of EH and will be optimized out by optimize_clobbers later in the
2445 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2446 that can be clobber only, too.. When it is false, the RESX is not necessary
2447 on the end of basic block. */
2450 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2452 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2458 if (gsi_end_p (gsi
))
2460 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2464 else if (!single_succ_p (bb
))
2467 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2469 gimple stmt
= gsi_stmt (gsi
);
2470 if (is_gimple_debug (stmt
))
2472 if (gimple_clobber_p (stmt
))
2474 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2479 /* See if all predecestors are either throws or clobber only BBs. */
2480 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2481 if (!(e
->flags
& EDGE_EH
)
2482 && !clobber_only_eh_bb_p (e
->src
, false))
2488 /* Compute function body size parameters for NODE.
2489 When EARLY is true, we compute only simple summaries without
2490 non-trivial predicates to drive the early inliner. */
2493 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2496 /* Estimate static overhead for function prologue/epilogue and alignment. */
2498 /* Benefits are scaled by probability of elimination that is in range
2501 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2503 struct inline_summary
*info
= inline_summaries
->get (node
);
2504 struct predicate bb_predicate
;
2505 struct ipa_node_params
*parms_info
= NULL
;
2506 vec
<predicate_t
> nonconstant_names
= vNULL
;
2509 predicate array_index
= true_predicate ();
2510 gimple fix_builtin_expect_stmt
;
2515 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2516 so we can produce proper inline hints.
2518 When optimizing and analyzing for early inliner, initialize node params
2519 so we can produce correct BB predicates. */
2521 if (opt_for_fn (node
->decl
, optimize
))
2523 calculate_dominance_info (CDI_DOMINATORS
);
2525 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2528 ipa_check_create_node_params ();
2529 ipa_initialize_node_params (node
);
2532 if (ipa_node_params_sum
)
2534 parms_info
= IPA_NODE_REF (node
);
2535 nonconstant_names
.safe_grow_cleared
2536 (SSANAMES (my_function
)->length ());
2541 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2544 /* When we run into maximal number of entries, we assign everything to the
2545 constant truth case. Be sure to have it in list. */
2546 bb_predicate
= true_predicate ();
2547 account_size_time (info
, 0, 0, &bb_predicate
);
2549 bb_predicate
= not_inlined_predicate ();
2550 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2552 gcc_assert (my_function
&& my_function
->cfg
);
2554 compute_bb_predicates (node
, parms_info
, info
);
2555 gcc_assert (cfun
== my_function
);
2556 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2557 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2558 for (n
= 0; n
< nblocks
; n
++)
2560 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2561 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2562 if (clobber_only_eh_bb_p (bb
))
2564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2565 fprintf (dump_file
, "\n Ignoring BB %i;"
2566 " it will be optimized away by cleanup_clobbers\n",
2571 /* TODO: Obviously predicates can be propagated down across CFG. */
2575 bb_predicate
= *(struct predicate
*) bb
->aux
;
2577 bb_predicate
= false_predicate ();
2580 bb_predicate
= true_predicate ();
2582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2584 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2585 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2588 if (parms_info
&& nonconstant_names
.exists ())
2590 struct predicate phi_predicate
;
2591 bool first_phi
= true;
2593 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2597 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2604 fprintf (dump_file
, " ");
2605 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2607 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2612 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2614 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2617 gimple stmt
= gsi_stmt (bsi
);
2618 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2619 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2621 struct predicate will_be_nonconstant
;
2623 /* This relation stmt should be folded after we remove
2624 buildin_expect call. Adjust the cost here. */
2625 if (stmt
== fix_builtin_expect_stmt
)
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2633 fprintf (dump_file
, " ");
2634 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2635 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2636 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2640 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2642 struct predicate this_array_index
;
2644 array_index_predicate (info
, nonconstant_names
,
2645 gimple_assign_rhs1 (stmt
));
2646 if (!false_predicate_p (&this_array_index
))
2648 and_predicates (info
->conds
, &array_index
,
2651 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2653 struct predicate this_array_index
;
2655 array_index_predicate (info
, nonconstant_names
,
2656 gimple_get_lhs (stmt
));
2657 if (!false_predicate_p (&this_array_index
))
2659 and_predicates (info
->conds
, &array_index
,
2664 if (is_gimple_call (stmt
)
2665 && !gimple_call_internal_p (stmt
))
2667 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2668 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2670 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2671 resolved as constant. We however don't want to optimize
2672 out the cgraph edges. */
2673 if (nonconstant_names
.exists ()
2674 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2675 && gimple_call_lhs (stmt
)
2676 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2678 struct predicate false_p
= false_predicate ();
2679 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2682 if (ipa_node_params_sum
)
2684 int count
= gimple_call_num_args (stmt
);
2688 es
->param
.safe_grow_cleared (count
);
2689 for (i
= 0; i
< count
; i
++)
2691 int prob
= param_change_prob (stmt
, i
);
2692 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2693 es
->param
[i
].change_prob
= prob
;
2697 es
->call_stmt_size
= this_size
;
2698 es
->call_stmt_time
= this_time
;
2699 es
->loop_depth
= bb_loop_depth (bb
);
2700 edge_set_predicate (edge
, &bb_predicate
);
2703 /* TODO: When conditional jump or swithc is known to be constant, but
2704 we did not translate it into the predicates, we really can account
2705 just maximum of the possible paths. */
2708 = will_be_nonconstant_predicate (parms_info
, info
,
2709 stmt
, nonconstant_names
);
2710 if (this_time
|| this_size
)
2716 prob
= eliminated_by_inlining_prob (stmt
);
2717 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2719 "\t\t50%% will be eliminated by inlining\n");
2720 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2721 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2724 p
= and_predicates (info
->conds
, &bb_predicate
,
2725 &will_be_nonconstant
);
2727 p
= true_predicate ();
2729 if (!false_predicate_p (&p
)
2730 || (is_gimple_call (stmt
)
2731 && !false_predicate_p (&bb_predicate
)))
2735 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2736 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2739 /* We account everything but the calls. Calls have their own
2740 size/time info attached to cgraph edges. This is necessary
2741 in order to make the cost disappear after inlining. */
2742 if (!is_gimple_call (stmt
))
2746 struct predicate ip
= not_inlined_predicate ();
2747 ip
= and_predicates (info
->conds
, &ip
, &p
);
2748 account_size_time (info
, this_size
* prob
,
2749 this_time
* prob
, &ip
);
2752 account_size_time (info
, this_size
* (2 - prob
),
2753 this_time
* (2 - prob
), &p
);
2756 gcc_assert (time
>= 0);
2757 gcc_assert (size
>= 0);
2761 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2762 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2763 if (time
> MAX_TIME
)
2767 if (nonconstant_names
.exists () && !early
)
2770 predicate loop_iterations
= true_predicate ();
2771 predicate loop_stride
= true_predicate ();
2773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2774 flow_loops_dump (dump_file
, NULL
, 0);
2776 FOR_EACH_LOOP (loop
, 0)
2781 struct tree_niter_desc niter_desc
;
2782 basic_block
*body
= get_loop_body (loop
);
2783 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2785 exits
= get_loop_exit_edges (loop
);
2786 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2787 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2788 && !is_gimple_min_invariant (niter_desc
.niter
))
2790 predicate will_be_nonconstant
2791 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2794 if (!true_predicate_p (&will_be_nonconstant
))
2795 will_be_nonconstant
= and_predicates (info
->conds
,
2797 &will_be_nonconstant
);
2798 if (!true_predicate_p (&will_be_nonconstant
)
2799 && !false_predicate_p (&will_be_nonconstant
))
2800 /* This is slightly inprecise. We may want to represent each
2801 loop with independent predicate. */
2803 and_predicates (info
->conds
, &loop_iterations
,
2804 &will_be_nonconstant
);
2808 for (i
= 0; i
< loop
->num_nodes
; i
++)
2810 gimple_stmt_iterator gsi
;
2811 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2812 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2815 gimple stmt
= gsi_stmt (gsi
);
2820 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2822 predicate will_be_nonconstant
;
2825 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2826 || is_gimple_min_invariant (iv
.step
))
2829 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2832 if (!true_predicate_p (&will_be_nonconstant
))
2834 = and_predicates (info
->conds
,
2836 &will_be_nonconstant
);
2837 if (!true_predicate_p (&will_be_nonconstant
)
2838 && !false_predicate_p (&will_be_nonconstant
))
2839 /* This is slightly inprecise. We may want to represent
2840 each loop with independent predicate. */
2842 and_predicates (info
->conds
, &loop_stride
,
2843 &will_be_nonconstant
);
2849 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2851 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2854 FOR_ALL_BB_FN (bb
, my_function
)
2860 pool_free (edge_predicate_pool
, bb
->aux
);
2862 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2865 pool_free (edge_predicate_pool
, e
->aux
);
2869 inline_summaries
->get (node
)->self_time
= time
;
2870 inline_summaries
->get (node
)->self_size
= size
;
2871 nonconstant_names
.release ();
2872 if (opt_for_fn (node
->decl
, optimize
))
2875 loop_optimizer_finalize ();
2876 else if (!ipa_edge_args_vector
)
2877 ipa_free_all_node_params ();
2878 free_dominance_info (CDI_DOMINATORS
);
2882 fprintf (dump_file
, "\n");
2883 dump_inline_summary (dump_file
, node
);
2888 /* Compute parameters of functions used by inliner.
2889 EARLY is true when we compute parameters for the early inliner */
2892 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2894 HOST_WIDE_INT self_stack_size
;
2895 struct cgraph_edge
*e
;
2896 struct inline_summary
*info
;
2898 gcc_assert (!node
->global
.inlined_to
);
2900 inline_summary_alloc ();
2902 info
= inline_summaries
->get (node
);
2903 reset_inline_summary (node
, info
);
2905 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2906 Once this happen, we will need to more curefully predict call
2908 if (node
->thunk
.thunk_p
)
2910 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2911 struct predicate t
= true_predicate ();
2913 info
->inlinable
= 0;
2914 node
->callees
->call_stmt_cannot_inline_p
= true;
2915 node
->local
.can_change_signature
= false;
2916 es
->call_stmt_time
= 1;
2917 es
->call_stmt_size
= 1;
2918 account_size_time (info
, 0, 0, &t
);
2922 /* Even is_gimple_min_invariant rely on current_function_decl. */
2923 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2925 /* Estimate the stack size for the function if we're optimizing. */
2926 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2927 info
->estimated_self_stack_size
= self_stack_size
;
2928 info
->estimated_stack_size
= self_stack_size
;
2929 info
->stack_frame_offset
= 0;
2931 /* Can this function be inlined at all? */
2932 if (!opt_for_fn (node
->decl
, optimize
)
2933 && !lookup_attribute ("always_inline",
2934 DECL_ATTRIBUTES (node
->decl
)))
2935 info
->inlinable
= false;
2937 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2939 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2941 /* Type attributes can use parameter indices to describe them. */
2942 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2943 node
->local
.can_change_signature
= false;
2946 /* Otherwise, inlinable functions always can change signature. */
2947 if (info
->inlinable
)
2948 node
->local
.can_change_signature
= true;
2951 /* Functions calling builtin_apply can not change signature. */
2952 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2954 tree
cdecl = e
->callee
->decl
;
2955 if (DECL_BUILT_IN (cdecl)
2956 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2957 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2958 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2961 node
->local
.can_change_signature
= !e
;
2964 estimate_function_body_sizes (node
, early
);
2966 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2967 if (e
->callee
->comdat_local_p ())
2969 node
->calls_comdat_local
= (e
!= NULL
);
2971 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2972 info
->time
= info
->self_time
;
2973 info
->size
= info
->self_size
;
2974 info
->stack_frame_offset
= 0;
2975 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2976 #ifdef ENABLE_CHECKING
2977 inline_update_overall_summary (node
);
2978 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2985 /* Compute parameters of functions used by inliner using
2986 current_function_decl. */
2989 compute_inline_parameters_for_current (void)
2991 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2997 const pass_data pass_data_inline_parameters
=
2999 GIMPLE_PASS
, /* type */
3000 "inline_param", /* name */
3001 OPTGROUP_INLINE
, /* optinfo_flags */
3002 TV_INLINE_PARAMETERS
, /* tv_id */
3003 0, /* properties_required */
3004 0, /* properties_provided */
3005 0, /* properties_destroyed */
3006 0, /* todo_flags_start */
3007 0, /* todo_flags_finish */
3010 class pass_inline_parameters
: public gimple_opt_pass
3013 pass_inline_parameters (gcc::context
*ctxt
)
3014 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3017 /* opt_pass methods: */
3018 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3019 virtual unsigned int execute (function
*)
3021 return compute_inline_parameters_for_current ();
3024 }; // class pass_inline_parameters
3029 make_pass_inline_parameters (gcc::context
*ctxt
)
3031 return new pass_inline_parameters (ctxt
);
3035 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3036 KNOWN_CONTEXTS and KNOWN_AGGS. */
3039 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3040 int *size
, int *time
,
3041 vec
<tree
> known_vals
,
3042 vec
<ipa_polymorphic_call_context
> known_contexts
,
3043 vec
<ipa_agg_jump_function_p
> known_aggs
)
3046 struct cgraph_node
*callee
;
3047 struct inline_summary
*isummary
;
3048 enum availability avail
;
3051 if (!known_vals
.exists () && !known_contexts
.exists ())
3053 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3056 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3057 known_aggs
, &speculative
);
3058 if (!target
|| speculative
)
3061 /* Account for difference in cost between indirect and direct calls. */
3062 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3063 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3064 gcc_checking_assert (*time
>= 0);
3065 gcc_checking_assert (*size
>= 0);
3067 callee
= cgraph_node::get (target
);
3068 if (!callee
|| !callee
->definition
)
3070 callee
= callee
->function_symbol (&avail
);
3071 if (avail
< AVAIL_AVAILABLE
)
3073 isummary
= inline_summaries
->get (callee
);
3074 return isummary
->inlinable
;
3077 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3078 handle edge E with probability PROB.
3079 Set HINTS if edge may be devirtualized.
3080 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3084 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3087 vec
<tree
> known_vals
,
3088 vec
<ipa_polymorphic_call_context
> known_contexts
,
3089 vec
<ipa_agg_jump_function_p
> known_aggs
,
3090 inline_hints
*hints
)
3092 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3093 int call_size
= es
->call_stmt_size
;
3094 int call_time
= es
->call_stmt_time
;
3097 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3098 known_vals
, known_contexts
, known_aggs
)
3099 && hints
&& e
->maybe_hot_p ())
3100 *hints
|= INLINE_HINT_indirect_call
;
3101 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3104 *min_size
+= cur_size
;
3105 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3106 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3107 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3108 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3113 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3114 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3115 describe context of the call site. */
3118 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3119 int *min_size
, int *time
,
3120 inline_hints
*hints
,
3121 clause_t possible_truths
,
3122 vec
<tree
> known_vals
,
3123 vec
<ipa_polymorphic_call_context
> known_contexts
,
3124 vec
<ipa_agg_jump_function_p
> known_aggs
)
3126 struct cgraph_edge
*e
;
3127 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3129 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3131 /* Do not care about zero sized builtins. */
3132 if (e
->inline_failed
&& !es
->call_stmt_size
)
3134 gcc_checking_assert (!es
->call_stmt_time
);
3138 || evaluate_predicate (es
->predicate
, possible_truths
))
3140 if (e
->inline_failed
)
3142 /* Predicates of calls shall not use NOT_CHANGED codes,
3143 sowe do not need to compute probabilities. */
3144 estimate_edge_size_and_time (e
, size
,
3145 es
->predicate
? NULL
: min_size
,
3146 time
, REG_BR_PROB_BASE
,
3147 known_vals
, known_contexts
,
3151 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3154 known_vals
, known_contexts
,
3158 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3160 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3162 || evaluate_predicate (es
->predicate
, possible_truths
))
3163 estimate_edge_size_and_time (e
, size
,
3164 es
->predicate
? NULL
: min_size
,
3165 time
, REG_BR_PROB_BASE
,
3166 known_vals
, known_contexts
, known_aggs
,
3172 /* Estimate size and time needed to execute NODE assuming
3173 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3174 information about NODE's arguments. If non-NULL use also probability
3175 information present in INLINE_PARAM_SUMMARY vector.
3176 Additionally detemine hints determined by the context. Finally compute
3177 minimal size needed for the call that is independent on the call context and
3178 can be used for fast estimates. Return the values in RET_SIZE,
3179 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3182 estimate_node_size_and_time (struct cgraph_node
*node
,
3183 clause_t possible_truths
,
3184 vec
<tree
> known_vals
,
3185 vec
<ipa_polymorphic_call_context
> known_contexts
,
3186 vec
<ipa_agg_jump_function_p
> known_aggs
,
3187 int *ret_size
, int *ret_min_size
, int *ret_time
,
3188 inline_hints
*ret_hints
,
3189 vec
<inline_param_summary
>
3190 inline_param_summary
)
3192 struct inline_summary
*info
= inline_summaries
->get (node
);
3197 inline_hints hints
= 0;
3200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3203 fprintf (dump_file
, " Estimating body: %s/%i\n"
3204 " Known to be false: ", node
->name (),
3207 for (i
= predicate_not_inlined_condition
;
3208 i
< (predicate_first_dynamic_condition
3209 + (int) vec_safe_length (info
->conds
)); i
++)
3210 if (!(possible_truths
& (1 << i
)))
3213 fprintf (dump_file
, ", ");
3215 dump_condition (dump_file
, info
->conds
, i
);
3219 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3220 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3223 gcc_checking_assert (e
->time
>= 0);
3224 gcc_checking_assert (time
>= 0);
3225 if (!inline_param_summary
.exists ())
3229 int prob
= predicate_probability (info
->conds
,
3232 inline_param_summary
);
3233 gcc_checking_assert (prob
>= 0);
3234 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3235 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3237 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3238 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3239 gcc_checking_assert (time
>= 0);
3242 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3243 min_size
= (*info
->entry
)[0].size
;
3244 gcc_checking_assert (size
>= 0);
3245 gcc_checking_assert (time
>= 0);
3247 if (info
->loop_iterations
3248 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3249 hints
|= INLINE_HINT_loop_iterations
;
3250 if (info
->loop_stride
3251 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3252 hints
|= INLINE_HINT_loop_stride
;
3253 if (info
->array_index
3254 && !evaluate_predicate (info
->array_index
, possible_truths
))
3255 hints
|= INLINE_HINT_array_index
;
3257 hints
|= INLINE_HINT_in_scc
;
3258 if (DECL_DECLARED_INLINE_P (node
->decl
))
3259 hints
|= INLINE_HINT_declared_inline
;
3261 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3262 known_vals
, known_contexts
, known_aggs
);
3263 gcc_checking_assert (size
>= 0);
3264 gcc_checking_assert (time
>= 0);
3265 time
= RDIV (time
, INLINE_TIME_SCALE
);
3266 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3267 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3269 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3270 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3276 *ret_min_size
= min_size
;
3283 /* Estimate size and time needed to execute callee of EDGE assuming that
3284 parameters known to be constant at caller of EDGE are propagated.
3285 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3286 and types for parameters. */
3289 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3290 vec
<tree
> known_vals
,
3291 vec
<ipa_polymorphic_call_context
>
3293 vec
<ipa_agg_jump_function_p
> known_aggs
,
3294 int *ret_size
, int *ret_time
,
3295 inline_hints
*hints
)
3299 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3301 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3302 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3305 /* Translate all conditions from callee representation into caller
3306 representation and symbolically evaluate predicate P into new predicate.
3308 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3309 is summary of function predicate P is from. OPERAND_MAP is array giving
3310 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3311 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3312 predicate under which callee is executed. OFFSET_MAP is an array of of
3313 offsets that need to be added to conditions, negative offset means that
3314 conditions relying on values passed by reference have to be discarded
3315 because they might not be preserved (and should be considered offset zero
3316 for other purposes). */
3318 static struct predicate
3319 remap_predicate (struct inline_summary
*info
,
3320 struct inline_summary
*callee_info
,
3321 struct predicate
*p
,
3322 vec
<int> operand_map
,
3323 vec
<int> offset_map
,
3324 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3327 struct predicate out
= true_predicate ();
3329 /* True predicate is easy. */
3330 if (true_predicate_p (p
))
3331 return *toplev_predicate
;
3332 for (i
= 0; p
->clause
[i
]; i
++)
3334 clause_t clause
= p
->clause
[i
];
3336 struct predicate clause_predicate
= false_predicate ();
3338 gcc_assert (i
< MAX_CLAUSES
);
3340 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3341 /* Do we have condition we can't disprove? */
3342 if (clause
& possible_truths
& (1 << cond
))
3344 struct predicate cond_predicate
;
3345 /* Work out if the condition can translate to predicate in the
3346 inlined function. */
3347 if (cond
>= predicate_first_dynamic_condition
)
3349 struct condition
*c
;
3351 c
= &(*callee_info
->conds
)[cond
3353 predicate_first_dynamic_condition
];
3354 /* See if we can remap condition operand to caller's operand.
3355 Otherwise give up. */
3356 if (!operand_map
.exists ()
3357 || (int) operand_map
.length () <= c
->operand_num
3358 || operand_map
[c
->operand_num
] == -1
3359 /* TODO: For non-aggregate conditions, adding an offset is
3360 basically an arithmetic jump function processing which
3361 we should support in future. */
3362 || ((!c
->agg_contents
|| !c
->by_ref
)
3363 && offset_map
[c
->operand_num
] > 0)
3364 || (c
->agg_contents
&& c
->by_ref
3365 && offset_map
[c
->operand_num
] < 0))
3366 cond_predicate
= true_predicate ();
3369 struct agg_position_info ap
;
3370 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3371 if (offset_delta
< 0)
3373 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3376 gcc_assert (!c
->agg_contents
3377 || c
->by_ref
|| offset_delta
== 0);
3378 ap
.offset
= c
->offset
+ offset_delta
;
3379 ap
.agg_contents
= c
->agg_contents
;
3380 ap
.by_ref
= c
->by_ref
;
3381 cond_predicate
= add_condition (info
,
3382 operand_map
[c
->operand_num
],
3383 &ap
, c
->code
, c
->val
);
3386 /* Fixed conditions remains same, construct single
3387 condition predicate. */
3390 cond_predicate
.clause
[0] = 1 << cond
;
3391 cond_predicate
.clause
[1] = 0;
3393 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3396 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3398 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3402 /* Update summary information of inline clones after inlining.
3403 Compute peak stack usage. */
3406 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3408 struct cgraph_edge
*e
;
3409 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3410 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3413 callee_info
->stack_frame_offset
3414 = caller_info
->stack_frame_offset
3415 + caller_info
->estimated_self_stack_size
;
3416 peak
= callee_info
->stack_frame_offset
3417 + callee_info
->estimated_self_stack_size
;
3418 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3419 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3420 ipa_propagate_frequency (node
);
3421 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3423 if (!e
->inline_failed
)
3424 inline_update_callee_summaries (e
->callee
, depth
);
3425 inline_edge_summary (e
)->loop_depth
+= depth
;
3427 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3428 inline_edge_summary (e
)->loop_depth
+= depth
;
3431 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3432 When functoin A is inlined in B and A calls C with parameter that
3433 changes with probability PROB1 and C is known to be passthroug
3434 of argument if B that change with probability PROB2, the probability
3435 of change is now PROB1*PROB2. */
3438 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3439 struct cgraph_edge
*edge
)
3441 if (ipa_node_params_sum
)
3444 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3445 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3446 struct inline_edge_summary
*inlined_es
3447 = inline_edge_summary (inlined_edge
);
3449 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3451 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3452 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3453 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3454 < (int) inlined_es
->param
.length ()))
3456 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3457 int prob1
= es
->param
[i
].change_prob
;
3458 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3459 int prob
= combine_probabilities (prob1
, prob2
);
3461 if (prob1
&& prob2
&& !prob
)
3464 es
->param
[i
].change_prob
= prob
;
3470 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3472 Remap predicates of callees of NODE. Rest of arguments match
3475 Also update change probabilities. */
3478 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3479 struct cgraph_node
*node
,
3480 struct inline_summary
*info
,
3481 struct inline_summary
*callee_info
,
3482 vec
<int> operand_map
,
3483 vec
<int> offset_map
,
3484 clause_t possible_truths
,
3485 struct predicate
*toplev_predicate
)
3487 struct cgraph_edge
*e
;
3488 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3490 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3493 if (e
->inline_failed
)
3495 remap_edge_change_prob (inlined_edge
, e
);
3499 p
= remap_predicate (info
, callee_info
,
3500 es
->predicate
, operand_map
, offset_map
,
3501 possible_truths
, toplev_predicate
);
3502 edge_set_predicate (e
, &p
);
3505 edge_set_predicate (e
, toplev_predicate
);
3508 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3509 operand_map
, offset_map
, possible_truths
,
3512 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3514 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3517 remap_edge_change_prob (inlined_edge
, e
);
3520 p
= remap_predicate (info
, callee_info
,
3521 es
->predicate
, operand_map
, offset_map
,
3522 possible_truths
, toplev_predicate
);
3523 edge_set_predicate (e
, &p
);
3526 edge_set_predicate (e
, toplev_predicate
);
3530 /* Same as remap_predicate, but set result into hint *HINT. */
3533 remap_hint_predicate (struct inline_summary
*info
,
3534 struct inline_summary
*callee_info
,
3535 struct predicate
**hint
,
3536 vec
<int> operand_map
,
3537 vec
<int> offset_map
,
3538 clause_t possible_truths
,
3539 struct predicate
*toplev_predicate
)
3545 p
= remap_predicate (info
, callee_info
,
3547 operand_map
, offset_map
,
3548 possible_truths
, toplev_predicate
);
3549 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3552 set_hint_predicate (hint
, p
);
3554 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3558 /* We inlined EDGE. Update summary of the function we inlined into. */
3561 inline_merge_summary (struct cgraph_edge
*edge
)
3563 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3564 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3565 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3566 struct inline_summary
*info
= inline_summaries
->get (to
);
3567 clause_t clause
= 0; /* not_inline is known to be false. */
3569 vec
<int> operand_map
= vNULL
;
3570 vec
<int> offset_map
= vNULL
;
3572 struct predicate toplev_predicate
;
3573 struct predicate true_p
= true_predicate ();
3574 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3577 toplev_predicate
= *es
->predicate
;
3579 toplev_predicate
= true_predicate ();
3581 if (callee_info
->conds
)
3582 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3583 if (ipa_node_params_sum
&& callee_info
->conds
)
3585 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3586 int count
= ipa_get_cs_argument_count (args
);
3591 operand_map
.safe_grow_cleared (count
);
3592 offset_map
.safe_grow_cleared (count
);
3594 for (i
= 0; i
< count
; i
++)
3596 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3599 /* TODO: handle non-NOPs when merging. */
3600 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3602 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3603 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3604 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3607 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3609 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3610 if (offset
>= 0 && offset
< INT_MAX
)
3612 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3613 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3615 offset_map
[i
] = offset
;
3618 operand_map
[i
] = map
;
3619 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3622 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3624 struct predicate p
= remap_predicate (info
, callee_info
,
3625 &e
->predicate
, operand_map
,
3628 if (!false_predicate_p (&p
))
3630 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3631 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3632 int prob
= predicate_probability (callee_info
->conds
,
3635 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3636 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3637 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3638 if (prob
!= REG_BR_PROB_BASE
3639 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3641 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3642 (double) prob
/ REG_BR_PROB_BASE
);
3644 account_size_time (info
, e
->size
, add_time
, &p
);
3647 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3648 offset_map
, clause
, &toplev_predicate
);
3649 remap_hint_predicate (info
, callee_info
,
3650 &callee_info
->loop_iterations
,
3651 operand_map
, offset_map
, clause
, &toplev_predicate
);
3652 remap_hint_predicate (info
, callee_info
,
3653 &callee_info
->loop_stride
,
3654 operand_map
, offset_map
, clause
, &toplev_predicate
);
3655 remap_hint_predicate (info
, callee_info
,
3656 &callee_info
->array_index
,
3657 operand_map
, offset_map
, clause
, &toplev_predicate
);
3659 inline_update_callee_summaries (edge
->callee
,
3660 inline_edge_summary (edge
)->loop_depth
);
3662 /* We do not maintain predicates of inlined edges, free it. */
3663 edge_set_predicate (edge
, &true_p
);
3664 /* Similarly remove param summaries. */
3665 es
->param
.release ();
3666 operand_map
.release ();
3667 offset_map
.release ();
3670 /* For performance reasons inline_merge_summary is not updating overall size
3671 and time. Recompute it. */
3674 inline_update_overall_summary (struct cgraph_node
*node
)
3676 struct inline_summary
*info
= inline_summaries
->get (node
);
3682 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3684 info
->size
+= e
->size
, info
->time
+= e
->time
;
3685 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3686 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3688 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3690 ~(clause_t
) (1 << predicate_false_condition
),
3691 vNULL
, vNULL
, vNULL
);
3692 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3693 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3696 /* Return hints derrived from EDGE. */
3698 simple_edge_hints (struct cgraph_edge
*edge
)
3701 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3702 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3703 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3704 if (inline_summaries
->get (to
)->scc_no
3705 && inline_summaries
->get (to
)->scc_no
3706 == inline_summaries
->get (callee
)->scc_no
3707 && !edge
->recursive_p ())
3708 hints
|= INLINE_HINT_same_scc
;
3710 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3711 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3713 hints
|= INLINE_HINT_cross_module
;
3718 /* Estimate the time cost for the caller when inlining EDGE.
3719 Only to be called via estimate_edge_time, that handles the
3722 When caching, also update the cache entry. Compute both time and
3723 size, since we always need both metrics eventually. */
3726 do_estimate_edge_time (struct cgraph_edge
*edge
)
3731 struct cgraph_node
*callee
;
3733 vec
<tree
> known_vals
;
3734 vec
<ipa_polymorphic_call_context
> known_contexts
;
3735 vec
<ipa_agg_jump_function_p
> known_aggs
;
3736 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3739 callee
= edge
->callee
->ultimate_alias_target ();
3741 gcc_checking_assert (edge
->inline_failed
);
3742 evaluate_properties_for_edge (edge
, true,
3743 &clause
, &known_vals
, &known_contexts
,
3745 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3746 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3748 /* When we have profile feedback, we can quite safely identify hot
3749 edges and for those we disable size limits. Don't do that when
3750 probability that caller will call the callee is low however, since it
3751 may hurt optimization of the caller's hot path. */
3752 if (edge
->count
&& edge
->maybe_hot_p ()
3754 > (edge
->caller
->global
.inlined_to
3755 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3756 hints
|= INLINE_HINT_known_hot
;
3758 known_vals
.release ();
3759 known_contexts
.release ();
3760 known_aggs
.release ();
3761 gcc_checking_assert (size
>= 0);
3762 gcc_checking_assert (time
>= 0);
3764 /* When caching, update the cache entry. */
3765 if (edge_growth_cache
.exists ())
3767 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3768 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3769 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3770 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3772 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3773 hints
|= simple_edge_hints (edge
);
3774 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3780 /* Return estimated callee growth after inlining EDGE.
3781 Only to be called via estimate_edge_size. */
3784 do_estimate_edge_size (struct cgraph_edge
*edge
)
3787 struct cgraph_node
*callee
;
3789 vec
<tree
> known_vals
;
3790 vec
<ipa_polymorphic_call_context
> known_contexts
;
3791 vec
<ipa_agg_jump_function_p
> known_aggs
;
3793 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3795 if (edge_growth_cache
.exists ())
3797 do_estimate_edge_time (edge
);
3798 size
= edge_growth_cache
[edge
->uid
].size
;
3799 gcc_checking_assert (size
);
3800 return size
- (size
> 0);
3803 callee
= edge
->callee
->ultimate_alias_target ();
3805 /* Early inliner runs without caching, go ahead and do the dirty work. */
3806 gcc_checking_assert (edge
->inline_failed
);
3807 evaluate_properties_for_edge (edge
, true,
3808 &clause
, &known_vals
, &known_contexts
,
3810 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3811 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3812 known_vals
.release ();
3813 known_contexts
.release ();
3814 known_aggs
.release ();
3819 /* Estimate the growth of the caller when inlining EDGE.
3820 Only to be called via estimate_edge_size. */
3823 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3826 struct cgraph_node
*callee
;
3828 vec
<tree
> known_vals
;
3829 vec
<ipa_polymorphic_call_context
> known_contexts
;
3830 vec
<ipa_agg_jump_function_p
> known_aggs
;
3832 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3834 if (edge_growth_cache
.exists ())
3836 do_estimate_edge_time (edge
);
3837 hints
= edge_growth_cache
[edge
->uid
].hints
;
3838 gcc_checking_assert (hints
);
3842 callee
= edge
->callee
->ultimate_alias_target ();
3844 /* Early inliner runs without caching, go ahead and do the dirty work. */
3845 gcc_checking_assert (edge
->inline_failed
);
3846 evaluate_properties_for_edge (edge
, true,
3847 &clause
, &known_vals
, &known_contexts
,
3849 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3850 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3851 known_vals
.release ();
3852 known_contexts
.release ();
3853 known_aggs
.release ();
3854 hints
|= simple_edge_hints (edge
);
3859 /* Estimate self time of the function NODE after inlining EDGE. */
3862 estimate_time_after_inlining (struct cgraph_node
*node
,
3863 struct cgraph_edge
*edge
)
3865 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3866 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3869 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3872 if (time
> MAX_TIME
)
3876 return inline_summaries
->get (node
)->time
;
3880 /* Estimate the size of NODE after inlining EDGE which should be an
3881 edge to either NODE or a call inlined into NODE. */
3884 estimate_size_after_inlining (struct cgraph_node
*node
,
3885 struct cgraph_edge
*edge
)
3887 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3888 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3890 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3891 gcc_assert (size
>= 0);
3894 return inline_summaries
->get (node
)->size
;
3900 struct cgraph_node
*node
;
3901 bool self_recursive
;
3907 /* Worker for do_estimate_growth. Collect growth for all callers. */
3910 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3912 struct cgraph_edge
*e
;
3913 struct growth_data
*d
= (struct growth_data
*) data
;
3915 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3917 gcc_checking_assert (e
->inline_failed
);
3919 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3921 d
->uninlinable
= true;
3925 if (e
->recursive_p ())
3927 d
->self_recursive
= true;
3930 d
->growth
+= estimate_edge_growth (e
);
3936 /* Estimate the growth caused by inlining NODE into all callees. */
3939 estimate_growth (struct cgraph_node
*node
)
3941 struct growth_data d
= { node
, false, false, 0 };
3942 struct inline_summary
*info
= inline_summaries
->get (node
);
3944 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3946 /* For self recursive functions the growth estimation really should be
3947 infinity. We don't want to return very large values because the growth
3948 plays various roles in badness computation fractions. Be sure to not
3949 return zero or negative growths. */
3950 if (d
.self_recursive
)
3951 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3952 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3956 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3957 d
.growth
-= info
->size
;
3958 /* COMDAT functions are very often not shared across multiple units
3959 since they come from various template instantiations.
3960 Take this into account. */
3961 else if (DECL_COMDAT (node
->decl
)
3962 && node
->can_remove_if_no_direct_calls_p ())
3963 d
.growth
-= (info
->size
3964 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3971 /* Verify if there are fewer than MAX_CALLERS. */
3974 check_callers (cgraph_node
*node
, int *max_callers
)
3978 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
3981 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3985 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3989 FOR_EACH_ALIAS (node
, ref
)
3990 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3997 /* Make cheap estimation if growth of NODE is likely positive knowing
3998 EDGE_GROWTH of one particular edge.
3999 We assume that most of other edges will have similar growth
4000 and skip computation if there are too many callers. */
4003 growth_likely_positive (struct cgraph_node
*node
,
4007 struct cgraph_edge
*e
;
4008 gcc_checking_assert (edge_growth
> 0);
4010 /* First quickly check if NODE is removable at all. */
4011 if (DECL_EXTERNAL (node
->decl
))
4013 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4014 || node
->address_taken
)
4017 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4019 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4023 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4028 FOR_EACH_ALIAS (node
, ref
)
4029 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4032 /* Unlike for functions called once, we play unsafe with
4033 COMDATs. We can allow that since we know functions
4034 in consideration are small (and thus risk is small) and
4035 moreover grow estimates already accounts that COMDAT
4036 functions may or may not disappear when eliminated from
4037 current unit. With good probability making aggressive
4038 choice in all units is going to make overall program
4040 if (DECL_COMDAT (node
->decl
))
4042 if (!node
->can_remove_if_no_direct_calls_p ())
4045 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4048 return estimate_growth (node
) > 0;
4052 /* This function performs intraprocedural analysis in NODE that is required to
4053 inline indirect calls. */
4056 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4058 ipa_analyze_node (node
);
4059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4061 ipa_print_node_params (dump_file
, node
);
4062 ipa_print_node_jump_functions (dump_file
, node
);
4067 /* Note function body size. */
4070 inline_analyze_function (struct cgraph_node
*node
)
4072 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4075 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4076 node
->name (), node
->order
);
4077 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4078 inline_indirect_intraprocedural_analysis (node
);
4079 compute_inline_parameters (node
, false);
4082 struct cgraph_edge
*e
;
4083 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4085 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4086 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4087 e
->call_stmt_cannot_inline_p
= true;
4089 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4091 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4092 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4093 e
->call_stmt_cannot_inline_p
= true;
4101 /* Called when new function is inserted to callgraph late. */
4104 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4106 inline_analyze_function (node
);
4109 /* Note function body size. */
4112 inline_generate_summary (void)
4114 struct cgraph_node
*node
;
4116 /* When not optimizing, do not bother to analyze. Inlining is still done
4117 because edge redirection needs to happen there. */
4118 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4121 if (!inline_summaries
)
4122 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4124 inline_summaries
->enable_insertion_hook ();
4126 ipa_register_cgraph_hooks ();
4127 inline_free_summary ();
4129 FOR_EACH_DEFINED_FUNCTION (node
)
4131 inline_analyze_function (node
);
4135 /* Read predicate from IB. */
4137 static struct predicate
4138 read_predicate (struct lto_input_block
*ib
)
4140 struct predicate out
;
4146 gcc_assert (k
<= MAX_CLAUSES
);
4147 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4151 /* Zero-initialize the remaining clauses in OUT. */
4152 while (k
<= MAX_CLAUSES
)
4153 out
.clause
[k
++] = 0;
4159 /* Write inline summary for edge E to OB. */
4162 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4164 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4168 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4169 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4170 es
->loop_depth
= streamer_read_uhwi (ib
);
4171 p
= read_predicate (ib
);
4172 edge_set_predicate (e
, &p
);
4173 length
= streamer_read_uhwi (ib
);
4176 es
->param
.safe_grow_cleared (length
);
4177 for (i
= 0; i
< length
; i
++)
4178 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4183 /* Stream in inline summaries from the section. */
4186 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4189 const struct lto_function_header
*header
=
4190 (const struct lto_function_header
*) data
;
4191 const int cfg_offset
= sizeof (struct lto_function_header
);
4192 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4193 const int string_offset
= main_offset
+ header
->main_size
;
4194 struct data_in
*data_in
;
4195 unsigned int i
, count2
, j
;
4196 unsigned int f_count
;
4198 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4199 file_data
->mode_table
);
4202 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4203 header
->string_size
, vNULL
);
4204 f_count
= streamer_read_uhwi (&ib
);
4205 for (i
= 0; i
< f_count
; i
++)
4208 struct cgraph_node
*node
;
4209 struct inline_summary
*info
;
4210 lto_symtab_encoder_t encoder
;
4211 struct bitpack_d bp
;
4212 struct cgraph_edge
*e
;
4215 index
= streamer_read_uhwi (&ib
);
4216 encoder
= file_data
->symtab_node_encoder
;
4217 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4219 info
= inline_summaries
->get (node
);
4221 info
->estimated_stack_size
4222 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4223 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4224 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4226 bp
= streamer_read_bitpack (&ib
);
4227 info
->inlinable
= bp_unpack_value (&bp
, 1);
4228 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4230 count2
= streamer_read_uhwi (&ib
);
4231 gcc_assert (!info
->conds
);
4232 for (j
= 0; j
< count2
; j
++)
4235 c
.operand_num
= streamer_read_uhwi (&ib
);
4236 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4237 c
.val
= stream_read_tree (&ib
, data_in
);
4238 bp
= streamer_read_bitpack (&ib
);
4239 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4240 c
.by_ref
= bp_unpack_value (&bp
, 1);
4242 c
.offset
= streamer_read_uhwi (&ib
);
4243 vec_safe_push (info
->conds
, c
);
4245 count2
= streamer_read_uhwi (&ib
);
4246 gcc_assert (!info
->entry
);
4247 for (j
= 0; j
< count2
; j
++)
4249 struct size_time_entry e
;
4251 e
.size
= streamer_read_uhwi (&ib
);
4252 e
.time
= streamer_read_uhwi (&ib
);
4253 e
.predicate
= read_predicate (&ib
);
4255 vec_safe_push (info
->entry
, e
);
4258 p
= read_predicate (&ib
);
4259 set_hint_predicate (&info
->loop_iterations
, p
);
4260 p
= read_predicate (&ib
);
4261 set_hint_predicate (&info
->loop_stride
, p
);
4262 p
= read_predicate (&ib
);
4263 set_hint_predicate (&info
->array_index
, p
);
4264 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4265 read_inline_edge_summary (&ib
, e
);
4266 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4267 read_inline_edge_summary (&ib
, e
);
4270 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4272 lto_data_in_delete (data_in
);
4276 /* Read inline summary. Jump functions are shared among ipa-cp
4277 and inliner, so when ipa-cp is active, we don't need to write them
4281 inline_read_summary (void)
4283 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4284 struct lto_file_decl_data
*file_data
;
4287 inline_summary_alloc ();
4289 while ((file_data
= file_data_vec
[j
++]))
4292 const char *data
= lto_get_section_data (file_data
,
4293 LTO_section_inline_summary
,
4296 inline_read_section (file_data
, data
, len
);
4298 /* Fatal error here. We do not want to support compiling ltrans units
4299 with different version of compiler or different flags than the WPA
4300 unit, so this should never happen. */
4301 fatal_error (input_location
,
4302 "ipa inline summary is missing in input file");
4306 ipa_register_cgraph_hooks ();
4308 ipa_prop_read_jump_functions ();
4311 gcc_assert (inline_summaries
);
4312 inline_summaries
->enable_insertion_hook ();
4316 /* Write predicate P to OB. */
4319 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4323 for (j
= 0; p
->clause
[j
]; j
++)
4325 gcc_assert (j
< MAX_CLAUSES
);
4326 streamer_write_uhwi (ob
, p
->clause
[j
]);
4328 streamer_write_uhwi (ob
, 0);
4332 /* Write inline summary for edge E to OB. */
4335 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4337 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4340 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4341 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4342 streamer_write_uhwi (ob
, es
->loop_depth
);
4343 write_predicate (ob
, es
->predicate
);
4344 streamer_write_uhwi (ob
, es
->param
.length ());
4345 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4346 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4350 /* Write inline summary for node in SET.
4351 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4352 active, we don't need to write them twice. */
4355 inline_write_summary (void)
4357 struct cgraph_node
*node
;
4358 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4359 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4360 unsigned int count
= 0;
4363 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4365 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4366 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4367 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4370 streamer_write_uhwi (ob
, count
);
4372 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4374 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4375 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4376 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4378 struct inline_summary
*info
= inline_summaries
->get (node
);
4379 struct bitpack_d bp
;
4380 struct cgraph_edge
*edge
;
4383 struct condition
*c
;
4385 streamer_write_uhwi (ob
,
4386 lto_symtab_encoder_encode (encoder
,
4389 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4390 streamer_write_hwi (ob
, info
->self_size
);
4391 streamer_write_hwi (ob
, info
->self_time
);
4392 bp
= bitpack_create (ob
->main_stream
);
4393 bp_pack_value (&bp
, info
->inlinable
, 1);
4394 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4395 streamer_write_bitpack (&bp
);
4396 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4397 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4399 streamer_write_uhwi (ob
, c
->operand_num
);
4400 streamer_write_uhwi (ob
, c
->code
);
4401 stream_write_tree (ob
, c
->val
, true);
4402 bp
= bitpack_create (ob
->main_stream
);
4403 bp_pack_value (&bp
, c
->agg_contents
, 1);
4404 bp_pack_value (&bp
, c
->by_ref
, 1);
4405 streamer_write_bitpack (&bp
);
4406 if (c
->agg_contents
)
4407 streamer_write_uhwi (ob
, c
->offset
);
4409 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4410 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4412 streamer_write_uhwi (ob
, e
->size
);
4413 streamer_write_uhwi (ob
, e
->time
);
4414 write_predicate (ob
, &e
->predicate
);
4416 write_predicate (ob
, info
->loop_iterations
);
4417 write_predicate (ob
, info
->loop_stride
);
4418 write_predicate (ob
, info
->array_index
);
4419 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4420 write_inline_edge_summary (ob
, edge
);
4421 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4422 write_inline_edge_summary (ob
, edge
);
4425 streamer_write_char_stream (ob
->main_stream
, 0);
4426 produce_asm (ob
, NULL
);
4427 destroy_output_block (ob
);
4429 if (optimize
&& !flag_ipa_cp
)
4430 ipa_prop_write_jump_functions ();
4434 /* Release inline summary. */
4437 inline_free_summary (void)
4439 struct cgraph_node
*node
;
4440 if (edge_removal_hook_holder
)
4441 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4442 edge_removal_hook_holder
= NULL
;
4443 if (edge_duplication_hook_holder
)
4444 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4445 edge_duplication_hook_holder
= NULL
;
4446 if (!inline_edge_summary_vec
.exists ())
4448 FOR_EACH_DEFINED_FUNCTION (node
)
4450 reset_inline_summary (node
, inline_summaries
->get (node
));
4451 inline_summaries
->release ();
4452 inline_summaries
= NULL
;
4453 inline_edge_summary_vec
.release ();
4454 if (edge_predicate_pool
)
4455 free_alloc_pool (edge_predicate_pool
);
4456 edge_predicate_pool
= 0;