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
<int> node_growth_cache
;
171 vec
<edge_growth_cache_entry
> edge_growth_cache
;
173 /* Edge predicates goes here. */
174 static alloc_pool edge_predicate_pool
;
176 /* Return true predicate (tautology).
177 We represent it by empty list of clauses. */
179 static inline struct predicate
180 true_predicate (void)
188 /* Return predicate testing single condition number COND. */
190 static inline struct predicate
191 single_cond_predicate (int cond
)
194 p
.clause
[0] = 1 << cond
;
200 /* Return false predicate. First clause require false condition. */
202 static inline struct predicate
203 false_predicate (void)
205 return single_cond_predicate (predicate_false_condition
);
209 /* Return true if P is (true). */
212 true_predicate_p (struct predicate
*p
)
214 return !p
->clause
[0];
218 /* Return true if P is (false). */
221 false_predicate_p (struct predicate
*p
)
223 if (p
->clause
[0] == (1 << predicate_false_condition
))
225 gcc_checking_assert (!p
->clause
[1]
226 && p
->clause
[0] == 1 << predicate_false_condition
);
233 /* Return predicate that is set true when function is not inlined. */
235 static inline struct predicate
236 not_inlined_predicate (void)
238 return single_cond_predicate (predicate_not_inlined_condition
);
241 /* Simple description of whether a memory load or a condition refers to a load
242 from an aggregate and if so, how and where from in the aggregate.
243 Individual fields have the same meaning like fields with the same name in
246 struct agg_position_info
248 HOST_WIDE_INT offset
;
253 /* Add condition to condition list CONDS. AGGPOS describes whether the used
254 oprand is loaded from an aggregate and where in the aggregate it is. It can
255 be NULL, which means this not a load from an aggregate. */
257 static struct predicate
258 add_condition (struct inline_summary
*summary
, int operand_num
,
259 struct agg_position_info
*aggpos
,
260 enum tree_code code
, tree val
)
264 struct condition new_cond
;
265 HOST_WIDE_INT offset
;
266 bool agg_contents
, by_ref
;
270 offset
= aggpos
->offset
;
271 agg_contents
= aggpos
->agg_contents
;
272 by_ref
= aggpos
->by_ref
;
277 agg_contents
= false;
281 gcc_checking_assert (operand_num
>= 0);
282 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
284 if (c
->operand_num
== operand_num
287 && c
->agg_contents
== agg_contents
288 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
289 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
291 /* Too many conditions. Give up and return constant true. */
292 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
293 return true_predicate ();
295 new_cond
.operand_num
= operand_num
;
296 new_cond
.code
= code
;
298 new_cond
.agg_contents
= agg_contents
;
299 new_cond
.by_ref
= by_ref
;
300 new_cond
.offset
= offset
;
301 vec_safe_push (summary
->conds
, new_cond
);
302 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
306 /* Add clause CLAUSE into the predicate P. */
309 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
313 int insert_here
= -1;
320 /* False clause makes the whole predicate false. Kill the other variants. */
321 if (clause
== (1 << predicate_false_condition
))
323 p
->clause
[0] = (1 << predicate_false_condition
);
327 if (false_predicate_p (p
))
330 /* No one should be silly enough to add false into nontrivial clauses. */
331 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
333 /* Look where to insert the clause. At the same time prune out
334 clauses of P that are implied by the new clause and thus
336 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
338 p
->clause
[i2
] = p
->clause
[i
];
343 /* If p->clause[i] implies clause, there is nothing to add. */
344 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
346 /* We had nothing to add, none of clauses should've become
348 gcc_checking_assert (i
== i2
);
352 if (p
->clause
[i
] < clause
&& insert_here
< 0)
355 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
356 Otherwise the p->clause[i] has to stay. */
357 if ((p
->clause
[i
] & clause
) != clause
)
361 /* Look for clauses that are obviously true. I.e.
362 op0 == 5 || op0 != 5. */
363 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
366 if (!(clause
& (1 << c1
)))
368 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
369 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
370 and thus there is no point for looking for them. */
371 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
373 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
374 if (clause
& (1 << c2
))
377 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
379 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
380 if (cc1
->operand_num
== cc2
->operand_num
381 && cc1
->val
== cc2
->val
382 && cc2
->code
!= IS_NOT_CONSTANT
383 && cc2
->code
!= CHANGED
384 && cc1
->code
== invert_tree_comparison (cc2
->code
,
385 HONOR_NANS (cc1
->val
)))
391 /* We run out of variants. Be conservative in positive direction. */
392 if (i2
== MAX_CLAUSES
)
394 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
395 p
->clause
[i2
+ 1] = 0;
396 if (insert_here
>= 0)
397 for (; i2
> insert_here
; i2
--)
398 p
->clause
[i2
] = p
->clause
[i2
- 1];
401 p
->clause
[insert_here
] = clause
;
407 static struct predicate
408 and_predicates (conditions conditions
,
409 struct predicate
*p
, struct predicate
*p2
)
411 struct predicate out
= *p
;
414 /* Avoid busy work. */
415 if (false_predicate_p (p2
) || true_predicate_p (p
))
417 if (false_predicate_p (p
) || true_predicate_p (p2
))
420 /* See how far predicates match. */
421 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
423 gcc_checking_assert (i
< MAX_CLAUSES
);
426 /* Combine the predicates rest. */
427 for (; p2
->clause
[i
]; i
++)
429 gcc_checking_assert (i
< MAX_CLAUSES
);
430 add_clause (conditions
, &out
, p2
->clause
[i
]);
436 /* Return true if predicates are obviously equal. */
439 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
442 for (i
= 0; p
->clause
[i
]; i
++)
444 gcc_checking_assert (i
< MAX_CLAUSES
);
445 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
446 gcc_checking_assert (!p2
->clause
[i
]
447 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
448 if (p
->clause
[i
] != p2
->clause
[i
])
451 return !p2
->clause
[i
];
457 static struct predicate
458 or_predicates (conditions conditions
,
459 struct predicate
*p
, struct predicate
*p2
)
461 struct predicate out
= true_predicate ();
464 /* Avoid busy work. */
465 if (false_predicate_p (p2
) || true_predicate_p (p
))
467 if (false_predicate_p (p
) || true_predicate_p (p2
))
469 if (predicates_equal_p (p
, p2
))
472 /* OK, combine the predicates. */
473 for (i
= 0; p
->clause
[i
]; i
++)
474 for (j
= 0; p2
->clause
[j
]; j
++)
476 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
477 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
483 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
484 if predicate P is known to be false. */
487 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
491 /* True remains true. */
492 if (true_predicate_p (p
))
495 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
497 /* See if we can find clause we can disprove. */
498 for (i
= 0; p
->clause
[i
]; i
++)
500 gcc_checking_assert (i
< MAX_CLAUSES
);
501 if (!(p
->clause
[i
] & possible_truths
))
507 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
508 instruction will be recomputed per invocation of the inlined call. */
511 predicate_probability (conditions conds
,
512 struct predicate
*p
, clause_t possible_truths
,
513 vec
<inline_param_summary
> inline_param_summary
)
516 int combined_prob
= REG_BR_PROB_BASE
;
518 /* True remains true. */
519 if (true_predicate_p (p
))
520 return REG_BR_PROB_BASE
;
522 if (false_predicate_p (p
))
525 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
527 /* See if we can find clause we can disprove. */
528 for (i
= 0; p
->clause
[i
]; i
++)
530 gcc_checking_assert (i
< MAX_CLAUSES
);
531 if (!(p
->clause
[i
] & possible_truths
))
537 if (!inline_param_summary
.exists ())
538 return REG_BR_PROB_BASE
;
539 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
540 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
542 if (i2
>= predicate_first_dynamic_condition
)
545 &(*conds
)[i2
- predicate_first_dynamic_condition
];
546 if (c
->code
== CHANGED
548 (int) inline_param_summary
.length ()))
551 inline_param_summary
[c
->operand_num
].change_prob
;
552 this_prob
= MAX (this_prob
, iprob
);
555 this_prob
= REG_BR_PROB_BASE
;
558 this_prob
= REG_BR_PROB_BASE
;
560 combined_prob
= MIN (this_prob
, combined_prob
);
565 return combined_prob
;
569 /* Dump conditional COND. */
572 dump_condition (FILE *f
, conditions conditions
, int cond
)
575 if (cond
== predicate_false_condition
)
576 fprintf (f
, "false");
577 else if (cond
== predicate_not_inlined_condition
)
578 fprintf (f
, "not inlined");
581 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
582 fprintf (f
, "op%i", c
->operand_num
);
584 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
585 c
->by_ref
? "ref " : "", c
->offset
);
586 if (c
->code
== IS_NOT_CONSTANT
)
588 fprintf (f
, " not constant");
591 if (c
->code
== CHANGED
)
593 fprintf (f
, " changed");
596 fprintf (f
, " %s ", op_symbol_code (c
->code
));
597 print_generic_expr (f
, c
->val
, 1);
602 /* Dump clause CLAUSE. */
605 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
612 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
613 if (clause
& (1 << i
))
618 dump_condition (f
, conds
, i
);
624 /* Dump predicate PREDICATE. */
627 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
630 if (true_predicate_p (pred
))
631 dump_clause (f
, conds
, 0);
633 for (i
= 0; pred
->clause
[i
]; i
++)
637 dump_clause (f
, conds
, pred
->clause
[i
]);
643 /* Dump inline hints. */
645 dump_inline_hints (FILE *f
, inline_hints hints
)
649 fprintf (f
, "inline hints:");
650 if (hints
& INLINE_HINT_indirect_call
)
652 hints
&= ~INLINE_HINT_indirect_call
;
653 fprintf (f
, " indirect_call");
655 if (hints
& INLINE_HINT_loop_iterations
)
657 hints
&= ~INLINE_HINT_loop_iterations
;
658 fprintf (f
, " loop_iterations");
660 if (hints
& INLINE_HINT_loop_stride
)
662 hints
&= ~INLINE_HINT_loop_stride
;
663 fprintf (f
, " loop_stride");
665 if (hints
& INLINE_HINT_same_scc
)
667 hints
&= ~INLINE_HINT_same_scc
;
668 fprintf (f
, " same_scc");
670 if (hints
& INLINE_HINT_in_scc
)
672 hints
&= ~INLINE_HINT_in_scc
;
673 fprintf (f
, " in_scc");
675 if (hints
& INLINE_HINT_cross_module
)
677 hints
&= ~INLINE_HINT_cross_module
;
678 fprintf (f
, " cross_module");
680 if (hints
& INLINE_HINT_declared_inline
)
682 hints
&= ~INLINE_HINT_declared_inline
;
683 fprintf (f
, " declared_inline");
685 if (hints
& INLINE_HINT_array_index
)
687 hints
&= ~INLINE_HINT_array_index
;
688 fprintf (f
, " array_index");
690 if (hints
& INLINE_HINT_known_hot
)
692 hints
&= ~INLINE_HINT_known_hot
;
693 fprintf (f
, " known_hot");
699 /* Record SIZE and TIME under condition PRED into the inline summary. */
702 account_size_time (struct inline_summary
*summary
, int size
, int time
,
703 struct predicate
*pred
)
709 if (false_predicate_p (pred
))
712 /* We need to create initial empty unconitional clause, but otherwie
713 we don't need to account empty times and sizes. */
714 if (!size
&& !time
&& summary
->entry
)
717 /* Watch overflow that might result from insane profiles. */
718 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
719 time
= MAX_TIME
* INLINE_TIME_SCALE
;
720 gcc_assert (time
>= 0);
722 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
723 if (predicates_equal_p (&e
->predicate
, pred
))
732 e
= &(*summary
->entry
)[0];
733 gcc_assert (!e
->predicate
.clause
[0]);
734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
736 "\t\tReached limit on number of entries, "
737 "ignoring the predicate.");
739 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
742 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
743 ((double) size
) / INLINE_SIZE_SCALE
,
744 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
745 dump_predicate (dump_file
, summary
->conds
, pred
);
749 struct size_time_entry new_entry
;
750 new_entry
.size
= size
;
751 new_entry
.time
= time
;
752 new_entry
.predicate
= *pred
;
753 vec_safe_push (summary
->entry
, new_entry
);
759 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
760 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
764 /* Set predicate for edge E. */
767 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
769 struct inline_edge_summary
*es
= inline_edge_summary (e
);
771 /* If the edge is determined to be never executed, redirect it
772 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
773 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
775 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
777 e
->redirect_callee (cgraph_node::get_create
778 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
779 e
->inline_failed
= CIF_UNREACHABLE
;
780 es
->call_stmt_size
= 0;
781 es
->call_stmt_time
= 0;
783 callee
->remove_symbol_and_inline_clones ();
785 if (predicate
&& !true_predicate_p (predicate
))
788 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
789 *es
->predicate
= *predicate
;
794 pool_free (edge_predicate_pool
, es
->predicate
);
795 es
->predicate
= NULL
;
799 /* Set predicate for hint *P. */
802 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
804 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
807 pool_free (edge_predicate_pool
, *p
);
813 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
819 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
820 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
821 Return clause of possible truths. When INLINE_P is true, assume that we are
824 ERROR_MARK means compile time invariant. */
827 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
829 vec
<tree
> known_vals
,
830 vec
<ipa_agg_jump_function_p
>
833 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
834 struct inline_summary
*info
= inline_summaries
->get (node
);
838 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
843 /* We allow call stmt to have fewer arguments than the callee function
844 (especially for K&R style programs). So bound check here (we assume
845 known_aggs vector, if non-NULL, has the same length as
847 gcc_checking_assert (!known_aggs
.exists ()
848 || (known_vals
.length () == known_aggs
.length ()));
849 if (c
->operand_num
>= (int) known_vals
.length ())
851 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
857 struct ipa_agg_jump_function
*agg
;
859 if (c
->code
== CHANGED
861 && (known_vals
[c
->operand_num
] == error_mark_node
))
864 if (known_aggs
.exists ())
866 agg
= known_aggs
[c
->operand_num
];
867 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
874 val
= known_vals
[c
->operand_num
];
875 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
881 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
884 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
887 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
888 TYPE_SIZE (TREE_TYPE (val
)), 0))
890 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
893 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
896 if (res
&& integer_zerop (res
))
899 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
905 /* Work out what conditions might be true at invocation of E. */
908 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
909 clause_t
*clause_ptr
,
910 vec
<tree
> *known_vals_ptr
,
911 vec
<ipa_polymorphic_call_context
>
913 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
915 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
916 struct inline_summary
*info
= inline_summaries
->get (callee
);
917 vec
<tree
> known_vals
= vNULL
;
918 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
921 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
923 known_vals_ptr
->create (0);
924 if (known_contexts_ptr
)
925 known_contexts_ptr
->create (0);
927 if (ipa_node_params_sum
928 && !e
->call_stmt_cannot_inline_p
929 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
931 struct ipa_node_params
*parms_info
;
932 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
933 struct inline_edge_summary
*es
= inline_edge_summary (e
);
934 int i
, count
= ipa_get_cs_argument_count (args
);
936 if (e
->caller
->global
.inlined_to
)
937 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
939 parms_info
= IPA_NODE_REF (e
->caller
);
941 if (count
&& (info
->conds
|| known_vals_ptr
))
942 known_vals
.safe_grow_cleared (count
);
943 if (count
&& (info
->conds
|| known_aggs_ptr
))
944 known_aggs
.safe_grow_cleared (count
);
945 if (count
&& known_contexts_ptr
)
946 known_contexts_ptr
->safe_grow_cleared (count
);
948 for (i
= 0; i
< count
; i
++)
950 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
951 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
953 if (!cst
&& e
->call_stmt
954 && i
< (int)gimple_call_num_args (e
->call_stmt
))
956 cst
= gimple_call_arg (e
->call_stmt
, i
);
957 if (!is_gimple_min_invariant (cst
))
962 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
963 if (known_vals
.exists ())
966 else if (inline_p
&& !es
->param
[i
].change_prob
)
967 known_vals
[i
] = error_mark_node
;
969 if (known_contexts_ptr
)
970 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
972 /* TODO: When IPA-CP starts propagating and merging aggregate jump
973 functions, use its knowledge of the caller too, just like the
974 scalar case above. */
975 known_aggs
[i
] = &jf
->agg
;
978 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
979 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
981 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
983 if (count
&& (info
->conds
|| known_vals_ptr
))
984 known_vals
.safe_grow_cleared (count
);
985 for (i
= 0; i
< count
; i
++)
987 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
988 if (!is_gimple_min_invariant (cst
))
996 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
997 known_vals
, known_aggs
);
1000 *known_vals_ptr
= known_vals
;
1002 known_vals
.release ();
1005 *known_aggs_ptr
= known_aggs
;
1007 known_aggs
.release ();
1011 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1014 inline_summary_alloc (void)
1016 if (!edge_removal_hook_holder
)
1017 edge_removal_hook_holder
=
1018 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1019 if (!edge_duplication_hook_holder
)
1020 edge_duplication_hook_holder
=
1021 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1023 if (!inline_summaries
)
1024 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1026 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1027 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1028 if (!edge_predicate_pool
)
1029 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1030 sizeof (struct predicate
), 10);
1033 /* We are called multiple time for given function; clear
1034 data from previous run so they are not cumulated. */
1037 reset_inline_edge_summary (struct cgraph_edge
*e
)
1039 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1041 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1043 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1045 pool_free (edge_predicate_pool
, es
->predicate
);
1046 es
->predicate
= NULL
;
1047 es
->param
.release ();
1051 /* We are called multiple time for given function; clear
1052 data from previous run so they are not cumulated. */
1055 reset_inline_summary (struct cgraph_node
*node
,
1056 inline_summary
*info
)
1058 struct cgraph_edge
*e
;
1060 info
->self_size
= info
->self_time
= 0;
1061 info
->estimated_stack_size
= 0;
1062 info
->estimated_self_stack_size
= 0;
1063 info
->stack_frame_offset
= 0;
1068 if (info
->loop_iterations
)
1070 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1071 info
->loop_iterations
= NULL
;
1073 if (info
->loop_stride
)
1075 pool_free (edge_predicate_pool
, info
->loop_stride
);
1076 info
->loop_stride
= NULL
;
1078 if (info
->array_index
)
1080 pool_free (edge_predicate_pool
, info
->array_index
);
1081 info
->array_index
= NULL
;
1083 vec_free (info
->conds
);
1084 vec_free (info
->entry
);
1085 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1086 reset_inline_edge_summary (e
);
1087 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1088 reset_inline_edge_summary (e
);
1091 /* Hook that is called by cgraph.c when a node is removed. */
1094 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1096 reset_inline_summary (node
, info
);
1099 /* Remap predicate P of former function to be predicate of duplicated function.
1100 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1101 INFO is inline summary of the duplicated node. */
1103 static struct predicate
1104 remap_predicate_after_duplication (struct predicate
*p
,
1105 clause_t possible_truths
,
1106 struct inline_summary
*info
)
1108 struct predicate new_predicate
= true_predicate ();
1110 for (j
= 0; p
->clause
[j
]; j
++)
1111 if (!(possible_truths
& p
->clause
[j
]))
1113 new_predicate
= false_predicate ();
1117 add_clause (info
->conds
, &new_predicate
,
1118 possible_truths
& p
->clause
[j
]);
1119 return new_predicate
;
1122 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1123 Additionally care about allocating new memory slot for updated predicate
1124 and set it to NULL when it becomes true or false (and thus uninteresting).
1128 remap_hint_predicate_after_duplication (struct predicate
**p
,
1129 clause_t possible_truths
,
1130 struct inline_summary
*info
)
1132 struct predicate new_predicate
;
1137 new_predicate
= remap_predicate_after_duplication (*p
,
1138 possible_truths
, info
);
1139 /* We do not want to free previous predicate; it is used by node origin. */
1141 set_hint_predicate (p
, new_predicate
);
1145 /* Hook that is called by cgraph.c when a node is duplicated. */
1147 inline_summary_t::duplicate (cgraph_node
*src
,
1150 inline_summary
*info
)
1152 inline_summary_alloc ();
1153 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1154 /* TODO: as an optimization, we may avoid copying conditions
1155 that are known to be false or true. */
1156 info
->conds
= vec_safe_copy (info
->conds
);
1158 /* When there are any replacements in the function body, see if we can figure
1159 out that something was optimized out. */
1160 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1162 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1163 /* Use SRC parm info since it may not be copied yet. */
1164 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1165 vec
<tree
> known_vals
= vNULL
;
1166 int count
= ipa_get_param_count (parms_info
);
1168 clause_t possible_truths
;
1169 struct predicate true_pred
= true_predicate ();
1171 int optimized_out_size
= 0;
1172 bool inlined_to_p
= false;
1173 struct cgraph_edge
*edge
;
1176 known_vals
.safe_grow_cleared (count
);
1177 for (i
= 0; i
< count
; i
++)
1179 struct ipa_replace_map
*r
;
1181 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1183 if (((!r
->old_tree
&& r
->parm_num
== i
)
1184 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1185 && r
->replace_p
&& !r
->ref_p
)
1187 known_vals
[i
] = r
->new_tree
;
1192 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1195 known_vals
.release ();
1197 account_size_time (info
, 0, 0, &true_pred
);
1199 /* Remap size_time vectors.
1200 Simplify the predicate by prunning out alternatives that are known
1202 TODO: as on optimization, we can also eliminate conditions known
1204 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1206 struct predicate new_predicate
;
1207 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1210 if (false_predicate_p (&new_predicate
))
1211 optimized_out_size
+= e
->size
;
1213 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1216 /* Remap edge predicates with the same simplification as above.
1217 Also copy constantness arrays. */
1218 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1220 struct predicate new_predicate
;
1221 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1223 if (!edge
->inline_failed
)
1224 inlined_to_p
= true;
1227 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1230 if (false_predicate_p (&new_predicate
)
1231 && !false_predicate_p (es
->predicate
))
1233 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1234 edge
->frequency
= 0;
1236 edge_set_predicate (edge
, &new_predicate
);
1239 /* Remap indirect edge predicates with the same simplificaiton as above.
1240 Also copy constantness arrays. */
1241 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1243 struct predicate new_predicate
;
1244 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1246 gcc_checking_assert (edge
->inline_failed
);
1249 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1252 if (false_predicate_p (&new_predicate
)
1253 && !false_predicate_p (es
->predicate
))
1255 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1256 edge
->frequency
= 0;
1258 edge_set_predicate (edge
, &new_predicate
);
1260 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1261 possible_truths
, info
);
1262 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1263 possible_truths
, info
);
1264 remap_hint_predicate_after_duplication (&info
->array_index
,
1265 possible_truths
, info
);
1267 /* If inliner or someone after inliner will ever start producing
1268 non-trivial clones, we will get trouble with lack of information
1269 about updating self sizes, because size vectors already contains
1270 sizes of the calees. */
1271 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1275 info
->entry
= vec_safe_copy (info
->entry
);
1276 if (info
->loop_iterations
)
1278 predicate p
= *info
->loop_iterations
;
1279 info
->loop_iterations
= NULL
;
1280 set_hint_predicate (&info
->loop_iterations
, p
);
1282 if (info
->loop_stride
)
1284 predicate p
= *info
->loop_stride
;
1285 info
->loop_stride
= NULL
;
1286 set_hint_predicate (&info
->loop_stride
, p
);
1288 if (info
->array_index
)
1290 predicate p
= *info
->array_index
;
1291 info
->array_index
= NULL
;
1292 set_hint_predicate (&info
->array_index
, p
);
1295 inline_update_overall_summary (dst
);
1299 /* Hook that is called by cgraph.c when a node is duplicated. */
1302 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1303 struct cgraph_edge
*dst
,
1304 ATTRIBUTE_UNUSED
void *data
)
1306 struct inline_edge_summary
*info
;
1307 struct inline_edge_summary
*srcinfo
;
1308 inline_summary_alloc ();
1309 info
= inline_edge_summary (dst
);
1310 srcinfo
= inline_edge_summary (src
);
1311 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1312 info
->predicate
= NULL
;
1313 edge_set_predicate (dst
, srcinfo
->predicate
);
1314 info
->param
= srcinfo
->param
.copy ();
1318 /* Keep edge cache consistent across edge removal. */
1321 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1322 void *data ATTRIBUTE_UNUSED
)
1324 if (edge_growth_cache
.exists ())
1325 reset_edge_growth_cache (edge
);
1326 reset_inline_edge_summary (edge
);
1330 /* Initialize growth caches. */
1333 initialize_growth_caches (void)
1335 if (symtab
->edges_max_uid
)
1336 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1337 if (symtab
->cgraph_max_uid
)
1338 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1342 /* Free growth caches. */
1345 free_growth_caches (void)
1347 edge_growth_cache
.release ();
1348 node_growth_cache
.release ();
1352 /* Dump edge summaries associated to NODE and recursively to all clones.
1353 Indent by INDENT. */
1356 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1357 struct inline_summary
*info
)
1359 struct cgraph_edge
*edge
;
1360 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1362 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1363 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1367 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1368 " time: %2i callee size:%2i stack:%2i",
1369 indent
, "", callee
->name (), callee
->order
,
1370 !edge
->inline_failed
1371 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1372 indent
, "", es
->loop_depth
, edge
->frequency
,
1373 es
->call_stmt_size
, es
->call_stmt_time
,
1374 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1375 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1379 fprintf (f
, " predicate: ");
1380 dump_predicate (f
, info
->conds
, es
->predicate
);
1384 if (es
->param
.exists ())
1385 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1387 int prob
= es
->param
[i
].change_prob
;
1390 fprintf (f
, "%*s op%i is compile time invariant\n",
1392 else if (prob
!= REG_BR_PROB_BASE
)
1393 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1394 prob
* 100.0 / REG_BR_PROB_BASE
);
1396 if (!edge
->inline_failed
)
1398 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1399 " callee size %i\n",
1401 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1402 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1403 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1404 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1407 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1409 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1410 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1414 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1417 fprintf (f
, "predicate: ");
1418 dump_predicate (f
, info
->conds
, es
->predicate
);
1427 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1429 if (node
->definition
)
1431 struct inline_summary
*s
= inline_summaries
->get (node
);
1434 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1436 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1437 fprintf (f
, " always_inline");
1439 fprintf (f
, " inlinable");
1440 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1441 fprintf (f
, " global time: %i\n", s
->time
);
1442 fprintf (f
, " self size: %i\n", s
->self_size
);
1443 fprintf (f
, " global size: %i\n", s
->size
);
1444 fprintf (f
, " min size: %i\n", s
->min_size
);
1445 fprintf (f
, " self stack: %i\n",
1446 (int) s
->estimated_self_stack_size
);
1447 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1449 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1451 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1452 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1454 fprintf (f
, " size:%f, time:%f, predicate:",
1455 (double) e
->size
/ INLINE_SIZE_SCALE
,
1456 (double) e
->time
/ INLINE_TIME_SCALE
);
1457 dump_predicate (f
, s
->conds
, &e
->predicate
);
1459 if (s
->loop_iterations
)
1461 fprintf (f
, " loop iterations:");
1462 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1466 fprintf (f
, " loop stride:");
1467 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1471 fprintf (f
, " array index:");
1472 dump_predicate (f
, s
->conds
, s
->array_index
);
1474 fprintf (f
, " calls:\n");
1475 dump_inline_edge_summary (f
, 4, node
, s
);
1481 debug_inline_summary (struct cgraph_node
*node
)
1483 dump_inline_summary (stderr
, node
);
1487 dump_inline_summaries (FILE *f
)
1489 struct cgraph_node
*node
;
1491 FOR_EACH_DEFINED_FUNCTION (node
)
1492 if (!node
->global
.inlined_to
)
1493 dump_inline_summary (f
, node
);
1496 /* Give initial reasons why inlining would fail on EDGE. This gets either
1497 nullified or usually overwritten by more precise reasons later. */
1500 initialize_inline_failed (struct cgraph_edge
*e
)
1502 struct cgraph_node
*callee
= e
->callee
;
1504 if (e
->indirect_unknown_callee
)
1505 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1506 else if (!callee
->definition
)
1507 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1508 else if (callee
->local
.redefined_extern_inline
)
1509 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1510 else if (e
->call_stmt_cannot_inline_p
)
1511 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1512 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1513 /* We can't inline if the function is spawing a function. */
1514 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1516 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1519 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1520 boolean variable pointed to by DATA. */
1523 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1526 bool *b
= (bool *) data
;
1531 /* If OP refers to value of function parameter, return the corresponding
1535 unmodified_parm_1 (gimple stmt
, tree op
)
1537 /* SSA_NAME referring to parm default def? */
1538 if (TREE_CODE (op
) == SSA_NAME
1539 && SSA_NAME_IS_DEFAULT_DEF (op
)
1540 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1541 return SSA_NAME_VAR (op
);
1542 /* Non-SSA parm reference? */
1543 if (TREE_CODE (op
) == PARM_DECL
)
1545 bool modified
= false;
1548 ao_ref_init (&refd
, op
);
1549 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1557 /* If OP refers to value of function parameter, return the corresponding
1558 parameter. Also traverse chains of SSA register assignments. */
1561 unmodified_parm (gimple stmt
, tree op
)
1563 tree res
= unmodified_parm_1 (stmt
, op
);
1567 if (TREE_CODE (op
) == SSA_NAME
1568 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1569 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1570 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1571 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1575 /* If OP refers to a value of a function parameter or value loaded from an
1576 aggregate passed to a parameter (either by value or reference), return TRUE
1577 and store the number of the parameter to *INDEX_P and information whether
1578 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1579 the function parameters, STMT is the statement in which OP is used or
1583 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1584 gimple stmt
, tree op
, int *index_p
,
1585 struct agg_position_info
*aggpos
)
1587 tree res
= unmodified_parm_1 (stmt
, op
);
1589 gcc_checking_assert (aggpos
);
1592 *index_p
= ipa_get_param_decl_index (info
, res
);
1595 aggpos
->agg_contents
= false;
1596 aggpos
->by_ref
= false;
1600 if (TREE_CODE (op
) == SSA_NAME
)
1602 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1603 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1605 stmt
= SSA_NAME_DEF_STMT (op
);
1606 op
= gimple_assign_rhs1 (stmt
);
1607 if (!REFERENCE_CLASS_P (op
))
1608 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1612 aggpos
->agg_contents
= true;
1613 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1617 /* See if statement might disappear after inlining.
1618 0 - means not eliminated
1619 1 - half of statements goes away
1620 2 - for sure it is eliminated.
1621 We are not terribly sophisticated, basically looking for simple abstraction
1622 penalty wrappers. */
1625 eliminated_by_inlining_prob (gimple stmt
)
1627 enum gimple_code code
= gimple_code (stmt
);
1628 enum tree_code rhs_code
;
1638 if (gimple_num_ops (stmt
) != 2)
1641 rhs_code
= gimple_assign_rhs_code (stmt
);
1643 /* Casts of parameters, loads from parameters passed by reference
1644 and stores to return value or parameters are often free after
1645 inlining dua to SRA and further combining.
1646 Assume that half of statements goes away. */
1647 if (CONVERT_EXPR_CODE_P (rhs_code
)
1648 || rhs_code
== VIEW_CONVERT_EXPR
1649 || rhs_code
== ADDR_EXPR
1650 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1652 tree rhs
= gimple_assign_rhs1 (stmt
);
1653 tree lhs
= gimple_assign_lhs (stmt
);
1654 tree inner_rhs
= get_base_address (rhs
);
1655 tree inner_lhs
= get_base_address (lhs
);
1656 bool rhs_free
= false;
1657 bool lhs_free
= false;
1664 /* Reads of parameter are expected to be free. */
1665 if (unmodified_parm (stmt
, inner_rhs
))
1667 /* Match expressions of form &this->field. Those will most likely
1668 combine with something upstream after inlining. */
1669 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1671 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1672 if (TREE_CODE (op
) == PARM_DECL
)
1674 else if (TREE_CODE (op
) == MEM_REF
1675 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1679 /* When parameter is not SSA register because its address is taken
1680 and it is just copied into one, the statement will be completely
1681 free after inlining (we will copy propagate backward). */
1682 if (rhs_free
&& is_gimple_reg (lhs
))
1685 /* Reads of parameters passed by reference
1686 expected to be free (i.e. optimized out after inlining). */
1687 if (TREE_CODE (inner_rhs
) == MEM_REF
1688 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1691 /* Copying parameter passed by reference into gimple register is
1692 probably also going to copy propagate, but we can't be quite
1694 if (rhs_free
&& is_gimple_reg (lhs
))
1697 /* Writes to parameters, parameters passed by value and return value
1698 (either dirrectly or passed via invisible reference) are free.
1700 TODO: We ought to handle testcase like
1701 struct a {int a,b;};
1703 retrurnsturct (void)
1709 This translate into:
1724 For that we either need to copy ipa-split logic detecting writes
1726 if (TREE_CODE (inner_lhs
) == PARM_DECL
1727 || TREE_CODE (inner_lhs
) == RESULT_DECL
1728 || (TREE_CODE (inner_lhs
) == MEM_REF
1729 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1730 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1731 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1732 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1734 0))) == RESULT_DECL
))))
1737 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1739 if (lhs_free
&& rhs_free
)
1749 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1750 predicates to the CFG edges. */
1753 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1754 struct inline_summary
*summary
,
1760 struct agg_position_info aggpos
;
1761 enum tree_code code
, inverted_code
;
1767 last
= last_stmt (bb
);
1768 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1770 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1772 op
= gimple_cond_lhs (last
);
1773 /* TODO: handle conditionals like
1776 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1778 code
= gimple_cond_code (last
);
1779 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1781 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1783 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1784 ? code
: inverted_code
);
1785 /* invert_tree_comparison will return ERROR_MARK on FP
1786 comparsions that are not EQ/NE instead of returning proper
1787 unordered one. Be sure it is not confused with NON_CONSTANT. */
1788 if (this_code
!= ERROR_MARK
)
1790 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1792 gimple_cond_rhs (last
));
1793 e
->aux
= pool_alloc (edge_predicate_pool
);
1794 *(struct predicate
*) e
->aux
= p
;
1799 if (TREE_CODE (op
) != SSA_NAME
)
1802 if (builtin_constant_p (op))
1806 Here we can predicate nonconstant_code. We can't
1807 really handle constant_code since we have no predicate
1808 for this and also the constant code is not known to be
1809 optimized away when inliner doen't see operand is constant.
1810 Other optimizers might think otherwise. */
1811 if (gimple_cond_code (last
) != NE_EXPR
1812 || !integer_zerop (gimple_cond_rhs (last
)))
1814 set_stmt
= SSA_NAME_DEF_STMT (op
);
1815 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1816 || gimple_call_num_args (set_stmt
) != 1)
1818 op2
= gimple_call_arg (set_stmt
, 0);
1819 if (!unmodified_parm_or_parm_agg_item
1820 (info
, set_stmt
, op2
, &index
, &aggpos
))
1822 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1824 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1825 IS_NOT_CONSTANT
, NULL_TREE
);
1826 e
->aux
= pool_alloc (edge_predicate_pool
);
1827 *(struct predicate
*) e
->aux
= p
;
1832 /* If BB ends by a switch we can turn into predicates, attach corresponding
1833 predicates to the CFG edges. */
1836 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1837 struct inline_summary
*summary
,
1843 struct agg_position_info aggpos
;
1849 lastg
= last_stmt (bb
);
1850 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1852 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1853 op
= gimple_switch_index (last
);
1854 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1859 e
->aux
= pool_alloc (edge_predicate_pool
);
1860 *(struct predicate
*) e
->aux
= false_predicate ();
1862 n
= gimple_switch_num_labels (last
);
1863 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1865 tree cl
= gimple_switch_label (last
, case_idx
);
1869 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1870 min
= CASE_LOW (cl
);
1871 max
= CASE_HIGH (cl
);
1873 /* For default we might want to construct predicate that none
1874 of cases is met, but it is bit hard to do not having negations
1875 of conditionals handy. */
1877 p
= true_predicate ();
1879 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1882 struct predicate p1
, p2
;
1883 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1884 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1885 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1887 *(struct predicate
*) e
->aux
1888 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1893 /* For each BB in NODE attach to its AUX pointer predicate under
1894 which it is executable. */
1897 compute_bb_predicates (struct cgraph_node
*node
,
1898 struct ipa_node_params
*parms_info
,
1899 struct inline_summary
*summary
)
1901 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1905 FOR_EACH_BB_FN (bb
, my_function
)
1907 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1908 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1911 /* Entry block is always executable. */
1912 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1913 = pool_alloc (edge_predicate_pool
);
1914 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1915 = true_predicate ();
1917 /* A simple dataflow propagation of predicates forward in the CFG.
1918 TODO: work in reverse postorder. */
1922 FOR_EACH_BB_FN (bb
, my_function
)
1924 struct predicate p
= false_predicate ();
1927 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1931 struct predicate this_bb_predicate
1932 = *(struct predicate
*) e
->src
->aux
;
1935 = and_predicates (summary
->conds
, &this_bb_predicate
,
1936 (struct predicate
*) e
->aux
);
1937 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1938 if (true_predicate_p (&p
))
1942 if (false_predicate_p (&p
))
1943 gcc_assert (!bb
->aux
);
1949 bb
->aux
= pool_alloc (edge_predicate_pool
);
1950 *((struct predicate
*) bb
->aux
) = p
;
1952 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1954 /* This OR operation is needed to ensure monotonous data flow
1955 in the case we hit the limit on number of clauses and the
1956 and/or operations above give approximate answers. */
1957 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1958 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1961 *((struct predicate
*) bb
->aux
) = p
;
1970 /* We keep info about constantness of SSA names. */
1972 typedef struct predicate predicate_t
;
1973 /* Return predicate specifying when the STMT might have result that is not
1974 a compile time constant. */
1976 static struct predicate
1977 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1978 struct inline_summary
*summary
,
1980 vec
<predicate_t
> nonconstant_names
)
1985 while (UNARY_CLASS_P (expr
))
1986 expr
= TREE_OPERAND (expr
, 0);
1988 parm
= unmodified_parm (NULL
, expr
);
1989 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1990 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1991 if (is_gimple_min_invariant (expr
))
1992 return false_predicate ();
1993 if (TREE_CODE (expr
) == SSA_NAME
)
1994 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1995 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1997 struct predicate p1
= will_be_nonconstant_expr_predicate
1998 (info
, summary
, TREE_OPERAND (expr
, 0),
2000 struct predicate p2
;
2001 if (true_predicate_p (&p1
))
2003 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2004 TREE_OPERAND (expr
, 1),
2006 return or_predicates (summary
->conds
, &p1
, &p2
);
2008 else if (TREE_CODE (expr
) == COND_EXPR
)
2010 struct predicate p1
= will_be_nonconstant_expr_predicate
2011 (info
, summary
, TREE_OPERAND (expr
, 0),
2013 struct predicate p2
;
2014 if (true_predicate_p (&p1
))
2016 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2017 TREE_OPERAND (expr
, 1),
2019 if (true_predicate_p (&p2
))
2021 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2022 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2023 TREE_OPERAND (expr
, 2),
2025 return or_predicates (summary
->conds
, &p1
, &p2
);
2032 return false_predicate ();
2036 /* Return predicate specifying when the STMT might have result that is not
2037 a compile time constant. */
2039 static struct predicate
2040 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2041 struct inline_summary
*summary
,
2043 vec
<predicate_t
> nonconstant_names
)
2045 struct predicate p
= true_predicate ();
2048 struct predicate op_non_const
;
2051 struct agg_position_info aggpos
;
2053 /* What statments might be optimized away
2054 when their arguments are constant. */
2055 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2056 && gimple_code (stmt
) != GIMPLE_COND
2057 && gimple_code (stmt
) != GIMPLE_SWITCH
2058 && (gimple_code (stmt
) != GIMPLE_CALL
2059 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2062 /* Stores will stay anyway. */
2063 if (gimple_store_p (stmt
))
2066 is_load
= gimple_assign_load_p (stmt
);
2068 /* Loads can be optimized when the value is known. */
2072 gcc_assert (gimple_assign_single_p (stmt
));
2073 op
= gimple_assign_rhs1 (stmt
);
2074 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2081 /* See if we understand all operands before we start
2082 adding conditionals. */
2083 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2085 tree parm
= unmodified_parm (stmt
, use
);
2086 /* For arguments we can build a condition. */
2087 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2089 if (TREE_CODE (use
) != SSA_NAME
)
2091 /* If we know when operand is constant,
2092 we still can say something useful. */
2093 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2100 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2102 op_non_const
= false_predicate ();
2103 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2105 tree parm
= unmodified_parm (stmt
, use
);
2108 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2110 if (index
!= base_index
)
2111 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2116 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2117 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2119 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2120 && gimple_op (stmt
, 0)
2121 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2122 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2124 return op_non_const
;
2127 struct record_modified_bb_info
2133 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2134 set except for info->stmt. */
2137 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2139 struct record_modified_bb_info
*info
=
2140 (struct record_modified_bb_info
*) data
;
2141 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2143 bitmap_set_bit (info
->bb_set
,
2144 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2145 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2146 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2150 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2151 will change since last invocation of STMT.
2153 Value 0 is reserved for compile time invariants.
2154 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2155 ought to be REG_BR_PROB_BASE / estimated_iters. */
2158 param_change_prob (gimple stmt
, int i
)
2160 tree op
= gimple_call_arg (stmt
, i
);
2161 basic_block bb
= gimple_bb (stmt
);
2164 /* Global invariants neve change. */
2165 if (is_gimple_min_invariant (op
))
2167 /* We would have to do non-trivial analysis to really work out what
2168 is the probability of value to change (i.e. when init statement
2169 is in a sibling loop of the call).
2171 We do an conservative estimate: when call is executed N times more often
2172 than the statement defining value, we take the frequency 1/N. */
2173 if (TREE_CODE (op
) == SSA_NAME
)
2178 return REG_BR_PROB_BASE
;
2180 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2181 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2183 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2187 if (init_freq
< bb
->frequency
)
2188 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2190 return REG_BR_PROB_BASE
;
2193 base
= get_base_address (op
);
2198 struct record_modified_bb_info info
;
2201 tree init
= ctor_for_folding (base
);
2203 if (init
!= error_mark_node
)
2206 return REG_BR_PROB_BASE
;
2207 ao_ref_init (&refd
, op
);
2209 info
.bb_set
= BITMAP_ALLOC (NULL
);
2210 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2212 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2214 BITMAP_FREE (info
.bb_set
);
2215 return REG_BR_PROB_BASE
;
2218 /* Assume that every memory is initialized at entry.
2219 TODO: Can we easilly determine if value is always defined
2220 and thus we may skip entry block? */
2221 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2222 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2226 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2227 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2229 BITMAP_FREE (info
.bb_set
);
2230 if (max
< bb
->frequency
)
2231 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2233 return REG_BR_PROB_BASE
;
2235 return REG_BR_PROB_BASE
;
2238 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2239 sub-graph and if the predicate the condition depends on is known. If so,
2240 return true and store the pointer the predicate in *P. */
2243 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2244 inline_summary
*summary
, basic_block bb
,
2245 struct predicate
*p
,
2246 vec
<predicate_t
> nonconstant_names
)
2250 basic_block first_bb
= NULL
;
2253 if (single_pred_p (bb
))
2255 *p
= false_predicate ();
2259 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2261 if (single_succ_p (e
->src
))
2263 if (!single_pred_p (e
->src
))
2266 first_bb
= single_pred (e
->src
);
2267 else if (single_pred (e
->src
) != first_bb
)
2274 else if (e
->src
!= first_bb
)
2282 stmt
= last_stmt (first_bb
);
2284 || gimple_code (stmt
) != GIMPLE_COND
2285 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2288 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2289 gimple_cond_lhs (stmt
),
2291 if (true_predicate_p (p
))
2297 /* Given a PHI statement in a function described by inline properties SUMMARY
2298 and *P being the predicate describing whether the selected PHI argument is
2299 known, store a predicate for the result of the PHI statement into
2300 NONCONSTANT_NAMES, if possible. */
2303 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2304 struct predicate
*p
,
2305 vec
<predicate_t
> nonconstant_names
)
2309 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2311 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2312 if (!is_gimple_min_invariant (arg
))
2314 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2315 *p
= or_predicates (summary
->conds
, p
,
2316 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2317 if (true_predicate_p (p
))
2322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2324 fprintf (dump_file
, "\t\tphi predicate: ");
2325 dump_predicate (dump_file
, summary
->conds
, p
);
2327 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2330 /* Return predicate specifying when array index in access OP becomes non-constant. */
2332 static struct predicate
2333 array_index_predicate (inline_summary
*info
,
2334 vec
< predicate_t
> nonconstant_names
, tree op
)
2336 struct predicate p
= false_predicate ();
2337 while (handled_component_p (op
))
2339 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2341 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2342 p
= or_predicates (info
->conds
, &p
,
2343 &nonconstant_names
[SSA_NAME_VERSION
2344 (TREE_OPERAND (op
, 1))]);
2346 op
= TREE_OPERAND (op
, 0);
2351 /* For a typical usage of __builtin_expect (a<b, 1), we
2352 may introduce an extra relation stmt:
2353 With the builtin, we have
2356 t3 = __builtin_expect (t2, 1);
2359 Without the builtin, we have
2362 This affects the size/time estimation and may have
2363 an impact on the earlier inlining.
2364 Here find this pattern and fix it up later. */
2367 find_foldable_builtin_expect (basic_block bb
)
2369 gimple_stmt_iterator bsi
;
2371 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2373 gimple stmt
= gsi_stmt (bsi
);
2374 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2375 || (is_gimple_call (stmt
)
2376 && gimple_call_internal_p (stmt
)
2377 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2379 tree var
= gimple_call_lhs (stmt
);
2380 tree arg
= gimple_call_arg (stmt
, 0);
2381 use_operand_p use_p
;
2388 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2390 while (TREE_CODE (arg
) == SSA_NAME
)
2392 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2393 if (!is_gimple_assign (stmt_tmp
))
2395 switch (gimple_assign_rhs_code (stmt_tmp
))
2414 arg
= gimple_assign_rhs1 (stmt_tmp
);
2417 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2418 && gimple_code (use_stmt
) == GIMPLE_COND
)
2425 /* Return true when the basic blocks contains only clobbers followed by RESX.
2426 Such BBs are kept around to make removal of dead stores possible with
2427 presence of EH and will be optimized out by optimize_clobbers later in the
2430 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2431 that can be clobber only, too.. When it is false, the RESX is not necessary
2432 on the end of basic block. */
2435 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2437 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2443 if (gsi_end_p (gsi
))
2445 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2449 else if (!single_succ_p (bb
))
2452 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2454 gimple stmt
= gsi_stmt (gsi
);
2455 if (is_gimple_debug (stmt
))
2457 if (gimple_clobber_p (stmt
))
2459 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2464 /* See if all predecestors are either throws or clobber only BBs. */
2465 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2466 if (!(e
->flags
& EDGE_EH
)
2467 && !clobber_only_eh_bb_p (e
->src
, false))
2473 /* Compute function body size parameters for NODE.
2474 When EARLY is true, we compute only simple summaries without
2475 non-trivial predicates to drive the early inliner. */
2478 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2481 /* Estimate static overhead for function prologue/epilogue and alignment. */
2483 /* Benefits are scaled by probability of elimination that is in range
2486 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2488 struct inline_summary
*info
= inline_summaries
->get (node
);
2489 struct predicate bb_predicate
;
2490 struct ipa_node_params
*parms_info
= NULL
;
2491 vec
<predicate_t
> nonconstant_names
= vNULL
;
2494 predicate array_index
= true_predicate ();
2495 gimple fix_builtin_expect_stmt
;
2500 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2501 so we can produce proper inline hints.
2503 When optimizing and analyzing for early inliner, initialize node params
2504 so we can produce correct BB predicates. */
2506 if (opt_for_fn (node
->decl
, optimize
))
2508 calculate_dominance_info (CDI_DOMINATORS
);
2510 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2513 ipa_check_create_node_params ();
2514 ipa_initialize_node_params (node
);
2517 if (ipa_node_params_sum
)
2519 parms_info
= IPA_NODE_REF (node
);
2520 nonconstant_names
.safe_grow_cleared
2521 (SSANAMES (my_function
)->length ());
2526 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2529 /* When we run into maximal number of entries, we assign everything to the
2530 constant truth case. Be sure to have it in list. */
2531 bb_predicate
= true_predicate ();
2532 account_size_time (info
, 0, 0, &bb_predicate
);
2534 bb_predicate
= not_inlined_predicate ();
2535 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2537 gcc_assert (my_function
&& my_function
->cfg
);
2539 compute_bb_predicates (node
, parms_info
, info
);
2540 gcc_assert (cfun
== my_function
);
2541 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2542 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2543 for (n
= 0; n
< nblocks
; n
++)
2545 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2546 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2547 if (clobber_only_eh_bb_p (bb
))
2549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2550 fprintf (dump_file
, "\n Ignoring BB %i;"
2551 " it will be optimized away by cleanup_clobbers\n",
2556 /* TODO: Obviously predicates can be propagated down across CFG. */
2560 bb_predicate
= *(struct predicate
*) bb
->aux
;
2562 bb_predicate
= false_predicate ();
2565 bb_predicate
= true_predicate ();
2567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2569 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2570 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2573 if (parms_info
&& nonconstant_names
.exists ())
2575 struct predicate phi_predicate
;
2576 bool first_phi
= true;
2578 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2582 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2589 fprintf (dump_file
, " ");
2590 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2592 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2597 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2599 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2602 gimple stmt
= gsi_stmt (bsi
);
2603 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2604 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2606 struct predicate will_be_nonconstant
;
2608 /* This relation stmt should be folded after we remove
2609 buildin_expect call. Adjust the cost here. */
2610 if (stmt
== fix_builtin_expect_stmt
)
2616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2618 fprintf (dump_file
, " ");
2619 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2620 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2621 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2625 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2627 struct predicate this_array_index
;
2629 array_index_predicate (info
, nonconstant_names
,
2630 gimple_assign_rhs1 (stmt
));
2631 if (!false_predicate_p (&this_array_index
))
2633 and_predicates (info
->conds
, &array_index
,
2636 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2638 struct predicate this_array_index
;
2640 array_index_predicate (info
, nonconstant_names
,
2641 gimple_get_lhs (stmt
));
2642 if (!false_predicate_p (&this_array_index
))
2644 and_predicates (info
->conds
, &array_index
,
2649 if (is_gimple_call (stmt
)
2650 && !gimple_call_internal_p (stmt
))
2652 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2653 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2655 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2656 resolved as constant. We however don't want to optimize
2657 out the cgraph edges. */
2658 if (nonconstant_names
.exists ()
2659 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2660 && gimple_call_lhs (stmt
)
2661 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2663 struct predicate false_p
= false_predicate ();
2664 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2667 if (ipa_node_params_sum
)
2669 int count
= gimple_call_num_args (stmt
);
2673 es
->param
.safe_grow_cleared (count
);
2674 for (i
= 0; i
< count
; i
++)
2676 int prob
= param_change_prob (stmt
, i
);
2677 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2678 es
->param
[i
].change_prob
= prob
;
2682 es
->call_stmt_size
= this_size
;
2683 es
->call_stmt_time
= this_time
;
2684 es
->loop_depth
= bb_loop_depth (bb
);
2685 edge_set_predicate (edge
, &bb_predicate
);
2688 /* TODO: When conditional jump or swithc is known to be constant, but
2689 we did not translate it into the predicates, we really can account
2690 just maximum of the possible paths. */
2693 = will_be_nonconstant_predicate (parms_info
, info
,
2694 stmt
, nonconstant_names
);
2695 if (this_time
|| this_size
)
2701 prob
= eliminated_by_inlining_prob (stmt
);
2702 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2704 "\t\t50%% will be eliminated by inlining\n");
2705 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2706 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2709 p
= and_predicates (info
->conds
, &bb_predicate
,
2710 &will_be_nonconstant
);
2712 p
= true_predicate ();
2714 if (!false_predicate_p (&p
)
2715 || (is_gimple_call (stmt
)
2716 && !false_predicate_p (&bb_predicate
)))
2720 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2721 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2724 /* We account everything but the calls. Calls have their own
2725 size/time info attached to cgraph edges. This is necessary
2726 in order to make the cost disappear after inlining. */
2727 if (!is_gimple_call (stmt
))
2731 struct predicate ip
= not_inlined_predicate ();
2732 ip
= and_predicates (info
->conds
, &ip
, &p
);
2733 account_size_time (info
, this_size
* prob
,
2734 this_time
* prob
, &ip
);
2737 account_size_time (info
, this_size
* (2 - prob
),
2738 this_time
* (2 - prob
), &p
);
2741 gcc_assert (time
>= 0);
2742 gcc_assert (size
>= 0);
2746 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2747 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2748 if (time
> MAX_TIME
)
2752 if (nonconstant_names
.exists () && !early
)
2755 predicate loop_iterations
= true_predicate ();
2756 predicate loop_stride
= true_predicate ();
2758 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2759 flow_loops_dump (dump_file
, NULL
, 0);
2761 FOR_EACH_LOOP (loop
, 0)
2766 struct tree_niter_desc niter_desc
;
2767 basic_block
*body
= get_loop_body (loop
);
2768 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2770 exits
= get_loop_exit_edges (loop
);
2771 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2772 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2773 && !is_gimple_min_invariant (niter_desc
.niter
))
2775 predicate will_be_nonconstant
2776 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2779 if (!true_predicate_p (&will_be_nonconstant
))
2780 will_be_nonconstant
= and_predicates (info
->conds
,
2782 &will_be_nonconstant
);
2783 if (!true_predicate_p (&will_be_nonconstant
)
2784 && !false_predicate_p (&will_be_nonconstant
))
2785 /* This is slightly inprecise. We may want to represent each
2786 loop with independent predicate. */
2788 and_predicates (info
->conds
, &loop_iterations
,
2789 &will_be_nonconstant
);
2793 for (i
= 0; i
< loop
->num_nodes
; i
++)
2795 gimple_stmt_iterator gsi
;
2796 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2797 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2800 gimple stmt
= gsi_stmt (gsi
);
2805 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2807 predicate will_be_nonconstant
;
2810 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2811 || is_gimple_min_invariant (iv
.step
))
2814 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2817 if (!true_predicate_p (&will_be_nonconstant
))
2819 = and_predicates (info
->conds
,
2821 &will_be_nonconstant
);
2822 if (!true_predicate_p (&will_be_nonconstant
)
2823 && !false_predicate_p (&will_be_nonconstant
))
2824 /* This is slightly inprecise. We may want to represent
2825 each loop with independent predicate. */
2827 and_predicates (info
->conds
, &loop_stride
,
2828 &will_be_nonconstant
);
2834 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2836 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2839 FOR_ALL_BB_FN (bb
, my_function
)
2845 pool_free (edge_predicate_pool
, bb
->aux
);
2847 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2850 pool_free (edge_predicate_pool
, e
->aux
);
2854 inline_summaries
->get (node
)->self_time
= time
;
2855 inline_summaries
->get (node
)->self_size
= size
;
2856 nonconstant_names
.release ();
2857 if (opt_for_fn (node
->decl
, optimize
))
2860 loop_optimizer_finalize ();
2861 else if (!ipa_edge_args_vector
)
2862 ipa_free_all_node_params ();
2863 free_dominance_info (CDI_DOMINATORS
);
2867 fprintf (dump_file
, "\n");
2868 dump_inline_summary (dump_file
, node
);
2873 /* Compute parameters of functions used by inliner.
2874 EARLY is true when we compute parameters for the early inliner */
2877 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2879 HOST_WIDE_INT self_stack_size
;
2880 struct cgraph_edge
*e
;
2881 struct inline_summary
*info
;
2883 gcc_assert (!node
->global
.inlined_to
);
2885 inline_summary_alloc ();
2887 info
= inline_summaries
->get (node
);
2888 reset_inline_summary (node
, info
);
2890 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2891 Once this happen, we will need to more curefully predict call
2893 if (node
->thunk
.thunk_p
)
2895 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2896 struct predicate t
= true_predicate ();
2898 info
->inlinable
= 0;
2899 node
->callees
->call_stmt_cannot_inline_p
= true;
2900 node
->local
.can_change_signature
= false;
2901 es
->call_stmt_time
= 1;
2902 es
->call_stmt_size
= 1;
2903 account_size_time (info
, 0, 0, &t
);
2907 /* Even is_gimple_min_invariant rely on current_function_decl. */
2908 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2910 /* Estimate the stack size for the function if we're optimizing. */
2911 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2912 info
->estimated_self_stack_size
= self_stack_size
;
2913 info
->estimated_stack_size
= self_stack_size
;
2914 info
->stack_frame_offset
= 0;
2916 /* Can this function be inlined at all? */
2917 if (!opt_for_fn (node
->decl
, optimize
)
2918 && !lookup_attribute ("always_inline",
2919 DECL_ATTRIBUTES (node
->decl
)))
2920 info
->inlinable
= false;
2922 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2924 /* Type attributes can use parameter indices to describe them. */
2925 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2926 node
->local
.can_change_signature
= false;
2929 /* Otherwise, inlinable functions always can change signature. */
2930 if (info
->inlinable
)
2931 node
->local
.can_change_signature
= true;
2934 /* Functions calling builtin_apply can not change signature. */
2935 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2937 tree
cdecl = e
->callee
->decl
;
2938 if (DECL_BUILT_IN (cdecl)
2939 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2940 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2941 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2944 node
->local
.can_change_signature
= !e
;
2947 estimate_function_body_sizes (node
, early
);
2949 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2950 if (e
->callee
->comdat_local_p ())
2952 node
->calls_comdat_local
= (e
!= NULL
);
2954 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2955 info
->time
= info
->self_time
;
2956 info
->size
= info
->self_size
;
2957 info
->stack_frame_offset
= 0;
2958 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2959 #ifdef ENABLE_CHECKING
2960 inline_update_overall_summary (node
);
2961 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2968 /* Compute parameters of functions used by inliner using
2969 current_function_decl. */
2972 compute_inline_parameters_for_current (void)
2974 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2980 const pass_data pass_data_inline_parameters
=
2982 GIMPLE_PASS
, /* type */
2983 "inline_param", /* name */
2984 OPTGROUP_INLINE
, /* optinfo_flags */
2985 TV_INLINE_PARAMETERS
, /* tv_id */
2986 0, /* properties_required */
2987 0, /* properties_provided */
2988 0, /* properties_destroyed */
2989 0, /* todo_flags_start */
2990 0, /* todo_flags_finish */
2993 class pass_inline_parameters
: public gimple_opt_pass
2996 pass_inline_parameters (gcc::context
*ctxt
)
2997 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3000 /* opt_pass methods: */
3001 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3002 virtual unsigned int execute (function
*)
3004 return compute_inline_parameters_for_current ();
3007 }; // class pass_inline_parameters
3012 make_pass_inline_parameters (gcc::context
*ctxt
)
3014 return new pass_inline_parameters (ctxt
);
3018 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3019 KNOWN_CONTEXTS and KNOWN_AGGS. */
3022 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3023 int *size
, int *time
,
3024 vec
<tree
> known_vals
,
3025 vec
<ipa_polymorphic_call_context
> known_contexts
,
3026 vec
<ipa_agg_jump_function_p
> known_aggs
)
3029 struct cgraph_node
*callee
;
3030 struct inline_summary
*isummary
;
3031 enum availability avail
;
3034 if (!known_vals
.exists () && !known_contexts
.exists ())
3036 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3039 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3040 known_aggs
, &speculative
);
3041 if (!target
|| speculative
)
3044 /* Account for difference in cost between indirect and direct calls. */
3045 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3046 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3047 gcc_checking_assert (*time
>= 0);
3048 gcc_checking_assert (*size
>= 0);
3050 callee
= cgraph_node::get (target
);
3051 if (!callee
|| !callee
->definition
)
3053 callee
= callee
->function_symbol (&avail
);
3054 if (avail
< AVAIL_AVAILABLE
)
3056 isummary
= inline_summaries
->get (callee
);
3057 return isummary
->inlinable
;
3060 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3061 handle edge E with probability PROB.
3062 Set HINTS if edge may be devirtualized.
3063 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3067 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3070 vec
<tree
> known_vals
,
3071 vec
<ipa_polymorphic_call_context
> known_contexts
,
3072 vec
<ipa_agg_jump_function_p
> known_aggs
,
3073 inline_hints
*hints
)
3075 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3076 int call_size
= es
->call_stmt_size
;
3077 int call_time
= es
->call_stmt_time
;
3080 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3081 known_vals
, known_contexts
, known_aggs
)
3082 && hints
&& e
->maybe_hot_p ())
3083 *hints
|= INLINE_HINT_indirect_call
;
3084 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3087 *min_size
+= cur_size
;
3088 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3089 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3090 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3091 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3096 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3097 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3098 describe context of the call site. */
3101 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3102 int *min_size
, int *time
,
3103 inline_hints
*hints
,
3104 clause_t possible_truths
,
3105 vec
<tree
> known_vals
,
3106 vec
<ipa_polymorphic_call_context
> known_contexts
,
3107 vec
<ipa_agg_jump_function_p
> known_aggs
)
3109 struct cgraph_edge
*e
;
3110 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3112 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3114 /* Do not care about zero sized builtins. */
3115 if (e
->inline_failed
&& !es
->call_stmt_size
)
3117 gcc_checking_assert (!es
->call_stmt_time
);
3121 || evaluate_predicate (es
->predicate
, possible_truths
))
3123 if (e
->inline_failed
)
3125 /* Predicates of calls shall not use NOT_CHANGED codes,
3126 sowe do not need to compute probabilities. */
3127 estimate_edge_size_and_time (e
, size
,
3128 es
->predicate
? NULL
: min_size
,
3129 time
, REG_BR_PROB_BASE
,
3130 known_vals
, known_contexts
,
3134 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3137 known_vals
, known_contexts
,
3141 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3143 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3145 || evaluate_predicate (es
->predicate
, possible_truths
))
3146 estimate_edge_size_and_time (e
, size
,
3147 es
->predicate
? NULL
: min_size
,
3148 time
, REG_BR_PROB_BASE
,
3149 known_vals
, known_contexts
, known_aggs
,
3155 /* Estimate size and time needed to execute NODE assuming
3156 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3157 information about NODE's arguments. If non-NULL use also probability
3158 information present in INLINE_PARAM_SUMMARY vector.
3159 Additionally detemine hints determined by the context. Finally compute
3160 minimal size needed for the call that is independent on the call context and
3161 can be used for fast estimates. Return the values in RET_SIZE,
3162 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3165 estimate_node_size_and_time (struct cgraph_node
*node
,
3166 clause_t possible_truths
,
3167 vec
<tree
> known_vals
,
3168 vec
<ipa_polymorphic_call_context
> known_contexts
,
3169 vec
<ipa_agg_jump_function_p
> known_aggs
,
3170 int *ret_size
, int *ret_min_size
, int *ret_time
,
3171 inline_hints
*ret_hints
,
3172 vec
<inline_param_summary
>
3173 inline_param_summary
)
3175 struct inline_summary
*info
= inline_summaries
->get (node
);
3180 inline_hints hints
= 0;
3183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3186 fprintf (dump_file
, " Estimating body: %s/%i\n"
3187 " Known to be false: ", node
->name (),
3190 for (i
= predicate_not_inlined_condition
;
3191 i
< (predicate_first_dynamic_condition
3192 + (int) vec_safe_length (info
->conds
)); i
++)
3193 if (!(possible_truths
& (1 << i
)))
3196 fprintf (dump_file
, ", ");
3198 dump_condition (dump_file
, info
->conds
, i
);
3202 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3203 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3206 gcc_checking_assert (e
->time
>= 0);
3207 gcc_checking_assert (time
>= 0);
3208 if (!inline_param_summary
.exists ())
3212 int prob
= predicate_probability (info
->conds
,
3215 inline_param_summary
);
3216 gcc_checking_assert (prob
>= 0);
3217 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3218 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3220 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3221 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3222 gcc_checking_assert (time
>= 0);
3225 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3226 min_size
= (*info
->entry
)[0].size
;
3227 gcc_checking_assert (size
>= 0);
3228 gcc_checking_assert (time
>= 0);
3230 if (info
->loop_iterations
3231 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3232 hints
|= INLINE_HINT_loop_iterations
;
3233 if (info
->loop_stride
3234 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3235 hints
|= INLINE_HINT_loop_stride
;
3236 if (info
->array_index
3237 && !evaluate_predicate (info
->array_index
, possible_truths
))
3238 hints
|= INLINE_HINT_array_index
;
3240 hints
|= INLINE_HINT_in_scc
;
3241 if (DECL_DECLARED_INLINE_P (node
->decl
))
3242 hints
|= INLINE_HINT_declared_inline
;
3244 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3245 known_vals
, known_contexts
, known_aggs
);
3246 gcc_checking_assert (size
>= 0);
3247 gcc_checking_assert (time
>= 0);
3248 time
= RDIV (time
, INLINE_TIME_SCALE
);
3249 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3250 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3253 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3259 *ret_min_size
= min_size
;
3266 /* Estimate size and time needed to execute callee of EDGE assuming that
3267 parameters known to be constant at caller of EDGE are propagated.
3268 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3269 and types for parameters. */
3272 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3273 vec
<tree
> known_vals
,
3274 vec
<ipa_polymorphic_call_context
>
3276 vec
<ipa_agg_jump_function_p
> known_aggs
,
3277 int *ret_size
, int *ret_time
,
3278 inline_hints
*hints
)
3282 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3284 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3285 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3288 /* Translate all conditions from callee representation into caller
3289 representation and symbolically evaluate predicate P into new predicate.
3291 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3292 is summary of function predicate P is from. OPERAND_MAP is array giving
3293 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3294 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3295 predicate under which callee is executed. OFFSET_MAP is an array of of
3296 offsets that need to be added to conditions, negative offset means that
3297 conditions relying on values passed by reference have to be discarded
3298 because they might not be preserved (and should be considered offset zero
3299 for other purposes). */
3301 static struct predicate
3302 remap_predicate (struct inline_summary
*info
,
3303 struct inline_summary
*callee_info
,
3304 struct predicate
*p
,
3305 vec
<int> operand_map
,
3306 vec
<int> offset_map
,
3307 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3310 struct predicate out
= true_predicate ();
3312 /* True predicate is easy. */
3313 if (true_predicate_p (p
))
3314 return *toplev_predicate
;
3315 for (i
= 0; p
->clause
[i
]; i
++)
3317 clause_t clause
= p
->clause
[i
];
3319 struct predicate clause_predicate
= false_predicate ();
3321 gcc_assert (i
< MAX_CLAUSES
);
3323 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3324 /* Do we have condition we can't disprove? */
3325 if (clause
& possible_truths
& (1 << cond
))
3327 struct predicate cond_predicate
;
3328 /* Work out if the condition can translate to predicate in the
3329 inlined function. */
3330 if (cond
>= predicate_first_dynamic_condition
)
3332 struct condition
*c
;
3334 c
= &(*callee_info
->conds
)[cond
3336 predicate_first_dynamic_condition
];
3337 /* See if we can remap condition operand to caller's operand.
3338 Otherwise give up. */
3339 if (!operand_map
.exists ()
3340 || (int) operand_map
.length () <= c
->operand_num
3341 || operand_map
[c
->operand_num
] == -1
3342 /* TODO: For non-aggregate conditions, adding an offset is
3343 basically an arithmetic jump function processing which
3344 we should support in future. */
3345 || ((!c
->agg_contents
|| !c
->by_ref
)
3346 && offset_map
[c
->operand_num
] > 0)
3347 || (c
->agg_contents
&& c
->by_ref
3348 && offset_map
[c
->operand_num
] < 0))
3349 cond_predicate
= true_predicate ();
3352 struct agg_position_info ap
;
3353 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3354 if (offset_delta
< 0)
3356 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3359 gcc_assert (!c
->agg_contents
3360 || c
->by_ref
|| offset_delta
== 0);
3361 ap
.offset
= c
->offset
+ offset_delta
;
3362 ap
.agg_contents
= c
->agg_contents
;
3363 ap
.by_ref
= c
->by_ref
;
3364 cond_predicate
= add_condition (info
,
3365 operand_map
[c
->operand_num
],
3366 &ap
, c
->code
, c
->val
);
3369 /* Fixed conditions remains same, construct single
3370 condition predicate. */
3373 cond_predicate
.clause
[0] = 1 << cond
;
3374 cond_predicate
.clause
[1] = 0;
3376 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3379 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3381 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3385 /* Update summary information of inline clones after inlining.
3386 Compute peak stack usage. */
3389 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3391 struct cgraph_edge
*e
;
3392 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3393 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3396 callee_info
->stack_frame_offset
3397 = caller_info
->stack_frame_offset
3398 + caller_info
->estimated_self_stack_size
;
3399 peak
= callee_info
->stack_frame_offset
3400 + callee_info
->estimated_self_stack_size
;
3401 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3402 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3403 ipa_propagate_frequency (node
);
3404 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3406 if (!e
->inline_failed
)
3407 inline_update_callee_summaries (e
->callee
, depth
);
3408 inline_edge_summary (e
)->loop_depth
+= depth
;
3410 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3411 inline_edge_summary (e
)->loop_depth
+= depth
;
3414 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3415 When functoin A is inlined in B and A calls C with parameter that
3416 changes with probability PROB1 and C is known to be passthroug
3417 of argument if B that change with probability PROB2, the probability
3418 of change is now PROB1*PROB2. */
3421 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3422 struct cgraph_edge
*edge
)
3424 if (ipa_node_params_sum
)
3427 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3428 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3429 struct inline_edge_summary
*inlined_es
3430 = inline_edge_summary (inlined_edge
);
3432 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3434 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3435 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3436 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3437 < (int) inlined_es
->param
.length ()))
3439 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3440 int prob1
= es
->param
[i
].change_prob
;
3441 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3442 int prob
= combine_probabilities (prob1
, prob2
);
3444 if (prob1
&& prob2
&& !prob
)
3447 es
->param
[i
].change_prob
= prob
;
3453 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3455 Remap predicates of callees of NODE. Rest of arguments match
3458 Also update change probabilities. */
3461 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3462 struct cgraph_node
*node
,
3463 struct inline_summary
*info
,
3464 struct inline_summary
*callee_info
,
3465 vec
<int> operand_map
,
3466 vec
<int> offset_map
,
3467 clause_t possible_truths
,
3468 struct predicate
*toplev_predicate
)
3470 struct cgraph_edge
*e
;
3471 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3473 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3476 if (e
->inline_failed
)
3478 remap_edge_change_prob (inlined_edge
, e
);
3482 p
= remap_predicate (info
, callee_info
,
3483 es
->predicate
, operand_map
, offset_map
,
3484 possible_truths
, toplev_predicate
);
3485 edge_set_predicate (e
, &p
);
3486 /* TODO: We should remove the edge for code that will be
3487 optimized out, but we need to keep verifiers and tree-inline
3488 happy. Make it cold for now. */
3489 if (false_predicate_p (&p
))
3496 edge_set_predicate (e
, toplev_predicate
);
3499 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3500 operand_map
, offset_map
, possible_truths
,
3503 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3505 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3508 remap_edge_change_prob (inlined_edge
, e
);
3511 p
= remap_predicate (info
, callee_info
,
3512 es
->predicate
, operand_map
, offset_map
,
3513 possible_truths
, toplev_predicate
);
3514 edge_set_predicate (e
, &p
);
3515 /* TODO: We should remove the edge for code that will be optimized
3516 out, but we need to keep verifiers and tree-inline happy.
3517 Make it cold for now. */
3518 if (false_predicate_p (&p
))
3525 edge_set_predicate (e
, toplev_predicate
);
3529 /* Same as remap_predicate, but set result into hint *HINT. */
3532 remap_hint_predicate (struct inline_summary
*info
,
3533 struct inline_summary
*callee_info
,
3534 struct predicate
**hint
,
3535 vec
<int> operand_map
,
3536 vec
<int> offset_map
,
3537 clause_t possible_truths
,
3538 struct predicate
*toplev_predicate
)
3544 p
= remap_predicate (info
, callee_info
,
3546 operand_map
, offset_map
,
3547 possible_truths
, toplev_predicate
);
3548 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3551 set_hint_predicate (hint
, p
);
3553 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3557 /* We inlined EDGE. Update summary of the function we inlined into. */
3560 inline_merge_summary (struct cgraph_edge
*edge
)
3562 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3563 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3564 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3565 struct inline_summary
*info
= inline_summaries
->get (to
);
3566 clause_t clause
= 0; /* not_inline is known to be false. */
3568 vec
<int> operand_map
= vNULL
;
3569 vec
<int> offset_map
= vNULL
;
3571 struct predicate toplev_predicate
;
3572 struct predicate true_p
= true_predicate ();
3573 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3576 toplev_predicate
= *es
->predicate
;
3578 toplev_predicate
= true_predicate ();
3580 if (callee_info
->conds
)
3581 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3582 if (ipa_node_params_sum
&& callee_info
->conds
)
3584 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3585 int count
= ipa_get_cs_argument_count (args
);
3590 operand_map
.safe_grow_cleared (count
);
3591 offset_map
.safe_grow_cleared (count
);
3593 for (i
= 0; i
< count
; i
++)
3595 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3598 /* TODO: handle non-NOPs when merging. */
3599 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3601 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3602 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3603 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3606 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3608 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3609 if (offset
>= 0 && offset
< INT_MAX
)
3611 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3612 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3614 offset_map
[i
] = offset
;
3617 operand_map
[i
] = map
;
3618 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3621 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3623 struct predicate p
= remap_predicate (info
, callee_info
,
3624 &e
->predicate
, operand_map
,
3627 if (!false_predicate_p (&p
))
3629 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3630 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3631 int prob
= predicate_probability (callee_info
->conds
,
3634 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3635 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3636 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3637 if (prob
!= REG_BR_PROB_BASE
3638 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3640 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3641 (double) prob
/ REG_BR_PROB_BASE
);
3643 account_size_time (info
, e
->size
, add_time
, &p
);
3646 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3647 offset_map
, clause
, &toplev_predicate
);
3648 remap_hint_predicate (info
, callee_info
,
3649 &callee_info
->loop_iterations
,
3650 operand_map
, offset_map
, clause
, &toplev_predicate
);
3651 remap_hint_predicate (info
, callee_info
,
3652 &callee_info
->loop_stride
,
3653 operand_map
, offset_map
, clause
, &toplev_predicate
);
3654 remap_hint_predicate (info
, callee_info
,
3655 &callee_info
->array_index
,
3656 operand_map
, offset_map
, clause
, &toplev_predicate
);
3658 inline_update_callee_summaries (edge
->callee
,
3659 inline_edge_summary (edge
)->loop_depth
);
3661 /* We do not maintain predicates of inlined edges, free it. */
3662 edge_set_predicate (edge
, &true_p
);
3663 /* Similarly remove param summaries. */
3664 es
->param
.release ();
3665 operand_map
.release ();
3666 offset_map
.release ();
3669 /* For performance reasons inline_merge_summary is not updating overall size
3670 and time. Recompute it. */
3673 inline_update_overall_summary (struct cgraph_node
*node
)
3675 struct inline_summary
*info
= inline_summaries
->get (node
);
3681 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3683 info
->size
+= e
->size
, info
->time
+= e
->time
;
3684 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3685 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3687 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3689 ~(clause_t
) (1 << predicate_false_condition
),
3690 vNULL
, vNULL
, vNULL
);
3691 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3692 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3695 /* Return hints derrived from EDGE. */
3697 simple_edge_hints (struct cgraph_edge
*edge
)
3700 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3701 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3702 if (inline_summaries
->get (to
)->scc_no
3703 && inline_summaries
->get (to
)->scc_no
== inline_summaries
->get (edge
->callee
)->scc_no
3704 && !edge
->recursive_p ())
3705 hints
|= INLINE_HINT_same_scc
;
3707 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3708 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3709 hints
|= INLINE_HINT_cross_module
;
3714 /* Estimate the time cost for the caller when inlining EDGE.
3715 Only to be called via estimate_edge_time, that handles the
3718 When caching, also update the cache entry. Compute both time and
3719 size, since we always need both metrics eventually. */
3722 do_estimate_edge_time (struct cgraph_edge
*edge
)
3727 struct cgraph_node
*callee
;
3729 vec
<tree
> known_vals
;
3730 vec
<ipa_polymorphic_call_context
> known_contexts
;
3731 vec
<ipa_agg_jump_function_p
> known_aggs
;
3732 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3735 callee
= edge
->callee
->ultimate_alias_target ();
3737 gcc_checking_assert (edge
->inline_failed
);
3738 evaluate_properties_for_edge (edge
, true,
3739 &clause
, &known_vals
, &known_contexts
,
3741 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3742 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3744 /* When we have profile feedback, we can quite safely identify hot
3745 edges and for those we disable size limits. Don't do that when
3746 probability that caller will call the callee is low however, since it
3747 may hurt optimization of the caller's hot path. */
3748 if (edge
->count
&& edge
->maybe_hot_p ()
3750 > (edge
->caller
->global
.inlined_to
3751 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3752 hints
|= INLINE_HINT_known_hot
;
3754 known_vals
.release ();
3755 known_contexts
.release ();
3756 known_aggs
.release ();
3757 gcc_checking_assert (size
>= 0);
3758 gcc_checking_assert (time
>= 0);
3760 /* When caching, update the cache entry. */
3761 if (edge_growth_cache
.exists ())
3763 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3764 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3765 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3766 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3768 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3769 hints
|= simple_edge_hints (edge
);
3770 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3776 /* Return estimated callee growth after inlining EDGE.
3777 Only to be called via estimate_edge_size. */
3780 do_estimate_edge_size (struct cgraph_edge
*edge
)
3783 struct cgraph_node
*callee
;
3785 vec
<tree
> known_vals
;
3786 vec
<ipa_polymorphic_call_context
> known_contexts
;
3787 vec
<ipa_agg_jump_function_p
> known_aggs
;
3789 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3791 if (edge_growth_cache
.exists ())
3793 do_estimate_edge_time (edge
);
3794 size
= edge_growth_cache
[edge
->uid
].size
;
3795 gcc_checking_assert (size
);
3796 return size
- (size
> 0);
3799 callee
= edge
->callee
->ultimate_alias_target ();
3801 /* Early inliner runs without caching, go ahead and do the dirty work. */
3802 gcc_checking_assert (edge
->inline_failed
);
3803 evaluate_properties_for_edge (edge
, true,
3804 &clause
, &known_vals
, &known_contexts
,
3806 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3807 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3808 known_vals
.release ();
3809 known_contexts
.release ();
3810 known_aggs
.release ();
3815 /* Estimate the growth of the caller when inlining EDGE.
3816 Only to be called via estimate_edge_size. */
3819 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3822 struct cgraph_node
*callee
;
3824 vec
<tree
> known_vals
;
3825 vec
<ipa_polymorphic_call_context
> known_contexts
;
3826 vec
<ipa_agg_jump_function_p
> known_aggs
;
3828 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3830 if (edge_growth_cache
.exists ())
3832 do_estimate_edge_time (edge
);
3833 hints
= edge_growth_cache
[edge
->uid
].hints
;
3834 gcc_checking_assert (hints
);
3838 callee
= edge
->callee
->ultimate_alias_target ();
3840 /* Early inliner runs without caching, go ahead and do the dirty work. */
3841 gcc_checking_assert (edge
->inline_failed
);
3842 evaluate_properties_for_edge (edge
, true,
3843 &clause
, &known_vals
, &known_contexts
,
3845 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3846 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3847 known_vals
.release ();
3848 known_contexts
.release ();
3849 known_aggs
.release ();
3850 hints
|= simple_edge_hints (edge
);
3855 /* Estimate self time of the function NODE after inlining EDGE. */
3858 estimate_time_after_inlining (struct cgraph_node
*node
,
3859 struct cgraph_edge
*edge
)
3861 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3862 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3865 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3868 if (time
> MAX_TIME
)
3872 return inline_summaries
->get (node
)->time
;
3876 /* Estimate the size of NODE after inlining EDGE which should be an
3877 edge to either NODE or a call inlined into NODE. */
3880 estimate_size_after_inlining (struct cgraph_node
*node
,
3881 struct cgraph_edge
*edge
)
3883 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3884 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3886 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3887 gcc_assert (size
>= 0);
3890 return inline_summaries
->get (node
)->size
;
3896 struct cgraph_node
*node
;
3897 bool self_recursive
;
3902 /* Worker for do_estimate_growth. Collect growth for all callers. */
3905 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3907 struct cgraph_edge
*e
;
3908 struct growth_data
*d
= (struct growth_data
*) data
;
3910 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3912 gcc_checking_assert (e
->inline_failed
);
3914 if (e
->caller
== d
->node
3915 || (e
->caller
->global
.inlined_to
3916 && e
->caller
->global
.inlined_to
== d
->node
))
3917 d
->self_recursive
= true;
3918 d
->growth
+= estimate_edge_growth (e
);
3924 /* Estimate the growth caused by inlining NODE into all callees. */
3927 do_estimate_growth (struct cgraph_node
*node
)
3929 struct growth_data d
= { node
, 0, false };
3930 struct inline_summary
*info
= inline_summaries
->get (node
);
3932 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3934 /* For self recursive functions the growth estimation really should be
3935 infinity. We don't want to return very large values because the growth
3936 plays various roles in badness computation fractions. Be sure to not
3937 return zero or negative growths. */
3938 if (d
.self_recursive
)
3939 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3940 else if (DECL_EXTERNAL (node
->decl
))
3944 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3945 d
.growth
-= info
->size
;
3946 /* COMDAT functions are very often not shared across multiple units
3947 since they come from various template instantiations.
3948 Take this into account. */
3949 else if (DECL_COMDAT (node
->decl
)
3950 && node
->can_remove_if_no_direct_calls_p ())
3951 d
.growth
-= (info
->size
3952 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3956 if (node_growth_cache
.exists ())
3958 if ((int) node_growth_cache
.length () <= node
->uid
)
3959 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3960 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3966 /* Make cheap estimation if growth of NODE is likely positive knowing
3967 EDGE_GROWTH of one particular edge.
3968 We assume that most of other edges will have similar growth
3969 and skip computation if there are too many callers. */
3972 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3976 struct cgraph_edge
*e
;
3977 gcc_checking_assert (edge_growth
> 0);
3979 /* Unlike for functions called once, we play unsafe with
3980 COMDATs. We can allow that since we know functions
3981 in consideration are small (and thus risk is small) and
3982 moreover grow estimates already accounts that COMDAT
3983 functions may or may not disappear when eliminated from
3984 current unit. With good probability making aggressive
3985 choice in all units is going to make overall program
3988 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3990 cgraph_will_be_removed_from_program_if_no_direct_calls */
3991 if (DECL_EXTERNAL (node
->decl
)
3992 || !node
->can_remove_if_no_direct_calls_p ())
3995 /* If there is cached value, just go ahead. */
3996 if ((int)node_growth_cache
.length () > node
->uid
3997 && (ret
= node_growth_cache
[node
->uid
]))
3999 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
4000 && (!DECL_COMDAT (node
->decl
)
4001 || !node
->can_remove_if_no_direct_calls_p ()))
4003 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4005 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4011 return estimate_growth (node
) > 0;
4015 /* This function performs intraprocedural analysis in NODE that is required to
4016 inline indirect calls. */
4019 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4021 ipa_analyze_node (node
);
4022 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4024 ipa_print_node_params (dump_file
, node
);
4025 ipa_print_node_jump_functions (dump_file
, node
);
4030 /* Note function body size. */
4033 inline_analyze_function (struct cgraph_node
*node
)
4035 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4038 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4039 node
->name (), node
->order
);
4040 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4041 inline_indirect_intraprocedural_analysis (node
);
4042 compute_inline_parameters (node
, false);
4045 struct cgraph_edge
*e
;
4046 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4048 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4049 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4050 e
->call_stmt_cannot_inline_p
= true;
4052 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4054 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4055 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4056 e
->call_stmt_cannot_inline_p
= true;
4064 /* Called when new function is inserted to callgraph late. */
4067 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4069 inline_analyze_function (node
);
4072 /* Note function body size. */
4075 inline_generate_summary (void)
4077 struct cgraph_node
*node
;
4079 /* When not optimizing, do not bother to analyze. Inlining is still done
4080 because edge redirection needs to happen there. */
4081 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4084 if (!inline_summaries
)
4085 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4087 inline_summaries
->enable_insertion_hook ();
4089 ipa_register_cgraph_hooks ();
4090 inline_free_summary ();
4092 FOR_EACH_DEFINED_FUNCTION (node
)
4094 inline_analyze_function (node
);
4098 /* Read predicate from IB. */
4100 static struct predicate
4101 read_predicate (struct lto_input_block
*ib
)
4103 struct predicate out
;
4109 gcc_assert (k
<= MAX_CLAUSES
);
4110 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4114 /* Zero-initialize the remaining clauses in OUT. */
4115 while (k
<= MAX_CLAUSES
)
4116 out
.clause
[k
++] = 0;
4122 /* Write inline summary for edge E to OB. */
4125 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4127 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4131 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4132 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4133 es
->loop_depth
= streamer_read_uhwi (ib
);
4134 p
= read_predicate (ib
);
4135 edge_set_predicate (e
, &p
);
4136 length
= streamer_read_uhwi (ib
);
4139 es
->param
.safe_grow_cleared (length
);
4140 for (i
= 0; i
< length
; i
++)
4141 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4146 /* Stream in inline summaries from the section. */
4149 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4152 const struct lto_function_header
*header
=
4153 (const struct lto_function_header
*) data
;
4154 const int cfg_offset
= sizeof (struct lto_function_header
);
4155 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4156 const int string_offset
= main_offset
+ header
->main_size
;
4157 struct data_in
*data_in
;
4158 unsigned int i
, count2
, j
;
4159 unsigned int f_count
;
4161 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4164 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4165 header
->string_size
, vNULL
);
4166 f_count
= streamer_read_uhwi (&ib
);
4167 for (i
= 0; i
< f_count
; i
++)
4170 struct cgraph_node
*node
;
4171 struct inline_summary
*info
;
4172 lto_symtab_encoder_t encoder
;
4173 struct bitpack_d bp
;
4174 struct cgraph_edge
*e
;
4177 index
= streamer_read_uhwi (&ib
);
4178 encoder
= file_data
->symtab_node_encoder
;
4179 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4181 info
= inline_summaries
->get (node
);
4183 info
->estimated_stack_size
4184 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4185 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4186 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4188 bp
= streamer_read_bitpack (&ib
);
4189 info
->inlinable
= bp_unpack_value (&bp
, 1);
4191 count2
= streamer_read_uhwi (&ib
);
4192 gcc_assert (!info
->conds
);
4193 for (j
= 0; j
< count2
; j
++)
4196 c
.operand_num
= streamer_read_uhwi (&ib
);
4197 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4198 c
.val
= stream_read_tree (&ib
, data_in
);
4199 bp
= streamer_read_bitpack (&ib
);
4200 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4201 c
.by_ref
= bp_unpack_value (&bp
, 1);
4203 c
.offset
= streamer_read_uhwi (&ib
);
4204 vec_safe_push (info
->conds
, c
);
4206 count2
= streamer_read_uhwi (&ib
);
4207 gcc_assert (!info
->entry
);
4208 for (j
= 0; j
< count2
; j
++)
4210 struct size_time_entry e
;
4212 e
.size
= streamer_read_uhwi (&ib
);
4213 e
.time
= streamer_read_uhwi (&ib
);
4214 e
.predicate
= read_predicate (&ib
);
4216 vec_safe_push (info
->entry
, e
);
4219 p
= read_predicate (&ib
);
4220 set_hint_predicate (&info
->loop_iterations
, p
);
4221 p
= read_predicate (&ib
);
4222 set_hint_predicate (&info
->loop_stride
, p
);
4223 p
= read_predicate (&ib
);
4224 set_hint_predicate (&info
->array_index
, p
);
4225 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4226 read_inline_edge_summary (&ib
, e
);
4227 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4228 read_inline_edge_summary (&ib
, e
);
4231 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4233 lto_data_in_delete (data_in
);
4237 /* Read inline summary. Jump functions are shared among ipa-cp
4238 and inliner, so when ipa-cp is active, we don't need to write them
4242 inline_read_summary (void)
4244 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4245 struct lto_file_decl_data
*file_data
;
4248 inline_summary_alloc ();
4250 while ((file_data
= file_data_vec
[j
++]))
4253 const char *data
= lto_get_section_data (file_data
,
4254 LTO_section_inline_summary
,
4257 inline_read_section (file_data
, data
, len
);
4259 /* Fatal error here. We do not want to support compiling ltrans units
4260 with different version of compiler or different flags than the WPA
4261 unit, so this should never happen. */
4262 fatal_error ("ipa inline summary is missing in input file");
4266 ipa_register_cgraph_hooks ();
4268 ipa_prop_read_jump_functions ();
4271 gcc_assert (inline_summaries
);
4272 inline_summaries
->enable_insertion_hook ();
4276 /* Write predicate P to OB. */
4279 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4283 for (j
= 0; p
->clause
[j
]; j
++)
4285 gcc_assert (j
< MAX_CLAUSES
);
4286 streamer_write_uhwi (ob
, p
->clause
[j
]);
4288 streamer_write_uhwi (ob
, 0);
4292 /* Write inline summary for edge E to OB. */
4295 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4297 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4300 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4301 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4302 streamer_write_uhwi (ob
, es
->loop_depth
);
4303 write_predicate (ob
, es
->predicate
);
4304 streamer_write_uhwi (ob
, es
->param
.length ());
4305 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4306 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4310 /* Write inline summary for node in SET.
4311 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4312 active, we don't need to write them twice. */
4315 inline_write_summary (void)
4317 struct cgraph_node
*node
;
4318 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4319 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4320 unsigned int count
= 0;
4323 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4325 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4326 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4327 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4330 streamer_write_uhwi (ob
, count
);
4332 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4334 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4335 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4336 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4338 struct inline_summary
*info
= inline_summaries
->get (node
);
4339 struct bitpack_d bp
;
4340 struct cgraph_edge
*edge
;
4343 struct condition
*c
;
4345 streamer_write_uhwi (ob
,
4346 lto_symtab_encoder_encode (encoder
,
4349 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4350 streamer_write_hwi (ob
, info
->self_size
);
4351 streamer_write_hwi (ob
, info
->self_time
);
4352 bp
= bitpack_create (ob
->main_stream
);
4353 bp_pack_value (&bp
, info
->inlinable
, 1);
4354 streamer_write_bitpack (&bp
);
4355 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4356 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4358 streamer_write_uhwi (ob
, c
->operand_num
);
4359 streamer_write_uhwi (ob
, c
->code
);
4360 stream_write_tree (ob
, c
->val
, true);
4361 bp
= bitpack_create (ob
->main_stream
);
4362 bp_pack_value (&bp
, c
->agg_contents
, 1);
4363 bp_pack_value (&bp
, c
->by_ref
, 1);
4364 streamer_write_bitpack (&bp
);
4365 if (c
->agg_contents
)
4366 streamer_write_uhwi (ob
, c
->offset
);
4368 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4369 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4371 streamer_write_uhwi (ob
, e
->size
);
4372 streamer_write_uhwi (ob
, e
->time
);
4373 write_predicate (ob
, &e
->predicate
);
4375 write_predicate (ob
, info
->loop_iterations
);
4376 write_predicate (ob
, info
->loop_stride
);
4377 write_predicate (ob
, info
->array_index
);
4378 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4379 write_inline_edge_summary (ob
, edge
);
4380 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4381 write_inline_edge_summary (ob
, edge
);
4384 streamer_write_char_stream (ob
->main_stream
, 0);
4385 produce_asm (ob
, NULL
);
4386 destroy_output_block (ob
);
4388 if (optimize
&& !flag_ipa_cp
)
4389 ipa_prop_write_jump_functions ();
4393 /* Release inline summary. */
4396 inline_free_summary (void)
4398 struct cgraph_node
*node
;
4399 if (edge_removal_hook_holder
)
4400 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4401 edge_removal_hook_holder
= NULL
;
4402 if (edge_duplication_hook_holder
)
4403 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4404 edge_duplication_hook_holder
= NULL
;
4405 if (!inline_edge_summary_vec
.exists ())
4407 FOR_EACH_DEFINED_FUNCTION (node
)
4409 reset_inline_summary (node
, inline_summaries
->get (node
));
4410 inline_summaries
->release ();
4411 inline_summaries
= NULL
;
4412 inline_edge_summary_vec
.release ();
4413 if (edge_predicate_pool
)
4414 free_alloc_pool (edge_predicate_pool
);
4415 edge_predicate_pool
= 0;