1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
72 #include "stor-layout.h"
73 #include "stringpool.h"
74 #include "print-tree.h"
75 #include "tree-inline.h"
76 #include "langhooks.h"
78 #include "diagnostic.h"
79 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
83 #include "basic-block.h"
84 #include "tree-ssa-alias.h"
85 #include "internal-fn.h"
86 #include "gimple-expr.h"
89 #include "gimple-iterator.h"
90 #include "gimple-ssa.h"
92 #include "tree-phinodes.h"
93 #include "ssa-iterators.h"
94 #include "tree-ssanames.h"
95 #include "tree-ssa-loop-niter.h"
96 #include "tree-ssa-loop.h"
98 #include "lto-streamer.h"
99 #include "data-streamer.h"
100 #include "tree-streamer.h"
101 #include "ipa-inline.h"
102 #include "alloc-pool.h"
104 #include "tree-scalar-evolution.h"
105 #include "ipa-utils.h"
107 #include "cfgexpand.h"
109 /* Estimate runtime of function can easilly run into huge numbers with many
110 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
111 integer. For anything larger we use gcov_type. */
112 #define MAX_TIME 500000
114 /* Number of bits in integer, but we really want to be stable across different
116 #define NUM_CONDITIONS 32
118 enum predicate_conditions
120 predicate_false_condition
= 0,
121 predicate_not_inlined_condition
= 1,
122 predicate_first_dynamic_condition
= 2
125 /* Special condition code we use to represent test that operand is compile time
127 #define IS_NOT_CONSTANT ERROR_MARK
128 /* Special condition code we use to represent test that operand is not changed
129 across invocation of the function. When operand IS_NOT_CONSTANT it is always
130 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
131 of executions even when they are not compile time constants. */
132 #define CHANGED IDENTIFIER_NODE
134 /* Holders of ipa cgraph hooks: */
135 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
136 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
137 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
138 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
139 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
140 static void inline_node_removal_hook (struct cgraph_node
*, void *);
141 static void inline_node_duplication_hook (struct cgraph_node
*,
142 struct cgraph_node
*, void *);
143 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
144 static void inline_edge_duplication_hook (struct cgraph_edge
*,
145 struct cgraph_edge
*, void *);
147 /* VECtor holding inline summaries.
148 In GGC memory because conditions might point to constant trees. */
149 vec
<inline_summary_t
, va_gc
> *inline_summary_vec
;
150 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
152 /* Cached node/edge growths. */
153 vec
<int> node_growth_cache
;
154 vec
<edge_growth_cache_entry
> edge_growth_cache
;
156 /* Edge predicates goes here. */
157 static alloc_pool edge_predicate_pool
;
159 /* Return true predicate (tautology).
160 We represent it by empty list of clauses. */
162 static inline struct predicate
163 true_predicate (void)
171 /* Return predicate testing single condition number COND. */
173 static inline struct predicate
174 single_cond_predicate (int cond
)
177 p
.clause
[0] = 1 << cond
;
183 /* Return false predicate. First clause require false condition. */
185 static inline struct predicate
186 false_predicate (void)
188 return single_cond_predicate (predicate_false_condition
);
192 /* Return true if P is (true). */
195 true_predicate_p (struct predicate
*p
)
197 return !p
->clause
[0];
201 /* Return true if P is (false). */
204 false_predicate_p (struct predicate
*p
)
206 if (p
->clause
[0] == (1 << predicate_false_condition
))
208 gcc_checking_assert (!p
->clause
[1]
209 && p
->clause
[0] == 1 << predicate_false_condition
);
216 /* Return predicate that is set true when function is not inlined. */
218 static inline struct predicate
219 not_inlined_predicate (void)
221 return single_cond_predicate (predicate_not_inlined_condition
);
224 /* Simple description of whether a memory load or a condition refers to a load
225 from an aggregate and if so, how and where from in the aggregate.
226 Individual fields have the same meaning like fields with the same name in
229 struct agg_position_info
231 HOST_WIDE_INT offset
;
236 /* Add condition to condition list CONDS. AGGPOS describes whether the used
237 oprand is loaded from an aggregate and where in the aggregate it is. It can
238 be NULL, which means this not a load from an aggregate. */
240 static struct predicate
241 add_condition (struct inline_summary
*summary
, int operand_num
,
242 struct agg_position_info
*aggpos
,
243 enum tree_code code
, tree val
)
247 struct condition new_cond
;
248 HOST_WIDE_INT offset
;
249 bool agg_contents
, by_ref
;
253 offset
= aggpos
->offset
;
254 agg_contents
= aggpos
->agg_contents
;
255 by_ref
= aggpos
->by_ref
;
260 agg_contents
= false;
264 gcc_checking_assert (operand_num
>= 0);
265 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
267 if (c
->operand_num
== operand_num
270 && c
->agg_contents
== agg_contents
271 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
272 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
274 /* Too many conditions. Give up and return constant true. */
275 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
276 return true_predicate ();
278 new_cond
.operand_num
= operand_num
;
279 new_cond
.code
= code
;
281 new_cond
.agg_contents
= agg_contents
;
282 new_cond
.by_ref
= by_ref
;
283 new_cond
.offset
= offset
;
284 vec_safe_push (summary
->conds
, new_cond
);
285 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
289 /* Add clause CLAUSE into the predicate P. */
292 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
296 int insert_here
= -1;
303 /* False clause makes the whole predicate false. Kill the other variants. */
304 if (clause
== (1 << predicate_false_condition
))
306 p
->clause
[0] = (1 << predicate_false_condition
);
310 if (false_predicate_p (p
))
313 /* No one should be silly enough to add false into nontrivial clauses. */
314 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
316 /* Look where to insert the clause. At the same time prune out
317 clauses of P that are implied by the new clause and thus
319 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
321 p
->clause
[i2
] = p
->clause
[i
];
326 /* If p->clause[i] implies clause, there is nothing to add. */
327 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
329 /* We had nothing to add, none of clauses should've become
331 gcc_checking_assert (i
== i2
);
335 if (p
->clause
[i
] < clause
&& insert_here
< 0)
338 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
339 Otherwise the p->clause[i] has to stay. */
340 if ((p
->clause
[i
] & clause
) != clause
)
344 /* Look for clauses that are obviously true. I.e.
345 op0 == 5 || op0 != 5. */
346 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
349 if (!(clause
& (1 << c1
)))
351 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
352 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
353 and thus there is no point for looking for them. */
354 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
356 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
357 if (clause
& (1 << c2
))
360 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
362 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
363 if (cc1
->operand_num
== cc2
->operand_num
364 && cc1
->val
== cc2
->val
365 && cc2
->code
!= IS_NOT_CONSTANT
366 && cc2
->code
!= CHANGED
367 && cc1
->code
== invert_tree_comparison
369 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1
->val
)))))
375 /* We run out of variants. Be conservative in positive direction. */
376 if (i2
== MAX_CLAUSES
)
378 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
379 p
->clause
[i2
+ 1] = 0;
380 if (insert_here
>= 0)
381 for (; i2
> insert_here
; i2
--)
382 p
->clause
[i2
] = p
->clause
[i2
- 1];
385 p
->clause
[insert_here
] = clause
;
391 static struct predicate
392 and_predicates (conditions conditions
,
393 struct predicate
*p
, struct predicate
*p2
)
395 struct predicate out
= *p
;
398 /* Avoid busy work. */
399 if (false_predicate_p (p2
) || true_predicate_p (p
))
401 if (false_predicate_p (p
) || true_predicate_p (p2
))
404 /* See how far predicates match. */
405 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
407 gcc_checking_assert (i
< MAX_CLAUSES
);
410 /* Combine the predicates rest. */
411 for (; p2
->clause
[i
]; i
++)
413 gcc_checking_assert (i
< MAX_CLAUSES
);
414 add_clause (conditions
, &out
, p2
->clause
[i
]);
420 /* Return true if predicates are obviously equal. */
423 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
426 for (i
= 0; p
->clause
[i
]; i
++)
428 gcc_checking_assert (i
< MAX_CLAUSES
);
429 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
430 gcc_checking_assert (!p2
->clause
[i
]
431 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
432 if (p
->clause
[i
] != p2
->clause
[i
])
435 return !p2
->clause
[i
];
441 static struct predicate
442 or_predicates (conditions conditions
,
443 struct predicate
*p
, struct predicate
*p2
)
445 struct predicate out
= true_predicate ();
448 /* Avoid busy work. */
449 if (false_predicate_p (p2
) || true_predicate_p (p
))
451 if (false_predicate_p (p
) || true_predicate_p (p2
))
453 if (predicates_equal_p (p
, p2
))
456 /* OK, combine the predicates. */
457 for (i
= 0; p
->clause
[i
]; i
++)
458 for (j
= 0; p2
->clause
[j
]; j
++)
460 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
461 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
467 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
468 if predicate P is known to be false. */
471 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
475 /* True remains true. */
476 if (true_predicate_p (p
))
479 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
481 /* See if we can find clause we can disprove. */
482 for (i
= 0; p
->clause
[i
]; i
++)
484 gcc_checking_assert (i
< MAX_CLAUSES
);
485 if (!(p
->clause
[i
] & possible_truths
))
491 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
492 instruction will be recomputed per invocation of the inlined call. */
495 predicate_probability (conditions conds
,
496 struct predicate
*p
, clause_t possible_truths
,
497 vec
<inline_param_summary
> inline_param_summary
)
500 int combined_prob
= REG_BR_PROB_BASE
;
502 /* True remains true. */
503 if (true_predicate_p (p
))
504 return REG_BR_PROB_BASE
;
506 if (false_predicate_p (p
))
509 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
511 /* See if we can find clause we can disprove. */
512 for (i
= 0; p
->clause
[i
]; i
++)
514 gcc_checking_assert (i
< MAX_CLAUSES
);
515 if (!(p
->clause
[i
] & possible_truths
))
521 if (!inline_param_summary
.exists ())
522 return REG_BR_PROB_BASE
;
523 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
524 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
526 if (i2
>= predicate_first_dynamic_condition
)
529 &(*conds
)[i2
- predicate_first_dynamic_condition
];
530 if (c
->code
== CHANGED
532 (int) inline_param_summary
.length ()))
535 inline_param_summary
[c
->operand_num
].change_prob
;
536 this_prob
= MAX (this_prob
, iprob
);
539 this_prob
= REG_BR_PROB_BASE
;
542 this_prob
= REG_BR_PROB_BASE
;
544 combined_prob
= MIN (this_prob
, combined_prob
);
549 return combined_prob
;
553 /* Dump conditional COND. */
556 dump_condition (FILE *f
, conditions conditions
, int cond
)
559 if (cond
== predicate_false_condition
)
560 fprintf (f
, "false");
561 else if (cond
== predicate_not_inlined_condition
)
562 fprintf (f
, "not inlined");
565 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
566 fprintf (f
, "op%i", c
->operand_num
);
568 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
569 c
->by_ref
? "ref " : "", c
->offset
);
570 if (c
->code
== IS_NOT_CONSTANT
)
572 fprintf (f
, " not constant");
575 if (c
->code
== CHANGED
)
577 fprintf (f
, " changed");
580 fprintf (f
, " %s ", op_symbol_code (c
->code
));
581 print_generic_expr (f
, c
->val
, 1);
586 /* Dump clause CLAUSE. */
589 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
596 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
597 if (clause
& (1 << i
))
602 dump_condition (f
, conds
, i
);
608 /* Dump predicate PREDICATE. */
611 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
614 if (true_predicate_p (pred
))
615 dump_clause (f
, conds
, 0);
617 for (i
= 0; pred
->clause
[i
]; i
++)
621 dump_clause (f
, conds
, pred
->clause
[i
]);
627 /* Dump inline hints. */
629 dump_inline_hints (FILE *f
, inline_hints hints
)
633 fprintf (f
, "inline hints:");
634 if (hints
& INLINE_HINT_indirect_call
)
636 hints
&= ~INLINE_HINT_indirect_call
;
637 fprintf (f
, " indirect_call");
639 if (hints
& INLINE_HINT_loop_iterations
)
641 hints
&= ~INLINE_HINT_loop_iterations
;
642 fprintf (f
, " loop_iterations");
644 if (hints
& INLINE_HINT_loop_stride
)
646 hints
&= ~INLINE_HINT_loop_stride
;
647 fprintf (f
, " loop_stride");
649 if (hints
& INLINE_HINT_same_scc
)
651 hints
&= ~INLINE_HINT_same_scc
;
652 fprintf (f
, " same_scc");
654 if (hints
& INLINE_HINT_in_scc
)
656 hints
&= ~INLINE_HINT_in_scc
;
657 fprintf (f
, " in_scc");
659 if (hints
& INLINE_HINT_cross_module
)
661 hints
&= ~INLINE_HINT_cross_module
;
662 fprintf (f
, " cross_module");
664 if (hints
& INLINE_HINT_declared_inline
)
666 hints
&= ~INLINE_HINT_declared_inline
;
667 fprintf (f
, " declared_inline");
669 if (hints
& INLINE_HINT_array_index
)
671 hints
&= ~INLINE_HINT_array_index
;
672 fprintf (f
, " array_index");
678 /* Record SIZE and TIME under condition PRED into the inline summary. */
681 account_size_time (struct inline_summary
*summary
, int size
, int time
,
682 struct predicate
*pred
)
688 if (false_predicate_p (pred
))
691 /* We need to create initial empty unconitional clause, but otherwie
692 we don't need to account empty times and sizes. */
693 if (!size
&& !time
&& summary
->entry
)
696 /* Watch overflow that might result from insane profiles. */
697 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
698 time
= MAX_TIME
* INLINE_TIME_SCALE
;
699 gcc_assert (time
>= 0);
701 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
702 if (predicates_equal_p (&e
->predicate
, pred
))
711 e
= &(*summary
->entry
)[0];
712 gcc_assert (!e
->predicate
.clause
[0]);
713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
715 "\t\tReached limit on number of entries, "
716 "ignoring the predicate.");
718 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
721 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
722 ((double) size
) / INLINE_SIZE_SCALE
,
723 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
724 dump_predicate (dump_file
, summary
->conds
, pred
);
728 struct size_time_entry new_entry
;
729 new_entry
.size
= size
;
730 new_entry
.time
= time
;
731 new_entry
.predicate
= *pred
;
732 vec_safe_push (summary
->entry
, new_entry
);
738 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
739 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
743 /* Set predicate for edge E. */
746 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
748 struct inline_edge_summary
*es
= inline_edge_summary (e
);
750 /* If the edge is determined to be never executed, redirect it
751 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
752 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
754 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
756 cgraph_redirect_edge_callee (e
,
757 cgraph_get_create_node
758 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
759 e
->inline_failed
= CIF_UNREACHABLE
;
761 cgraph_remove_node_and_inline_clones (callee
, NULL
);
763 if (predicate
&& !true_predicate_p (predicate
))
766 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
767 *es
->predicate
= *predicate
;
772 pool_free (edge_predicate_pool
, es
->predicate
);
773 es
->predicate
= NULL
;
777 /* Set predicate for hint *P. */
780 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
782 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
785 pool_free (edge_predicate_pool
, *p
);
791 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
797 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
798 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
799 Return clause of possible truths. When INLINE_P is true, assume that we are
802 ERROR_MARK means compile time invariant. */
805 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
807 vec
<tree
> known_vals
,
808 vec
<ipa_agg_jump_function_p
>
811 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
812 struct inline_summary
*info
= inline_summary (node
);
816 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
821 /* We allow call stmt to have fewer arguments than the callee function
822 (especially for K&R style programs). So bound check here (we assume
823 known_aggs vector, if non-NULL, has the same length as
825 gcc_checking_assert (!known_aggs
.exists ()
826 || (known_vals
.length () == known_aggs
.length ()));
827 if (c
->operand_num
>= (int) known_vals
.length ())
829 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
835 struct ipa_agg_jump_function
*agg
;
837 if (c
->code
== CHANGED
839 && (known_vals
[c
->operand_num
] == error_mark_node
))
842 if (known_aggs
.exists ())
844 agg
= known_aggs
[c
->operand_num
];
845 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
852 val
= known_vals
[c
->operand_num
];
853 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
859 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
862 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
864 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
865 if (res
&& integer_zerop (res
))
867 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
873 /* Work out what conditions might be true at invocation of E. */
876 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
877 clause_t
*clause_ptr
,
878 vec
<tree
> *known_vals_ptr
,
879 vec
<tree
> *known_binfos_ptr
,
880 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
882 struct cgraph_node
*callee
=
883 cgraph_function_or_thunk_node (e
->callee
, NULL
);
884 struct inline_summary
*info
= inline_summary (callee
);
885 vec
<tree
> known_vals
= vNULL
;
886 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
889 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
891 known_vals_ptr
->create (0);
892 if (known_binfos_ptr
)
893 known_binfos_ptr
->create (0);
895 if (ipa_node_params_vector
.exists ()
896 && !e
->call_stmt_cannot_inline_p
897 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_binfos_ptr
))
899 struct ipa_node_params
*parms_info
;
900 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
901 struct inline_edge_summary
*es
= inline_edge_summary (e
);
902 int i
, count
= ipa_get_cs_argument_count (args
);
904 if (e
->caller
->global
.inlined_to
)
905 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
907 parms_info
= IPA_NODE_REF (e
->caller
);
909 if (count
&& (info
->conds
|| known_vals_ptr
))
910 known_vals
.safe_grow_cleared (count
);
911 if (count
&& (info
->conds
|| known_aggs_ptr
))
912 known_aggs
.safe_grow_cleared (count
);
913 if (count
&& known_binfos_ptr
)
914 known_binfos_ptr
->safe_grow_cleared (count
);
916 for (i
= 0; i
< count
; i
++)
918 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
919 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
922 if (known_vals
.exists () && TREE_CODE (cst
) != TREE_BINFO
)
924 else if (known_binfos_ptr
!= NULL
925 && TREE_CODE (cst
) == TREE_BINFO
)
926 (*known_binfos_ptr
)[i
] = cst
;
928 else if (inline_p
&& !es
->param
[i
].change_prob
)
929 known_vals
[i
] = error_mark_node
;
930 /* TODO: When IPA-CP starts propagating and merging aggregate jump
931 functions, use its knowledge of the caller too, just like the
932 scalar case above. */
933 known_aggs
[i
] = &jf
->agg
;
938 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
939 known_vals
, known_aggs
);
942 *known_vals_ptr
= known_vals
;
944 known_vals
.release ();
947 *known_aggs_ptr
= known_aggs
;
949 known_aggs
.release ();
953 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
956 inline_summary_alloc (void)
958 if (!node_removal_hook_holder
)
959 node_removal_hook_holder
=
960 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
961 if (!edge_removal_hook_holder
)
962 edge_removal_hook_holder
=
963 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
964 if (!node_duplication_hook_holder
)
965 node_duplication_hook_holder
=
966 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
967 if (!edge_duplication_hook_holder
)
968 edge_duplication_hook_holder
=
969 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
971 if (vec_safe_length (inline_summary_vec
) <= (unsigned) cgraph_max_uid
)
972 vec_safe_grow_cleared (inline_summary_vec
, cgraph_max_uid
+ 1);
973 if (inline_edge_summary_vec
.length () <= (unsigned) cgraph_edge_max_uid
)
974 inline_edge_summary_vec
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
975 if (!edge_predicate_pool
)
976 edge_predicate_pool
= create_alloc_pool ("edge predicates",
977 sizeof (struct predicate
), 10);
980 /* We are called multiple time for given function; clear
981 data from previous run so they are not cumulated. */
984 reset_inline_edge_summary (struct cgraph_edge
*e
)
986 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
988 struct inline_edge_summary
*es
= inline_edge_summary (e
);
990 es
->call_stmt_size
= es
->call_stmt_time
= 0;
992 pool_free (edge_predicate_pool
, es
->predicate
);
993 es
->predicate
= NULL
;
994 es
->param
.release ();
998 /* We are called multiple time for given function; clear
999 data from previous run so they are not cumulated. */
1002 reset_inline_summary (struct cgraph_node
*node
)
1004 struct inline_summary
*info
= inline_summary (node
);
1005 struct cgraph_edge
*e
;
1007 info
->self_size
= info
->self_time
= 0;
1008 info
->estimated_stack_size
= 0;
1009 info
->estimated_self_stack_size
= 0;
1010 info
->stack_frame_offset
= 0;
1015 if (info
->loop_iterations
)
1017 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1018 info
->loop_iterations
= NULL
;
1020 if (info
->loop_stride
)
1022 pool_free (edge_predicate_pool
, info
->loop_stride
);
1023 info
->loop_stride
= NULL
;
1025 if (info
->array_index
)
1027 pool_free (edge_predicate_pool
, info
->array_index
);
1028 info
->array_index
= NULL
;
1030 vec_free (info
->conds
);
1031 vec_free (info
->entry
);
1032 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1033 reset_inline_edge_summary (e
);
1034 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1035 reset_inline_edge_summary (e
);
1038 /* Hook that is called by cgraph.c when a node is removed. */
1041 inline_node_removal_hook (struct cgraph_node
*node
,
1042 void *data ATTRIBUTE_UNUSED
)
1044 struct inline_summary
*info
;
1045 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1047 info
= inline_summary (node
);
1048 reset_inline_summary (node
);
1049 memset (info
, 0, sizeof (inline_summary_t
));
1052 /* Remap predicate P of former function to be predicate of duplicated function.
1053 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1054 INFO is inline summary of the duplicated node. */
1056 static struct predicate
1057 remap_predicate_after_duplication (struct predicate
*p
,
1058 clause_t possible_truths
,
1059 struct inline_summary
*info
)
1061 struct predicate new_predicate
= true_predicate ();
1063 for (j
= 0; p
->clause
[j
]; j
++)
1064 if (!(possible_truths
& p
->clause
[j
]))
1066 new_predicate
= false_predicate ();
1070 add_clause (info
->conds
, &new_predicate
,
1071 possible_truths
& p
->clause
[j
]);
1072 return new_predicate
;
1075 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1076 Additionally care about allocating new memory slot for updated predicate
1077 and set it to NULL when it becomes true or false (and thus uninteresting).
1081 remap_hint_predicate_after_duplication (struct predicate
**p
,
1082 clause_t possible_truths
,
1083 struct inline_summary
*info
)
1085 struct predicate new_predicate
;
1090 new_predicate
= remap_predicate_after_duplication (*p
,
1091 possible_truths
, info
);
1092 /* We do not want to free previous predicate; it is used by node origin. */
1094 set_hint_predicate (p
, new_predicate
);
1098 /* Hook that is called by cgraph.c when a node is duplicated. */
1101 inline_node_duplication_hook (struct cgraph_node
*src
,
1102 struct cgraph_node
*dst
,
1103 ATTRIBUTE_UNUSED
void *data
)
1105 struct inline_summary
*info
;
1106 inline_summary_alloc ();
1107 info
= inline_summary (dst
);
1108 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1109 /* TODO: as an optimization, we may avoid copying conditions
1110 that are known to be false or true. */
1111 info
->conds
= vec_safe_copy (info
->conds
);
1113 /* When there are any replacements in the function body, see if we can figure
1114 out that something was optimized out. */
1115 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1117 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1118 /* Use SRC parm info since it may not be copied yet. */
1119 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1120 vec
<tree
> known_vals
= vNULL
;
1121 int count
= ipa_get_param_count (parms_info
);
1123 clause_t possible_truths
;
1124 struct predicate true_pred
= true_predicate ();
1126 int optimized_out_size
= 0;
1127 bool inlined_to_p
= false;
1128 struct cgraph_edge
*edge
;
1131 known_vals
.safe_grow_cleared (count
);
1132 for (i
= 0; i
< count
; i
++)
1134 struct ipa_replace_map
*r
;
1136 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1138 if (((!r
->old_tree
&& r
->parm_num
== i
)
1139 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1140 && r
->replace_p
&& !r
->ref_p
)
1142 known_vals
[i
] = r
->new_tree
;
1147 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1150 known_vals
.release ();
1152 account_size_time (info
, 0, 0, &true_pred
);
1154 /* Remap size_time vectors.
1155 Simplify the predicate by prunning out alternatives that are known
1157 TODO: as on optimization, we can also eliminate conditions known
1159 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1161 struct predicate new_predicate
;
1162 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1165 if (false_predicate_p (&new_predicate
))
1166 optimized_out_size
+= e
->size
;
1168 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1171 /* Remap edge predicates with the same simplification as above.
1172 Also copy constantness arrays. */
1173 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1175 struct predicate new_predicate
;
1176 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1178 if (!edge
->inline_failed
)
1179 inlined_to_p
= true;
1182 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1185 if (false_predicate_p (&new_predicate
)
1186 && !false_predicate_p (es
->predicate
))
1188 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1189 edge
->frequency
= 0;
1191 edge_set_predicate (edge
, &new_predicate
);
1194 /* Remap indirect edge predicates with the same simplificaiton as above.
1195 Also copy constantness arrays. */
1196 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1198 struct predicate new_predicate
;
1199 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1201 gcc_checking_assert (edge
->inline_failed
);
1204 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1207 if (false_predicate_p (&new_predicate
)
1208 && !false_predicate_p (es
->predicate
))
1210 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1211 edge
->frequency
= 0;
1213 edge_set_predicate (edge
, &new_predicate
);
1215 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1216 possible_truths
, info
);
1217 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1218 possible_truths
, info
);
1219 remap_hint_predicate_after_duplication (&info
->array_index
,
1220 possible_truths
, info
);
1222 /* If inliner or someone after inliner will ever start producing
1223 non-trivial clones, we will get trouble with lack of information
1224 about updating self sizes, because size vectors already contains
1225 sizes of the calees. */
1226 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1230 info
->entry
= vec_safe_copy (info
->entry
);
1231 if (info
->loop_iterations
)
1233 predicate p
= *info
->loop_iterations
;
1234 info
->loop_iterations
= NULL
;
1235 set_hint_predicate (&info
->loop_iterations
, p
);
1237 if (info
->loop_stride
)
1239 predicate p
= *info
->loop_stride
;
1240 info
->loop_stride
= NULL
;
1241 set_hint_predicate (&info
->loop_stride
, p
);
1243 if (info
->array_index
)
1245 predicate p
= *info
->array_index
;
1246 info
->array_index
= NULL
;
1247 set_hint_predicate (&info
->array_index
, p
);
1250 inline_update_overall_summary (dst
);
1254 /* Hook that is called by cgraph.c when a node is duplicated. */
1257 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1258 struct cgraph_edge
*dst
,
1259 ATTRIBUTE_UNUSED
void *data
)
1261 struct inline_edge_summary
*info
;
1262 struct inline_edge_summary
*srcinfo
;
1263 inline_summary_alloc ();
1264 info
= inline_edge_summary (dst
);
1265 srcinfo
= inline_edge_summary (src
);
1266 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1267 info
->predicate
= NULL
;
1268 edge_set_predicate (dst
, srcinfo
->predicate
);
1269 info
->param
= srcinfo
->param
.copy ();
1273 /* Keep edge cache consistent across edge removal. */
1276 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1277 void *data ATTRIBUTE_UNUSED
)
1279 if (edge_growth_cache
.exists ())
1280 reset_edge_growth_cache (edge
);
1281 reset_inline_edge_summary (edge
);
1285 /* Initialize growth caches. */
1288 initialize_growth_caches (void)
1290 if (cgraph_edge_max_uid
)
1291 edge_growth_cache
.safe_grow_cleared (cgraph_edge_max_uid
);
1293 node_growth_cache
.safe_grow_cleared (cgraph_max_uid
);
1297 /* Free growth caches. */
1300 free_growth_caches (void)
1302 edge_growth_cache
.release ();
1303 node_growth_cache
.release ();
1307 /* Dump edge summaries associated to NODE and recursively to all clones.
1308 Indent by INDENT. */
1311 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1312 struct inline_summary
*info
)
1314 struct cgraph_edge
*edge
;
1315 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1317 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1318 struct cgraph_node
*callee
=
1319 cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1323 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1324 " time: %2i callee size:%2i stack:%2i",
1325 indent
, "", callee
->name (), callee
->order
,
1326 !edge
->inline_failed
1327 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1328 indent
, "", es
->loop_depth
, edge
->frequency
,
1329 es
->call_stmt_size
, es
->call_stmt_time
,
1330 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1331 (int) inline_summary (callee
)->estimated_stack_size
);
1335 fprintf (f
, " predicate: ");
1336 dump_predicate (f
, info
->conds
, es
->predicate
);
1340 if (es
->param
.exists ())
1341 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1343 int prob
= es
->param
[i
].change_prob
;
1346 fprintf (f
, "%*s op%i is compile time invariant\n",
1348 else if (prob
!= REG_BR_PROB_BASE
)
1349 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1350 prob
* 100.0 / REG_BR_PROB_BASE
);
1352 if (!edge
->inline_failed
)
1354 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1355 " callee size %i\n",
1357 (int) inline_summary (callee
)->stack_frame_offset
,
1358 (int) inline_summary (callee
)->estimated_self_stack_size
,
1359 (int) inline_summary (callee
)->estimated_stack_size
);
1360 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1363 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1365 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1366 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1370 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1373 fprintf (f
, "predicate: ");
1374 dump_predicate (f
, info
->conds
, es
->predicate
);
1383 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1385 if (node
->definition
)
1387 struct inline_summary
*s
= inline_summary (node
);
1390 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1392 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1393 fprintf (f
, " always_inline");
1395 fprintf (f
, " inlinable");
1396 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1397 fprintf (f
, " global time: %i\n", s
->time
);
1398 fprintf (f
, " self size: %i\n", s
->self_size
);
1399 fprintf (f
, " global size: %i\n", s
->size
);
1400 fprintf (f
, " self stack: %i\n",
1401 (int) s
->estimated_self_stack_size
);
1402 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1404 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1406 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1407 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1409 fprintf (f
, " size:%f, time:%f, predicate:",
1410 (double) e
->size
/ INLINE_SIZE_SCALE
,
1411 (double) e
->time
/ INLINE_TIME_SCALE
);
1412 dump_predicate (f
, s
->conds
, &e
->predicate
);
1414 if (s
->loop_iterations
)
1416 fprintf (f
, " loop iterations:");
1417 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1421 fprintf (f
, " loop stride:");
1422 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1426 fprintf (f
, " array index:");
1427 dump_predicate (f
, s
->conds
, s
->array_index
);
1429 fprintf (f
, " calls:\n");
1430 dump_inline_edge_summary (f
, 4, node
, s
);
1436 debug_inline_summary (struct cgraph_node
*node
)
1438 dump_inline_summary (stderr
, node
);
1442 dump_inline_summaries (FILE *f
)
1444 struct cgraph_node
*node
;
1446 FOR_EACH_DEFINED_FUNCTION (node
)
1447 if (!node
->global
.inlined_to
)
1448 dump_inline_summary (f
, node
);
1451 /* Give initial reasons why inlining would fail on EDGE. This gets either
1452 nullified or usually overwritten by more precise reasons later. */
1455 initialize_inline_failed (struct cgraph_edge
*e
)
1457 struct cgraph_node
*callee
= e
->callee
;
1459 if (e
->indirect_unknown_callee
)
1460 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1461 else if (!callee
->definition
)
1462 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1463 else if (callee
->local
.redefined_extern_inline
)
1464 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1465 else if (e
->call_stmt_cannot_inline_p
)
1466 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1467 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1468 /* We can't inline if the function is spawing a function. */
1469 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1471 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1474 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1475 boolean variable pointed to by DATA. */
1478 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1481 bool *b
= (bool *) data
;
1486 /* If OP refers to value of function parameter, return the corresponding
1490 unmodified_parm_1 (gimple stmt
, tree op
)
1492 /* SSA_NAME referring to parm default def? */
1493 if (TREE_CODE (op
) == SSA_NAME
1494 && SSA_NAME_IS_DEFAULT_DEF (op
)
1495 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1496 return SSA_NAME_VAR (op
);
1497 /* Non-SSA parm reference? */
1498 if (TREE_CODE (op
) == PARM_DECL
)
1500 bool modified
= false;
1503 ao_ref_init (&refd
, op
);
1504 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1512 /* If OP refers to value of function parameter, return the corresponding
1513 parameter. Also traverse chains of SSA register assignments. */
1516 unmodified_parm (gimple stmt
, tree op
)
1518 tree res
= unmodified_parm_1 (stmt
, op
);
1522 if (TREE_CODE (op
) == SSA_NAME
1523 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1524 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1525 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1526 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1530 /* If OP refers to a value of a function parameter or value loaded from an
1531 aggregate passed to a parameter (either by value or reference), return TRUE
1532 and store the number of the parameter to *INDEX_P and information whether
1533 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1534 the function parameters, STMT is the statement in which OP is used or
1538 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1539 gimple stmt
, tree op
, int *index_p
,
1540 struct agg_position_info
*aggpos
)
1542 tree res
= unmodified_parm_1 (stmt
, op
);
1544 gcc_checking_assert (aggpos
);
1547 *index_p
= ipa_get_param_decl_index (info
, res
);
1550 aggpos
->agg_contents
= false;
1551 aggpos
->by_ref
= false;
1555 if (TREE_CODE (op
) == SSA_NAME
)
1557 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1558 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1560 stmt
= SSA_NAME_DEF_STMT (op
);
1561 op
= gimple_assign_rhs1 (stmt
);
1562 if (!REFERENCE_CLASS_P (op
))
1563 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1567 aggpos
->agg_contents
= true;
1568 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1572 /* See if statement might disappear after inlining.
1573 0 - means not eliminated
1574 1 - half of statements goes away
1575 2 - for sure it is eliminated.
1576 We are not terribly sophisticated, basically looking for simple abstraction
1577 penalty wrappers. */
1580 eliminated_by_inlining_prob (gimple stmt
)
1582 enum gimple_code code
= gimple_code (stmt
);
1583 enum tree_code rhs_code
;
1593 if (gimple_num_ops (stmt
) != 2)
1596 rhs_code
= gimple_assign_rhs_code (stmt
);
1598 /* Casts of parameters, loads from parameters passed by reference
1599 and stores to return value or parameters are often free after
1600 inlining dua to SRA and further combining.
1601 Assume that half of statements goes away. */
1602 if (rhs_code
== CONVERT_EXPR
1603 || rhs_code
== NOP_EXPR
1604 || rhs_code
== VIEW_CONVERT_EXPR
1605 || rhs_code
== ADDR_EXPR
1606 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1608 tree rhs
= gimple_assign_rhs1 (stmt
);
1609 tree lhs
= gimple_assign_lhs (stmt
);
1610 tree inner_rhs
= get_base_address (rhs
);
1611 tree inner_lhs
= get_base_address (lhs
);
1612 bool rhs_free
= false;
1613 bool lhs_free
= false;
1620 /* Reads of parameter are expected to be free. */
1621 if (unmodified_parm (stmt
, inner_rhs
))
1623 /* Match expressions of form &this->field. Those will most likely
1624 combine with something upstream after inlining. */
1625 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1627 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1628 if (TREE_CODE (op
) == PARM_DECL
)
1630 else if (TREE_CODE (op
) == MEM_REF
1631 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1635 /* When parameter is not SSA register because its address is taken
1636 and it is just copied into one, the statement will be completely
1637 free after inlining (we will copy propagate backward). */
1638 if (rhs_free
&& is_gimple_reg (lhs
))
1641 /* Reads of parameters passed by reference
1642 expected to be free (i.e. optimized out after inlining). */
1643 if (TREE_CODE (inner_rhs
) == MEM_REF
1644 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1647 /* Copying parameter passed by reference into gimple register is
1648 probably also going to copy propagate, but we can't be quite
1650 if (rhs_free
&& is_gimple_reg (lhs
))
1653 /* Writes to parameters, parameters passed by value and return value
1654 (either dirrectly or passed via invisible reference) are free.
1656 TODO: We ought to handle testcase like
1657 struct a {int a,b;};
1659 retrurnsturct (void)
1665 This translate into:
1680 For that we either need to copy ipa-split logic detecting writes
1682 if (TREE_CODE (inner_lhs
) == PARM_DECL
1683 || TREE_CODE (inner_lhs
) == RESULT_DECL
1684 || (TREE_CODE (inner_lhs
) == MEM_REF
1685 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1686 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1687 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1688 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1690 0))) == RESULT_DECL
))))
1693 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1695 if (lhs_free
&& rhs_free
)
1705 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1706 predicates to the CFG edges. */
1709 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1710 struct inline_summary
*summary
,
1716 struct agg_position_info aggpos
;
1717 enum tree_code code
, inverted_code
;
1723 last
= last_stmt (bb
);
1724 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1726 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1728 op
= gimple_cond_lhs (last
);
1729 /* TODO: handle conditionals like
1732 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1734 code
= gimple_cond_code (last
);
1736 = invert_tree_comparison (code
,
1737 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1739 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1741 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1742 ? code
: inverted_code
);
1743 /* invert_tree_comparison will return ERROR_MARK on FP
1744 comparsions that are not EQ/NE instead of returning proper
1745 unordered one. Be sure it is not confused with NON_CONSTANT. */
1746 if (this_code
!= ERROR_MARK
)
1748 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1749 e
->flags
& EDGE_TRUE_VALUE
1750 ? code
: inverted_code
,
1751 gimple_cond_rhs (last
));
1752 e
->aux
= pool_alloc (edge_predicate_pool
);
1753 *(struct predicate
*) e
->aux
= p
;
1758 if (TREE_CODE (op
) != SSA_NAME
)
1761 if (builtin_constant_p (op))
1765 Here we can predicate nonconstant_code. We can't
1766 really handle constant_code since we have no predicate
1767 for this and also the constant code is not known to be
1768 optimized away when inliner doen't see operand is constant.
1769 Other optimizers might think otherwise. */
1770 if (gimple_cond_code (last
) != NE_EXPR
1771 || !integer_zerop (gimple_cond_rhs (last
)))
1773 set_stmt
= SSA_NAME_DEF_STMT (op
);
1774 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1775 || gimple_call_num_args (set_stmt
) != 1)
1777 op2
= gimple_call_arg (set_stmt
, 0);
1778 if (!unmodified_parm_or_parm_agg_item
1779 (info
, set_stmt
, op2
, &index
, &aggpos
))
1781 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1783 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1784 IS_NOT_CONSTANT
, NULL_TREE
);
1785 e
->aux
= pool_alloc (edge_predicate_pool
);
1786 *(struct predicate
*) e
->aux
= p
;
1791 /* If BB ends by a switch we can turn into predicates, attach corresponding
1792 predicates to the CFG edges. */
1795 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1796 struct inline_summary
*summary
,
1802 struct agg_position_info aggpos
;
1808 last
= last_stmt (bb
);
1809 if (!last
|| gimple_code (last
) != GIMPLE_SWITCH
)
1811 op
= gimple_switch_index (last
);
1812 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1815 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1817 e
->aux
= pool_alloc (edge_predicate_pool
);
1818 *(struct predicate
*) e
->aux
= false_predicate ();
1820 n
= gimple_switch_num_labels (last
);
1821 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1823 tree cl
= gimple_switch_label (last
, case_idx
);
1827 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1828 min
= CASE_LOW (cl
);
1829 max
= CASE_HIGH (cl
);
1831 /* For default we might want to construct predicate that none
1832 of cases is met, but it is bit hard to do not having negations
1833 of conditionals handy. */
1835 p
= true_predicate ();
1837 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1840 struct predicate p1
, p2
;
1841 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1842 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1843 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1845 *(struct predicate
*) e
->aux
1846 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1851 /* For each BB in NODE attach to its AUX pointer predicate under
1852 which it is executable. */
1855 compute_bb_predicates (struct cgraph_node
*node
,
1856 struct ipa_node_params
*parms_info
,
1857 struct inline_summary
*summary
)
1859 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1863 FOR_EACH_BB_FN (bb
, my_function
)
1865 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1866 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1869 /* Entry block is always executable. */
1870 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1871 = pool_alloc (edge_predicate_pool
);
1872 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1873 = true_predicate ();
1875 /* A simple dataflow propagation of predicates forward in the CFG.
1876 TODO: work in reverse postorder. */
1880 FOR_EACH_BB_FN (bb
, my_function
)
1882 struct predicate p
= false_predicate ();
1885 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1889 struct predicate this_bb_predicate
1890 = *(struct predicate
*) e
->src
->aux
;
1893 = and_predicates (summary
->conds
, &this_bb_predicate
,
1894 (struct predicate
*) e
->aux
);
1895 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1896 if (true_predicate_p (&p
))
1900 if (false_predicate_p (&p
))
1901 gcc_assert (!bb
->aux
);
1907 bb
->aux
= pool_alloc (edge_predicate_pool
);
1908 *((struct predicate
*) bb
->aux
) = p
;
1910 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1912 /* This OR operation is needed to ensure monotonous data flow
1913 in the case we hit the limit on number of clauses and the
1914 and/or operations above give approximate answers. */
1915 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1916 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1919 *((struct predicate
*) bb
->aux
) = p
;
1928 /* We keep info about constantness of SSA names. */
1930 typedef struct predicate predicate_t
;
1931 /* Return predicate specifying when the STMT might have result that is not
1932 a compile time constant. */
1934 static struct predicate
1935 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1936 struct inline_summary
*summary
,
1938 vec
<predicate_t
> nonconstant_names
)
1943 while (UNARY_CLASS_P (expr
))
1944 expr
= TREE_OPERAND (expr
, 0);
1946 parm
= unmodified_parm (NULL
, expr
);
1947 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1948 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1949 if (is_gimple_min_invariant (expr
))
1950 return false_predicate ();
1951 if (TREE_CODE (expr
) == SSA_NAME
)
1952 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1953 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1955 struct predicate p1
= will_be_nonconstant_expr_predicate
1956 (info
, summary
, TREE_OPERAND (expr
, 0),
1958 struct predicate p2
;
1959 if (true_predicate_p (&p1
))
1961 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1962 TREE_OPERAND (expr
, 1),
1964 return or_predicates (summary
->conds
, &p1
, &p2
);
1966 else if (TREE_CODE (expr
) == COND_EXPR
)
1968 struct predicate p1
= will_be_nonconstant_expr_predicate
1969 (info
, summary
, TREE_OPERAND (expr
, 0),
1971 struct predicate p2
;
1972 if (true_predicate_p (&p1
))
1974 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1975 TREE_OPERAND (expr
, 1),
1977 if (true_predicate_p (&p2
))
1979 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
1980 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1981 TREE_OPERAND (expr
, 2),
1983 return or_predicates (summary
->conds
, &p1
, &p2
);
1990 return false_predicate ();
1994 /* Return predicate specifying when the STMT might have result that is not
1995 a compile time constant. */
1997 static struct predicate
1998 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
1999 struct inline_summary
*summary
,
2001 vec
<predicate_t
> nonconstant_names
)
2003 struct predicate p
= true_predicate ();
2006 struct predicate op_non_const
;
2009 struct agg_position_info aggpos
;
2011 /* What statments might be optimized away
2012 when their arguments are constant
2013 TODO: also trivial builtins.
2014 builtin_constant_p is already handled later. */
2015 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2016 && gimple_code (stmt
) != GIMPLE_COND
2017 && gimple_code (stmt
) != GIMPLE_SWITCH
)
2020 /* Stores will stay anyway. */
2021 if (gimple_store_p (stmt
))
2024 is_load
= gimple_assign_load_p (stmt
);
2026 /* Loads can be optimized when the value is known. */
2030 gcc_assert (gimple_assign_single_p (stmt
));
2031 op
= gimple_assign_rhs1 (stmt
);
2032 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2039 /* See if we understand all operands before we start
2040 adding conditionals. */
2041 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2043 tree parm
= unmodified_parm (stmt
, use
);
2044 /* For arguments we can build a condition. */
2045 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2047 if (TREE_CODE (use
) != SSA_NAME
)
2049 /* If we know when operand is constant,
2050 we still can say something useful. */
2051 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2058 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2060 op_non_const
= false_predicate ();
2061 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2063 tree parm
= unmodified_parm (stmt
, use
);
2066 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2068 if (index
!= base_index
)
2069 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2074 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2075 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2077 if (gimple_code (stmt
) == GIMPLE_ASSIGN
2078 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
2079 nonconstant_names
[SSA_NAME_VERSION (gimple_assign_lhs (stmt
))]
2081 return op_non_const
;
2084 struct record_modified_bb_info
2090 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2091 set except for info->stmt. */
2094 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2096 struct record_modified_bb_info
*info
=
2097 (struct record_modified_bb_info
*) data
;
2098 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2100 bitmap_set_bit (info
->bb_set
,
2101 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2102 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2103 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2107 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2108 will change since last invocation of STMT.
2110 Value 0 is reserved for compile time invariants.
2111 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2112 ought to be REG_BR_PROB_BASE / estimated_iters. */
2115 param_change_prob (gimple stmt
, int i
)
2117 tree op
= gimple_call_arg (stmt
, i
);
2118 basic_block bb
= gimple_bb (stmt
);
2121 /* Global invariants neve change. */
2122 if (is_gimple_min_invariant (op
))
2124 /* We would have to do non-trivial analysis to really work out what
2125 is the probability of value to change (i.e. when init statement
2126 is in a sibling loop of the call).
2128 We do an conservative estimate: when call is executed N times more often
2129 than the statement defining value, we take the frequency 1/N. */
2130 if (TREE_CODE (op
) == SSA_NAME
)
2135 return REG_BR_PROB_BASE
;
2137 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2138 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2140 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2144 if (init_freq
< bb
->frequency
)
2145 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2147 return REG_BR_PROB_BASE
;
2150 base
= get_base_address (op
);
2155 struct record_modified_bb_info info
;
2158 tree init
= ctor_for_folding (base
);
2160 if (init
!= error_mark_node
)
2163 return REG_BR_PROB_BASE
;
2164 ao_ref_init (&refd
, op
);
2166 info
.bb_set
= BITMAP_ALLOC (NULL
);
2167 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2169 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2171 BITMAP_FREE (info
.bb_set
);
2172 return REG_BR_PROB_BASE
;
2175 /* Assume that every memory is initialized at entry.
2176 TODO: Can we easilly determine if value is always defined
2177 and thus we may skip entry block? */
2178 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2179 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2183 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2184 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2186 BITMAP_FREE (info
.bb_set
);
2187 if (max
< bb
->frequency
)
2188 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2190 return REG_BR_PROB_BASE
;
2192 return REG_BR_PROB_BASE
;
2195 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2196 sub-graph and if the predicate the condition depends on is known. If so,
2197 return true and store the pointer the predicate in *P. */
2200 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2201 struct inline_summary
*summary
, basic_block bb
,
2202 struct predicate
*p
,
2203 vec
<predicate_t
> nonconstant_names
)
2207 basic_block first_bb
= NULL
;
2210 if (single_pred_p (bb
))
2212 *p
= false_predicate ();
2216 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2218 if (single_succ_p (e
->src
))
2220 if (!single_pred_p (e
->src
))
2223 first_bb
= single_pred (e
->src
);
2224 else if (single_pred (e
->src
) != first_bb
)
2231 else if (e
->src
!= first_bb
)
2239 stmt
= last_stmt (first_bb
);
2241 || gimple_code (stmt
) != GIMPLE_COND
2242 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2245 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2246 gimple_cond_lhs (stmt
),
2248 if (true_predicate_p (p
))
2254 /* Given a PHI statement in a function described by inline properties SUMMARY
2255 and *P being the predicate describing whether the selected PHI argument is
2256 known, store a predicate for the result of the PHI statement into
2257 NONCONSTANT_NAMES, if possible. */
2260 predicate_for_phi_result (struct inline_summary
*summary
, gimple phi
,
2261 struct predicate
*p
,
2262 vec
<predicate_t
> nonconstant_names
)
2266 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2268 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2269 if (!is_gimple_min_invariant (arg
))
2271 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2272 *p
= or_predicates (summary
->conds
, p
,
2273 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2274 if (true_predicate_p (p
))
2279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2281 fprintf (dump_file
, "\t\tphi predicate: ");
2282 dump_predicate (dump_file
, summary
->conds
, p
);
2284 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2287 /* Return predicate specifying when array index in access OP becomes non-constant. */
2289 static struct predicate
2290 array_index_predicate (struct inline_summary
*info
,
2291 vec
< predicate_t
> nonconstant_names
, tree op
)
2293 struct predicate p
= false_predicate ();
2294 while (handled_component_p (op
))
2296 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2298 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2299 p
= or_predicates (info
->conds
, &p
,
2300 &nonconstant_names
[SSA_NAME_VERSION
2301 (TREE_OPERAND (op
, 1))]);
2303 op
= TREE_OPERAND (op
, 0);
2308 /* For a typical usage of __builtin_expect (a<b, 1), we
2309 may introduce an extra relation stmt:
2310 With the builtin, we have
2313 t3 = __builtin_expect (t2, 1);
2316 Without the builtin, we have
2319 This affects the size/time estimation and may have
2320 an impact on the earlier inlining.
2321 Here find this pattern and fix it up later. */
2324 find_foldable_builtin_expect (basic_block bb
)
2326 gimple_stmt_iterator bsi
;
2328 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2330 gimple stmt
= gsi_stmt (bsi
);
2331 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2332 || (is_gimple_call (stmt
)
2333 && gimple_call_internal_p (stmt
)
2334 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2336 tree var
= gimple_call_lhs (stmt
);
2337 tree arg
= gimple_call_arg (stmt
, 0);
2338 use_operand_p use_p
;
2345 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2347 while (TREE_CODE (arg
) == SSA_NAME
)
2349 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2350 if (!is_gimple_assign (stmt_tmp
))
2352 switch (gimple_assign_rhs_code (stmt_tmp
))
2371 arg
= gimple_assign_rhs1 (stmt_tmp
);
2374 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2375 && gimple_code (use_stmt
) == GIMPLE_COND
)
2382 /* Return true when the basic blocks contains only clobbers followed by RESX.
2383 Such BBs are kept around to make removal of dead stores possible with
2384 presence of EH and will be optimized out by optimize_clobbers later in the
2387 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2388 that can be clobber only, too.. When it is false, the RESX is not necessary
2389 on the end of basic block. */
2392 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2394 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2400 if (gsi_end_p (gsi
))
2402 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2406 else if (!single_succ_p (bb
))
2409 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2411 gimple stmt
= gsi_stmt (gsi
);
2412 if (is_gimple_debug (stmt
))
2414 if (gimple_clobber_p (stmt
))
2416 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2421 /* See if all predecestors are either throws or clobber only BBs. */
2422 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2423 if (!(e
->flags
& EDGE_EH
)
2424 && !clobber_only_eh_bb_p (e
->src
, false))
2430 /* Compute function body size parameters for NODE.
2431 When EARLY is true, we compute only simple summaries without
2432 non-trivial predicates to drive the early inliner. */
2435 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2438 /* Estimate static overhead for function prologue/epilogue and alignment. */
2440 /* Benefits are scaled by probability of elimination that is in range
2443 gimple_stmt_iterator bsi
;
2444 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2446 struct inline_summary
*info
= inline_summary (node
);
2447 struct predicate bb_predicate
;
2448 struct ipa_node_params
*parms_info
= NULL
;
2449 vec
<predicate_t
> nonconstant_names
= vNULL
;
2452 predicate array_index
= true_predicate ();
2453 gimple fix_builtin_expect_stmt
;
2458 if (optimize
&& !early
)
2460 calculate_dominance_info (CDI_DOMINATORS
);
2461 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2463 if (ipa_node_params_vector
.exists ())
2465 parms_info
= IPA_NODE_REF (node
);
2466 nonconstant_names
.safe_grow_cleared
2467 (SSANAMES (my_function
)->length ());
2472 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2475 /* When we run into maximal number of entries, we assign everything to the
2476 constant truth case. Be sure to have it in list. */
2477 bb_predicate
= true_predicate ();
2478 account_size_time (info
, 0, 0, &bb_predicate
);
2480 bb_predicate
= not_inlined_predicate ();
2481 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2483 gcc_assert (my_function
&& my_function
->cfg
);
2485 compute_bb_predicates (node
, parms_info
, info
);
2486 gcc_assert (cfun
== my_function
);
2487 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2488 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2489 for (n
= 0; n
< nblocks
; n
++)
2491 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2492 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2493 if (clobber_only_eh_bb_p (bb
))
2495 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2496 fprintf (dump_file
, "\n Ignoring BB %i;"
2497 " it will be optimized away by cleanup_clobbers\n",
2502 /* TODO: Obviously predicates can be propagated down across CFG. */
2506 bb_predicate
= *(struct predicate
*) bb
->aux
;
2508 bb_predicate
= false_predicate ();
2511 bb_predicate
= true_predicate ();
2513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2515 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2516 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2519 if (parms_info
&& nonconstant_names
.exists ())
2521 struct predicate phi_predicate
;
2522 bool first_phi
= true;
2524 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2527 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2534 fprintf (dump_file
, " ");
2535 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2537 predicate_for_phi_result (info
, gsi_stmt (bsi
), &phi_predicate
,
2542 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2544 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2546 gimple stmt
= gsi_stmt (bsi
);
2547 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2548 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2550 struct predicate will_be_nonconstant
;
2552 /* This relation stmt should be folded after we remove
2553 buildin_expect call. Adjust the cost here. */
2554 if (stmt
== fix_builtin_expect_stmt
)
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2562 fprintf (dump_file
, " ");
2563 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2564 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2565 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2569 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2571 struct predicate this_array_index
;
2573 array_index_predicate (info
, nonconstant_names
,
2574 gimple_assign_rhs1 (stmt
));
2575 if (!false_predicate_p (&this_array_index
))
2577 and_predicates (info
->conds
, &array_index
,
2580 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2582 struct predicate this_array_index
;
2584 array_index_predicate (info
, nonconstant_names
,
2585 gimple_get_lhs (stmt
));
2586 if (!false_predicate_p (&this_array_index
))
2588 and_predicates (info
->conds
, &array_index
,
2593 if (is_gimple_call (stmt
)
2594 && !gimple_call_internal_p (stmt
))
2596 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
2597 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2599 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2600 resolved as constant. We however don't want to optimize
2601 out the cgraph edges. */
2602 if (nonconstant_names
.exists ()
2603 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2604 && gimple_call_lhs (stmt
)
2605 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2607 struct predicate false_p
= false_predicate ();
2608 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2611 if (ipa_node_params_vector
.exists ())
2613 int count
= gimple_call_num_args (stmt
);
2617 es
->param
.safe_grow_cleared (count
);
2618 for (i
= 0; i
< count
; i
++)
2620 int prob
= param_change_prob (stmt
, i
);
2621 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2622 es
->param
[i
].change_prob
= prob
;
2626 es
->call_stmt_size
= this_size
;
2627 es
->call_stmt_time
= this_time
;
2628 es
->loop_depth
= bb_loop_depth (bb
);
2629 edge_set_predicate (edge
, &bb_predicate
);
2632 /* TODO: When conditional jump or swithc is known to be constant, but
2633 we did not translate it into the predicates, we really can account
2634 just maximum of the possible paths. */
2637 = will_be_nonconstant_predicate (parms_info
, info
,
2638 stmt
, nonconstant_names
);
2639 if (this_time
|| this_size
)
2645 prob
= eliminated_by_inlining_prob (stmt
);
2646 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2648 "\t\t50%% will be eliminated by inlining\n");
2649 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2653 p
= and_predicates (info
->conds
, &bb_predicate
,
2654 &will_be_nonconstant
);
2656 p
= true_predicate ();
2658 if (!false_predicate_p (&p
))
2662 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2663 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2666 /* We account everything but the calls. Calls have their own
2667 size/time info attached to cgraph edges. This is necessary
2668 in order to make the cost disappear after inlining. */
2669 if (!is_gimple_call (stmt
))
2673 struct predicate ip
= not_inlined_predicate ();
2674 ip
= and_predicates (info
->conds
, &ip
, &p
);
2675 account_size_time (info
, this_size
* prob
,
2676 this_time
* prob
, &ip
);
2679 account_size_time (info
, this_size
* (2 - prob
),
2680 this_time
* (2 - prob
), &p
);
2683 gcc_assert (time
>= 0);
2684 gcc_assert (size
>= 0);
2688 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2689 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2690 if (time
> MAX_TIME
)
2694 if (!early
&& nonconstant_names
.exists ())
2697 predicate loop_iterations
= true_predicate ();
2698 predicate loop_stride
= true_predicate ();
2700 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2701 flow_loops_dump (dump_file
, NULL
, 0);
2703 FOR_EACH_LOOP (loop
, 0)
2708 struct tree_niter_desc niter_desc
;
2709 basic_block
*body
= get_loop_body (loop
);
2710 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2712 exits
= get_loop_exit_edges (loop
);
2713 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2714 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2715 && !is_gimple_min_invariant (niter_desc
.niter
))
2717 predicate will_be_nonconstant
2718 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2721 if (!true_predicate_p (&will_be_nonconstant
))
2722 will_be_nonconstant
= and_predicates (info
->conds
,
2724 &will_be_nonconstant
);
2725 if (!true_predicate_p (&will_be_nonconstant
)
2726 && !false_predicate_p (&will_be_nonconstant
))
2727 /* This is slightly inprecise. We may want to represent each
2728 loop with independent predicate. */
2730 and_predicates (info
->conds
, &loop_iterations
,
2731 &will_be_nonconstant
);
2735 for (i
= 0; i
< loop
->num_nodes
; i
++)
2737 gimple_stmt_iterator gsi
;
2738 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2739 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2742 gimple stmt
= gsi_stmt (gsi
);
2747 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2749 predicate will_be_nonconstant
;
2752 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2753 || is_gimple_min_invariant (iv
.step
))
2756 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2759 if (!true_predicate_p (&will_be_nonconstant
))
2761 = and_predicates (info
->conds
,
2763 &will_be_nonconstant
);
2764 if (!true_predicate_p (&will_be_nonconstant
)
2765 && !false_predicate_p (&will_be_nonconstant
))
2766 /* This is slightly inprecise. We may want to represent
2767 each loop with independent predicate. */
2769 and_predicates (info
->conds
, &loop_stride
,
2770 &will_be_nonconstant
);
2776 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2778 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2781 FOR_ALL_BB_FN (bb
, my_function
)
2787 pool_free (edge_predicate_pool
, bb
->aux
);
2789 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2792 pool_free (edge_predicate_pool
, e
->aux
);
2796 inline_summary (node
)->self_time
= time
;
2797 inline_summary (node
)->self_size
= size
;
2798 nonconstant_names
.release ();
2799 if (optimize
&& !early
)
2801 loop_optimizer_finalize ();
2802 free_dominance_info (CDI_DOMINATORS
);
2806 fprintf (dump_file
, "\n");
2807 dump_inline_summary (dump_file
, node
);
2812 /* Compute parameters of functions used by inliner.
2813 EARLY is true when we compute parameters for the early inliner */
2816 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2818 HOST_WIDE_INT self_stack_size
;
2819 struct cgraph_edge
*e
;
2820 struct inline_summary
*info
;
2822 gcc_assert (!node
->global
.inlined_to
);
2824 inline_summary_alloc ();
2826 info
= inline_summary (node
);
2827 reset_inline_summary (node
);
2829 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2830 Once this happen, we will need to more curefully predict call
2832 if (node
->thunk
.thunk_p
)
2834 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2835 struct predicate t
= true_predicate ();
2837 info
->inlinable
= 0;
2838 node
->callees
->call_stmt_cannot_inline_p
= true;
2839 node
->local
.can_change_signature
= false;
2840 es
->call_stmt_time
= 1;
2841 es
->call_stmt_size
= 1;
2842 account_size_time (info
, 0, 0, &t
);
2846 /* Even is_gimple_min_invariant rely on current_function_decl. */
2847 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2849 /* Estimate the stack size for the function if we're optimizing. */
2850 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2851 info
->estimated_self_stack_size
= self_stack_size
;
2852 info
->estimated_stack_size
= self_stack_size
;
2853 info
->stack_frame_offset
= 0;
2855 /* Can this function be inlined at all? */
2856 if (!optimize
&& !lookup_attribute ("always_inline",
2857 DECL_ATTRIBUTES (node
->decl
)))
2858 info
->inlinable
= false;
2860 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2862 /* Type attributes can use parameter indices to describe them. */
2863 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2864 node
->local
.can_change_signature
= false;
2867 /* Otherwise, inlinable functions always can change signature. */
2868 if (info
->inlinable
)
2869 node
->local
.can_change_signature
= true;
2872 /* Functions calling builtin_apply can not change signature. */
2873 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2875 tree
cdecl = e
->callee
->decl
;
2876 if (DECL_BUILT_IN (cdecl)
2877 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2878 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2879 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2882 node
->local
.can_change_signature
= !e
;
2885 estimate_function_body_sizes (node
, early
);
2887 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2888 if (symtab_comdat_local_p (e
->callee
))
2890 node
->calls_comdat_local
= (e
!= NULL
);
2892 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2893 info
->time
= info
->self_time
;
2894 info
->size
= info
->self_size
;
2895 info
->stack_frame_offset
= 0;
2896 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2897 #ifdef ENABLE_CHECKING
2898 inline_update_overall_summary (node
);
2899 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2906 /* Compute parameters of functions used by inliner using
2907 current_function_decl. */
2910 compute_inline_parameters_for_current (void)
2912 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
2918 const pass_data pass_data_inline_parameters
=
2920 GIMPLE_PASS
, /* type */
2921 "inline_param", /* name */
2922 OPTGROUP_INLINE
, /* optinfo_flags */
2923 false, /* has_gate */
2924 true, /* has_execute */
2925 TV_INLINE_PARAMETERS
, /* tv_id */
2926 0, /* properties_required */
2927 0, /* properties_provided */
2928 0, /* properties_destroyed */
2929 0, /* todo_flags_start */
2930 0, /* todo_flags_finish */
2933 class pass_inline_parameters
: public gimple_opt_pass
2936 pass_inline_parameters (gcc::context
*ctxt
)
2937 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2940 /* opt_pass methods: */
2941 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2942 unsigned int execute () {
2943 return compute_inline_parameters_for_current ();
2946 }; // class pass_inline_parameters
2951 make_pass_inline_parameters (gcc::context
*ctxt
)
2953 return new pass_inline_parameters (ctxt
);
2957 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2961 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2962 int *size
, int *time
,
2963 vec
<tree
> known_vals
,
2964 vec
<tree
> known_binfos
,
2965 vec
<ipa_agg_jump_function_p
> known_aggs
)
2968 struct cgraph_node
*callee
;
2969 struct inline_summary
*isummary
;
2971 if (!known_vals
.exists () && !known_binfos
.exists ())
2973 if (!flag_indirect_inlining
)
2976 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_binfos
,
2981 /* Account for difference in cost between indirect and direct calls. */
2982 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
2983 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
2984 gcc_checking_assert (*time
>= 0);
2985 gcc_checking_assert (*size
>= 0);
2987 callee
= cgraph_get_node (target
);
2988 if (!callee
|| !callee
->definition
)
2990 isummary
= inline_summary (callee
);
2991 return isummary
->inlinable
;
2994 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2997 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
,
2999 vec
<tree
> known_vals
,
3000 vec
<tree
> known_binfos
,
3001 vec
<ipa_agg_jump_function_p
> known_aggs
,
3002 inline_hints
*hints
)
3004 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3005 int call_size
= es
->call_stmt_size
;
3006 int call_time
= es
->call_stmt_time
;
3008 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3009 known_vals
, known_binfos
, known_aggs
)
3010 && hints
&& cgraph_maybe_hot_edge_p (e
))
3011 *hints
|= INLINE_HINT_indirect_call
;
3012 *size
+= call_size
* INLINE_SIZE_SCALE
;
3013 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3014 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3015 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3016 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3021 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
3022 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
3026 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
,
3027 inline_hints
*hints
,
3028 clause_t possible_truths
,
3029 vec
<tree
> known_vals
,
3030 vec
<tree
> known_binfos
,
3031 vec
<ipa_agg_jump_function_p
> known_aggs
)
3033 struct cgraph_edge
*e
;
3034 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3036 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3038 || evaluate_predicate (es
->predicate
, possible_truths
))
3040 if (e
->inline_failed
)
3042 /* Predicates of calls shall not use NOT_CHANGED codes,
3043 sowe do not need to compute probabilities. */
3044 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
,
3045 known_vals
, known_binfos
,
3049 estimate_calls_size_and_time (e
->callee
, size
, time
, hints
,
3051 known_vals
, known_binfos
,
3055 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3057 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3059 || evaluate_predicate (es
->predicate
, possible_truths
))
3060 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
,
3061 known_vals
, known_binfos
, known_aggs
,
3067 /* Estimate size and time needed to execute NODE assuming
3068 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
3069 about NODE's arguments. */
3072 estimate_node_size_and_time (struct cgraph_node
*node
,
3073 clause_t possible_truths
,
3074 vec
<tree
> known_vals
,
3075 vec
<tree
> known_binfos
,
3076 vec
<ipa_agg_jump_function_p
> known_aggs
,
3077 int *ret_size
, int *ret_time
,
3078 inline_hints
*ret_hints
,
3079 vec
<inline_param_summary
>
3080 inline_param_summary
)
3082 struct inline_summary
*info
= inline_summary (node
);
3086 inline_hints hints
= 0;
3089 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3092 fprintf (dump_file
, " Estimating body: %s/%i\n"
3093 " Known to be false: ", node
->name (),
3096 for (i
= predicate_not_inlined_condition
;
3097 i
< (predicate_first_dynamic_condition
3098 + (int) vec_safe_length (info
->conds
)); i
++)
3099 if (!(possible_truths
& (1 << i
)))
3102 fprintf (dump_file
, ", ");
3104 dump_condition (dump_file
, info
->conds
, i
);
3108 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3109 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3112 gcc_checking_assert (e
->time
>= 0);
3113 gcc_checking_assert (time
>= 0);
3114 if (!inline_param_summary
.exists ())
3118 int prob
= predicate_probability (info
->conds
,
3121 inline_param_summary
);
3122 gcc_checking_assert (prob
>= 0);
3123 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3124 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3126 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3127 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3128 gcc_checking_assert (time
>= 0);
3131 gcc_checking_assert (size
>= 0);
3132 gcc_checking_assert (time
>= 0);
3134 if (info
->loop_iterations
3135 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3136 hints
|= INLINE_HINT_loop_iterations
;
3137 if (info
->loop_stride
3138 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3139 hints
|= INLINE_HINT_loop_stride
;
3140 if (info
->array_index
3141 && !evaluate_predicate (info
->array_index
, possible_truths
))
3142 hints
|= INLINE_HINT_array_index
;
3144 hints
|= INLINE_HINT_in_scc
;
3145 if (DECL_DECLARED_INLINE_P (node
->decl
))
3146 hints
|= INLINE_HINT_declared_inline
;
3148 estimate_calls_size_and_time (node
, &size
, &time
, &hints
, possible_truths
,
3149 known_vals
, known_binfos
, known_aggs
);
3150 gcc_checking_assert (size
>= 0);
3151 gcc_checking_assert (time
>= 0);
3152 time
= RDIV (time
, INLINE_TIME_SCALE
);
3153 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3156 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3167 /* Estimate size and time needed to execute callee of EDGE assuming that
3168 parameters known to be constant at caller of EDGE are propagated.
3169 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
3170 and types for parameters. */
3173 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3174 vec
<tree
> known_vals
,
3175 vec
<tree
> known_binfos
,
3176 vec
<ipa_agg_jump_function_p
> known_aggs
,
3177 int *ret_size
, int *ret_time
,
3178 inline_hints
*hints
)
3182 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3184 estimate_node_size_and_time (node
, clause
, known_vals
, known_binfos
,
3185 known_aggs
, ret_size
, ret_time
, hints
, vNULL
);
3188 /* Translate all conditions from callee representation into caller
3189 representation and symbolically evaluate predicate P into new predicate.
3191 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3192 is summary of function predicate P is from. OPERAND_MAP is array giving
3193 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3194 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3195 predicate under which callee is executed. OFFSET_MAP is an array of of
3196 offsets that need to be added to conditions, negative offset means that
3197 conditions relying on values passed by reference have to be discarded
3198 because they might not be preserved (and should be considered offset zero
3199 for other purposes). */
3201 static struct predicate
3202 remap_predicate (struct inline_summary
*info
,
3203 struct inline_summary
*callee_info
,
3204 struct predicate
*p
,
3205 vec
<int> operand_map
,
3206 vec
<int> offset_map
,
3207 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3210 struct predicate out
= true_predicate ();
3212 /* True predicate is easy. */
3213 if (true_predicate_p (p
))
3214 return *toplev_predicate
;
3215 for (i
= 0; p
->clause
[i
]; i
++)
3217 clause_t clause
= p
->clause
[i
];
3219 struct predicate clause_predicate
= false_predicate ();
3221 gcc_assert (i
< MAX_CLAUSES
);
3223 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3224 /* Do we have condition we can't disprove? */
3225 if (clause
& possible_truths
& (1 << cond
))
3227 struct predicate cond_predicate
;
3228 /* Work out if the condition can translate to predicate in the
3229 inlined function. */
3230 if (cond
>= predicate_first_dynamic_condition
)
3232 struct condition
*c
;
3234 c
= &(*callee_info
->conds
)[cond
3236 predicate_first_dynamic_condition
];
3237 /* See if we can remap condition operand to caller's operand.
3238 Otherwise give up. */
3239 if (!operand_map
.exists ()
3240 || (int) operand_map
.length () <= c
->operand_num
3241 || operand_map
[c
->operand_num
] == -1
3242 /* TODO: For non-aggregate conditions, adding an offset is
3243 basically an arithmetic jump function processing which
3244 we should support in future. */
3245 || ((!c
->agg_contents
|| !c
->by_ref
)
3246 && offset_map
[c
->operand_num
] > 0)
3247 || (c
->agg_contents
&& c
->by_ref
3248 && offset_map
[c
->operand_num
] < 0))
3249 cond_predicate
= true_predicate ();
3252 struct agg_position_info ap
;
3253 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3254 if (offset_delta
< 0)
3256 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3259 gcc_assert (!c
->agg_contents
3260 || c
->by_ref
|| offset_delta
== 0);
3261 ap
.offset
= c
->offset
+ offset_delta
;
3262 ap
.agg_contents
= c
->agg_contents
;
3263 ap
.by_ref
= c
->by_ref
;
3264 cond_predicate
= add_condition (info
,
3265 operand_map
[c
->operand_num
],
3266 &ap
, c
->code
, c
->val
);
3269 /* Fixed conditions remains same, construct single
3270 condition predicate. */
3273 cond_predicate
.clause
[0] = 1 << cond
;
3274 cond_predicate
.clause
[1] = 0;
3276 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3279 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3281 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3285 /* Update summary information of inline clones after inlining.
3286 Compute peak stack usage. */
3289 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3291 struct cgraph_edge
*e
;
3292 struct inline_summary
*callee_info
= inline_summary (node
);
3293 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3296 callee_info
->stack_frame_offset
3297 = caller_info
->stack_frame_offset
3298 + caller_info
->estimated_self_stack_size
;
3299 peak
= callee_info
->stack_frame_offset
3300 + callee_info
->estimated_self_stack_size
;
3301 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3302 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3303 ipa_propagate_frequency (node
);
3304 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3306 if (!e
->inline_failed
)
3307 inline_update_callee_summaries (e
->callee
, depth
);
3308 inline_edge_summary (e
)->loop_depth
+= depth
;
3310 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3311 inline_edge_summary (e
)->loop_depth
+= depth
;
3314 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3315 When functoin A is inlined in B and A calls C with parameter that
3316 changes with probability PROB1 and C is known to be passthroug
3317 of argument if B that change with probability PROB2, the probability
3318 of change is now PROB1*PROB2. */
3321 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3322 struct cgraph_edge
*edge
)
3324 if (ipa_node_params_vector
.exists ())
3327 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3328 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3329 struct inline_edge_summary
*inlined_es
3330 = inline_edge_summary (inlined_edge
);
3332 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3334 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3335 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3336 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3337 < (int) inlined_es
->param
.length ()))
3339 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3340 int prob1
= es
->param
[i
].change_prob
;
3341 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3342 int prob
= combine_probabilities (prob1
, prob2
);
3344 if (prob1
&& prob2
&& !prob
)
3347 es
->param
[i
].change_prob
= prob
;
3353 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3355 Remap predicates of callees of NODE. Rest of arguments match
3358 Also update change probabilities. */
3361 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3362 struct cgraph_node
*node
,
3363 struct inline_summary
*info
,
3364 struct inline_summary
*callee_info
,
3365 vec
<int> operand_map
,
3366 vec
<int> offset_map
,
3367 clause_t possible_truths
,
3368 struct predicate
*toplev_predicate
)
3370 struct cgraph_edge
*e
;
3371 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3373 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3376 if (e
->inline_failed
)
3378 remap_edge_change_prob (inlined_edge
, e
);
3382 p
= remap_predicate (info
, callee_info
,
3383 es
->predicate
, operand_map
, offset_map
,
3384 possible_truths
, toplev_predicate
);
3385 edge_set_predicate (e
, &p
);
3386 /* TODO: We should remove the edge for code that will be
3387 optimized out, but we need to keep verifiers and tree-inline
3388 happy. Make it cold for now. */
3389 if (false_predicate_p (&p
))
3396 edge_set_predicate (e
, toplev_predicate
);
3399 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3400 operand_map
, offset_map
, possible_truths
,
3403 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3405 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3408 remap_edge_change_prob (inlined_edge
, e
);
3411 p
= remap_predicate (info
, callee_info
,
3412 es
->predicate
, operand_map
, offset_map
,
3413 possible_truths
, toplev_predicate
);
3414 edge_set_predicate (e
, &p
);
3415 /* TODO: We should remove the edge for code that will be optimized
3416 out, but we need to keep verifiers and tree-inline happy.
3417 Make it cold for now. */
3418 if (false_predicate_p (&p
))
3425 edge_set_predicate (e
, toplev_predicate
);
3429 /* Same as remap_predicate, but set result into hint *HINT. */
3432 remap_hint_predicate (struct inline_summary
*info
,
3433 struct inline_summary
*callee_info
,
3434 struct predicate
**hint
,
3435 vec
<int> operand_map
,
3436 vec
<int> offset_map
,
3437 clause_t possible_truths
,
3438 struct predicate
*toplev_predicate
)
3444 p
= remap_predicate (info
, callee_info
,
3446 operand_map
, offset_map
,
3447 possible_truths
, toplev_predicate
);
3448 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3451 set_hint_predicate (hint
, p
);
3453 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3457 /* We inlined EDGE. Update summary of the function we inlined into. */
3460 inline_merge_summary (struct cgraph_edge
*edge
)
3462 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3463 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3464 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3465 struct inline_summary
*info
= inline_summary (to
);
3466 clause_t clause
= 0; /* not_inline is known to be false. */
3468 vec
<int> operand_map
= vNULL
;
3469 vec
<int> offset_map
= vNULL
;
3471 struct predicate toplev_predicate
;
3472 struct predicate true_p
= true_predicate ();
3473 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3476 toplev_predicate
= *es
->predicate
;
3478 toplev_predicate
= true_predicate ();
3480 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3482 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3483 int count
= ipa_get_cs_argument_count (args
);
3486 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3489 operand_map
.safe_grow_cleared (count
);
3490 offset_map
.safe_grow_cleared (count
);
3492 for (i
= 0; i
< count
; i
++)
3494 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3497 /* TODO: handle non-NOPs when merging. */
3498 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3500 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3501 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3502 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3505 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3507 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3508 if (offset
>= 0 && offset
< INT_MAX
)
3510 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3511 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3513 offset_map
[i
] = offset
;
3516 operand_map
[i
] = map
;
3517 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3520 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3522 struct predicate p
= remap_predicate (info
, callee_info
,
3523 &e
->predicate
, operand_map
,
3526 if (!false_predicate_p (&p
))
3528 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3529 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3530 int prob
= predicate_probability (callee_info
->conds
,
3533 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3534 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3535 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3536 if (prob
!= REG_BR_PROB_BASE
3537 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3539 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3540 (double) prob
/ REG_BR_PROB_BASE
);
3542 account_size_time (info
, e
->size
, add_time
, &p
);
3545 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3546 offset_map
, clause
, &toplev_predicate
);
3547 remap_hint_predicate (info
, callee_info
,
3548 &callee_info
->loop_iterations
,
3549 operand_map
, offset_map
, clause
, &toplev_predicate
);
3550 remap_hint_predicate (info
, callee_info
,
3551 &callee_info
->loop_stride
,
3552 operand_map
, offset_map
, clause
, &toplev_predicate
);
3553 remap_hint_predicate (info
, callee_info
,
3554 &callee_info
->array_index
,
3555 operand_map
, offset_map
, clause
, &toplev_predicate
);
3557 inline_update_callee_summaries (edge
->callee
,
3558 inline_edge_summary (edge
)->loop_depth
);
3560 /* We do not maintain predicates of inlined edges, free it. */
3561 edge_set_predicate (edge
, &true_p
);
3562 /* Similarly remove param summaries. */
3563 es
->param
.release ();
3564 operand_map
.release ();
3565 offset_map
.release ();
3568 /* For performance reasons inline_merge_summary is not updating overall size
3569 and time. Recompute it. */
3572 inline_update_overall_summary (struct cgraph_node
*node
)
3574 struct inline_summary
*info
= inline_summary (node
);
3580 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3582 info
->size
+= e
->size
, info
->time
+= e
->time
;
3583 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3584 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3586 estimate_calls_size_and_time (node
, &info
->size
, &info
->time
, NULL
,
3587 ~(clause_t
) (1 << predicate_false_condition
),
3588 vNULL
, vNULL
, vNULL
);
3589 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3590 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3593 /* Return hints derrived from EDGE. */
3595 simple_edge_hints (struct cgraph_edge
*edge
)
3598 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3599 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3600 if (inline_summary (to
)->scc_no
3601 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3602 && !cgraph_edge_recursive_p (edge
))
3603 hints
|= INLINE_HINT_same_scc
;
3605 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3606 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3607 hints
|= INLINE_HINT_cross_module
;
3612 /* Estimate the time cost for the caller when inlining EDGE.
3613 Only to be called via estimate_edge_time, that handles the
3616 When caching, also update the cache entry. Compute both time and
3617 size, since we always need both metrics eventually. */
3620 do_estimate_edge_time (struct cgraph_edge
*edge
)
3625 struct cgraph_node
*callee
;
3627 vec
<tree
> known_vals
;
3628 vec
<tree
> known_binfos
;
3629 vec
<ipa_agg_jump_function_p
> known_aggs
;
3630 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3632 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3634 gcc_checking_assert (edge
->inline_failed
);
3635 evaluate_properties_for_edge (edge
, true,
3636 &clause
, &known_vals
, &known_binfos
,
3638 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3639 known_aggs
, &size
, &time
, &hints
, es
->param
);
3640 known_vals
.release ();
3641 known_binfos
.release ();
3642 known_aggs
.release ();
3643 gcc_checking_assert (size
>= 0);
3644 gcc_checking_assert (time
>= 0);
3646 /* When caching, update the cache entry. */
3647 if (edge_growth_cache
.exists ())
3649 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3650 edge_growth_cache
.safe_grow_cleared (cgraph_edge_max_uid
);
3651 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3653 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3654 hints
|= simple_edge_hints (edge
);
3655 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3661 /* Return estimated callee growth after inlining EDGE.
3662 Only to be called via estimate_edge_size. */
3665 do_estimate_edge_size (struct cgraph_edge
*edge
)
3668 struct cgraph_node
*callee
;
3670 vec
<tree
> known_vals
;
3671 vec
<tree
> known_binfos
;
3672 vec
<ipa_agg_jump_function_p
> known_aggs
;
3674 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3676 if (edge_growth_cache
.exists ())
3678 do_estimate_edge_time (edge
);
3679 size
= edge_growth_cache
[edge
->uid
].size
;
3680 gcc_checking_assert (size
);
3681 return size
- (size
> 0);
3684 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3686 /* Early inliner runs without caching, go ahead and do the dirty work. */
3687 gcc_checking_assert (edge
->inline_failed
);
3688 evaluate_properties_for_edge (edge
, true,
3689 &clause
, &known_vals
, &known_binfos
,
3691 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3692 known_aggs
, &size
, NULL
, NULL
, vNULL
);
3693 known_vals
.release ();
3694 known_binfos
.release ();
3695 known_aggs
.release ();
3700 /* Estimate the growth of the caller when inlining EDGE.
3701 Only to be called via estimate_edge_size. */
3704 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3707 struct cgraph_node
*callee
;
3709 vec
<tree
> known_vals
;
3710 vec
<tree
> known_binfos
;
3711 vec
<ipa_agg_jump_function_p
> known_aggs
;
3713 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3715 if (edge_growth_cache
.exists ())
3717 do_estimate_edge_time (edge
);
3718 hints
= edge_growth_cache
[edge
->uid
].hints
;
3719 gcc_checking_assert (hints
);
3723 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3725 /* Early inliner runs without caching, go ahead and do the dirty work. */
3726 gcc_checking_assert (edge
->inline_failed
);
3727 evaluate_properties_for_edge (edge
, true,
3728 &clause
, &known_vals
, &known_binfos
,
3730 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3731 known_aggs
, NULL
, NULL
, &hints
, vNULL
);
3732 known_vals
.release ();
3733 known_binfos
.release ();
3734 known_aggs
.release ();
3735 hints
|= simple_edge_hints (edge
);
3740 /* Estimate self time of the function NODE after inlining EDGE. */
3743 estimate_time_after_inlining (struct cgraph_node
*node
,
3744 struct cgraph_edge
*edge
)
3746 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3747 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3750 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3753 if (time
> MAX_TIME
)
3757 return inline_summary (node
)->time
;
3761 /* Estimate the size of NODE after inlining EDGE which should be an
3762 edge to either NODE or a call inlined into NODE. */
3765 estimate_size_after_inlining (struct cgraph_node
*node
,
3766 struct cgraph_edge
*edge
)
3768 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3769 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3771 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3772 gcc_assert (size
>= 0);
3775 return inline_summary (node
)->size
;
3781 struct cgraph_node
*node
;
3782 bool self_recursive
;
3787 /* Worker for do_estimate_growth. Collect growth for all callers. */
3790 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3792 struct cgraph_edge
*e
;
3793 struct growth_data
*d
= (struct growth_data
*) data
;
3795 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3797 gcc_checking_assert (e
->inline_failed
);
3799 if (e
->caller
== d
->node
3800 || (e
->caller
->global
.inlined_to
3801 && e
->caller
->global
.inlined_to
== d
->node
))
3802 d
->self_recursive
= true;
3803 d
->growth
+= estimate_edge_growth (e
);
3809 /* Estimate the growth caused by inlining NODE into all callees. */
3812 do_estimate_growth (struct cgraph_node
*node
)
3814 struct growth_data d
= { node
, 0, false };
3815 struct inline_summary
*info
= inline_summary (node
);
3817 cgraph_for_node_and_aliases (node
, do_estimate_growth_1
, &d
, true);
3819 /* For self recursive functions the growth estimation really should be
3820 infinity. We don't want to return very large values because the growth
3821 plays various roles in badness computation fractions. Be sure to not
3822 return zero or negative growths. */
3823 if (d
.self_recursive
)
3824 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3825 else if (DECL_EXTERNAL (node
->decl
))
3829 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
3830 d
.growth
-= info
->size
;
3831 /* COMDAT functions are very often not shared across multiple units
3832 since they come from various template instantiations.
3833 Take this into account. */
3834 else if (DECL_COMDAT (node
->decl
)
3835 && cgraph_can_remove_if_no_direct_calls_p (node
))
3836 d
.growth
-= (info
->size
3837 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3841 if (node_growth_cache
.exists ())
3843 if ((int) node_growth_cache
.length () <= node
->uid
)
3844 node_growth_cache
.safe_grow_cleared (cgraph_max_uid
);
3845 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3851 /* This function performs intraprocedural analysis in NODE that is required to
3852 inline indirect calls. */
3855 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3857 ipa_analyze_node (node
);
3858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3860 ipa_print_node_params (dump_file
, node
);
3861 ipa_print_node_jump_functions (dump_file
, node
);
3866 /* Note function body size. */
3869 inline_analyze_function (struct cgraph_node
*node
)
3871 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3874 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3875 node
->name (), node
->order
);
3876 if (optimize
&& !node
->thunk
.thunk_p
)
3877 inline_indirect_intraprocedural_analysis (node
);
3878 compute_inline_parameters (node
, false);
3881 struct cgraph_edge
*e
;
3882 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3884 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3885 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3886 e
->call_stmt_cannot_inline_p
= true;
3888 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3890 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3891 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3892 e
->call_stmt_cannot_inline_p
= true;
3900 /* Called when new function is inserted to callgraph late. */
3903 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
3905 inline_analyze_function (node
);
3909 /* Note function body size. */
3912 inline_generate_summary (void)
3914 struct cgraph_node
*node
;
3916 /* When not optimizing, do not bother to analyze. Inlining is still done
3917 because edge redirection needs to happen there. */
3918 if (!optimize
&& !flag_lto
&& !flag_wpa
)
3921 function_insertion_hook_holder
=
3922 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
3924 ipa_register_cgraph_hooks ();
3925 inline_free_summary ();
3927 FOR_EACH_DEFINED_FUNCTION (node
)
3929 inline_analyze_function (node
);
3933 /* Read predicate from IB. */
3935 static struct predicate
3936 read_predicate (struct lto_input_block
*ib
)
3938 struct predicate out
;
3944 gcc_assert (k
<= MAX_CLAUSES
);
3945 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
3949 /* Zero-initialize the remaining clauses in OUT. */
3950 while (k
<= MAX_CLAUSES
)
3951 out
.clause
[k
++] = 0;
3957 /* Write inline summary for edge E to OB. */
3960 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
3962 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3966 es
->call_stmt_size
= streamer_read_uhwi (ib
);
3967 es
->call_stmt_time
= streamer_read_uhwi (ib
);
3968 es
->loop_depth
= streamer_read_uhwi (ib
);
3969 p
= read_predicate (ib
);
3970 edge_set_predicate (e
, &p
);
3971 length
= streamer_read_uhwi (ib
);
3974 es
->param
.safe_grow_cleared (length
);
3975 for (i
= 0; i
< length
; i
++)
3976 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
3981 /* Stream in inline summaries from the section. */
3984 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
3987 const struct lto_function_header
*header
=
3988 (const struct lto_function_header
*) data
;
3989 const int cfg_offset
= sizeof (struct lto_function_header
);
3990 const int main_offset
= cfg_offset
+ header
->cfg_size
;
3991 const int string_offset
= main_offset
+ header
->main_size
;
3992 struct data_in
*data_in
;
3993 struct lto_input_block ib
;
3994 unsigned int i
, count2
, j
;
3995 unsigned int f_count
;
3997 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
4001 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4002 header
->string_size
, vNULL
);
4003 f_count
= streamer_read_uhwi (&ib
);
4004 for (i
= 0; i
< f_count
; i
++)
4007 struct cgraph_node
*node
;
4008 struct inline_summary
*info
;
4009 lto_symtab_encoder_t encoder
;
4010 struct bitpack_d bp
;
4011 struct cgraph_edge
*e
;
4014 index
= streamer_read_uhwi (&ib
);
4015 encoder
= file_data
->symtab_node_encoder
;
4016 node
= cgraph (lto_symtab_encoder_deref (encoder
, index
));
4017 info
= inline_summary (node
);
4019 info
->estimated_stack_size
4020 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4021 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4022 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4024 bp
= streamer_read_bitpack (&ib
);
4025 info
->inlinable
= bp_unpack_value (&bp
, 1);
4027 count2
= streamer_read_uhwi (&ib
);
4028 gcc_assert (!info
->conds
);
4029 for (j
= 0; j
< count2
; j
++)
4032 c
.operand_num
= streamer_read_uhwi (&ib
);
4033 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4034 c
.val
= stream_read_tree (&ib
, data_in
);
4035 bp
= streamer_read_bitpack (&ib
);
4036 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4037 c
.by_ref
= bp_unpack_value (&bp
, 1);
4039 c
.offset
= streamer_read_uhwi (&ib
);
4040 vec_safe_push (info
->conds
, c
);
4042 count2
= streamer_read_uhwi (&ib
);
4043 gcc_assert (!info
->entry
);
4044 for (j
= 0; j
< count2
; j
++)
4046 struct size_time_entry e
;
4048 e
.size
= streamer_read_uhwi (&ib
);
4049 e
.time
= streamer_read_uhwi (&ib
);
4050 e
.predicate
= read_predicate (&ib
);
4052 vec_safe_push (info
->entry
, e
);
4055 p
= read_predicate (&ib
);
4056 set_hint_predicate (&info
->loop_iterations
, p
);
4057 p
= read_predicate (&ib
);
4058 set_hint_predicate (&info
->loop_stride
, p
);
4059 p
= read_predicate (&ib
);
4060 set_hint_predicate (&info
->array_index
, p
);
4061 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4062 read_inline_edge_summary (&ib
, e
);
4063 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4064 read_inline_edge_summary (&ib
, e
);
4067 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4069 lto_data_in_delete (data_in
);
4073 /* Read inline summary. Jump functions are shared among ipa-cp
4074 and inliner, so when ipa-cp is active, we don't need to write them
4078 inline_read_summary (void)
4080 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4081 struct lto_file_decl_data
*file_data
;
4084 inline_summary_alloc ();
4086 while ((file_data
= file_data_vec
[j
++]))
4089 const char *data
= lto_get_section_data (file_data
,
4090 LTO_section_inline_summary
,
4093 inline_read_section (file_data
, data
, len
);
4095 /* Fatal error here. We do not want to support compiling ltrans units
4096 with different version of compiler or different flags than the WPA
4097 unit, so this should never happen. */
4098 fatal_error ("ipa inline summary is missing in input file");
4102 ipa_register_cgraph_hooks ();
4104 ipa_prop_read_jump_functions ();
4106 function_insertion_hook_holder
=
4107 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
4111 /* Write predicate P to OB. */
4114 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4118 for (j
= 0; p
->clause
[j
]; j
++)
4120 gcc_assert (j
< MAX_CLAUSES
);
4121 streamer_write_uhwi (ob
, p
->clause
[j
]);
4123 streamer_write_uhwi (ob
, 0);
4127 /* Write inline summary for edge E to OB. */
4130 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4132 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4135 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4136 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4137 streamer_write_uhwi (ob
, es
->loop_depth
);
4138 write_predicate (ob
, es
->predicate
);
4139 streamer_write_uhwi (ob
, es
->param
.length ());
4140 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4141 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4145 /* Write inline summary for node in SET.
4146 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4147 active, we don't need to write them twice. */
4150 inline_write_summary (void)
4152 struct cgraph_node
*node
;
4153 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4154 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4155 unsigned int count
= 0;
4158 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4160 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4161 cgraph_node
*cnode
= dyn_cast
<cgraph_node
> (snode
);
4162 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4165 streamer_write_uhwi (ob
, count
);
4167 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4169 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4170 cgraph_node
*cnode
= dyn_cast
<cgraph_node
> (snode
);
4171 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4173 struct inline_summary
*info
= inline_summary (node
);
4174 struct bitpack_d bp
;
4175 struct cgraph_edge
*edge
;
4178 struct condition
*c
;
4180 streamer_write_uhwi (ob
,
4181 lto_symtab_encoder_encode (encoder
,
4184 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4185 streamer_write_hwi (ob
, info
->self_size
);
4186 streamer_write_hwi (ob
, info
->self_time
);
4187 bp
= bitpack_create (ob
->main_stream
);
4188 bp_pack_value (&bp
, info
->inlinable
, 1);
4189 streamer_write_bitpack (&bp
);
4190 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4191 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4193 streamer_write_uhwi (ob
, c
->operand_num
);
4194 streamer_write_uhwi (ob
, c
->code
);
4195 stream_write_tree (ob
, c
->val
, true);
4196 bp
= bitpack_create (ob
->main_stream
);
4197 bp_pack_value (&bp
, c
->agg_contents
, 1);
4198 bp_pack_value (&bp
, c
->by_ref
, 1);
4199 streamer_write_bitpack (&bp
);
4200 if (c
->agg_contents
)
4201 streamer_write_uhwi (ob
, c
->offset
);
4203 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4204 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4206 streamer_write_uhwi (ob
, e
->size
);
4207 streamer_write_uhwi (ob
, e
->time
);
4208 write_predicate (ob
, &e
->predicate
);
4210 write_predicate (ob
, info
->loop_iterations
);
4211 write_predicate (ob
, info
->loop_stride
);
4212 write_predicate (ob
, info
->array_index
);
4213 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4214 write_inline_edge_summary (ob
, edge
);
4215 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4216 write_inline_edge_summary (ob
, edge
);
4219 streamer_write_char_stream (ob
->main_stream
, 0);
4220 produce_asm (ob
, NULL
);
4221 destroy_output_block (ob
);
4223 if (optimize
&& !flag_ipa_cp
)
4224 ipa_prop_write_jump_functions ();
4228 /* Release inline summary. */
4231 inline_free_summary (void)
4233 struct cgraph_node
*node
;
4234 if (!inline_edge_summary_vec
.exists ())
4236 FOR_EACH_DEFINED_FUNCTION (node
)
4238 reset_inline_summary (node
);
4239 if (function_insertion_hook_holder
)
4240 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
4241 function_insertion_hook_holder
= NULL
;
4242 if (node_removal_hook_holder
)
4243 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
4244 node_removal_hook_holder
= NULL
;
4245 if (edge_removal_hook_holder
)
4246 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
4247 edge_removal_hook_holder
= NULL
;
4248 if (node_duplication_hook_holder
)
4249 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
4250 node_duplication_hook_holder
= NULL
;
4251 if (edge_duplication_hook_holder
)
4252 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
4253 edge_duplication_hook_holder
= NULL
;
4254 vec_free (inline_summary_vec
);
4255 inline_edge_summary_vec
.release ();
4256 if (edge_predicate_pool
)
4257 free_alloc_pool (edge_predicate_pool
);
4258 edge_predicate_pool
= 0;