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 (false). */
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 sily 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
);
749 if (predicate
&& !true_predicate_p (predicate
))
752 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
753 *es
->predicate
= *predicate
;
758 pool_free (edge_predicate_pool
, es
->predicate
);
759 es
->predicate
= NULL
;
763 /* Set predicate for hint *P. */
766 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
768 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
771 pool_free (edge_predicate_pool
, *p
);
777 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
783 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
784 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
785 Return clause of possible truths. When INLINE_P is true, assume that we are
788 ERROR_MARK means compile time invariant. */
791 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
793 vec
<tree
> known_vals
,
794 vec
<ipa_agg_jump_function_p
>
797 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
798 struct inline_summary
*info
= inline_summary (node
);
802 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
807 /* We allow call stmt to have fewer arguments than the callee function
808 (especially for K&R style programs). So bound check here (we assume
809 known_aggs vector, if non-NULL, has the same length as
811 gcc_checking_assert (!known_aggs
.exists ()
812 || (known_vals
.length () == known_aggs
.length ()));
813 if (c
->operand_num
>= (int) known_vals
.length ())
815 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
821 struct ipa_agg_jump_function
*agg
;
823 if (c
->code
== CHANGED
825 && (known_vals
[c
->operand_num
] == error_mark_node
))
828 if (known_aggs
.exists ())
830 agg
= known_aggs
[c
->operand_num
];
831 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
838 val
= known_vals
[c
->operand_num
];
839 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
845 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
848 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
850 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
851 if (res
&& integer_zerop (res
))
853 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
859 /* Work out what conditions might be true at invocation of E. */
862 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
863 clause_t
*clause_ptr
,
864 vec
<tree
> *known_vals_ptr
,
865 vec
<tree
> *known_binfos_ptr
,
866 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
868 struct cgraph_node
*callee
=
869 cgraph_function_or_thunk_node (e
->callee
, NULL
);
870 struct inline_summary
*info
= inline_summary (callee
);
871 vec
<tree
> known_vals
= vNULL
;
872 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
875 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
877 known_vals_ptr
->create (0);
878 if (known_binfos_ptr
)
879 known_binfos_ptr
->create (0);
881 if (ipa_node_params_vector
.exists ()
882 && !e
->call_stmt_cannot_inline_p
883 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_binfos_ptr
))
885 struct ipa_node_params
*parms_info
;
886 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
887 struct inline_edge_summary
*es
= inline_edge_summary (e
);
888 int i
, count
= ipa_get_cs_argument_count (args
);
890 if (e
->caller
->global
.inlined_to
)
891 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
893 parms_info
= IPA_NODE_REF (e
->caller
);
895 if (count
&& (info
->conds
|| known_vals_ptr
))
896 known_vals
.safe_grow_cleared (count
);
897 if (count
&& (info
->conds
|| known_aggs_ptr
))
898 known_aggs
.safe_grow_cleared (count
);
899 if (count
&& known_binfos_ptr
)
900 known_binfos_ptr
->safe_grow_cleared (count
);
902 for (i
= 0; i
< count
; i
++)
904 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
905 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
908 if (known_vals
.exists () && TREE_CODE (cst
) != TREE_BINFO
)
910 else if (known_binfos_ptr
!= NULL
911 && TREE_CODE (cst
) == TREE_BINFO
)
912 (*known_binfos_ptr
)[i
] = cst
;
914 else if (inline_p
&& !es
->param
[i
].change_prob
)
915 known_vals
[i
] = error_mark_node
;
916 /* TODO: When IPA-CP starts propagating and merging aggregate jump
917 functions, use its knowledge of the caller too, just like the
918 scalar case above. */
919 known_aggs
[i
] = &jf
->agg
;
924 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
925 known_vals
, known_aggs
);
928 *known_vals_ptr
= known_vals
;
930 known_vals
.release ();
933 *known_aggs_ptr
= known_aggs
;
935 known_aggs
.release ();
939 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
942 inline_summary_alloc (void)
944 if (!node_removal_hook_holder
)
945 node_removal_hook_holder
=
946 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
947 if (!edge_removal_hook_holder
)
948 edge_removal_hook_holder
=
949 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
950 if (!node_duplication_hook_holder
)
951 node_duplication_hook_holder
=
952 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
953 if (!edge_duplication_hook_holder
)
954 edge_duplication_hook_holder
=
955 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
957 if (vec_safe_length (inline_summary_vec
) <= (unsigned) cgraph_max_uid
)
958 vec_safe_grow_cleared (inline_summary_vec
, cgraph_max_uid
+ 1);
959 if (inline_edge_summary_vec
.length () <= (unsigned) cgraph_edge_max_uid
)
960 inline_edge_summary_vec
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
961 if (!edge_predicate_pool
)
962 edge_predicate_pool
= create_alloc_pool ("edge predicates",
963 sizeof (struct predicate
), 10);
966 /* We are called multiple time for given function; clear
967 data from previous run so they are not cumulated. */
970 reset_inline_edge_summary (struct cgraph_edge
*e
)
972 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
974 struct inline_edge_summary
*es
= inline_edge_summary (e
);
976 es
->call_stmt_size
= es
->call_stmt_time
= 0;
978 pool_free (edge_predicate_pool
, es
->predicate
);
979 es
->predicate
= NULL
;
980 es
->param
.release ();
984 /* We are called multiple time for given function; clear
985 data from previous run so they are not cumulated. */
988 reset_inline_summary (struct cgraph_node
*node
)
990 struct inline_summary
*info
= inline_summary (node
);
991 struct cgraph_edge
*e
;
993 info
->self_size
= info
->self_time
= 0;
994 info
->estimated_stack_size
= 0;
995 info
->estimated_self_stack_size
= 0;
996 info
->stack_frame_offset
= 0;
1001 if (info
->loop_iterations
)
1003 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1004 info
->loop_iterations
= NULL
;
1006 if (info
->loop_stride
)
1008 pool_free (edge_predicate_pool
, info
->loop_stride
);
1009 info
->loop_stride
= NULL
;
1011 if (info
->array_index
)
1013 pool_free (edge_predicate_pool
, info
->array_index
);
1014 info
->array_index
= NULL
;
1016 vec_free (info
->conds
);
1017 vec_free (info
->entry
);
1018 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1019 reset_inline_edge_summary (e
);
1020 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1021 reset_inline_edge_summary (e
);
1024 /* Hook that is called by cgraph.c when a node is removed. */
1027 inline_node_removal_hook (struct cgraph_node
*node
,
1028 void *data ATTRIBUTE_UNUSED
)
1030 struct inline_summary
*info
;
1031 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1033 info
= inline_summary (node
);
1034 reset_inline_summary (node
);
1035 memset (info
, 0, sizeof (inline_summary_t
));
1038 /* Remap predicate P of former function to be predicate of duplicated functoin.
1039 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1040 INFO is inline summary of the duplicated node. */
1042 static struct predicate
1043 remap_predicate_after_duplication (struct predicate
*p
,
1044 clause_t possible_truths
,
1045 struct inline_summary
*info
)
1047 struct predicate new_predicate
= true_predicate ();
1049 for (j
= 0; p
->clause
[j
]; j
++)
1050 if (!(possible_truths
& p
->clause
[j
]))
1052 new_predicate
= false_predicate ();
1056 add_clause (info
->conds
, &new_predicate
,
1057 possible_truths
& p
->clause
[j
]);
1058 return new_predicate
;
1061 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1062 Additionally care about allocating new memory slot for updated predicate
1063 and set it to NULL when it becomes true or false (and thus uninteresting).
1067 remap_hint_predicate_after_duplication (struct predicate
**p
,
1068 clause_t possible_truths
,
1069 struct inline_summary
*info
)
1071 struct predicate new_predicate
;
1076 new_predicate
= remap_predicate_after_duplication (*p
,
1077 possible_truths
, info
);
1078 /* We do not want to free previous predicate; it is used by node origin. */
1080 set_hint_predicate (p
, new_predicate
);
1084 /* Hook that is called by cgraph.c when a node is duplicated. */
1087 inline_node_duplication_hook (struct cgraph_node
*src
,
1088 struct cgraph_node
*dst
,
1089 ATTRIBUTE_UNUSED
void *data
)
1091 struct inline_summary
*info
;
1092 inline_summary_alloc ();
1093 info
= inline_summary (dst
);
1094 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1095 /* TODO: as an optimization, we may avoid copying conditions
1096 that are known to be false or true. */
1097 info
->conds
= vec_safe_copy (info
->conds
);
1099 /* When there are any replacements in the function body, see if we can figure
1100 out that something was optimized out. */
1101 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1103 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1104 /* Use SRC parm info since it may not be copied yet. */
1105 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1106 vec
<tree
> known_vals
= vNULL
;
1107 int count
= ipa_get_param_count (parms_info
);
1109 clause_t possible_truths
;
1110 struct predicate true_pred
= true_predicate ();
1112 int optimized_out_size
= 0;
1113 bool inlined_to_p
= false;
1114 struct cgraph_edge
*edge
;
1117 known_vals
.safe_grow_cleared (count
);
1118 for (i
= 0; i
< count
; i
++)
1120 struct ipa_replace_map
*r
;
1122 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1124 if (((!r
->old_tree
&& r
->parm_num
== i
)
1125 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1126 && r
->replace_p
&& !r
->ref_p
)
1128 known_vals
[i
] = r
->new_tree
;
1133 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1136 known_vals
.release ();
1138 account_size_time (info
, 0, 0, &true_pred
);
1140 /* Remap size_time vectors.
1141 Simplify the predicate by prunning out alternatives that are known
1143 TODO: as on optimization, we can also eliminate conditions known
1145 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1147 struct predicate new_predicate
;
1148 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1151 if (false_predicate_p (&new_predicate
))
1152 optimized_out_size
+= e
->size
;
1154 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1157 /* Remap edge predicates with the same simplification as above.
1158 Also copy constantness arrays. */
1159 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1161 struct predicate new_predicate
;
1162 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1164 if (!edge
->inline_failed
)
1165 inlined_to_p
= true;
1168 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1171 if (false_predicate_p (&new_predicate
)
1172 && !false_predicate_p (es
->predicate
))
1174 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1175 edge
->frequency
= 0;
1177 edge_set_predicate (edge
, &new_predicate
);
1180 /* Remap indirect edge predicates with the same simplificaiton as above.
1181 Also copy constantness arrays. */
1182 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1184 struct predicate new_predicate
;
1185 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1187 gcc_checking_assert (edge
->inline_failed
);
1190 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1193 if (false_predicate_p (&new_predicate
)
1194 && !false_predicate_p (es
->predicate
))
1196 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1197 edge
->frequency
= 0;
1199 edge_set_predicate (edge
, &new_predicate
);
1201 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1202 possible_truths
, info
);
1203 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1204 possible_truths
, info
);
1205 remap_hint_predicate_after_duplication (&info
->array_index
,
1206 possible_truths
, info
);
1208 /* If inliner or someone after inliner will ever start producing
1209 non-trivial clones, we will get trouble with lack of information
1210 about updating self sizes, because size vectors already contains
1211 sizes of the calees. */
1212 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1216 info
->entry
= vec_safe_copy (info
->entry
);
1217 if (info
->loop_iterations
)
1219 predicate p
= *info
->loop_iterations
;
1220 info
->loop_iterations
= NULL
;
1221 set_hint_predicate (&info
->loop_iterations
, p
);
1223 if (info
->loop_stride
)
1225 predicate p
= *info
->loop_stride
;
1226 info
->loop_stride
= NULL
;
1227 set_hint_predicate (&info
->loop_stride
, p
);
1229 if (info
->array_index
)
1231 predicate p
= *info
->array_index
;
1232 info
->array_index
= NULL
;
1233 set_hint_predicate (&info
->array_index
, p
);
1236 inline_update_overall_summary (dst
);
1240 /* Hook that is called by cgraph.c when a node is duplicated. */
1243 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1244 struct cgraph_edge
*dst
,
1245 ATTRIBUTE_UNUSED
void *data
)
1247 struct inline_edge_summary
*info
;
1248 struct inline_edge_summary
*srcinfo
;
1249 inline_summary_alloc ();
1250 info
= inline_edge_summary (dst
);
1251 srcinfo
= inline_edge_summary (src
);
1252 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1253 info
->predicate
= NULL
;
1254 edge_set_predicate (dst
, srcinfo
->predicate
);
1255 info
->param
= srcinfo
->param
.copy ();
1259 /* Keep edge cache consistent across edge removal. */
1262 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1263 void *data ATTRIBUTE_UNUSED
)
1265 if (edge_growth_cache
.exists ())
1266 reset_edge_growth_cache (edge
);
1267 reset_inline_edge_summary (edge
);
1271 /* Initialize growth caches. */
1274 initialize_growth_caches (void)
1276 if (cgraph_edge_max_uid
)
1277 edge_growth_cache
.safe_grow_cleared (cgraph_edge_max_uid
);
1279 node_growth_cache
.safe_grow_cleared (cgraph_max_uid
);
1283 /* Free growth caches. */
1286 free_growth_caches (void)
1288 edge_growth_cache
.release ();
1289 node_growth_cache
.release ();
1293 /* Dump edge summaries associated to NODE and recursively to all clones.
1294 Indent by INDENT. */
1297 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1298 struct inline_summary
*info
)
1300 struct cgraph_edge
*edge
;
1301 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1303 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1304 struct cgraph_node
*callee
=
1305 cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1309 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1310 " time: %2i callee size:%2i stack:%2i",
1311 indent
, "", callee
->name (), callee
->order
,
1312 !edge
->inline_failed
1313 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1314 indent
, "", es
->loop_depth
, edge
->frequency
,
1315 es
->call_stmt_size
, es
->call_stmt_time
,
1316 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1317 (int) inline_summary (callee
)->estimated_stack_size
);
1321 fprintf (f
, " predicate: ");
1322 dump_predicate (f
, info
->conds
, es
->predicate
);
1326 if (es
->param
.exists ())
1327 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1329 int prob
= es
->param
[i
].change_prob
;
1332 fprintf (f
, "%*s op%i is compile time invariant\n",
1334 else if (prob
!= REG_BR_PROB_BASE
)
1335 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1336 prob
* 100.0 / REG_BR_PROB_BASE
);
1338 if (!edge
->inline_failed
)
1340 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1341 " callee size %i\n",
1343 (int) inline_summary (callee
)->stack_frame_offset
,
1344 (int) inline_summary (callee
)->estimated_self_stack_size
,
1345 (int) inline_summary (callee
)->estimated_stack_size
);
1346 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1349 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1351 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1352 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1356 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1359 fprintf (f
, "predicate: ");
1360 dump_predicate (f
, info
->conds
, es
->predicate
);
1369 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1371 if (node
->definition
)
1373 struct inline_summary
*s
= inline_summary (node
);
1376 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1378 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1379 fprintf (f
, " always_inline");
1381 fprintf (f
, " inlinable");
1382 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1383 fprintf (f
, " global time: %i\n", s
->time
);
1384 fprintf (f
, " self size: %i\n", s
->self_size
);
1385 fprintf (f
, " global size: %i\n", s
->size
);
1386 fprintf (f
, " self stack: %i\n",
1387 (int) s
->estimated_self_stack_size
);
1388 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1390 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1392 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1393 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1395 fprintf (f
, " size:%f, time:%f, predicate:",
1396 (double) e
->size
/ INLINE_SIZE_SCALE
,
1397 (double) e
->time
/ INLINE_TIME_SCALE
);
1398 dump_predicate (f
, s
->conds
, &e
->predicate
);
1400 if (s
->loop_iterations
)
1402 fprintf (f
, " loop iterations:");
1403 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1407 fprintf (f
, " loop stride:");
1408 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1412 fprintf (f
, " array index:");
1413 dump_predicate (f
, s
->conds
, s
->array_index
);
1415 fprintf (f
, " calls:\n");
1416 dump_inline_edge_summary (f
, 4, node
, s
);
1422 debug_inline_summary (struct cgraph_node
*node
)
1424 dump_inline_summary (stderr
, node
);
1428 dump_inline_summaries (FILE *f
)
1430 struct cgraph_node
*node
;
1432 FOR_EACH_DEFINED_FUNCTION (node
)
1433 if (!node
->global
.inlined_to
)
1434 dump_inline_summary (f
, node
);
1437 /* Give initial reasons why inlining would fail on EDGE. This gets either
1438 nullified or usually overwritten by more precise reasons later. */
1441 initialize_inline_failed (struct cgraph_edge
*e
)
1443 struct cgraph_node
*callee
= e
->callee
;
1445 if (e
->indirect_unknown_callee
)
1446 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1447 else if (!callee
->definition
)
1448 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1449 else if (callee
->local
.redefined_extern_inline
)
1450 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1451 else if (e
->call_stmt_cannot_inline_p
)
1452 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1453 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1454 /* We can't inline if the function is spawing a function. */
1455 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1457 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1460 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1461 boolean variable pointed to by DATA. */
1464 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1467 bool *b
= (bool *) data
;
1472 /* If OP refers to value of function parameter, return the corresponding
1476 unmodified_parm_1 (gimple stmt
, tree op
)
1478 /* SSA_NAME referring to parm default def? */
1479 if (TREE_CODE (op
) == SSA_NAME
1480 && SSA_NAME_IS_DEFAULT_DEF (op
)
1481 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1482 return SSA_NAME_VAR (op
);
1483 /* Non-SSA parm reference? */
1484 if (TREE_CODE (op
) == PARM_DECL
)
1486 bool modified
= false;
1489 ao_ref_init (&refd
, op
);
1490 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1498 /* If OP refers to value of function parameter, return the corresponding
1499 parameter. Also traverse chains of SSA register assignments. */
1502 unmodified_parm (gimple stmt
, tree op
)
1504 tree res
= unmodified_parm_1 (stmt
, op
);
1508 if (TREE_CODE (op
) == SSA_NAME
1509 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1510 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1511 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1512 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1516 /* If OP refers to a value of a function parameter or value loaded from an
1517 aggregate passed to a parameter (either by value or reference), return TRUE
1518 and store the number of the parameter to *INDEX_P and information whether
1519 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1520 the function parameters, STMT is the statement in which OP is used or
1524 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1525 gimple stmt
, tree op
, int *index_p
,
1526 struct agg_position_info
*aggpos
)
1528 tree res
= unmodified_parm_1 (stmt
, op
);
1530 gcc_checking_assert (aggpos
);
1533 *index_p
= ipa_get_param_decl_index (info
, res
);
1536 aggpos
->agg_contents
= false;
1537 aggpos
->by_ref
= false;
1541 if (TREE_CODE (op
) == SSA_NAME
)
1543 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1544 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1546 stmt
= SSA_NAME_DEF_STMT (op
);
1547 op
= gimple_assign_rhs1 (stmt
);
1548 if (!REFERENCE_CLASS_P (op
))
1549 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1553 aggpos
->agg_contents
= true;
1554 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1558 /* See if statement might disappear after inlining.
1559 0 - means not eliminated
1560 1 - half of statements goes away
1561 2 - for sure it is eliminated.
1562 We are not terribly sophisticated, basically looking for simple abstraction
1563 penalty wrappers. */
1566 eliminated_by_inlining_prob (gimple stmt
)
1568 enum gimple_code code
= gimple_code (stmt
);
1569 enum tree_code rhs_code
;
1579 if (gimple_num_ops (stmt
) != 2)
1582 rhs_code
= gimple_assign_rhs_code (stmt
);
1584 /* Casts of parameters, loads from parameters passed by reference
1585 and stores to return value or parameters are often free after
1586 inlining dua to SRA and further combining.
1587 Assume that half of statements goes away. */
1588 if (rhs_code
== CONVERT_EXPR
1589 || rhs_code
== NOP_EXPR
1590 || rhs_code
== VIEW_CONVERT_EXPR
1591 || rhs_code
== ADDR_EXPR
1592 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1594 tree rhs
= gimple_assign_rhs1 (stmt
);
1595 tree lhs
= gimple_assign_lhs (stmt
);
1596 tree inner_rhs
= get_base_address (rhs
);
1597 tree inner_lhs
= get_base_address (lhs
);
1598 bool rhs_free
= false;
1599 bool lhs_free
= false;
1606 /* Reads of parameter are expected to be free. */
1607 if (unmodified_parm (stmt
, inner_rhs
))
1609 /* Match expressions of form &this->field. Those will most likely
1610 combine with something upstream after inlining. */
1611 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1613 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1614 if (TREE_CODE (op
) == PARM_DECL
)
1616 else if (TREE_CODE (op
) == MEM_REF
1617 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1621 /* When parameter is not SSA register because its address is taken
1622 and it is just copied into one, the statement will be completely
1623 free after inlining (we will copy propagate backward). */
1624 if (rhs_free
&& is_gimple_reg (lhs
))
1627 /* Reads of parameters passed by reference
1628 expected to be free (i.e. optimized out after inlining). */
1629 if (TREE_CODE (inner_rhs
) == MEM_REF
1630 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1633 /* Copying parameter passed by reference into gimple register is
1634 probably also going to copy propagate, but we can't be quite
1636 if (rhs_free
&& is_gimple_reg (lhs
))
1639 /* Writes to parameters, parameters passed by value and return value
1640 (either dirrectly or passed via invisible reference) are free.
1642 TODO: We ought to handle testcase like
1643 struct a {int a,b;};
1645 retrurnsturct (void)
1651 This translate into:
1666 For that we either need to copy ipa-split logic detecting writes
1668 if (TREE_CODE (inner_lhs
) == PARM_DECL
1669 || TREE_CODE (inner_lhs
) == RESULT_DECL
1670 || (TREE_CODE (inner_lhs
) == MEM_REF
1671 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1672 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1673 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1674 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1676 0))) == RESULT_DECL
))))
1679 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1681 if (lhs_free
&& rhs_free
)
1691 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1692 predicates to the CFG edges. */
1695 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1696 struct inline_summary
*summary
,
1702 struct agg_position_info aggpos
;
1703 enum tree_code code
, inverted_code
;
1709 last
= last_stmt (bb
);
1710 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1712 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1714 op
= gimple_cond_lhs (last
);
1715 /* TODO: handle conditionals like
1718 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1720 code
= gimple_cond_code (last
);
1722 = invert_tree_comparison (code
,
1723 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1725 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1727 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1728 e
->flags
& EDGE_TRUE_VALUE
1729 ? code
: inverted_code
,
1730 gimple_cond_rhs (last
));
1731 e
->aux
= pool_alloc (edge_predicate_pool
);
1732 *(struct predicate
*) e
->aux
= p
;
1736 if (TREE_CODE (op
) != SSA_NAME
)
1739 if (builtin_constant_p (op))
1743 Here we can predicate nonconstant_code. We can't
1744 really handle constant_code since we have no predicate
1745 for this and also the constant code is not known to be
1746 optimized away when inliner doen't see operand is constant.
1747 Other optimizers might think otherwise. */
1748 if (gimple_cond_code (last
) != NE_EXPR
1749 || !integer_zerop (gimple_cond_rhs (last
)))
1751 set_stmt
= SSA_NAME_DEF_STMT (op
);
1752 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1753 || gimple_call_num_args (set_stmt
) != 1)
1755 op2
= gimple_call_arg (set_stmt
, 0);
1756 if (!unmodified_parm_or_parm_agg_item
1757 (info
, set_stmt
, op2
, &index
, &aggpos
))
1759 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1761 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1762 IS_NOT_CONSTANT
, NULL_TREE
);
1763 e
->aux
= pool_alloc (edge_predicate_pool
);
1764 *(struct predicate
*) e
->aux
= p
;
1769 /* If BB ends by a switch we can turn into predicates, attach corresponding
1770 predicates to the CFG edges. */
1773 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1774 struct inline_summary
*summary
,
1780 struct agg_position_info aggpos
;
1786 last
= last_stmt (bb
);
1787 if (!last
|| gimple_code (last
) != GIMPLE_SWITCH
)
1789 op
= gimple_switch_index (last
);
1790 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1793 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1795 e
->aux
= pool_alloc (edge_predicate_pool
);
1796 *(struct predicate
*) e
->aux
= false_predicate ();
1798 n
= gimple_switch_num_labels (last
);
1799 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1801 tree cl
= gimple_switch_label (last
, case_idx
);
1805 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1806 min
= CASE_LOW (cl
);
1807 max
= CASE_HIGH (cl
);
1809 /* For default we might want to construct predicate that none
1810 of cases is met, but it is bit hard to do not having negations
1811 of conditionals handy. */
1813 p
= true_predicate ();
1815 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1818 struct predicate p1
, p2
;
1819 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1820 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1821 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1823 *(struct predicate
*) e
->aux
1824 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1829 /* For each BB in NODE attach to its AUX pointer predicate under
1830 which it is executable. */
1833 compute_bb_predicates (struct cgraph_node
*node
,
1834 struct ipa_node_params
*parms_info
,
1835 struct inline_summary
*summary
)
1837 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1841 FOR_EACH_BB_FN (bb
, my_function
)
1843 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1844 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1847 /* Entry block is always executable. */
1848 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1849 = pool_alloc (edge_predicate_pool
);
1850 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1851 = true_predicate ();
1853 /* A simple dataflow propagation of predicates forward in the CFG.
1854 TODO: work in reverse postorder. */
1858 FOR_EACH_BB_FN (bb
, my_function
)
1860 struct predicate p
= false_predicate ();
1863 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1867 struct predicate this_bb_predicate
1868 = *(struct predicate
*) e
->src
->aux
;
1871 = and_predicates (summary
->conds
, &this_bb_predicate
,
1872 (struct predicate
*) e
->aux
);
1873 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1874 if (true_predicate_p (&p
))
1878 if (false_predicate_p (&p
))
1879 gcc_assert (!bb
->aux
);
1885 bb
->aux
= pool_alloc (edge_predicate_pool
);
1886 *((struct predicate
*) bb
->aux
) = p
;
1888 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1891 *((struct predicate
*) bb
->aux
) = p
;
1899 /* We keep info about constantness of SSA names. */
1901 typedef struct predicate predicate_t
;
1902 /* Return predicate specifying when the STMT might have result that is not
1903 a compile time constant. */
1905 static struct predicate
1906 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1907 struct inline_summary
*summary
,
1909 vec
<predicate_t
> nonconstant_names
)
1914 while (UNARY_CLASS_P (expr
))
1915 expr
= TREE_OPERAND (expr
, 0);
1917 parm
= unmodified_parm (NULL
, expr
);
1918 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1919 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1920 if (is_gimple_min_invariant (expr
))
1921 return false_predicate ();
1922 if (TREE_CODE (expr
) == SSA_NAME
)
1923 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1924 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1926 struct predicate p1
= will_be_nonconstant_expr_predicate
1927 (info
, summary
, TREE_OPERAND (expr
, 0),
1929 struct predicate p2
;
1930 if (true_predicate_p (&p1
))
1932 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1933 TREE_OPERAND (expr
, 1),
1935 return or_predicates (summary
->conds
, &p1
, &p2
);
1937 else if (TREE_CODE (expr
) == COND_EXPR
)
1939 struct predicate p1
= will_be_nonconstant_expr_predicate
1940 (info
, summary
, TREE_OPERAND (expr
, 0),
1942 struct predicate p2
;
1943 if (true_predicate_p (&p1
))
1945 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1946 TREE_OPERAND (expr
, 1),
1948 if (true_predicate_p (&p2
))
1950 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
1951 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1952 TREE_OPERAND (expr
, 2),
1954 return or_predicates (summary
->conds
, &p1
, &p2
);
1961 return false_predicate ();
1965 /* Return predicate specifying when the STMT might have result that is not
1966 a compile time constant. */
1968 static struct predicate
1969 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
1970 struct inline_summary
*summary
,
1972 vec
<predicate_t
> nonconstant_names
)
1974 struct predicate p
= true_predicate ();
1977 struct predicate op_non_const
;
1980 struct agg_position_info aggpos
;
1982 /* What statments might be optimized away
1983 when their arguments are constant
1984 TODO: also trivial builtins.
1985 builtin_constant_p is already handled later. */
1986 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1987 && gimple_code (stmt
) != GIMPLE_COND
1988 && gimple_code (stmt
) != GIMPLE_SWITCH
)
1991 /* Stores will stay anyway. */
1992 if (gimple_store_p (stmt
))
1995 is_load
= gimple_assign_load_p (stmt
);
1997 /* Loads can be optimized when the value is known. */
2001 gcc_assert (gimple_assign_single_p (stmt
));
2002 op
= gimple_assign_rhs1 (stmt
);
2003 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2010 /* See if we understand all operands before we start
2011 adding conditionals. */
2012 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2014 tree parm
= unmodified_parm (stmt
, use
);
2015 /* For arguments we can build a condition. */
2016 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2018 if (TREE_CODE (use
) != SSA_NAME
)
2020 /* If we know when operand is constant,
2021 we still can say something useful. */
2022 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2029 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2031 op_non_const
= false_predicate ();
2032 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2034 tree parm
= unmodified_parm (stmt
, use
);
2037 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2039 if (index
!= base_index
)
2040 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2045 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2046 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2048 if (gimple_code (stmt
) == GIMPLE_ASSIGN
2049 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
2050 nonconstant_names
[SSA_NAME_VERSION (gimple_assign_lhs (stmt
))]
2052 return op_non_const
;
2055 struct record_modified_bb_info
2061 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2062 set except for info->stmt. */
2065 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2067 struct record_modified_bb_info
*info
=
2068 (struct record_modified_bb_info
*) data
;
2069 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2071 bitmap_set_bit (info
->bb_set
,
2072 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2073 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2074 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2078 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2079 will change since last invocation of STMT.
2081 Value 0 is reserved for compile time invariants.
2082 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2083 ought to be REG_BR_PROB_BASE / estimated_iters. */
2086 param_change_prob (gimple stmt
, int i
)
2088 tree op
= gimple_call_arg (stmt
, i
);
2089 basic_block bb
= gimple_bb (stmt
);
2092 /* Global invariants neve change. */
2093 if (is_gimple_min_invariant (op
))
2095 /* We would have to do non-trivial analysis to really work out what
2096 is the probability of value to change (i.e. when init statement
2097 is in a sibling loop of the call).
2099 We do an conservative estimate: when call is executed N times more often
2100 than the statement defining value, we take the frequency 1/N. */
2101 if (TREE_CODE (op
) == SSA_NAME
)
2106 return REG_BR_PROB_BASE
;
2108 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2109 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2111 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2115 if (init_freq
< bb
->frequency
)
2116 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2118 return REG_BR_PROB_BASE
;
2121 base
= get_base_address (op
);
2126 struct record_modified_bb_info info
;
2129 tree init
= ctor_for_folding (base
);
2131 if (init
!= error_mark_node
)
2134 return REG_BR_PROB_BASE
;
2135 ao_ref_init (&refd
, op
);
2137 info
.bb_set
= BITMAP_ALLOC (NULL
);
2138 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2140 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2142 BITMAP_FREE (info
.bb_set
);
2143 return REG_BR_PROB_BASE
;
2146 /* Assume that every memory is initialized at entry.
2147 TODO: Can we easilly determine if value is always defined
2148 and thus we may skip entry block? */
2149 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2150 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2154 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2155 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2157 BITMAP_FREE (info
.bb_set
);
2158 if (max
< bb
->frequency
)
2159 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2161 return REG_BR_PROB_BASE
;
2163 return REG_BR_PROB_BASE
;
2166 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2167 sub-graph and if the predicate the condition depends on is known. If so,
2168 return true and store the pointer the predicate in *P. */
2171 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2172 struct inline_summary
*summary
, basic_block bb
,
2173 struct predicate
*p
,
2174 vec
<predicate_t
> nonconstant_names
)
2178 basic_block first_bb
= NULL
;
2181 if (single_pred_p (bb
))
2183 *p
= false_predicate ();
2187 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2189 if (single_succ_p (e
->src
))
2191 if (!single_pred_p (e
->src
))
2194 first_bb
= single_pred (e
->src
);
2195 else if (single_pred (e
->src
) != first_bb
)
2202 else if (e
->src
!= first_bb
)
2210 stmt
= last_stmt (first_bb
);
2212 || gimple_code (stmt
) != GIMPLE_COND
2213 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2216 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2217 gimple_cond_lhs (stmt
),
2219 if (true_predicate_p (p
))
2225 /* Given a PHI statement in a function described by inline properties SUMMARY
2226 and *P being the predicate describing whether the selected PHI argument is
2227 known, store a predicate for the result of the PHI statement into
2228 NONCONSTANT_NAMES, if possible. */
2231 predicate_for_phi_result (struct inline_summary
*summary
, gimple phi
,
2232 struct predicate
*p
,
2233 vec
<predicate_t
> nonconstant_names
)
2237 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2239 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2240 if (!is_gimple_min_invariant (arg
))
2242 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2243 *p
= or_predicates (summary
->conds
, p
,
2244 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2245 if (true_predicate_p (p
))
2250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2252 fprintf (dump_file
, "\t\tphi predicate: ");
2253 dump_predicate (dump_file
, summary
->conds
, p
);
2255 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2258 /* Return predicate specifying when array index in access OP becomes non-constant. */
2260 static struct predicate
2261 array_index_predicate (struct inline_summary
*info
,
2262 vec
< predicate_t
> nonconstant_names
, tree op
)
2264 struct predicate p
= false_predicate ();
2265 while (handled_component_p (op
))
2267 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2269 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2270 p
= or_predicates (info
->conds
, &p
,
2271 &nonconstant_names
[SSA_NAME_VERSION
2272 (TREE_OPERAND (op
, 1))]);
2274 op
= TREE_OPERAND (op
, 0);
2279 /* For a typical usage of __builtin_expect (a<b, 1), we
2280 may introduce an extra relation stmt:
2281 With the builtin, we have
2284 t3 = __builtin_expect (t2, 1);
2287 Without the builtin, we have
2290 This affects the size/time estimation and may have
2291 an impact on the earlier inlining.
2292 Here find this pattern and fix it up later. */
2295 find_foldable_builtin_expect (basic_block bb
)
2297 gimple_stmt_iterator bsi
;
2299 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2301 gimple stmt
= gsi_stmt (bsi
);
2302 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
))
2304 tree var
= gimple_call_lhs (stmt
);
2305 tree arg
= gimple_call_arg (stmt
, 0);
2306 use_operand_p use_p
;
2313 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2315 while (TREE_CODE (arg
) == SSA_NAME
)
2317 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2318 if (!is_gimple_assign (stmt_tmp
))
2320 switch (gimple_assign_rhs_code (stmt_tmp
))
2339 arg
= gimple_assign_rhs1 (stmt_tmp
);
2342 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2343 && gimple_code (use_stmt
) == GIMPLE_COND
)
2350 /* Return true when the basic blocks contains only clobbers followed by RESX.
2351 Such BBs are kept around to make removal of dead stores possible with
2352 presence of EH and will be optimized out by optimize_clobbers later in the
2355 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2356 that can be clobber only, too.. When it is false, the RESX is not necessary
2357 on the end of basic block. */
2360 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2362 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2368 if (gsi_end_p (gsi
))
2370 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2374 else if (!single_succ_p (bb
))
2377 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2379 gimple stmt
= gsi_stmt (gsi
);
2380 if (is_gimple_debug (stmt
))
2382 if (gimple_clobber_p (stmt
))
2384 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2389 /* See if all predecestors are either throws or clobber only BBs. */
2390 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2391 if (!(e
->flags
& EDGE_EH
)
2392 && !clobber_only_eh_bb_p (e
->src
, false))
2398 /* Compute function body size parameters for NODE.
2399 When EARLY is true, we compute only simple summaries without
2400 non-trivial predicates to drive the early inliner. */
2403 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2406 /* Estimate static overhead for function prologue/epilogue and alignment. */
2408 /* Benefits are scaled by probability of elimination that is in range
2411 gimple_stmt_iterator bsi
;
2412 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2414 struct inline_summary
*info
= inline_summary (node
);
2415 struct predicate bb_predicate
;
2416 struct ipa_node_params
*parms_info
= NULL
;
2417 vec
<predicate_t
> nonconstant_names
= vNULL
;
2420 predicate array_index
= true_predicate ();
2421 gimple fix_builtin_expect_stmt
;
2426 if (optimize
&& !early
)
2428 calculate_dominance_info (CDI_DOMINATORS
);
2429 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2431 if (ipa_node_params_vector
.exists ())
2433 parms_info
= IPA_NODE_REF (node
);
2434 nonconstant_names
.safe_grow_cleared
2435 (SSANAMES (my_function
)->length ());
2440 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2443 /* When we run into maximal number of entries, we assign everything to the
2444 constant truth case. Be sure to have it in list. */
2445 bb_predicate
= true_predicate ();
2446 account_size_time (info
, 0, 0, &bb_predicate
);
2448 bb_predicate
= not_inlined_predicate ();
2449 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2451 gcc_assert (my_function
&& my_function
->cfg
);
2453 compute_bb_predicates (node
, parms_info
, info
);
2454 gcc_assert (cfun
== my_function
);
2455 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2456 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2457 for (n
= 0; n
< nblocks
; n
++)
2459 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2460 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2461 if (clobber_only_eh_bb_p (bb
))
2463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2464 fprintf (dump_file
, "\n Ignoring BB %i;"
2465 " it will be optimized away by cleanup_clobbers\n",
2470 /* TODO: Obviously predicates can be propagated down across CFG. */
2474 bb_predicate
= *(struct predicate
*) bb
->aux
;
2476 bb_predicate
= false_predicate ();
2479 bb_predicate
= true_predicate ();
2481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2483 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2484 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2487 if (parms_info
&& nonconstant_names
.exists ())
2489 struct predicate phi_predicate
;
2490 bool first_phi
= true;
2492 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2495 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2500 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2502 fprintf (dump_file
, " ");
2503 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2505 predicate_for_phi_result (info
, gsi_stmt (bsi
), &phi_predicate
,
2510 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2512 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2514 gimple stmt
= gsi_stmt (bsi
);
2515 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2516 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2518 struct predicate will_be_nonconstant
;
2520 /* This relation stmt should be folded after we remove
2521 buildin_expect call. Adjust the cost here. */
2522 if (stmt
== fix_builtin_expect_stmt
)
2528 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2530 fprintf (dump_file
, " ");
2531 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2532 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2533 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2537 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2539 struct predicate this_array_index
;
2541 array_index_predicate (info
, nonconstant_names
,
2542 gimple_assign_rhs1 (stmt
));
2543 if (!false_predicate_p (&this_array_index
))
2545 and_predicates (info
->conds
, &array_index
,
2548 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2550 struct predicate this_array_index
;
2552 array_index_predicate (info
, nonconstant_names
,
2553 gimple_get_lhs (stmt
));
2554 if (!false_predicate_p (&this_array_index
))
2556 and_predicates (info
->conds
, &array_index
,
2561 if (is_gimple_call (stmt
)
2562 && !gimple_call_internal_p (stmt
))
2564 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
2565 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2567 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2568 resolved as constant. We however don't want to optimize
2569 out the cgraph edges. */
2570 if (nonconstant_names
.exists ()
2571 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2572 && gimple_call_lhs (stmt
)
2573 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2575 struct predicate false_p
= false_predicate ();
2576 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2579 if (ipa_node_params_vector
.exists ())
2581 int count
= gimple_call_num_args (stmt
);
2585 es
->param
.safe_grow_cleared (count
);
2586 for (i
= 0; i
< count
; i
++)
2588 int prob
= param_change_prob (stmt
, i
);
2589 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2590 es
->param
[i
].change_prob
= prob
;
2594 es
->call_stmt_size
= this_size
;
2595 es
->call_stmt_time
= this_time
;
2596 es
->loop_depth
= bb_loop_depth (bb
);
2597 edge_set_predicate (edge
, &bb_predicate
);
2600 /* TODO: When conditional jump or swithc is known to be constant, but
2601 we did not translate it into the predicates, we really can account
2602 just maximum of the possible paths. */
2605 = will_be_nonconstant_predicate (parms_info
, info
,
2606 stmt
, nonconstant_names
);
2607 if (this_time
|| this_size
)
2613 prob
= eliminated_by_inlining_prob (stmt
);
2614 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2616 "\t\t50%% will be eliminated by inlining\n");
2617 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2618 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2621 p
= and_predicates (info
->conds
, &bb_predicate
,
2622 &will_be_nonconstant
);
2624 p
= true_predicate ();
2626 if (!false_predicate_p (&p
))
2630 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2631 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2634 /* We account everything but the calls. Calls have their own
2635 size/time info attached to cgraph edges. This is necessary
2636 in order to make the cost disappear after inlining. */
2637 if (!is_gimple_call (stmt
))
2641 struct predicate ip
= not_inlined_predicate ();
2642 ip
= and_predicates (info
->conds
, &ip
, &p
);
2643 account_size_time (info
, this_size
* prob
,
2644 this_time
* prob
, &ip
);
2647 account_size_time (info
, this_size
* (2 - prob
),
2648 this_time
* (2 - prob
), &p
);
2651 gcc_assert (time
>= 0);
2652 gcc_assert (size
>= 0);
2656 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2657 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2658 if (time
> MAX_TIME
)
2662 if (!early
&& nonconstant_names
.exists ())
2665 predicate loop_iterations
= true_predicate ();
2666 predicate loop_stride
= true_predicate ();
2668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2669 flow_loops_dump (dump_file
, NULL
, 0);
2671 FOR_EACH_LOOP (loop
, 0)
2676 struct tree_niter_desc niter_desc
;
2677 basic_block
*body
= get_loop_body (loop
);
2678 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2680 exits
= get_loop_exit_edges (loop
);
2681 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2682 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2683 && !is_gimple_min_invariant (niter_desc
.niter
))
2685 predicate will_be_nonconstant
2686 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2689 if (!true_predicate_p (&will_be_nonconstant
))
2690 will_be_nonconstant
= and_predicates (info
->conds
,
2692 &will_be_nonconstant
);
2693 if (!true_predicate_p (&will_be_nonconstant
)
2694 && !false_predicate_p (&will_be_nonconstant
))
2695 /* This is slightly inprecise. We may want to represent each
2696 loop with independent predicate. */
2698 and_predicates (info
->conds
, &loop_iterations
,
2699 &will_be_nonconstant
);
2703 for (i
= 0; i
< loop
->num_nodes
; i
++)
2705 gimple_stmt_iterator gsi
;
2706 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2707 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2710 gimple stmt
= gsi_stmt (gsi
);
2715 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2717 predicate will_be_nonconstant
;
2720 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2721 || is_gimple_min_invariant (iv
.step
))
2724 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2727 if (!true_predicate_p (&will_be_nonconstant
))
2729 = and_predicates (info
->conds
,
2731 &will_be_nonconstant
);
2732 if (!true_predicate_p (&will_be_nonconstant
)
2733 && !false_predicate_p (&will_be_nonconstant
))
2734 /* This is slightly inprecise. We may want to represent
2735 each loop with independent predicate. */
2737 and_predicates (info
->conds
, &loop_stride
,
2738 &will_be_nonconstant
);
2744 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2746 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2749 FOR_ALL_BB_FN (bb
, my_function
)
2755 pool_free (edge_predicate_pool
, bb
->aux
);
2757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2760 pool_free (edge_predicate_pool
, e
->aux
);
2764 inline_summary (node
)->self_time
= time
;
2765 inline_summary (node
)->self_size
= size
;
2766 nonconstant_names
.release ();
2767 if (optimize
&& !early
)
2769 loop_optimizer_finalize ();
2770 free_dominance_info (CDI_DOMINATORS
);
2774 fprintf (dump_file
, "\n");
2775 dump_inline_summary (dump_file
, node
);
2780 /* Compute parameters of functions used by inliner.
2781 EARLY is true when we compute parameters for the early inliner */
2784 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2786 HOST_WIDE_INT self_stack_size
;
2787 struct cgraph_edge
*e
;
2788 struct inline_summary
*info
;
2790 gcc_assert (!node
->global
.inlined_to
);
2792 inline_summary_alloc ();
2794 info
= inline_summary (node
);
2795 reset_inline_summary (node
);
2797 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2798 Once this happen, we will need to more curefully predict call
2800 if (node
->thunk
.thunk_p
)
2802 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2803 struct predicate t
= true_predicate ();
2805 info
->inlinable
= 0;
2806 node
->callees
->call_stmt_cannot_inline_p
= true;
2807 node
->local
.can_change_signature
= false;
2808 es
->call_stmt_time
= 1;
2809 es
->call_stmt_size
= 1;
2810 account_size_time (info
, 0, 0, &t
);
2814 /* Even is_gimple_min_invariant rely on current_function_decl. */
2815 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2817 /* Estimate the stack size for the function if we're optimizing. */
2818 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2819 info
->estimated_self_stack_size
= self_stack_size
;
2820 info
->estimated_stack_size
= self_stack_size
;
2821 info
->stack_frame_offset
= 0;
2823 /* Can this function be inlined at all? */
2824 if (!optimize
&& !lookup_attribute ("always_inline",
2825 DECL_ATTRIBUTES (node
->decl
)))
2826 info
->inlinable
= false;
2828 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2830 /* Type attributes can use parameter indices to describe them. */
2831 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2832 node
->local
.can_change_signature
= false;
2835 /* Otherwise, inlinable functions always can change signature. */
2836 if (info
->inlinable
)
2837 node
->local
.can_change_signature
= true;
2840 /* Functions calling builtin_apply can not change signature. */
2841 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2843 tree
cdecl = e
->callee
->decl
;
2844 if (DECL_BUILT_IN (cdecl)
2845 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2846 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2847 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2850 node
->local
.can_change_signature
= !e
;
2853 estimate_function_body_sizes (node
, early
);
2855 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2856 if (symtab_comdat_local_p (e
->callee
))
2858 node
->calls_comdat_local
= (e
!= NULL
);
2860 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2861 info
->time
= info
->self_time
;
2862 info
->size
= info
->self_size
;
2863 info
->stack_frame_offset
= 0;
2864 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2865 #ifdef ENABLE_CHECKING
2866 inline_update_overall_summary (node
);
2867 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2874 /* Compute parameters of functions used by inliner using
2875 current_function_decl. */
2878 compute_inline_parameters_for_current (void)
2880 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
2886 const pass_data pass_data_inline_parameters
=
2888 GIMPLE_PASS
, /* type */
2889 "inline_param", /* name */
2890 OPTGROUP_INLINE
, /* optinfo_flags */
2891 false, /* has_gate */
2892 true, /* has_execute */
2893 TV_INLINE_PARAMETERS
, /* tv_id */
2894 0, /* properties_required */
2895 0, /* properties_provided */
2896 0, /* properties_destroyed */
2897 0, /* todo_flags_start */
2898 0, /* todo_flags_finish */
2901 class pass_inline_parameters
: public gimple_opt_pass
2904 pass_inline_parameters (gcc::context
*ctxt
)
2905 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2908 /* opt_pass methods: */
2909 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2910 unsigned int execute () {
2911 return compute_inline_parameters_for_current ();
2914 }; // class pass_inline_parameters
2919 make_pass_inline_parameters (gcc::context
*ctxt
)
2921 return new pass_inline_parameters (ctxt
);
2925 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2929 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2930 int *size
, int *time
,
2931 vec
<tree
> known_vals
,
2932 vec
<tree
> known_binfos
,
2933 vec
<ipa_agg_jump_function_p
> known_aggs
)
2936 struct cgraph_node
*callee
;
2937 struct inline_summary
*isummary
;
2939 if (!known_vals
.exists () && !known_binfos
.exists ())
2941 if (!flag_indirect_inlining
)
2944 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_binfos
,
2949 /* Account for difference in cost between indirect and direct calls. */
2950 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
2951 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
2952 gcc_checking_assert (*time
>= 0);
2953 gcc_checking_assert (*size
>= 0);
2955 callee
= cgraph_get_node (target
);
2956 if (!callee
|| !callee
->definition
)
2958 isummary
= inline_summary (callee
);
2959 return isummary
->inlinable
;
2962 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2965 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
,
2967 vec
<tree
> known_vals
,
2968 vec
<tree
> known_binfos
,
2969 vec
<ipa_agg_jump_function_p
> known_aggs
,
2970 inline_hints
*hints
)
2972 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2973 int call_size
= es
->call_stmt_size
;
2974 int call_time
= es
->call_stmt_time
;
2976 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
2977 known_vals
, known_binfos
, known_aggs
)
2978 && hints
&& cgraph_maybe_hot_edge_p (e
))
2979 *hints
|= INLINE_HINT_indirect_call
;
2980 *size
+= call_size
* INLINE_SIZE_SCALE
;
2981 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
2982 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
2983 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
2984 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
2989 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
2990 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
2994 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
,
2995 inline_hints
*hints
,
2996 clause_t possible_truths
,
2997 vec
<tree
> known_vals
,
2998 vec
<tree
> known_binfos
,
2999 vec
<ipa_agg_jump_function_p
> known_aggs
)
3001 struct cgraph_edge
*e
;
3002 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3004 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3006 || evaluate_predicate (es
->predicate
, possible_truths
))
3008 if (e
->inline_failed
)
3010 /* Predicates of calls shall not use NOT_CHANGED codes,
3011 sowe do not need to compute probabilities. */
3012 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
,
3013 known_vals
, known_binfos
,
3017 estimate_calls_size_and_time (e
->callee
, size
, time
, hints
,
3019 known_vals
, known_binfos
,
3023 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3025 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3027 || evaluate_predicate (es
->predicate
, possible_truths
))
3028 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
,
3029 known_vals
, known_binfos
, known_aggs
,
3035 /* Estimate size and time needed to execute NODE assuming
3036 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
3037 about NODE's arguments. */
3040 estimate_node_size_and_time (struct cgraph_node
*node
,
3041 clause_t possible_truths
,
3042 vec
<tree
> known_vals
,
3043 vec
<tree
> known_binfos
,
3044 vec
<ipa_agg_jump_function_p
> known_aggs
,
3045 int *ret_size
, int *ret_time
,
3046 inline_hints
*ret_hints
,
3047 vec
<inline_param_summary
>
3048 inline_param_summary
)
3050 struct inline_summary
*info
= inline_summary (node
);
3054 inline_hints hints
= 0;
3057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3060 fprintf (dump_file
, " Estimating body: %s/%i\n"
3061 " Known to be false: ", node
->name (),
3064 for (i
= predicate_not_inlined_condition
;
3065 i
< (predicate_first_dynamic_condition
3066 + (int) vec_safe_length (info
->conds
)); i
++)
3067 if (!(possible_truths
& (1 << i
)))
3070 fprintf (dump_file
, ", ");
3072 dump_condition (dump_file
, info
->conds
, i
);
3076 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3077 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3080 gcc_checking_assert (e
->time
>= 0);
3081 gcc_checking_assert (time
>= 0);
3082 if (!inline_param_summary
.exists ())
3086 int prob
= predicate_probability (info
->conds
,
3089 inline_param_summary
);
3090 gcc_checking_assert (prob
>= 0);
3091 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3092 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3094 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3095 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3096 gcc_checking_assert (time
>= 0);
3099 gcc_checking_assert (size
>= 0);
3100 gcc_checking_assert (time
>= 0);
3102 if (info
->loop_iterations
3103 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3104 hints
|= INLINE_HINT_loop_iterations
;
3105 if (info
->loop_stride
3106 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3107 hints
|= INLINE_HINT_loop_stride
;
3108 if (info
->array_index
3109 && !evaluate_predicate (info
->array_index
, possible_truths
))
3110 hints
|= INLINE_HINT_array_index
;
3112 hints
|= INLINE_HINT_in_scc
;
3113 if (DECL_DECLARED_INLINE_P (node
->decl
))
3114 hints
|= INLINE_HINT_declared_inline
;
3116 estimate_calls_size_and_time (node
, &size
, &time
, &hints
, possible_truths
,
3117 known_vals
, known_binfos
, known_aggs
);
3118 gcc_checking_assert (size
>= 0);
3119 gcc_checking_assert (time
>= 0);
3120 time
= RDIV (time
, INLINE_TIME_SCALE
);
3121 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3124 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3135 /* Estimate size and time needed to execute callee of EDGE assuming that
3136 parameters known to be constant at caller of EDGE are propagated.
3137 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
3138 and types for parameters. */
3141 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3142 vec
<tree
> known_vals
,
3143 vec
<tree
> known_binfos
,
3144 vec
<ipa_agg_jump_function_p
> known_aggs
,
3145 int *ret_size
, int *ret_time
,
3146 inline_hints
*hints
)
3150 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3152 estimate_node_size_and_time (node
, clause
, known_vals
, known_binfos
,
3153 known_aggs
, ret_size
, ret_time
, hints
, vNULL
);
3156 /* Translate all conditions from callee representation into caller
3157 representation and symbolically evaluate predicate P into new predicate.
3159 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3160 is summary of function predicate P is from. OPERAND_MAP is array giving
3161 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3162 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3163 predicate under which callee is executed. OFFSET_MAP is an array of of
3164 offsets that need to be added to conditions, negative offset means that
3165 conditions relying on values passed by reference have to be discarded
3166 because they might not be preserved (and should be considered offset zero
3167 for other purposes). */
3169 static struct predicate
3170 remap_predicate (struct inline_summary
*info
,
3171 struct inline_summary
*callee_info
,
3172 struct predicate
*p
,
3173 vec
<int> operand_map
,
3174 vec
<int> offset_map
,
3175 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3178 struct predicate out
= true_predicate ();
3180 /* True predicate is easy. */
3181 if (true_predicate_p (p
))
3182 return *toplev_predicate
;
3183 for (i
= 0; p
->clause
[i
]; i
++)
3185 clause_t clause
= p
->clause
[i
];
3187 struct predicate clause_predicate
= false_predicate ();
3189 gcc_assert (i
< MAX_CLAUSES
);
3191 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3192 /* Do we have condition we can't disprove? */
3193 if (clause
& possible_truths
& (1 << cond
))
3195 struct predicate cond_predicate
;
3196 /* Work out if the condition can translate to predicate in the
3197 inlined function. */
3198 if (cond
>= predicate_first_dynamic_condition
)
3200 struct condition
*c
;
3202 c
= &(*callee_info
->conds
)[cond
3204 predicate_first_dynamic_condition
];
3205 /* See if we can remap condition operand to caller's operand.
3206 Otherwise give up. */
3207 if (!operand_map
.exists ()
3208 || (int) operand_map
.length () <= c
->operand_num
3209 || operand_map
[c
->operand_num
] == -1
3210 /* TODO: For non-aggregate conditions, adding an offset is
3211 basically an arithmetic jump function processing which
3212 we should support in future. */
3213 || ((!c
->agg_contents
|| !c
->by_ref
)
3214 && offset_map
[c
->operand_num
] > 0)
3215 || (c
->agg_contents
&& c
->by_ref
3216 && offset_map
[c
->operand_num
] < 0))
3217 cond_predicate
= true_predicate ();
3220 struct agg_position_info ap
;
3221 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3222 if (offset_delta
< 0)
3224 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3227 gcc_assert (!c
->agg_contents
3228 || c
->by_ref
|| offset_delta
== 0);
3229 ap
.offset
= c
->offset
+ offset_delta
;
3230 ap
.agg_contents
= c
->agg_contents
;
3231 ap
.by_ref
= c
->by_ref
;
3232 cond_predicate
= add_condition (info
,
3233 operand_map
[c
->operand_num
],
3234 &ap
, c
->code
, c
->val
);
3237 /* Fixed conditions remains same, construct single
3238 condition predicate. */
3241 cond_predicate
.clause
[0] = 1 << cond
;
3242 cond_predicate
.clause
[1] = 0;
3244 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3247 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3249 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3253 /* Update summary information of inline clones after inlining.
3254 Compute peak stack usage. */
3257 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3259 struct cgraph_edge
*e
;
3260 struct inline_summary
*callee_info
= inline_summary (node
);
3261 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3264 callee_info
->stack_frame_offset
3265 = caller_info
->stack_frame_offset
3266 + caller_info
->estimated_self_stack_size
;
3267 peak
= callee_info
->stack_frame_offset
3268 + callee_info
->estimated_self_stack_size
;
3269 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3270 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3271 ipa_propagate_frequency (node
);
3272 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3274 if (!e
->inline_failed
)
3275 inline_update_callee_summaries (e
->callee
, depth
);
3276 inline_edge_summary (e
)->loop_depth
+= depth
;
3278 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3279 inline_edge_summary (e
)->loop_depth
+= depth
;
3282 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3283 When functoin A is inlined in B and A calls C with parameter that
3284 changes with probability PROB1 and C is known to be passthroug
3285 of argument if B that change with probability PROB2, the probability
3286 of change is now PROB1*PROB2. */
3289 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3290 struct cgraph_edge
*edge
)
3292 if (ipa_node_params_vector
.exists ())
3295 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3296 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3297 struct inline_edge_summary
*inlined_es
3298 = inline_edge_summary (inlined_edge
);
3300 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3302 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3303 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3304 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3305 < (int) inlined_es
->param
.length ()))
3307 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3308 int prob1
= es
->param
[i
].change_prob
;
3309 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3310 int prob
= combine_probabilities (prob1
, prob2
);
3312 if (prob1
&& prob2
&& !prob
)
3315 es
->param
[i
].change_prob
= prob
;
3321 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3323 Remap predicates of callees of NODE. Rest of arguments match
3326 Also update change probabilities. */
3329 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3330 struct cgraph_node
*node
,
3331 struct inline_summary
*info
,
3332 struct inline_summary
*callee_info
,
3333 vec
<int> operand_map
,
3334 vec
<int> offset_map
,
3335 clause_t possible_truths
,
3336 struct predicate
*toplev_predicate
)
3338 struct cgraph_edge
*e
;
3339 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3341 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3344 if (e
->inline_failed
)
3346 remap_edge_change_prob (inlined_edge
, e
);
3350 p
= remap_predicate (info
, callee_info
,
3351 es
->predicate
, operand_map
, offset_map
,
3352 possible_truths
, toplev_predicate
);
3353 edge_set_predicate (e
, &p
);
3354 /* TODO: We should remove the edge for code that will be
3355 optimized out, but we need to keep verifiers and tree-inline
3356 happy. Make it cold for now. */
3357 if (false_predicate_p (&p
))
3364 edge_set_predicate (e
, toplev_predicate
);
3367 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3368 operand_map
, offset_map
, possible_truths
,
3371 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3373 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3376 remap_edge_change_prob (inlined_edge
, e
);
3379 p
= remap_predicate (info
, callee_info
,
3380 es
->predicate
, operand_map
, offset_map
,
3381 possible_truths
, toplev_predicate
);
3382 edge_set_predicate (e
, &p
);
3383 /* TODO: We should remove the edge for code that will be optimized
3384 out, but we need to keep verifiers and tree-inline happy.
3385 Make it cold for now. */
3386 if (false_predicate_p (&p
))
3393 edge_set_predicate (e
, toplev_predicate
);
3397 /* Same as remap_predicate, but set result into hint *HINT. */
3400 remap_hint_predicate (struct inline_summary
*info
,
3401 struct inline_summary
*callee_info
,
3402 struct predicate
**hint
,
3403 vec
<int> operand_map
,
3404 vec
<int> offset_map
,
3405 clause_t possible_truths
,
3406 struct predicate
*toplev_predicate
)
3412 p
= remap_predicate (info
, callee_info
,
3414 operand_map
, offset_map
,
3415 possible_truths
, toplev_predicate
);
3416 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3419 set_hint_predicate (hint
, p
);
3421 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3425 /* We inlined EDGE. Update summary of the function we inlined into. */
3428 inline_merge_summary (struct cgraph_edge
*edge
)
3430 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3431 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3432 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3433 struct inline_summary
*info
= inline_summary (to
);
3434 clause_t clause
= 0; /* not_inline is known to be false. */
3436 vec
<int> operand_map
= vNULL
;
3437 vec
<int> offset_map
= vNULL
;
3439 struct predicate toplev_predicate
;
3440 struct predicate true_p
= true_predicate ();
3441 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3444 toplev_predicate
= *es
->predicate
;
3446 toplev_predicate
= true_predicate ();
3448 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3450 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3451 int count
= ipa_get_cs_argument_count (args
);
3454 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3457 operand_map
.safe_grow_cleared (count
);
3458 offset_map
.safe_grow_cleared (count
);
3460 for (i
= 0; i
< count
; i
++)
3462 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3465 /* TODO: handle non-NOPs when merging. */
3466 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3468 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3469 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3470 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3473 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3475 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3476 if (offset
>= 0 && offset
< INT_MAX
)
3478 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3479 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3481 offset_map
[i
] = offset
;
3484 operand_map
[i
] = map
;
3485 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3488 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3490 struct predicate p
= remap_predicate (info
, callee_info
,
3491 &e
->predicate
, operand_map
,
3494 if (!false_predicate_p (&p
))
3496 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3497 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3498 int prob
= predicate_probability (callee_info
->conds
,
3501 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3502 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3503 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3504 if (prob
!= REG_BR_PROB_BASE
3505 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3507 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3508 (double) prob
/ REG_BR_PROB_BASE
);
3510 account_size_time (info
, e
->size
, add_time
, &p
);
3513 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3514 offset_map
, clause
, &toplev_predicate
);
3515 remap_hint_predicate (info
, callee_info
,
3516 &callee_info
->loop_iterations
,
3517 operand_map
, offset_map
, clause
, &toplev_predicate
);
3518 remap_hint_predicate (info
, callee_info
,
3519 &callee_info
->loop_stride
,
3520 operand_map
, offset_map
, clause
, &toplev_predicate
);
3521 remap_hint_predicate (info
, callee_info
,
3522 &callee_info
->array_index
,
3523 operand_map
, offset_map
, clause
, &toplev_predicate
);
3525 inline_update_callee_summaries (edge
->callee
,
3526 inline_edge_summary (edge
)->loop_depth
);
3528 /* We do not maintain predicates of inlined edges, free it. */
3529 edge_set_predicate (edge
, &true_p
);
3530 /* Similarly remove param summaries. */
3531 es
->param
.release ();
3532 operand_map
.release ();
3533 offset_map
.release ();
3536 /* For performance reasons inline_merge_summary is not updating overall size
3537 and time. Recompute it. */
3540 inline_update_overall_summary (struct cgraph_node
*node
)
3542 struct inline_summary
*info
= inline_summary (node
);
3548 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3550 info
->size
+= e
->size
, info
->time
+= e
->time
;
3551 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3552 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3554 estimate_calls_size_and_time (node
, &info
->size
, &info
->time
, NULL
,
3555 ~(clause_t
) (1 << predicate_false_condition
),
3556 vNULL
, vNULL
, vNULL
);
3557 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3558 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3561 /* Return hints derrived from EDGE. */
3563 simple_edge_hints (struct cgraph_edge
*edge
)
3566 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3567 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3568 if (inline_summary (to
)->scc_no
3569 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3570 && !cgraph_edge_recursive_p (edge
))
3571 hints
|= INLINE_HINT_same_scc
;
3573 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3574 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3575 hints
|= INLINE_HINT_cross_module
;
3580 /* Estimate the time cost for the caller when inlining EDGE.
3581 Only to be called via estimate_edge_time, that handles the
3584 When caching, also update the cache entry. Compute both time and
3585 size, since we always need both metrics eventually. */
3588 do_estimate_edge_time (struct cgraph_edge
*edge
)
3593 struct cgraph_node
*callee
;
3595 vec
<tree
> known_vals
;
3596 vec
<tree
> known_binfos
;
3597 vec
<ipa_agg_jump_function_p
> known_aggs
;
3598 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3600 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3602 gcc_checking_assert (edge
->inline_failed
);
3603 evaluate_properties_for_edge (edge
, true,
3604 &clause
, &known_vals
, &known_binfos
,
3606 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3607 known_aggs
, &size
, &time
, &hints
, es
->param
);
3608 known_vals
.release ();
3609 known_binfos
.release ();
3610 known_aggs
.release ();
3611 gcc_checking_assert (size
>= 0);
3612 gcc_checking_assert (time
>= 0);
3614 /* When caching, update the cache entry. */
3615 if (edge_growth_cache
.exists ())
3617 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3618 edge_growth_cache
.safe_grow_cleared (cgraph_edge_max_uid
);
3619 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3621 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3622 hints
|= simple_edge_hints (edge
);
3623 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3629 /* Return estimated callee growth after inlining EDGE.
3630 Only to be called via estimate_edge_size. */
3633 do_estimate_edge_size (struct cgraph_edge
*edge
)
3636 struct cgraph_node
*callee
;
3638 vec
<tree
> known_vals
;
3639 vec
<tree
> known_binfos
;
3640 vec
<ipa_agg_jump_function_p
> known_aggs
;
3642 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3644 if (edge_growth_cache
.exists ())
3646 do_estimate_edge_time (edge
);
3647 size
= edge_growth_cache
[edge
->uid
].size
;
3648 gcc_checking_assert (size
);
3649 return size
- (size
> 0);
3652 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3654 /* Early inliner runs without caching, go ahead and do the dirty work. */
3655 gcc_checking_assert (edge
->inline_failed
);
3656 evaluate_properties_for_edge (edge
, true,
3657 &clause
, &known_vals
, &known_binfos
,
3659 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3660 known_aggs
, &size
, NULL
, NULL
, vNULL
);
3661 known_vals
.release ();
3662 known_binfos
.release ();
3663 known_aggs
.release ();
3668 /* Estimate the growth of the caller when inlining EDGE.
3669 Only to be called via estimate_edge_size. */
3672 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3675 struct cgraph_node
*callee
;
3677 vec
<tree
> known_vals
;
3678 vec
<tree
> known_binfos
;
3679 vec
<ipa_agg_jump_function_p
> known_aggs
;
3681 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3683 if (edge_growth_cache
.exists ())
3685 do_estimate_edge_time (edge
);
3686 hints
= edge_growth_cache
[edge
->uid
].hints
;
3687 gcc_checking_assert (hints
);
3691 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
3693 /* Early inliner runs without caching, go ahead and do the dirty work. */
3694 gcc_checking_assert (edge
->inline_failed
);
3695 evaluate_properties_for_edge (edge
, true,
3696 &clause
, &known_vals
, &known_binfos
,
3698 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3699 known_aggs
, NULL
, NULL
, &hints
, vNULL
);
3700 known_vals
.release ();
3701 known_binfos
.release ();
3702 known_aggs
.release ();
3703 hints
|= simple_edge_hints (edge
);
3708 /* Estimate self time of the function NODE after inlining EDGE. */
3711 estimate_time_after_inlining (struct cgraph_node
*node
,
3712 struct cgraph_edge
*edge
)
3714 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3715 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3718 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3721 if (time
> MAX_TIME
)
3725 return inline_summary (node
)->time
;
3729 /* Estimate the size of NODE after inlining EDGE which should be an
3730 edge to either NODE or a call inlined into NODE. */
3733 estimate_size_after_inlining (struct cgraph_node
*node
,
3734 struct cgraph_edge
*edge
)
3736 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3737 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3739 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3740 gcc_assert (size
>= 0);
3743 return inline_summary (node
)->size
;
3749 struct cgraph_node
*node
;
3750 bool self_recursive
;
3755 /* Worker for do_estimate_growth. Collect growth for all callers. */
3758 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3760 struct cgraph_edge
*e
;
3761 struct growth_data
*d
= (struct growth_data
*) data
;
3763 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3765 gcc_checking_assert (e
->inline_failed
);
3767 if (e
->caller
== d
->node
3768 || (e
->caller
->global
.inlined_to
3769 && e
->caller
->global
.inlined_to
== d
->node
))
3770 d
->self_recursive
= true;
3771 d
->growth
+= estimate_edge_growth (e
);
3777 /* Estimate the growth caused by inlining NODE into all callees. */
3780 do_estimate_growth (struct cgraph_node
*node
)
3782 struct growth_data d
= { node
, 0, false };
3783 struct inline_summary
*info
= inline_summary (node
);
3785 cgraph_for_node_and_aliases (node
, do_estimate_growth_1
, &d
, true);
3787 /* For self recursive functions the growth estimation really should be
3788 infinity. We don't want to return very large values because the growth
3789 plays various roles in badness computation fractions. Be sure to not
3790 return zero or negative growths. */
3791 if (d
.self_recursive
)
3792 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3793 else if (DECL_EXTERNAL (node
->decl
))
3797 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
3798 d
.growth
-= info
->size
;
3799 /* COMDAT functions are very often not shared across multiple units
3800 since they come from various template instantiations.
3801 Take this into account. */
3802 else if (DECL_COMDAT (node
->decl
)
3803 && cgraph_can_remove_if_no_direct_calls_p (node
))
3804 d
.growth
-= (info
->size
3805 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3809 if (node_growth_cache
.exists ())
3811 if ((int) node_growth_cache
.length () <= node
->uid
)
3812 node_growth_cache
.safe_grow_cleared (cgraph_max_uid
);
3813 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3819 /* This function performs intraprocedural analysis in NODE that is required to
3820 inline indirect calls. */
3823 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3825 ipa_analyze_node (node
);
3826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3828 ipa_print_node_params (dump_file
, node
);
3829 ipa_print_node_jump_functions (dump_file
, node
);
3834 /* Note function body size. */
3837 inline_analyze_function (struct cgraph_node
*node
)
3839 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3842 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3843 node
->name (), node
->order
);
3844 if (optimize
&& !node
->thunk
.thunk_p
)
3845 inline_indirect_intraprocedural_analysis (node
);
3846 compute_inline_parameters (node
, false);
3849 struct cgraph_edge
*e
;
3850 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3852 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3853 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3854 e
->call_stmt_cannot_inline_p
= true;
3856 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3858 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3859 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3860 e
->call_stmt_cannot_inline_p
= true;
3868 /* Called when new function is inserted to callgraph late. */
3871 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
3873 inline_analyze_function (node
);
3877 /* Note function body size. */
3880 inline_generate_summary (void)
3882 struct cgraph_node
*node
;
3884 /* When not optimizing, do not bother to analyze. Inlining is still done
3885 because edge redirection needs to happen there. */
3886 if (!optimize
&& !flag_lto
&& !flag_wpa
)
3889 function_insertion_hook_holder
=
3890 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
3892 ipa_register_cgraph_hooks ();
3893 inline_free_summary ();
3895 FOR_EACH_DEFINED_FUNCTION (node
)
3897 inline_analyze_function (node
);
3901 /* Read predicate from IB. */
3903 static struct predicate
3904 read_predicate (struct lto_input_block
*ib
)
3906 struct predicate out
;
3912 gcc_assert (k
<= MAX_CLAUSES
);
3913 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
3917 /* Zero-initialize the remaining clauses in OUT. */
3918 while (k
<= MAX_CLAUSES
)
3919 out
.clause
[k
++] = 0;
3925 /* Write inline summary for edge E to OB. */
3928 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
3930 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3934 es
->call_stmt_size
= streamer_read_uhwi (ib
);
3935 es
->call_stmt_time
= streamer_read_uhwi (ib
);
3936 es
->loop_depth
= streamer_read_uhwi (ib
);
3937 p
= read_predicate (ib
);
3938 edge_set_predicate (e
, &p
);
3939 length
= streamer_read_uhwi (ib
);
3942 es
->param
.safe_grow_cleared (length
);
3943 for (i
= 0; i
< length
; i
++)
3944 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
3949 /* Stream in inline summaries from the section. */
3952 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
3955 const struct lto_function_header
*header
=
3956 (const struct lto_function_header
*) data
;
3957 const int cfg_offset
= sizeof (struct lto_function_header
);
3958 const int main_offset
= cfg_offset
+ header
->cfg_size
;
3959 const int string_offset
= main_offset
+ header
->main_size
;
3960 struct data_in
*data_in
;
3961 struct lto_input_block ib
;
3962 unsigned int i
, count2
, j
;
3963 unsigned int f_count
;
3965 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
3969 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
3970 header
->string_size
, vNULL
);
3971 f_count
= streamer_read_uhwi (&ib
);
3972 for (i
= 0; i
< f_count
; i
++)
3975 struct cgraph_node
*node
;
3976 struct inline_summary
*info
;
3977 lto_symtab_encoder_t encoder
;
3978 struct bitpack_d bp
;
3979 struct cgraph_edge
*e
;
3982 index
= streamer_read_uhwi (&ib
);
3983 encoder
= file_data
->symtab_node_encoder
;
3984 node
= cgraph (lto_symtab_encoder_deref (encoder
, index
));
3985 info
= inline_summary (node
);
3987 info
->estimated_stack_size
3988 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
3989 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
3990 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
3992 bp
= streamer_read_bitpack (&ib
);
3993 info
->inlinable
= bp_unpack_value (&bp
, 1);
3995 count2
= streamer_read_uhwi (&ib
);
3996 gcc_assert (!info
->conds
);
3997 for (j
= 0; j
< count2
; j
++)
4000 c
.operand_num
= streamer_read_uhwi (&ib
);
4001 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4002 c
.val
= stream_read_tree (&ib
, data_in
);
4003 bp
= streamer_read_bitpack (&ib
);
4004 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4005 c
.by_ref
= bp_unpack_value (&bp
, 1);
4007 c
.offset
= streamer_read_uhwi (&ib
);
4008 vec_safe_push (info
->conds
, c
);
4010 count2
= streamer_read_uhwi (&ib
);
4011 gcc_assert (!info
->entry
);
4012 for (j
= 0; j
< count2
; j
++)
4014 struct size_time_entry e
;
4016 e
.size
= streamer_read_uhwi (&ib
);
4017 e
.time
= streamer_read_uhwi (&ib
);
4018 e
.predicate
= read_predicate (&ib
);
4020 vec_safe_push (info
->entry
, e
);
4023 p
= read_predicate (&ib
);
4024 set_hint_predicate (&info
->loop_iterations
, p
);
4025 p
= read_predicate (&ib
);
4026 set_hint_predicate (&info
->loop_stride
, p
);
4027 p
= read_predicate (&ib
);
4028 set_hint_predicate (&info
->array_index
, p
);
4029 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4030 read_inline_edge_summary (&ib
, e
);
4031 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4032 read_inline_edge_summary (&ib
, e
);
4035 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4037 lto_data_in_delete (data_in
);
4041 /* Read inline summary. Jump functions are shared among ipa-cp
4042 and inliner, so when ipa-cp is active, we don't need to write them
4046 inline_read_summary (void)
4048 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4049 struct lto_file_decl_data
*file_data
;
4052 inline_summary_alloc ();
4054 while ((file_data
= file_data_vec
[j
++]))
4057 const char *data
= lto_get_section_data (file_data
,
4058 LTO_section_inline_summary
,
4061 inline_read_section (file_data
, data
, len
);
4063 /* Fatal error here. We do not want to support compiling ltrans units
4064 with different version of compiler or different flags than the WPA
4065 unit, so this should never happen. */
4066 fatal_error ("ipa inline summary is missing in input file");
4070 ipa_register_cgraph_hooks ();
4072 ipa_prop_read_jump_functions ();
4074 function_insertion_hook_holder
=
4075 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
4079 /* Write predicate P to OB. */
4082 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4086 for (j
= 0; p
->clause
[j
]; j
++)
4088 gcc_assert (j
< MAX_CLAUSES
);
4089 streamer_write_uhwi (ob
, p
->clause
[j
]);
4091 streamer_write_uhwi (ob
, 0);
4095 /* Write inline summary for edge E to OB. */
4098 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4100 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4103 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4104 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4105 streamer_write_uhwi (ob
, es
->loop_depth
);
4106 write_predicate (ob
, es
->predicate
);
4107 streamer_write_uhwi (ob
, es
->param
.length ());
4108 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4109 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4113 /* Write inline summary for node in SET.
4114 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4115 active, we don't need to write them twice. */
4118 inline_write_summary (void)
4120 struct cgraph_node
*node
;
4121 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4122 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4123 unsigned int count
= 0;
4126 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4128 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4129 cgraph_node
*cnode
= dyn_cast
<cgraph_node
> (snode
);
4130 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4133 streamer_write_uhwi (ob
, count
);
4135 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4137 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4138 cgraph_node
*cnode
= dyn_cast
<cgraph_node
> (snode
);
4139 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4141 struct inline_summary
*info
= inline_summary (node
);
4142 struct bitpack_d bp
;
4143 struct cgraph_edge
*edge
;
4146 struct condition
*c
;
4148 streamer_write_uhwi (ob
,
4149 lto_symtab_encoder_encode (encoder
,
4152 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4153 streamer_write_hwi (ob
, info
->self_size
);
4154 streamer_write_hwi (ob
, info
->self_time
);
4155 bp
= bitpack_create (ob
->main_stream
);
4156 bp_pack_value (&bp
, info
->inlinable
, 1);
4157 streamer_write_bitpack (&bp
);
4158 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4159 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4161 streamer_write_uhwi (ob
, c
->operand_num
);
4162 streamer_write_uhwi (ob
, c
->code
);
4163 stream_write_tree (ob
, c
->val
, true);
4164 bp
= bitpack_create (ob
->main_stream
);
4165 bp_pack_value (&bp
, c
->agg_contents
, 1);
4166 bp_pack_value (&bp
, c
->by_ref
, 1);
4167 streamer_write_bitpack (&bp
);
4168 if (c
->agg_contents
)
4169 streamer_write_uhwi (ob
, c
->offset
);
4171 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4172 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4174 streamer_write_uhwi (ob
, e
->size
);
4175 streamer_write_uhwi (ob
, e
->time
);
4176 write_predicate (ob
, &e
->predicate
);
4178 write_predicate (ob
, info
->loop_iterations
);
4179 write_predicate (ob
, info
->loop_stride
);
4180 write_predicate (ob
, info
->array_index
);
4181 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4182 write_inline_edge_summary (ob
, edge
);
4183 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4184 write_inline_edge_summary (ob
, edge
);
4187 streamer_write_char_stream (ob
->main_stream
, 0);
4188 produce_asm (ob
, NULL
);
4189 destroy_output_block (ob
);
4191 if (optimize
&& !flag_ipa_cp
)
4192 ipa_prop_write_jump_functions ();
4196 /* Release inline summary. */
4199 inline_free_summary (void)
4201 struct cgraph_node
*node
;
4202 if (!inline_edge_summary_vec
.exists ())
4204 FOR_EACH_DEFINED_FUNCTION (node
)
4206 reset_inline_summary (node
);
4207 if (function_insertion_hook_holder
)
4208 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
4209 function_insertion_hook_holder
= NULL
;
4210 if (node_removal_hook_holder
)
4211 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
4212 node_removal_hook_holder
= NULL
;
4213 if (edge_removal_hook_holder
)
4214 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
4215 edge_removal_hook_holder
= NULL
;
4216 if (node_duplication_hook_holder
)
4217 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
4218 node_duplication_hook_holder
= NULL
;
4219 if (edge_duplication_hook_holder
)
4220 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
4221 edge_duplication_hook_holder
= NULL
;
4222 vec_free (inline_summary_vec
);
4223 inline_edge_summary_vec
.release ();
4224 if (edge_predicate_pool
)
4225 free_alloc_pool (edge_predicate_pool
);
4226 edge_predicate_pool
= 0;