1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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/>. */
20
21 /* Analysis used by the inliner and other passes limiting code size growth.
22
23 We estimate for each function
24 - function body size
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
29 - function frame size
30 For each call
31 - call statement size and time
32
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).
37
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
40
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.
51
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.
58
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.
62
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. */
66
67 #include "config.h"
68 #include "system.h"
69 #include "coretypes.h"
70 #include "tm.h"
71 #include "tree.h"
72 #include "tree-inline.h"
73 #include "langhooks.h"
74 #include "flags.h"
75 #include "cgraph.h"
76 #include "diagnostic.h"
77 #include "gimple-pretty-print.h"
78 #include "params.h"
79 #include "tree-pass.h"
80 #include "coverage.h"
81 #include "ggc.h"
82 #include "tree-flow.h"
83 #include "ipa-prop.h"
84 #include "lto-streamer.h"
85 #include "data-streamer.h"
86 #include "tree-streamer.h"
87 #include "ipa-inline.h"
88 #include "alloc-pool.h"
89 #include "cfgloop.h"
90 #include "cfgloop.h"
91 #include "tree-scalar-evolution.h"
92
93 /* Estimate runtime of function can easilly run into huge numbers with many
94 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
95 integer. For anything larger we use gcov_type. */
96 #define MAX_TIME 500000
97
98 /* Number of bits in integer, but we really want to be stable across different
99 hosts. */
100 #define NUM_CONDITIONS 32
101
102 enum predicate_conditions
103 {
104 predicate_false_condition = 0,
105 predicate_not_inlined_condition = 1,
106 predicate_first_dynamic_condition = 2
107 };
108
109 /* Special condition code we use to represent test that operand is compile time
110 constant. */
111 #define IS_NOT_CONSTANT ERROR_MARK
112 /* Special condition code we use to represent test that operand is not changed
113 across invocation of the function. When operand IS_NOT_CONSTANT it is always
114 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
115 of executions even when they are not compile time constants. */
116 #define CHANGED IDENTIFIER_NODE
117
118 /* Holders of ipa cgraph hooks: */
119 static struct cgraph_node_hook_list *function_insertion_hook_holder;
120 static struct cgraph_node_hook_list *node_removal_hook_holder;
121 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
122 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
123 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
124 static void inline_node_removal_hook (struct cgraph_node *, void *);
125 static void inline_node_duplication_hook (struct cgraph_node *,
126 struct cgraph_node *, void *);
127 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
128 static void inline_edge_duplication_hook (struct cgraph_edge *,
129 struct cgraph_edge *, void *);
130
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 vec<inline_summary_t, va_gc> *inline_summary_vec;
134 vec<inline_edge_summary_t> inline_edge_summary_vec;
135
136 /* Cached node/edge growths. */
137 vec<int> node_growth_cache;
138 vec<edge_growth_cache_entry> edge_growth_cache;
139
140 /* Edge predicates goes here. */
141 static alloc_pool edge_predicate_pool;
142
143 /* Return true predicate (tautology).
144 We represent it by empty list of clauses. */
145
146 static inline struct predicate
true_predicate(void)147 true_predicate (void)
148 {
149 struct predicate p;
150 p.clause[0] = 0;
151 return p;
152 }
153
154
155 /* Return predicate testing single condition number COND. */
156
157 static inline struct predicate
single_cond_predicate(int cond)158 single_cond_predicate (int cond)
159 {
160 struct predicate p;
161 p.clause[0] = 1 << cond;
162 p.clause[1] = 0;
163 return p;
164 }
165
166
167 /* Return false predicate. First clause require false condition. */
168
169 static inline struct predicate
false_predicate(void)170 false_predicate (void)
171 {
172 return single_cond_predicate (predicate_false_condition);
173 }
174
175
176 /* Return true if P is (false). */
177
178 static inline bool
true_predicate_p(struct predicate * p)179 true_predicate_p (struct predicate *p)
180 {
181 return !p->clause[0];
182 }
183
184
185 /* Return true if P is (false). */
186
187 static inline bool
false_predicate_p(struct predicate * p)188 false_predicate_p (struct predicate *p)
189 {
190 if (p->clause[0] == (1 << predicate_false_condition))
191 {
192 gcc_checking_assert (!p->clause[1]
193 && p->clause[0] == 1 << predicate_false_condition);
194 return true;
195 }
196 return false;
197 }
198
199
200 /* Return predicate that is set true when function is not inlined. */
201
202 static inline struct predicate
not_inlined_predicate(void)203 not_inlined_predicate (void)
204 {
205 return single_cond_predicate (predicate_not_inlined_condition);
206 }
207
208 /* Simple description of whether a memory load or a condition refers to a load
209 from an aggregate and if so, how and where from in the aggregate.
210 Individual fields have the same meaning like fields with the same name in
211 struct condition. */
212
213 struct agg_position_info
214 {
215 HOST_WIDE_INT offset;
216 bool agg_contents;
217 bool by_ref;
218 };
219
220 /* Add condition to condition list CONDS. AGGPOS describes whether the used
221 oprand is loaded from an aggregate and where in the aggregate it is. It can
222 be NULL, which means this not a load from an aggregate. */
223
224 static struct predicate
add_condition(struct inline_summary * summary,int operand_num,struct agg_position_info * aggpos,enum tree_code code,tree val)225 add_condition (struct inline_summary *summary, int operand_num,
226 struct agg_position_info *aggpos,
227 enum tree_code code, tree val)
228 {
229 int i;
230 struct condition *c;
231 struct condition new_cond;
232 HOST_WIDE_INT offset;
233 bool agg_contents, by_ref;
234
235 if (aggpos)
236 {
237 offset = aggpos->offset;
238 agg_contents = aggpos->agg_contents;
239 by_ref = aggpos->by_ref;
240 }
241 else
242 {
243 offset = 0;
244 agg_contents = false;
245 by_ref = false;
246 }
247
248 gcc_checking_assert (operand_num >= 0);
249 for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
250 {
251 if (c->operand_num == operand_num
252 && c->code == code
253 && c->val == val
254 && c->agg_contents == agg_contents
255 && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
256 return single_cond_predicate (i + predicate_first_dynamic_condition);
257 }
258 /* Too many conditions. Give up and return constant true. */
259 if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
260 return true_predicate ();
261
262 new_cond.operand_num = operand_num;
263 new_cond.code = code;
264 new_cond.val = val;
265 new_cond.agg_contents = agg_contents;
266 new_cond.by_ref = by_ref;
267 new_cond.offset = offset;
268 vec_safe_push (summary->conds, new_cond);
269 return single_cond_predicate (i + predicate_first_dynamic_condition);
270 }
271
272
273 /* Add clause CLAUSE into the predicate P. */
274
275 static inline void
add_clause(conditions conditions,struct predicate * p,clause_t clause)276 add_clause (conditions conditions, struct predicate *p, clause_t clause)
277 {
278 int i;
279 int i2;
280 int insert_here = -1;
281 int c1, c2;
282
283 /* True clause. */
284 if (!clause)
285 return;
286
287 /* False clause makes the whole predicate false. Kill the other variants. */
288 if (clause == (1 << predicate_false_condition))
289 {
290 p->clause[0] = (1 << predicate_false_condition);
291 p->clause[1] = 0;
292 return;
293 }
294 if (false_predicate_p (p))
295 return;
296
297 /* No one should be sily enough to add false into nontrivial clauses. */
298 gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
299
300 /* Look where to insert the clause. At the same time prune out
301 clauses of P that are implied by the new clause and thus
302 redundant. */
303 for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
304 {
305 p->clause[i2] = p->clause[i];
306
307 if (!p->clause[i])
308 break;
309
310 /* If p->clause[i] implies clause, there is nothing to add. */
311 if ((p->clause[i] & clause) == p->clause[i])
312 {
313 /* We had nothing to add, none of clauses should've become
314 redundant. */
315 gcc_checking_assert (i == i2);
316 return;
317 }
318
319 if (p->clause[i] < clause && insert_here < 0)
320 insert_here = i2;
321
322 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
323 Otherwise the p->clause[i] has to stay. */
324 if ((p->clause[i] & clause) != clause)
325 i2++;
326 }
327
328 /* Look for clauses that are obviously true. I.e.
329 op0 == 5 || op0 != 5. */
330 for (c1 = predicate_first_dynamic_condition; c1 < NUM_CONDITIONS; c1++)
331 {
332 condition *cc1;
333 if (!(clause & (1 << c1)))
334 continue;
335 cc1 = &(*conditions)[c1 - predicate_first_dynamic_condition];
336 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
337 and thus there is no point for looking for them. */
338 if (cc1->code == CHANGED || cc1->code == IS_NOT_CONSTANT)
339 continue;
340 for (c2 = c1 + 1; c2 <= NUM_CONDITIONS; c2++)
341 if (clause & (1 << c2))
342 {
343 condition *cc1 =
344 &(*conditions)[c1 - predicate_first_dynamic_condition];
345 condition *cc2 =
346 &(*conditions)[c2 - predicate_first_dynamic_condition];
347 if (cc1->operand_num == cc2->operand_num
348 && cc1->val == cc2->val
349 && cc2->code != IS_NOT_CONSTANT
350 && cc2->code != CHANGED
351 && cc1->code == invert_tree_comparison
352 (cc2->code,
353 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1->val)))))
354 return;
355 }
356 }
357
358
359 /* We run out of variants. Be conservative in positive direction. */
360 if (i2 == MAX_CLAUSES)
361 return;
362 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
363 p->clause[i2 + 1] = 0;
364 if (insert_here >= 0)
365 for (; i2 > insert_here; i2--)
366 p->clause[i2] = p->clause[i2 - 1];
367 else
368 insert_here = i2;
369 p->clause[insert_here] = clause;
370 }
371
372
373 /* Return P & P2. */
374
375 static struct predicate
and_predicates(conditions conditions,struct predicate * p,struct predicate * p2)376 and_predicates (conditions conditions,
377 struct predicate *p, struct predicate *p2)
378 {
379 struct predicate out = *p;
380 int i;
381
382 /* Avoid busy work. */
383 if (false_predicate_p (p2) || true_predicate_p (p))
384 return *p2;
385 if (false_predicate_p (p) || true_predicate_p (p2))
386 return *p;
387
388 /* See how far predicates match. */
389 for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
390 {
391 gcc_checking_assert (i < MAX_CLAUSES);
392 }
393
394 /* Combine the predicates rest. */
395 for (; p2->clause[i]; i++)
396 {
397 gcc_checking_assert (i < MAX_CLAUSES);
398 add_clause (conditions, &out, p2->clause[i]);
399 }
400 return out;
401 }
402
403
404 /* Return true if predicates are obviously equal. */
405
406 static inline bool
predicates_equal_p(struct predicate * p,struct predicate * p2)407 predicates_equal_p (struct predicate *p, struct predicate *p2)
408 {
409 int i;
410 for (i = 0; p->clause[i]; i++)
411 {
412 gcc_checking_assert (i < MAX_CLAUSES);
413 gcc_checking_assert (p->clause[i] > p->clause[i + 1]);
414 gcc_checking_assert (!p2->clause[i]
415 || p2->clause[i] > p2->clause[i + 1]);
416 if (p->clause[i] != p2->clause[i])
417 return false;
418 }
419 return !p2->clause[i];
420 }
421
422
423 /* Return P | P2. */
424
425 static struct predicate
or_predicates(conditions conditions,struct predicate * p,struct predicate * p2)426 or_predicates (conditions conditions,
427 struct predicate *p, struct predicate *p2)
428 {
429 struct predicate out = true_predicate ();
430 int i, j;
431
432 /* Avoid busy work. */
433 if (false_predicate_p (p2) || true_predicate_p (p))
434 return *p;
435 if (false_predicate_p (p) || true_predicate_p (p2))
436 return *p2;
437 if (predicates_equal_p (p, p2))
438 return *p;
439
440 /* OK, combine the predicates. */
441 for (i = 0; p->clause[i]; i++)
442 for (j = 0; p2->clause[j]; j++)
443 {
444 gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
445 add_clause (conditions, &out, p->clause[i] | p2->clause[j]);
446 }
447 return out;
448 }
449
450
451 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
452 if predicate P is known to be false. */
453
454 static bool
evaluate_predicate(struct predicate * p,clause_t possible_truths)455 evaluate_predicate (struct predicate *p, clause_t possible_truths)
456 {
457 int i;
458
459 /* True remains true. */
460 if (true_predicate_p (p))
461 return true;
462
463 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
464
465 /* See if we can find clause we can disprove. */
466 for (i = 0; p->clause[i]; i++)
467 {
468 gcc_checking_assert (i < MAX_CLAUSES);
469 if (!(p->clause[i] & possible_truths))
470 return false;
471 }
472 return true;
473 }
474
475 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
476 instruction will be recomputed per invocation of the inlined call. */
477
478 static int
predicate_probability(conditions conds,struct predicate * p,clause_t possible_truths,vec<inline_param_summary_t> inline_param_summary)479 predicate_probability (conditions conds,
480 struct predicate *p, clause_t possible_truths,
481 vec<inline_param_summary_t> inline_param_summary)
482 {
483 int i;
484 int combined_prob = REG_BR_PROB_BASE;
485
486 /* True remains true. */
487 if (true_predicate_p (p))
488 return REG_BR_PROB_BASE;
489
490 if (false_predicate_p (p))
491 return 0;
492
493 gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
494
495 /* See if we can find clause we can disprove. */
496 for (i = 0; p->clause[i]; i++)
497 {
498 gcc_checking_assert (i < MAX_CLAUSES);
499 if (!(p->clause[i] & possible_truths))
500 return 0;
501 else
502 {
503 int this_prob = 0;
504 int i2;
505 if (!inline_param_summary.exists ())
506 return REG_BR_PROB_BASE;
507 for (i2 = 0; i2 < NUM_CONDITIONS; i2++)
508 if ((p->clause[i] & possible_truths) & (1 << i2))
509 {
510 if (i2 >= predicate_first_dynamic_condition)
511 {
512 condition *c =
513 &(*conds)[i2 - predicate_first_dynamic_condition];
514 if (c->code == CHANGED
515 && (c->operand_num <
516 (int) inline_param_summary.length ()))
517 {
518 int iprob =
519 inline_param_summary[c->operand_num].change_prob;
520 this_prob = MAX (this_prob, iprob);
521 }
522 else
523 this_prob = REG_BR_PROB_BASE;
524 }
525 else
526 this_prob = REG_BR_PROB_BASE;
527 }
528 combined_prob = MIN (this_prob, combined_prob);
529 if (!combined_prob)
530 return 0;
531 }
532 }
533 return combined_prob;
534 }
535
536
537 /* Dump conditional COND. */
538
539 static void
dump_condition(FILE * f,conditions conditions,int cond)540 dump_condition (FILE *f, conditions conditions, int cond)
541 {
542 condition *c;
543 if (cond == predicate_false_condition)
544 fprintf (f, "false");
545 else if (cond == predicate_not_inlined_condition)
546 fprintf (f, "not inlined");
547 else
548 {
549 c = &(*conditions)[cond - predicate_first_dynamic_condition];
550 fprintf (f, "op%i", c->operand_num);
551 if (c->agg_contents)
552 fprintf (f, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
553 c->by_ref ? "ref " : "", c->offset);
554 if (c->code == IS_NOT_CONSTANT)
555 {
556 fprintf (f, " not constant");
557 return;
558 }
559 if (c->code == CHANGED)
560 {
561 fprintf (f, " changed");
562 return;
563 }
564 fprintf (f, " %s ", op_symbol_code (c->code));
565 print_generic_expr (f, c->val, 1);
566 }
567 }
568
569
570 /* Dump clause CLAUSE. */
571
572 static void
dump_clause(FILE * f,conditions conds,clause_t clause)573 dump_clause (FILE *f, conditions conds, clause_t clause)
574 {
575 int i;
576 bool found = false;
577 fprintf (f, "(");
578 if (!clause)
579 fprintf (f, "true");
580 for (i = 0; i < NUM_CONDITIONS; i++)
581 if (clause & (1 << i))
582 {
583 if (found)
584 fprintf (f, " || ");
585 found = true;
586 dump_condition (f, conds, i);
587 }
588 fprintf (f, ")");
589 }
590
591
592 /* Dump predicate PREDICATE. */
593
594 static void
dump_predicate(FILE * f,conditions conds,struct predicate * pred)595 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
596 {
597 int i;
598 if (true_predicate_p (pred))
599 dump_clause (f, conds, 0);
600 else
601 for (i = 0; pred->clause[i]; i++)
602 {
603 if (i)
604 fprintf (f, " && ");
605 dump_clause (f, conds, pred->clause[i]);
606 }
607 fprintf (f, "\n");
608 }
609
610
611 /* Dump inline hints. */
612 void
dump_inline_hints(FILE * f,inline_hints hints)613 dump_inline_hints (FILE *f, inline_hints hints)
614 {
615 if (!hints)
616 return;
617 fprintf (f, "inline hints:");
618 if (hints & INLINE_HINT_indirect_call)
619 {
620 hints &= ~INLINE_HINT_indirect_call;
621 fprintf (f, " indirect_call");
622 }
623 if (hints & INLINE_HINT_loop_iterations)
624 {
625 hints &= ~INLINE_HINT_loop_iterations;
626 fprintf (f, " loop_iterations");
627 }
628 if (hints & INLINE_HINT_loop_stride)
629 {
630 hints &= ~INLINE_HINT_loop_stride;
631 fprintf (f, " loop_stride");
632 }
633 if (hints & INLINE_HINT_same_scc)
634 {
635 hints &= ~INLINE_HINT_same_scc;
636 fprintf (f, " same_scc");
637 }
638 if (hints & INLINE_HINT_in_scc)
639 {
640 hints &= ~INLINE_HINT_in_scc;
641 fprintf (f, " in_scc");
642 }
643 if (hints & INLINE_HINT_cross_module)
644 {
645 hints &= ~INLINE_HINT_cross_module;
646 fprintf (f, " cross_module");
647 }
648 if (hints & INLINE_HINT_declared_inline)
649 {
650 hints &= ~INLINE_HINT_declared_inline;
651 fprintf (f, " declared_inline");
652 }
653 if (hints & INLINE_HINT_array_index)
654 {
655 hints &= ~INLINE_HINT_array_index;
656 fprintf (f, " array_index");
657 }
658 gcc_assert (!hints);
659 }
660
661
662 /* Record SIZE and TIME under condition PRED into the inline summary. */
663
664 static void
account_size_time(struct inline_summary * summary,int size,int time,struct predicate * pred)665 account_size_time (struct inline_summary *summary, int size, int time,
666 struct predicate *pred)
667 {
668 size_time_entry *e;
669 bool found = false;
670 int i;
671
672 if (false_predicate_p (pred))
673 return;
674
675 /* We need to create initial empty unconitional clause, but otherwie
676 we don't need to account empty times and sizes. */
677 if (!size && !time && summary->entry)
678 return;
679
680 /* Watch overflow that might result from insane profiles. */
681 if (time > MAX_TIME * INLINE_TIME_SCALE)
682 time = MAX_TIME * INLINE_TIME_SCALE;
683 gcc_assert (time >= 0);
684
685 for (i = 0; vec_safe_iterate (summary->entry, i, &e); i++)
686 if (predicates_equal_p (&e->predicate, pred))
687 {
688 found = true;
689 break;
690 }
691 if (i == 256)
692 {
693 i = 0;
694 found = true;
695 e = &(*summary->entry)[0];
696 gcc_assert (!e->predicate.clause[0]);
697 if (dump_file && (dump_flags & TDF_DETAILS))
698 fprintf (dump_file,
699 "\t\tReached limit on number of entries, "
700 "ignoring the predicate.");
701 }
702 if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
703 {
704 fprintf (dump_file,
705 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
706 ((double) size) / INLINE_SIZE_SCALE,
707 ((double) time) / INLINE_TIME_SCALE, found ? "" : "new ");
708 dump_predicate (dump_file, summary->conds, pred);
709 }
710 if (!found)
711 {
712 struct size_time_entry new_entry;
713 new_entry.size = size;
714 new_entry.time = time;
715 new_entry.predicate = *pred;
716 vec_safe_push (summary->entry, new_entry);
717 }
718 else
719 {
720 e->size += size;
721 e->time += time;
722 if (e->time > MAX_TIME * INLINE_TIME_SCALE)
723 e->time = MAX_TIME * INLINE_TIME_SCALE;
724 }
725 }
726
727 /* Set predicate for edge E. */
728
729 static void
edge_set_predicate(struct cgraph_edge * e,struct predicate * predicate)730 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
731 {
732 struct inline_edge_summary *es = inline_edge_summary (e);
733 if (predicate && !true_predicate_p (predicate))
734 {
735 if (!es->predicate)
736 es->predicate = (struct predicate *) pool_alloc (edge_predicate_pool);
737 *es->predicate = *predicate;
738 }
739 else
740 {
741 if (es->predicate)
742 pool_free (edge_predicate_pool, es->predicate);
743 es->predicate = NULL;
744 }
745 }
746
747 /* Set predicate for hint *P. */
748
749 static void
set_hint_predicate(struct predicate ** p,struct predicate new_predicate)750 set_hint_predicate (struct predicate **p, struct predicate new_predicate)
751 {
752 if (false_predicate_p (&new_predicate) || true_predicate_p (&new_predicate))
753 {
754 if (*p)
755 pool_free (edge_predicate_pool, *p);
756 *p = NULL;
757 }
758 else
759 {
760 if (!*p)
761 *p = (struct predicate *) pool_alloc (edge_predicate_pool);
762 **p = new_predicate;
763 }
764 }
765
766
767 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
768 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
769 Return clause of possible truths. When INLINE_P is true, assume that we are
770 inlining.
771
772 ERROR_MARK means compile time invariant. */
773
774 static clause_t
evaluate_conditions_for_known_args(struct cgraph_node * node,bool inline_p,vec<tree> known_vals,vec<ipa_agg_jump_function_p> known_aggs)775 evaluate_conditions_for_known_args (struct cgraph_node *node,
776 bool inline_p,
777 vec<tree> known_vals,
778 vec<ipa_agg_jump_function_p>
779 known_aggs)
780 {
781 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
782 struct inline_summary *info = inline_summary (node);
783 int i;
784 struct condition *c;
785
786 for (i = 0; vec_safe_iterate (info->conds, i, &c); i++)
787 {
788 tree val;
789 tree res;
790
791 /* We allow call stmt to have fewer arguments than the callee function
792 (especially for K&R style programs). So bound check here (we assume
793 known_aggs vector, if non-NULL, has the same length as
794 known_vals). */
795 gcc_checking_assert (!known_aggs.exists ()
796 || (known_vals.length () == known_aggs.length ()));
797 if (c->operand_num >= (int) known_vals.length ())
798 {
799 clause |= 1 << (i + predicate_first_dynamic_condition);
800 continue;
801 }
802
803 if (c->agg_contents)
804 {
805 struct ipa_agg_jump_function *agg;
806
807 if (c->code == CHANGED
808 && !c->by_ref
809 && (known_vals[c->operand_num] == error_mark_node))
810 continue;
811
812 if (known_aggs.exists ())
813 {
814 agg = known_aggs[c->operand_num];
815 val = ipa_find_agg_cst_for_param (agg, c->offset, c->by_ref);
816 }
817 else
818 val = NULL_TREE;
819 }
820 else
821 {
822 val = known_vals[c->operand_num];
823 if (val == error_mark_node && c->code != CHANGED)
824 val = NULL_TREE;
825 }
826
827 if (!val)
828 {
829 clause |= 1 << (i + predicate_first_dynamic_condition);
830 continue;
831 }
832 if (c->code == IS_NOT_CONSTANT || c->code == CHANGED)
833 continue;
834
835 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c->val)),
836 TYPE_SIZE (TREE_TYPE (val)), 0))
837 {
838 val = fold_unary (VIEW_CONVERT_EXPR, TREE_TYPE (c->val), val);
839
840 res = val
841 ? fold_binary_to_constant (c->code, boolean_type_node, val, c->val)
842 : NULL;
843
844 if (res && integer_zerop (res))
845 continue;
846 }
847 clause |= 1 << (i + predicate_first_dynamic_condition);
848 }
849 return clause;
850 }
851
852
853 /* Work out what conditions might be true at invocation of E. */
854
855 static void
evaluate_properties_for_edge(struct cgraph_edge * e,bool inline_p,clause_t * clause_ptr,vec<tree> * known_vals_ptr,vec<tree> * known_binfos_ptr,vec<ipa_agg_jump_function_p> * known_aggs_ptr)856 evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
857 clause_t *clause_ptr,
858 vec<tree> *known_vals_ptr,
859 vec<tree> *known_binfos_ptr,
860 vec<ipa_agg_jump_function_p> *known_aggs_ptr)
861 {
862 struct cgraph_node *callee =
863 cgraph_function_or_thunk_node (e->callee, NULL);
864 struct inline_summary *info = inline_summary (callee);
865 vec<tree> known_vals = vNULL;
866 vec<ipa_agg_jump_function_p> known_aggs = vNULL;
867
868 if (clause_ptr)
869 *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition;
870 if (known_vals_ptr)
871 known_vals_ptr->create (0);
872 if (known_binfos_ptr)
873 known_binfos_ptr->create (0);
874
875 if (ipa_node_params_vector.exists ()
876 && !e->call_stmt_cannot_inline_p
877 && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
878 {
879 struct ipa_node_params *parms_info;
880 struct ipa_edge_args *args = IPA_EDGE_REF (e);
881 struct inline_edge_summary *es = inline_edge_summary (e);
882 int i, count = ipa_get_cs_argument_count (args);
883
884 if (e->caller->global.inlined_to)
885 parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
886 else
887 parms_info = IPA_NODE_REF (e->caller);
888
889 if (count && (info->conds || known_vals_ptr))
890 known_vals.safe_grow_cleared (count);
891 if (count && (info->conds || known_aggs_ptr))
892 known_aggs.safe_grow_cleared (count);
893 if (count && known_binfos_ptr)
894 known_binfos_ptr->safe_grow_cleared (count);
895
896 for (i = 0; i < count; i++)
897 {
898 struct ipa_jump_func *jf = ipa_get_ith_jump_func (args, i);
899 tree cst = ipa_value_from_jfunc (parms_info, jf);
900 if (cst)
901 {
902 if (known_vals.exists () && TREE_CODE (cst) != TREE_BINFO)
903 known_vals[i] = cst;
904 else if (known_binfos_ptr != NULL
905 && TREE_CODE (cst) == TREE_BINFO)
906 (*known_binfos_ptr)[i] = cst;
907 }
908 else if (inline_p && !es->param[i].change_prob)
909 known_vals[i] = error_mark_node;
910 /* TODO: When IPA-CP starts propagating and merging aggregate jump
911 functions, use its knowledge of the caller too, just like the
912 scalar case above. */
913 known_aggs[i] = &jf->agg;
914 }
915 }
916
917 if (clause_ptr)
918 *clause_ptr = evaluate_conditions_for_known_args (callee, inline_p,
919 known_vals, known_aggs);
920
921 if (known_vals_ptr)
922 *known_vals_ptr = known_vals;
923 else
924 known_vals.release ();
925
926 if (known_aggs_ptr)
927 *known_aggs_ptr = known_aggs;
928 else
929 known_aggs.release ();
930 }
931
932
933 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
934
935 static void
inline_summary_alloc(void)936 inline_summary_alloc (void)
937 {
938 if (!node_removal_hook_holder)
939 node_removal_hook_holder =
940 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
941 if (!edge_removal_hook_holder)
942 edge_removal_hook_holder =
943 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
944 if (!node_duplication_hook_holder)
945 node_duplication_hook_holder =
946 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
947 if (!edge_duplication_hook_holder)
948 edge_duplication_hook_holder =
949 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
950
951 if (vec_safe_length (inline_summary_vec) <= (unsigned) cgraph_max_uid)
952 vec_safe_grow_cleared (inline_summary_vec, cgraph_max_uid + 1);
953 if (inline_edge_summary_vec.length () <= (unsigned) cgraph_edge_max_uid)
954 inline_edge_summary_vec.safe_grow_cleared (cgraph_edge_max_uid + 1);
955 if (!edge_predicate_pool)
956 edge_predicate_pool = create_alloc_pool ("edge predicates",
957 sizeof (struct predicate), 10);
958 }
959
960 /* We are called multiple time for given function; clear
961 data from previous run so they are not cumulated. */
962
963 static void
reset_inline_edge_summary(struct cgraph_edge * e)964 reset_inline_edge_summary (struct cgraph_edge *e)
965 {
966 if (e->uid < (int) inline_edge_summary_vec.length ())
967 {
968 struct inline_edge_summary *es = inline_edge_summary (e);
969
970 es->call_stmt_size = es->call_stmt_time = 0;
971 if (es->predicate)
972 pool_free (edge_predicate_pool, es->predicate);
973 es->predicate = NULL;
974 es->param.release ();
975 }
976 }
977
978 /* We are called multiple time for given function; clear
979 data from previous run so they are not cumulated. */
980
981 static void
reset_inline_summary(struct cgraph_node * node)982 reset_inline_summary (struct cgraph_node *node)
983 {
984 struct inline_summary *info = inline_summary (node);
985 struct cgraph_edge *e;
986
987 info->self_size = info->self_time = 0;
988 info->estimated_stack_size = 0;
989 info->estimated_self_stack_size = 0;
990 info->stack_frame_offset = 0;
991 info->size = 0;
992 info->time = 0;
993 info->growth = 0;
994 info->scc_no = 0;
995 if (info->loop_iterations)
996 {
997 pool_free (edge_predicate_pool, info->loop_iterations);
998 info->loop_iterations = NULL;
999 }
1000 if (info->loop_stride)
1001 {
1002 pool_free (edge_predicate_pool, info->loop_stride);
1003 info->loop_stride = NULL;
1004 }
1005 if (info->array_index)
1006 {
1007 pool_free (edge_predicate_pool, info->array_index);
1008 info->array_index = NULL;
1009 }
1010 vec_free (info->conds);
1011 vec_free (info->entry);
1012 for (e = node->callees; e; e = e->next_callee)
1013 reset_inline_edge_summary (e);
1014 for (e = node->indirect_calls; e; e = e->next_callee)
1015 reset_inline_edge_summary (e);
1016 }
1017
1018 /* Hook that is called by cgraph.c when a node is removed. */
1019
1020 static void
inline_node_removal_hook(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)1021 inline_node_removal_hook (struct cgraph_node *node,
1022 void *data ATTRIBUTE_UNUSED)
1023 {
1024 struct inline_summary *info;
1025 if (vec_safe_length (inline_summary_vec) <= (unsigned) node->uid)
1026 return;
1027 info = inline_summary (node);
1028 reset_inline_summary (node);
1029 memset (info, 0, sizeof (inline_summary_t));
1030 }
1031
1032 /* Remap predicate P of former function to be predicate of duplicated functoin.
1033 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1034 INFO is inline summary of the duplicated node. */
1035
1036 static struct predicate
remap_predicate_after_duplication(struct predicate * p,clause_t possible_truths,struct inline_summary * info)1037 remap_predicate_after_duplication (struct predicate *p,
1038 clause_t possible_truths,
1039 struct inline_summary *info)
1040 {
1041 struct predicate new_predicate = true_predicate ();
1042 int j;
1043 for (j = 0; p->clause[j]; j++)
1044 if (!(possible_truths & p->clause[j]))
1045 {
1046 new_predicate = false_predicate ();
1047 break;
1048 }
1049 else
1050 add_clause (info->conds, &new_predicate,
1051 possible_truths & p->clause[j]);
1052 return new_predicate;
1053 }
1054
1055 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1056 Additionally care about allocating new memory slot for updated predicate
1057 and set it to NULL when it becomes true or false (and thus uninteresting).
1058 */
1059
1060 static void
remap_hint_predicate_after_duplication(struct predicate ** p,clause_t possible_truths,struct inline_summary * info)1061 remap_hint_predicate_after_duplication (struct predicate **p,
1062 clause_t possible_truths,
1063 struct inline_summary *info)
1064 {
1065 struct predicate new_predicate;
1066
1067 if (!*p)
1068 return;
1069
1070 new_predicate = remap_predicate_after_duplication (*p,
1071 possible_truths, info);
1072 /* We do not want to free previous predicate; it is used by node origin. */
1073 *p = NULL;
1074 set_hint_predicate (p, new_predicate);
1075 }
1076
1077
1078 /* Hook that is called by cgraph.c when a node is duplicated. */
1079
1080 static void
inline_node_duplication_hook(struct cgraph_node * src,struct cgraph_node * dst,ATTRIBUTE_UNUSED void * data)1081 inline_node_duplication_hook (struct cgraph_node *src,
1082 struct cgraph_node *dst,
1083 ATTRIBUTE_UNUSED void *data)
1084 {
1085 struct inline_summary *info;
1086 inline_summary_alloc ();
1087 info = inline_summary (dst);
1088 memcpy (info, inline_summary (src), sizeof (struct inline_summary));
1089 /* TODO: as an optimization, we may avoid copying conditions
1090 that are known to be false or true. */
1091 info->conds = vec_safe_copy (info->conds);
1092
1093 /* When there are any replacements in the function body, see if we can figure
1094 out that something was optimized out. */
1095 if (ipa_node_params_vector.exists () && dst->clone.tree_map)
1096 {
1097 vec<size_time_entry, va_gc> *entry = info->entry;
1098 /* Use SRC parm info since it may not be copied yet. */
1099 struct ipa_node_params *parms_info = IPA_NODE_REF (src);
1100 vec<tree> known_vals = vNULL;
1101 int count = ipa_get_param_count (parms_info);
1102 int i, j;
1103 clause_t possible_truths;
1104 struct predicate true_pred = true_predicate ();
1105 size_time_entry *e;
1106 int optimized_out_size = 0;
1107 bool inlined_to_p = false;
1108 struct cgraph_edge *edge;
1109
1110 info->entry = 0;
1111 known_vals.safe_grow_cleared (count);
1112 for (i = 0; i < count; i++)
1113 {
1114 tree t = ipa_get_param (parms_info, i);
1115 struct ipa_replace_map *r;
1116
1117 for (j = 0; vec_safe_iterate (dst->clone.tree_map, j, &r); j++)
1118 {
1119 if (r->old_tree == t && r->replace_p && !r->ref_p)
1120 {
1121 known_vals[i] = r->new_tree;
1122 break;
1123 }
1124 }
1125 }
1126 possible_truths = evaluate_conditions_for_known_args (dst, false,
1127 known_vals,
1128 vNULL);
1129 known_vals.release ();
1130
1131 account_size_time (info, 0, 0, &true_pred);
1132
1133 /* Remap size_time vectors.
1134 Simplify the predicate by prunning out alternatives that are known
1135 to be false.
1136 TODO: as on optimization, we can also eliminate conditions known
1137 to be true. */
1138 for (i = 0; vec_safe_iterate (entry, i, &e); i++)
1139 {
1140 struct predicate new_predicate;
1141 new_predicate = remap_predicate_after_duplication (&e->predicate,
1142 possible_truths,
1143 info);
1144 if (false_predicate_p (&new_predicate))
1145 optimized_out_size += e->size;
1146 else
1147 account_size_time (info, e->size, e->time, &new_predicate);
1148 }
1149
1150 /* Remap edge predicates with the same simplification as above.
1151 Also copy constantness arrays. */
1152 for (edge = dst->callees; edge; edge = edge->next_callee)
1153 {
1154 struct predicate new_predicate;
1155 struct inline_edge_summary *es = inline_edge_summary (edge);
1156
1157 if (!edge->inline_failed)
1158 inlined_to_p = true;
1159 if (!es->predicate)
1160 continue;
1161 new_predicate = remap_predicate_after_duplication (es->predicate,
1162 possible_truths,
1163 info);
1164 if (false_predicate_p (&new_predicate)
1165 && !false_predicate_p (es->predicate))
1166 {
1167 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
1168 edge->frequency = 0;
1169 }
1170 edge_set_predicate (edge, &new_predicate);
1171 }
1172
1173 /* Remap indirect edge predicates with the same simplificaiton as above.
1174 Also copy constantness arrays. */
1175 for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
1176 {
1177 struct predicate new_predicate;
1178 struct inline_edge_summary *es = inline_edge_summary (edge);
1179
1180 gcc_checking_assert (edge->inline_failed);
1181 if (!es->predicate)
1182 continue;
1183 new_predicate = remap_predicate_after_duplication (es->predicate,
1184 possible_truths,
1185 info);
1186 if (false_predicate_p (&new_predicate)
1187 && !false_predicate_p (es->predicate))
1188 {
1189 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
1190 edge->frequency = 0;
1191 }
1192 edge_set_predicate (edge, &new_predicate);
1193 }
1194 remap_hint_predicate_after_duplication (&info->loop_iterations,
1195 possible_truths, info);
1196 remap_hint_predicate_after_duplication (&info->loop_stride,
1197 possible_truths, info);
1198 remap_hint_predicate_after_duplication (&info->array_index,
1199 possible_truths, info);
1200
1201 /* If inliner or someone after inliner will ever start producing
1202 non-trivial clones, we will get trouble with lack of information
1203 about updating self sizes, because size vectors already contains
1204 sizes of the calees. */
1205 gcc_assert (!inlined_to_p || !optimized_out_size);
1206 }
1207 else
1208 {
1209 info->entry = vec_safe_copy (info->entry);
1210 if (info->loop_iterations)
1211 {
1212 predicate p = *info->loop_iterations;
1213 info->loop_iterations = NULL;
1214 set_hint_predicate (&info->loop_iterations, p);
1215 }
1216 if (info->loop_stride)
1217 {
1218 predicate p = *info->loop_stride;
1219 info->loop_stride = NULL;
1220 set_hint_predicate (&info->loop_stride, p);
1221 }
1222 if (info->array_index)
1223 {
1224 predicate p = *info->array_index;
1225 info->array_index = NULL;
1226 set_hint_predicate (&info->array_index, p);
1227 }
1228 }
1229 inline_update_overall_summary (dst);
1230 }
1231
1232
1233 /* Hook that is called by cgraph.c when a node is duplicated. */
1234
1235 static void
inline_edge_duplication_hook(struct cgraph_edge * src,struct cgraph_edge * dst,ATTRIBUTE_UNUSED void * data)1236 inline_edge_duplication_hook (struct cgraph_edge *src,
1237 struct cgraph_edge *dst,
1238 ATTRIBUTE_UNUSED void *data)
1239 {
1240 struct inline_edge_summary *info;
1241 struct inline_edge_summary *srcinfo;
1242 inline_summary_alloc ();
1243 info = inline_edge_summary (dst);
1244 srcinfo = inline_edge_summary (src);
1245 memcpy (info, srcinfo, sizeof (struct inline_edge_summary));
1246 info->predicate = NULL;
1247 edge_set_predicate (dst, srcinfo->predicate);
1248 info->param = srcinfo->param.copy ();
1249 }
1250
1251
1252 /* Keep edge cache consistent across edge removal. */
1253
1254 static void
inline_edge_removal_hook(struct cgraph_edge * edge,void * data ATTRIBUTE_UNUSED)1255 inline_edge_removal_hook (struct cgraph_edge *edge,
1256 void *data ATTRIBUTE_UNUSED)
1257 {
1258 if (edge_growth_cache.exists ())
1259 reset_edge_growth_cache (edge);
1260 reset_inline_edge_summary (edge);
1261 }
1262
1263
1264 /* Initialize growth caches. */
1265
1266 void
initialize_growth_caches(void)1267 initialize_growth_caches (void)
1268 {
1269 if (cgraph_edge_max_uid)
1270 edge_growth_cache.safe_grow_cleared (cgraph_edge_max_uid);
1271 if (cgraph_max_uid)
1272 node_growth_cache.safe_grow_cleared (cgraph_max_uid);
1273 }
1274
1275
1276 /* Free growth caches. */
1277
1278 void
free_growth_caches(void)1279 free_growth_caches (void)
1280 {
1281 edge_growth_cache.release ();
1282 node_growth_cache.release ();
1283 }
1284
1285
1286 /* Dump edge summaries associated to NODE and recursively to all clones.
1287 Indent by INDENT. */
1288
1289 static void
dump_inline_edge_summary(FILE * f,int indent,struct cgraph_node * node,struct inline_summary * info)1290 dump_inline_edge_summary (FILE *f, int indent, struct cgraph_node *node,
1291 struct inline_summary *info)
1292 {
1293 struct cgraph_edge *edge;
1294 for (edge = node->callees; edge; edge = edge->next_callee)
1295 {
1296 struct inline_edge_summary *es = inline_edge_summary (edge);
1297 struct cgraph_node *callee =
1298 cgraph_function_or_thunk_node (edge->callee, NULL);
1299 int i;
1300
1301 fprintf (f,
1302 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1303 " time: %2i callee size:%2i stack:%2i",
1304 indent, "", cgraph_node_name (callee), callee->uid,
1305 !edge->inline_failed
1306 ? "inlined" : cgraph_inline_failed_string (edge-> inline_failed),
1307 indent, "", es->loop_depth, edge->frequency,
1308 es->call_stmt_size, es->call_stmt_time,
1309 (int) inline_summary (callee)->size / INLINE_SIZE_SCALE,
1310 (int) inline_summary (callee)->estimated_stack_size);
1311
1312 if (es->predicate)
1313 {
1314 fprintf (f, " predicate: ");
1315 dump_predicate (f, info->conds, es->predicate);
1316 }
1317 else
1318 fprintf (f, "\n");
1319 if (es->param.exists ())
1320 for (i = 0; i < (int) es->param.length (); i++)
1321 {
1322 int prob = es->param[i].change_prob;
1323
1324 if (!prob)
1325 fprintf (f, "%*s op%i is compile time invariant\n",
1326 indent + 2, "", i);
1327 else if (prob != REG_BR_PROB_BASE)
1328 fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i,
1329 prob * 100.0 / REG_BR_PROB_BASE);
1330 }
1331 if (!edge->inline_failed)
1332 {
1333 fprintf (f, "%*sStack frame offset %i, callee self size %i,"
1334 " callee size %i\n",
1335 indent + 2, "",
1336 (int) inline_summary (callee)->stack_frame_offset,
1337 (int) inline_summary (callee)->estimated_self_stack_size,
1338 (int) inline_summary (callee)->estimated_stack_size);
1339 dump_inline_edge_summary (f, indent + 2, callee, info);
1340 }
1341 }
1342 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1343 {
1344 struct inline_edge_summary *es = inline_edge_summary (edge);
1345 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1346 " time: %2i",
1347 indent, "",
1348 es->loop_depth,
1349 edge->frequency, es->call_stmt_size, es->call_stmt_time);
1350 if (es->predicate)
1351 {
1352 fprintf (f, "predicate: ");
1353 dump_predicate (f, info->conds, es->predicate);
1354 }
1355 else
1356 fprintf (f, "\n");
1357 }
1358 }
1359
1360
1361 void
dump_inline_summary(FILE * f,struct cgraph_node * node)1362 dump_inline_summary (FILE *f, struct cgraph_node *node)
1363 {
1364 if (node->analyzed)
1365 {
1366 struct inline_summary *s = inline_summary (node);
1367 size_time_entry *e;
1368 int i;
1369 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
1370 node->uid);
1371 if (DECL_DISREGARD_INLINE_LIMITS (node->symbol.decl))
1372 fprintf (f, " always_inline");
1373 if (s->inlinable)
1374 fprintf (f, " inlinable");
1375 fprintf (f, "\n self time: %i\n", s->self_time);
1376 fprintf (f, " global time: %i\n", s->time);
1377 fprintf (f, " self size: %i\n", s->self_size);
1378 fprintf (f, " global size: %i\n", s->size);
1379 fprintf (f, " self stack: %i\n",
1380 (int) s->estimated_self_stack_size);
1381 fprintf (f, " global stack: %i\n", (int) s->estimated_stack_size);
1382 if (s->growth)
1383 fprintf (f, " estimated growth:%i\n", (int) s->growth);
1384 if (s->scc_no)
1385 fprintf (f, " In SCC: %i\n", (int) s->scc_no);
1386 for (i = 0; vec_safe_iterate (s->entry, i, &e); i++)
1387 {
1388 fprintf (f, " size:%f, time:%f, predicate:",
1389 (double) e->size / INLINE_SIZE_SCALE,
1390 (double) e->time / INLINE_TIME_SCALE);
1391 dump_predicate (f, s->conds, &e->predicate);
1392 }
1393 if (s->loop_iterations)
1394 {
1395 fprintf (f, " loop iterations:");
1396 dump_predicate (f, s->conds, s->loop_iterations);
1397 }
1398 if (s->loop_stride)
1399 {
1400 fprintf (f, " loop stride:");
1401 dump_predicate (f, s->conds, s->loop_stride);
1402 }
1403 if (s->array_index)
1404 {
1405 fprintf (f, " array index:");
1406 dump_predicate (f, s->conds, s->array_index);
1407 }
1408 fprintf (f, " calls:\n");
1409 dump_inline_edge_summary (f, 4, node, s);
1410 fprintf (f, "\n");
1411 }
1412 }
1413
1414 DEBUG_FUNCTION void
debug_inline_summary(struct cgraph_node * node)1415 debug_inline_summary (struct cgraph_node *node)
1416 {
1417 dump_inline_summary (stderr, node);
1418 }
1419
1420 void
dump_inline_summaries(FILE * f)1421 dump_inline_summaries (FILE *f)
1422 {
1423 struct cgraph_node *node;
1424
1425 FOR_EACH_DEFINED_FUNCTION (node)
1426 if (!node->global.inlined_to)
1427 dump_inline_summary (f, node);
1428 }
1429
1430 /* Give initial reasons why inlining would fail on EDGE. This gets either
1431 nullified or usually overwritten by more precise reasons later. */
1432
1433 void
initialize_inline_failed(struct cgraph_edge * e)1434 initialize_inline_failed (struct cgraph_edge *e)
1435 {
1436 struct cgraph_node *callee = e->callee;
1437
1438 if (e->indirect_unknown_callee)
1439 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1440 else if (!callee->analyzed)
1441 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1442 else if (callee->local.redefined_extern_inline)
1443 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1444 else if (e->call_stmt_cannot_inline_p)
1445 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1446 else
1447 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1448 }
1449
1450 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1451 boolean variable pointed to by DATA. */
1452
1453 static bool
mark_modified(ao_ref * ao ATTRIBUTE_UNUSED,tree vdef ATTRIBUTE_UNUSED,void * data)1454 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
1455 void *data)
1456 {
1457 bool *b = (bool *) data;
1458 *b = true;
1459 return true;
1460 }
1461
1462 /* If OP refers to value of function parameter, return the corresponding
1463 parameter. */
1464
1465 static tree
unmodified_parm_1(gimple stmt,tree op)1466 unmodified_parm_1 (gimple stmt, tree op)
1467 {
1468 /* SSA_NAME referring to parm default def? */
1469 if (TREE_CODE (op) == SSA_NAME
1470 && SSA_NAME_IS_DEFAULT_DEF (op)
1471 && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL)
1472 return SSA_NAME_VAR (op);
1473 /* Non-SSA parm reference? */
1474 if (TREE_CODE (op) == PARM_DECL)
1475 {
1476 bool modified = false;
1477
1478 ao_ref refd;
1479 ao_ref_init (&refd, op);
1480 walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
1481 NULL);
1482 if (!modified)
1483 return op;
1484 }
1485 return NULL_TREE;
1486 }
1487
1488 /* If OP refers to value of function parameter, return the corresponding
1489 parameter. Also traverse chains of SSA register assignments. */
1490
1491 static tree
unmodified_parm(gimple stmt,tree op)1492 unmodified_parm (gimple stmt, tree op)
1493 {
1494 tree res = unmodified_parm_1 (stmt, op);
1495 if (res)
1496 return res;
1497
1498 if (TREE_CODE (op) == SSA_NAME
1499 && !SSA_NAME_IS_DEFAULT_DEF (op)
1500 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1501 return unmodified_parm (SSA_NAME_DEF_STMT (op),
1502 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)));
1503 return NULL_TREE;
1504 }
1505
1506 /* If OP refers to a value of a function parameter or value loaded from an
1507 aggregate passed to a parameter (either by value or reference), return TRUE
1508 and store the number of the parameter to *INDEX_P and information whether
1509 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1510 the function parameters, STMT is the statement in which OP is used or
1511 loaded. */
1512
1513 static bool
unmodified_parm_or_parm_agg_item(struct ipa_node_params * info,gimple stmt,tree op,int * index_p,struct agg_position_info * aggpos)1514 unmodified_parm_or_parm_agg_item (struct ipa_node_params *info,
1515 gimple stmt, tree op, int *index_p,
1516 struct agg_position_info *aggpos)
1517 {
1518 tree res = unmodified_parm_1 (stmt, op);
1519
1520 gcc_checking_assert (aggpos);
1521 if (res)
1522 {
1523 *index_p = ipa_get_param_decl_index (info, res);
1524 if (*index_p < 0)
1525 return false;
1526 aggpos->agg_contents = false;
1527 aggpos->by_ref = false;
1528 return true;
1529 }
1530
1531 if (TREE_CODE (op) == SSA_NAME)
1532 {
1533 if (SSA_NAME_IS_DEFAULT_DEF (op)
1534 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1535 return false;
1536 stmt = SSA_NAME_DEF_STMT (op);
1537 op = gimple_assign_rhs1 (stmt);
1538 if (!REFERENCE_CLASS_P (op))
1539 return unmodified_parm_or_parm_agg_item (info, stmt, op, index_p,
1540 aggpos);
1541 }
1542
1543 aggpos->agg_contents = true;
1544 return ipa_load_from_parm_agg (info, stmt, op, index_p, &aggpos->offset,
1545 &aggpos->by_ref);
1546 }
1547
1548 /* See if statement might disappear after inlining.
1549 0 - means not eliminated
1550 1 - half of statements goes away
1551 2 - for sure it is eliminated.
1552 We are not terribly sophisticated, basically looking for simple abstraction
1553 penalty wrappers. */
1554
1555 static int
eliminated_by_inlining_prob(gimple stmt)1556 eliminated_by_inlining_prob (gimple stmt)
1557 {
1558 enum gimple_code code = gimple_code (stmt);
1559 enum tree_code rhs_code;
1560
1561 if (!optimize)
1562 return 0;
1563
1564 switch (code)
1565 {
1566 case GIMPLE_RETURN:
1567 return 2;
1568 case GIMPLE_ASSIGN:
1569 if (gimple_num_ops (stmt) != 2)
1570 return 0;
1571
1572 rhs_code = gimple_assign_rhs_code (stmt);
1573
1574 /* Casts of parameters, loads from parameters passed by reference
1575 and stores to return value or parameters are often free after
1576 inlining dua to SRA and further combining.
1577 Assume that half of statements goes away. */
1578 if (rhs_code == CONVERT_EXPR
1579 || rhs_code == NOP_EXPR
1580 || rhs_code == VIEW_CONVERT_EXPR
1581 || rhs_code == ADDR_EXPR
1582 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1583 {
1584 tree rhs = gimple_assign_rhs1 (stmt);
1585 tree lhs = gimple_assign_lhs (stmt);
1586 tree inner_rhs = get_base_address (rhs);
1587 tree inner_lhs = get_base_address (lhs);
1588 bool rhs_free = false;
1589 bool lhs_free = false;
1590
1591 if (!inner_rhs)
1592 inner_rhs = rhs;
1593 if (!inner_lhs)
1594 inner_lhs = lhs;
1595
1596 /* Reads of parameter are expected to be free. */
1597 if (unmodified_parm (stmt, inner_rhs))
1598 rhs_free = true;
1599 /* Match expressions of form &this->field. Those will most likely
1600 combine with something upstream after inlining. */
1601 else if (TREE_CODE (inner_rhs) == ADDR_EXPR)
1602 {
1603 tree op = get_base_address (TREE_OPERAND (inner_rhs, 0));
1604 if (TREE_CODE (op) == PARM_DECL)
1605 rhs_free = true;
1606 else if (TREE_CODE (op) == MEM_REF
1607 && unmodified_parm (stmt, TREE_OPERAND (op, 0)))
1608 rhs_free = true;
1609 }
1610
1611 /* When parameter is not SSA register because its address is taken
1612 and it is just copied into one, the statement will be completely
1613 free after inlining (we will copy propagate backward). */
1614 if (rhs_free && is_gimple_reg (lhs))
1615 return 2;
1616
1617 /* Reads of parameters passed by reference
1618 expected to be free (i.e. optimized out after inlining). */
1619 if (TREE_CODE (inner_rhs) == MEM_REF
1620 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0)))
1621 rhs_free = true;
1622
1623 /* Copying parameter passed by reference into gimple register is
1624 probably also going to copy propagate, but we can't be quite
1625 sure. */
1626 if (rhs_free && is_gimple_reg (lhs))
1627 lhs_free = true;
1628
1629 /* Writes to parameters, parameters passed by value and return value
1630 (either dirrectly or passed via invisible reference) are free.
1631
1632 TODO: We ought to handle testcase like
1633 struct a {int a,b;};
1634 struct a
1635 retrurnsturct (void)
1636 {
1637 struct a a ={1,2};
1638 return a;
1639 }
1640
1641 This translate into:
1642
1643 retrurnsturct ()
1644 {
1645 int a$b;
1646 int a$a;
1647 struct a a;
1648 struct a D.2739;
1649
1650 <bb 2>:
1651 D.2739.a = 1;
1652 D.2739.b = 2;
1653 return D.2739;
1654
1655 }
1656 For that we either need to copy ipa-split logic detecting writes
1657 to return value. */
1658 if (TREE_CODE (inner_lhs) == PARM_DECL
1659 || TREE_CODE (inner_lhs) == RESULT_DECL
1660 || (TREE_CODE (inner_lhs) == MEM_REF
1661 && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0))
1662 || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
1663 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs, 0))
1664 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1665 (inner_lhs,
1666 0))) == RESULT_DECL))))
1667 lhs_free = true;
1668 if (lhs_free
1669 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1670 rhs_free = true;
1671 if (lhs_free && rhs_free)
1672 return 1;
1673 }
1674 return 0;
1675 default:
1676 return 0;
1677 }
1678 }
1679
1680
1681 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1682 predicates to the CFG edges. */
1683
1684 static void
set_cond_stmt_execution_predicate(struct ipa_node_params * info,struct inline_summary * summary,basic_block bb)1685 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1686 struct inline_summary *summary,
1687 basic_block bb)
1688 {
1689 gimple last;
1690 tree op;
1691 int index;
1692 struct agg_position_info aggpos;
1693 enum tree_code code, inverted_code;
1694 edge e;
1695 edge_iterator ei;
1696 gimple set_stmt;
1697 tree op2;
1698
1699 last = last_stmt (bb);
1700 if (!last || gimple_code (last) != GIMPLE_COND)
1701 return;
1702 if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1703 return;
1704 op = gimple_cond_lhs (last);
1705 /* TODO: handle conditionals like
1706 var = op0 < 4;
1707 if (var != 0). */
1708 if (unmodified_parm_or_parm_agg_item (info, last, op, &index, &aggpos))
1709 {
1710 code = gimple_cond_code (last);
1711 inverted_code
1712 = invert_tree_comparison (code,
1713 HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1714
1715 FOR_EACH_EDGE (e, ei, bb->succs)
1716 {
1717 struct predicate p = add_condition (summary, index, &aggpos,
1718 e->flags & EDGE_TRUE_VALUE
1719 ? code : inverted_code,
1720 gimple_cond_rhs (last));
1721 e->aux = pool_alloc (edge_predicate_pool);
1722 *(struct predicate *) e->aux = p;
1723 }
1724 }
1725
1726 if (TREE_CODE (op) != SSA_NAME)
1727 return;
1728 /* Special case
1729 if (builtin_constant_p (op))
1730 constant_code
1731 else
1732 nonconstant_code.
1733 Here we can predicate nonconstant_code. We can't
1734 really handle constant_code since we have no predicate
1735 for this and also the constant code is not known to be
1736 optimized away when inliner doen't see operand is constant.
1737 Other optimizers might think otherwise. */
1738 if (gimple_cond_code (last) != NE_EXPR
1739 || !integer_zerop (gimple_cond_rhs (last)))
1740 return;
1741 set_stmt = SSA_NAME_DEF_STMT (op);
1742 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1743 || gimple_call_num_args (set_stmt) != 1)
1744 return;
1745 op2 = gimple_call_arg (set_stmt, 0);
1746 if (!unmodified_parm_or_parm_agg_item
1747 (info, set_stmt, op2, &index, &aggpos))
1748 return;
1749 FOR_EACH_EDGE (e, ei, bb->succs) if (e->flags & EDGE_FALSE_VALUE)
1750 {
1751 struct predicate p = add_condition (summary, index, &aggpos,
1752 IS_NOT_CONSTANT, NULL_TREE);
1753 e->aux = pool_alloc (edge_predicate_pool);
1754 *(struct predicate *) e->aux = p;
1755 }
1756 }
1757
1758
1759 /* If BB ends by a switch we can turn into predicates, attach corresponding
1760 predicates to the CFG edges. */
1761
1762 static void
set_switch_stmt_execution_predicate(struct ipa_node_params * info,struct inline_summary * summary,basic_block bb)1763 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1764 struct inline_summary *summary,
1765 basic_block bb)
1766 {
1767 gimple last;
1768 tree op;
1769 int index;
1770 struct agg_position_info aggpos;
1771 edge e;
1772 edge_iterator ei;
1773 size_t n;
1774 size_t case_idx;
1775
1776 last = last_stmt (bb);
1777 if (!last || gimple_code (last) != GIMPLE_SWITCH)
1778 return;
1779 op = gimple_switch_index (last);
1780 if (!unmodified_parm_or_parm_agg_item (info, last, op, &index, &aggpos))
1781 return;
1782
1783 FOR_EACH_EDGE (e, ei, bb->succs)
1784 {
1785 e->aux = pool_alloc (edge_predicate_pool);
1786 *(struct predicate *) e->aux = false_predicate ();
1787 }
1788 n = gimple_switch_num_labels (last);
1789 for (case_idx = 0; case_idx < n; ++case_idx)
1790 {
1791 tree cl = gimple_switch_label (last, case_idx);
1792 tree min, max;
1793 struct predicate p;
1794
1795 e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1796 min = CASE_LOW (cl);
1797 max = CASE_HIGH (cl);
1798
1799 /* For default we might want to construct predicate that none
1800 of cases is met, but it is bit hard to do not having negations
1801 of conditionals handy. */
1802 if (!min && !max)
1803 p = true_predicate ();
1804 else if (!max)
1805 p = add_condition (summary, index, &aggpos, EQ_EXPR, min);
1806 else
1807 {
1808 struct predicate p1, p2;
1809 p1 = add_condition (summary, index, &aggpos, GE_EXPR, min);
1810 p2 = add_condition (summary, index, &aggpos, LE_EXPR, max);
1811 p = and_predicates (summary->conds, &p1, &p2);
1812 }
1813 *(struct predicate *) e->aux
1814 = or_predicates (summary->conds, &p, (struct predicate *) e->aux);
1815 }
1816 }
1817
1818
1819 /* For each BB in NODE attach to its AUX pointer predicate under
1820 which it is executable. */
1821
1822 static void
compute_bb_predicates(struct cgraph_node * node,struct ipa_node_params * parms_info,struct inline_summary * summary)1823 compute_bb_predicates (struct cgraph_node *node,
1824 struct ipa_node_params *parms_info,
1825 struct inline_summary *summary)
1826 {
1827 struct function *my_function = DECL_STRUCT_FUNCTION (node->symbol.decl);
1828 bool done = false;
1829 basic_block bb;
1830
1831 FOR_EACH_BB_FN (bb, my_function)
1832 {
1833 set_cond_stmt_execution_predicate (parms_info, summary, bb);
1834 set_switch_stmt_execution_predicate (parms_info, summary, bb);
1835 }
1836
1837 /* Entry block is always executable. */
1838 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1839 = pool_alloc (edge_predicate_pool);
1840 *(struct predicate *) ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1841 = true_predicate ();
1842
1843 /* A simple dataflow propagation of predicates forward in the CFG.
1844 TODO: work in reverse postorder. */
1845 while (!done)
1846 {
1847 done = true;
1848 FOR_EACH_BB_FN (bb, my_function)
1849 {
1850 struct predicate p = false_predicate ();
1851 edge e;
1852 edge_iterator ei;
1853 FOR_EACH_EDGE (e, ei, bb->preds)
1854 {
1855 if (e->src->aux)
1856 {
1857 struct predicate this_bb_predicate
1858 = *(struct predicate *) e->src->aux;
1859 if (e->aux)
1860 this_bb_predicate
1861 = and_predicates (summary->conds, &this_bb_predicate,
1862 (struct predicate *) e->aux);
1863 p = or_predicates (summary->conds, &p, &this_bb_predicate);
1864 if (true_predicate_p (&p))
1865 break;
1866 }
1867 }
1868 if (false_predicate_p (&p))
1869 gcc_assert (!bb->aux);
1870 else
1871 {
1872 if (!bb->aux)
1873 {
1874 done = false;
1875 bb->aux = pool_alloc (edge_predicate_pool);
1876 *((struct predicate *) bb->aux) = p;
1877 }
1878 else if (!predicates_equal_p (&p, (struct predicate *) bb->aux))
1879 {
1880 done = false;
1881 *((struct predicate *) bb->aux) = p;
1882 }
1883 }
1884 }
1885 }
1886 }
1887
1888
1889 /* We keep info about constantness of SSA names. */
1890
1891 typedef struct predicate predicate_t;
1892 /* Return predicate specifying when the STMT might have result that is not
1893 a compile time constant. */
1894
1895 static struct predicate
will_be_nonconstant_expr_predicate(struct ipa_node_params * info,struct inline_summary * summary,tree expr,vec<predicate_t> nonconstant_names)1896 will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
1897 struct inline_summary *summary,
1898 tree expr,
1899 vec<predicate_t> nonconstant_names)
1900 {
1901 tree parm;
1902 int index;
1903
1904 while (UNARY_CLASS_P (expr))
1905 expr = TREE_OPERAND (expr, 0);
1906
1907 parm = unmodified_parm (NULL, expr);
1908 if (parm && (index = ipa_get_param_decl_index (info, parm)) >= 0)
1909 return add_condition (summary, index, NULL, CHANGED, NULL_TREE);
1910 if (is_gimple_min_invariant (expr))
1911 return false_predicate ();
1912 if (TREE_CODE (expr) == SSA_NAME)
1913 return nonconstant_names[SSA_NAME_VERSION (expr)];
1914 if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
1915 {
1916 struct predicate p1 = will_be_nonconstant_expr_predicate
1917 (info, summary, TREE_OPERAND (expr, 0),
1918 nonconstant_names);
1919 struct predicate p2;
1920 if (true_predicate_p (&p1))
1921 return p1;
1922 p2 = will_be_nonconstant_expr_predicate (info, summary,
1923 TREE_OPERAND (expr, 1),
1924 nonconstant_names);
1925 return or_predicates (summary->conds, &p1, &p2);
1926 }
1927 else if (TREE_CODE (expr) == COND_EXPR)
1928 {
1929 struct predicate p1 = will_be_nonconstant_expr_predicate
1930 (info, summary, TREE_OPERAND (expr, 0),
1931 nonconstant_names);
1932 struct predicate p2;
1933 if (true_predicate_p (&p1))
1934 return p1;
1935 p2 = will_be_nonconstant_expr_predicate (info, summary,
1936 TREE_OPERAND (expr, 1),
1937 nonconstant_names);
1938 if (true_predicate_p (&p2))
1939 return p2;
1940 p1 = or_predicates (summary->conds, &p1, &p2);
1941 p2 = will_be_nonconstant_expr_predicate (info, summary,
1942 TREE_OPERAND (expr, 2),
1943 nonconstant_names);
1944 return or_predicates (summary->conds, &p1, &p2);
1945 }
1946 else
1947 {
1948 debug_tree (expr);
1949 gcc_unreachable ();
1950 }
1951 return false_predicate ();
1952 }
1953
1954
1955 /* Return predicate specifying when the STMT might have result that is not
1956 a compile time constant. */
1957
1958 static struct predicate
will_be_nonconstant_predicate(struct ipa_node_params * info,struct inline_summary * summary,gimple stmt,vec<predicate_t> nonconstant_names)1959 will_be_nonconstant_predicate (struct ipa_node_params *info,
1960 struct inline_summary *summary,
1961 gimple stmt,
1962 vec<predicate_t> nonconstant_names)
1963 {
1964 struct predicate p = true_predicate ();
1965 ssa_op_iter iter;
1966 tree use;
1967 struct predicate op_non_const;
1968 bool is_load;
1969 int base_index;
1970 struct agg_position_info aggpos;
1971
1972 /* What statments might be optimized away
1973 when their arguments are constant
1974 TODO: also trivial builtins.
1975 builtin_constant_p is already handled later. */
1976 if (gimple_code (stmt) != GIMPLE_ASSIGN
1977 && gimple_code (stmt) != GIMPLE_COND
1978 && gimple_code (stmt) != GIMPLE_SWITCH)
1979 return p;
1980
1981 /* Stores will stay anyway. */
1982 if (gimple_store_p (stmt))
1983 return p;
1984
1985 is_load = gimple_assign_load_p (stmt);
1986
1987 /* Loads can be optimized when the value is known. */
1988 if (is_load)
1989 {
1990 tree op;
1991 gcc_assert (gimple_assign_single_p (stmt));
1992 op = gimple_assign_rhs1 (stmt);
1993 if (!unmodified_parm_or_parm_agg_item (info, stmt, op, &base_index,
1994 &aggpos))
1995 return p;
1996 }
1997 else
1998 base_index = -1;
1999
2000 /* See if we understand all operands before we start
2001 adding conditionals. */
2002 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2003 {
2004 tree parm = unmodified_parm (stmt, use);
2005 /* For arguments we can build a condition. */
2006 if (parm && ipa_get_param_decl_index (info, parm) >= 0)
2007 continue;
2008 if (TREE_CODE (use) != SSA_NAME)
2009 return p;
2010 /* If we know when operand is constant,
2011 we still can say something useful. */
2012 if (!true_predicate_p (&nonconstant_names[SSA_NAME_VERSION (use)]))
2013 continue;
2014 return p;
2015 }
2016
2017 if (is_load)
2018 op_non_const =
2019 add_condition (summary, base_index, &aggpos, CHANGED, NULL);
2020 else
2021 op_non_const = false_predicate ();
2022 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2023 {
2024 tree parm = unmodified_parm (stmt, use);
2025 int index;
2026
2027 if (parm && (index = ipa_get_param_decl_index (info, parm)) >= 0)
2028 {
2029 if (index != base_index)
2030 p = add_condition (summary, index, NULL, CHANGED, NULL_TREE);
2031 else
2032 continue;
2033 }
2034 else
2035 p = nonconstant_names[SSA_NAME_VERSION (use)];
2036 op_non_const = or_predicates (summary->conds, &p, &op_non_const);
2037 }
2038 if (gimple_code (stmt) == GIMPLE_ASSIGN
2039 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
2040 nonconstant_names[SSA_NAME_VERSION (gimple_assign_lhs (stmt))]
2041 = op_non_const;
2042 return op_non_const;
2043 }
2044
2045 struct record_modified_bb_info
2046 {
2047 bitmap bb_set;
2048 gimple stmt;
2049 };
2050
2051 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2052 set except for info->stmt. */
2053
2054 static bool
record_modified(ao_ref * ao ATTRIBUTE_UNUSED,tree vdef,void * data)2055 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
2056 {
2057 struct record_modified_bb_info *info =
2058 (struct record_modified_bb_info *) data;
2059 if (SSA_NAME_DEF_STMT (vdef) == info->stmt)
2060 return false;
2061 bitmap_set_bit (info->bb_set,
2062 SSA_NAME_IS_DEFAULT_DEF (vdef)
2063 ? ENTRY_BLOCK_PTR->index
2064 : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index);
2065 return false;
2066 }
2067
2068 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2069 will change since last invocation of STMT.
2070
2071 Value 0 is reserved for compile time invariants.
2072 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2073 ought to be REG_BR_PROB_BASE / estimated_iters. */
2074
2075 static int
param_change_prob(gimple stmt,int i)2076 param_change_prob (gimple stmt, int i)
2077 {
2078 tree op = gimple_call_arg (stmt, i);
2079 basic_block bb = gimple_bb (stmt);
2080 tree base;
2081
2082 /* Global invariants neve change. */
2083 if (is_gimple_min_invariant (op))
2084 return 0;
2085 /* We would have to do non-trivial analysis to really work out what
2086 is the probability of value to change (i.e. when init statement
2087 is in a sibling loop of the call).
2088
2089 We do an conservative estimate: when call is executed N times more often
2090 than the statement defining value, we take the frequency 1/N. */
2091 if (TREE_CODE (op) == SSA_NAME)
2092 {
2093 int init_freq;
2094
2095 if (!bb->frequency)
2096 return REG_BR_PROB_BASE;
2097
2098 if (SSA_NAME_IS_DEFAULT_DEF (op))
2099 init_freq = ENTRY_BLOCK_PTR->frequency;
2100 else
2101 init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency;
2102
2103 if (!init_freq)
2104 init_freq = 1;
2105 if (init_freq < bb->frequency)
2106 return MAX ((init_freq * REG_BR_PROB_BASE +
2107 bb->frequency / 2) / bb->frequency, 1);
2108 else
2109 return REG_BR_PROB_BASE;
2110 }
2111
2112 base = get_base_address (op);
2113 if (base)
2114 {
2115 ao_ref refd;
2116 int max;
2117 struct record_modified_bb_info info;
2118 bitmap_iterator bi;
2119 unsigned index;
2120
2121 if (const_value_known_p (base))
2122 return 0;
2123 if (!bb->frequency)
2124 return REG_BR_PROB_BASE;
2125 ao_ref_init (&refd, op);
2126 info.stmt = stmt;
2127 info.bb_set = BITMAP_ALLOC (NULL);
2128 walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
2129 NULL);
2130 if (bitmap_bit_p (info.bb_set, bb->index))
2131 {
2132 BITMAP_FREE (info.bb_set);
2133 return REG_BR_PROB_BASE;
2134 }
2135
2136 /* Assume that every memory is initialized at entry.
2137 TODO: Can we easilly determine if value is always defined
2138 and thus we may skip entry block? */
2139 if (ENTRY_BLOCK_PTR->frequency)
2140 max = ENTRY_BLOCK_PTR->frequency;
2141 else
2142 max = 1;
2143
2144 EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi)
2145 max = MIN (max, BASIC_BLOCK (index)->frequency);
2146
2147 BITMAP_FREE (info.bb_set);
2148 if (max < bb->frequency)
2149 return MAX ((max * REG_BR_PROB_BASE +
2150 bb->frequency / 2) / bb->frequency, 1);
2151 else
2152 return REG_BR_PROB_BASE;
2153 }
2154 return REG_BR_PROB_BASE;
2155 }
2156
2157 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2158 sub-graph and if the predicate the condition depends on is known. If so,
2159 return true and store the pointer the predicate in *P. */
2160
2161 static bool
phi_result_unknown_predicate(struct ipa_node_params * info,struct inline_summary * summary,basic_block bb,struct predicate * p,vec<predicate_t> nonconstant_names)2162 phi_result_unknown_predicate (struct ipa_node_params *info,
2163 struct inline_summary *summary, basic_block bb,
2164 struct predicate *p,
2165 vec<predicate_t> nonconstant_names)
2166 {
2167 edge e;
2168 edge_iterator ei;
2169 basic_block first_bb = NULL;
2170 gimple stmt;
2171
2172 if (single_pred_p (bb))
2173 {
2174 *p = false_predicate ();
2175 return true;
2176 }
2177
2178 FOR_EACH_EDGE (e, ei, bb->preds)
2179 {
2180 if (single_succ_p (e->src))
2181 {
2182 if (!single_pred_p (e->src))
2183 return false;
2184 if (!first_bb)
2185 first_bb = single_pred (e->src);
2186 else if (single_pred (e->src) != first_bb)
2187 return false;
2188 }
2189 else
2190 {
2191 if (!first_bb)
2192 first_bb = e->src;
2193 else if (e->src != first_bb)
2194 return false;
2195 }
2196 }
2197
2198 if (!first_bb)
2199 return false;
2200
2201 stmt = last_stmt (first_bb);
2202 if (!stmt
2203 || gimple_code (stmt) != GIMPLE_COND
2204 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt)))
2205 return false;
2206
2207 *p = will_be_nonconstant_expr_predicate (info, summary,
2208 gimple_cond_lhs (stmt),
2209 nonconstant_names);
2210 if (true_predicate_p (p))
2211 return false;
2212 else
2213 return true;
2214 }
2215
2216 /* Given a PHI statement in a function described by inline properties SUMMARY
2217 and *P being the predicate describing whether the selected PHI argument is
2218 known, store a predicate for the result of the PHI statement into
2219 NONCONSTANT_NAMES, if possible. */
2220
2221 static void
predicate_for_phi_result(struct inline_summary * summary,gimple phi,struct predicate * p,vec<predicate_t> nonconstant_names)2222 predicate_for_phi_result (struct inline_summary *summary, gimple phi,
2223 struct predicate *p,
2224 vec<predicate_t> nonconstant_names)
2225 {
2226 unsigned i;
2227
2228 for (i = 0; i < gimple_phi_num_args (phi); i++)
2229 {
2230 tree arg = gimple_phi_arg (phi, i)->def;
2231 if (!is_gimple_min_invariant (arg))
2232 {
2233 gcc_assert (TREE_CODE (arg) == SSA_NAME);
2234 *p = or_predicates (summary->conds, p,
2235 &nonconstant_names[SSA_NAME_VERSION (arg)]);
2236 if (true_predicate_p (p))
2237 return;
2238 }
2239 }
2240
2241 if (dump_file && (dump_flags & TDF_DETAILS))
2242 {
2243 fprintf (dump_file, "\t\tphi predicate: ");
2244 dump_predicate (dump_file, summary->conds, p);
2245 }
2246 nonconstant_names[SSA_NAME_VERSION (gimple_phi_result (phi))] = *p;
2247 }
2248
2249 /* Return predicate specifying when array index in access OP becomes non-constant. */
2250
2251 static struct predicate
array_index_predicate(struct inline_summary * info,vec<predicate_t> nonconstant_names,tree op)2252 array_index_predicate (struct inline_summary *info,
2253 vec< predicate_t> nonconstant_names, tree op)
2254 {
2255 struct predicate p = false_predicate ();
2256 while (handled_component_p (op))
2257 {
2258 if (TREE_CODE (op) == ARRAY_REF || TREE_CODE (op) == ARRAY_RANGE_REF)
2259 {
2260 if (TREE_CODE (TREE_OPERAND (op, 1)) == SSA_NAME)
2261 p = or_predicates (info->conds, &p,
2262 &nonconstant_names[SSA_NAME_VERSION
2263 (TREE_OPERAND (op, 1))]);
2264 }
2265 op = TREE_OPERAND (op, 0);
2266 }
2267 return p;
2268 }
2269
2270 /* Compute function body size parameters for NODE.
2271 When EARLY is true, we compute only simple summaries without
2272 non-trivial predicates to drive the early inliner. */
2273
2274 static void
estimate_function_body_sizes(struct cgraph_node * node,bool early)2275 estimate_function_body_sizes (struct cgraph_node *node, bool early)
2276 {
2277 gcov_type time = 0;
2278 /* Estimate static overhead for function prologue/epilogue and alignment. */
2279 int size = 2;
2280 /* Benefits are scaled by probability of elimination that is in range
2281 <0,2>. */
2282 basic_block bb;
2283 gimple_stmt_iterator bsi;
2284 struct function *my_function = DECL_STRUCT_FUNCTION (node->symbol.decl);
2285 int freq;
2286 struct inline_summary *info = inline_summary (node);
2287 struct predicate bb_predicate;
2288 struct ipa_node_params *parms_info = NULL;
2289 vec<predicate_t> nonconstant_names = vNULL;
2290 int nblocks, n;
2291 int *order;
2292 predicate array_index = true_predicate ();
2293
2294 info->conds = NULL;
2295 info->entry = NULL;
2296
2297 if (optimize && !early)
2298 {
2299 calculate_dominance_info (CDI_DOMINATORS);
2300 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
2301
2302 if (ipa_node_params_vector.exists ())
2303 {
2304 parms_info = IPA_NODE_REF (node);
2305 nonconstant_names.safe_grow_cleared
2306 (SSANAMES (my_function)->length ());
2307 }
2308 }
2309
2310 if (dump_file)
2311 fprintf (dump_file, "\nAnalyzing function body size: %s\n",
2312 cgraph_node_name (node));
2313
2314 /* When we run into maximal number of entries, we assign everything to the
2315 constant truth case. Be sure to have it in list. */
2316 bb_predicate = true_predicate ();
2317 account_size_time (info, 0, 0, &bb_predicate);
2318
2319 bb_predicate = not_inlined_predicate ();
2320 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
2321
2322 gcc_assert (my_function && my_function->cfg);
2323 if (parms_info)
2324 compute_bb_predicates (node, parms_info, info);
2325 gcc_assert (cfun == my_function);
2326 order = XNEWVEC (int, n_basic_blocks);
2327 nblocks = pre_and_rev_post_order_compute (NULL, order, false);
2328 for (n = 0; n < nblocks; n++)
2329 {
2330 bb = BASIC_BLOCK (order[n]);
2331 freq = compute_call_stmt_bb_frequency (node->symbol.decl, bb);
2332
2333 /* TODO: Obviously predicates can be propagated down across CFG. */
2334 if (parms_info)
2335 {
2336 if (bb->aux)
2337 bb_predicate = *(struct predicate *) bb->aux;
2338 else
2339 bb_predicate = false_predicate ();
2340 }
2341 else
2342 bb_predicate = true_predicate ();
2343
2344 if (dump_file && (dump_flags & TDF_DETAILS))
2345 {
2346 fprintf (dump_file, "\n BB %i predicate:", bb->index);
2347 dump_predicate (dump_file, info->conds, &bb_predicate);
2348 }
2349
2350 if (parms_info && nonconstant_names.exists ())
2351 {
2352 struct predicate phi_predicate;
2353 bool first_phi = true;
2354
2355 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2356 {
2357 if (first_phi
2358 && !phi_result_unknown_predicate (parms_info, info, bb,
2359 &phi_predicate,
2360 nonconstant_names))
2361 break;
2362 first_phi = false;
2363 if (dump_file && (dump_flags & TDF_DETAILS))
2364 {
2365 fprintf (dump_file, " ");
2366 print_gimple_stmt (dump_file, gsi_stmt (bsi), 0, 0);
2367 }
2368 predicate_for_phi_result (info, gsi_stmt (bsi), &phi_predicate,
2369 nonconstant_names);
2370 }
2371 }
2372
2373 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2374 {
2375 gimple stmt = gsi_stmt (bsi);
2376 int this_size = estimate_num_insns (stmt, &eni_size_weights);
2377 int this_time = estimate_num_insns (stmt, &eni_time_weights);
2378 int prob;
2379 struct predicate will_be_nonconstant;
2380
2381 if (dump_file && (dump_flags & TDF_DETAILS))
2382 {
2383 fprintf (dump_file, " ");
2384 print_gimple_stmt (dump_file, stmt, 0, 0);
2385 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2386 ((double) freq) / CGRAPH_FREQ_BASE, this_size,
2387 this_time);
2388 }
2389
2390 if (gimple_assign_load_p (stmt) && nonconstant_names.exists ())
2391 {
2392 struct predicate this_array_index;
2393 this_array_index =
2394 array_index_predicate (info, nonconstant_names,
2395 gimple_assign_rhs1 (stmt));
2396 if (!false_predicate_p (&this_array_index))
2397 array_index =
2398 and_predicates (info->conds, &array_index,
2399 &this_array_index);
2400 }
2401 if (gimple_store_p (stmt) && nonconstant_names.exists ())
2402 {
2403 struct predicate this_array_index;
2404 this_array_index =
2405 array_index_predicate (info, nonconstant_names,
2406 gimple_get_lhs (stmt));
2407 if (!false_predicate_p (&this_array_index))
2408 array_index =
2409 and_predicates (info->conds, &array_index,
2410 &this_array_index);
2411 }
2412
2413
2414 if (is_gimple_call (stmt))
2415 {
2416 struct cgraph_edge *edge = cgraph_edge (node, stmt);
2417 struct inline_edge_summary *es = inline_edge_summary (edge);
2418
2419 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2420 resolved as constant. We however don't want to optimize
2421 out the cgraph edges. */
2422 if (nonconstant_names.exists ()
2423 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
2424 && gimple_call_lhs (stmt)
2425 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
2426 {
2427 struct predicate false_p = false_predicate ();
2428 nonconstant_names[SSA_NAME_VERSION (gimple_call_lhs (stmt))]
2429 = false_p;
2430 }
2431 if (ipa_node_params_vector.exists ())
2432 {
2433 int count = gimple_call_num_args (stmt);
2434 int i;
2435
2436 if (count)
2437 es->param.safe_grow_cleared (count);
2438 for (i = 0; i < count; i++)
2439 {
2440 int prob = param_change_prob (stmt, i);
2441 gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
2442 es->param[i].change_prob = prob;
2443 }
2444 }
2445
2446 es->call_stmt_size = this_size;
2447 es->call_stmt_time = this_time;
2448 es->loop_depth = bb_loop_depth (bb);
2449 edge_set_predicate (edge, &bb_predicate);
2450 }
2451
2452 /* TODO: When conditional jump or swithc is known to be constant, but
2453 we did not translate it into the predicates, we really can account
2454 just maximum of the possible paths. */
2455 if (parms_info)
2456 will_be_nonconstant
2457 = will_be_nonconstant_predicate (parms_info, info,
2458 stmt, nonconstant_names);
2459 if (this_time || this_size)
2460 {
2461 struct predicate p;
2462
2463 this_time *= freq;
2464
2465 prob = eliminated_by_inlining_prob (stmt);
2466 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
2467 fprintf (dump_file,
2468 "\t\t50%% will be eliminated by inlining\n");
2469 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
2470 fprintf (dump_file, "\t\tWill be eliminated by inlining\n");
2471
2472 if (parms_info)
2473 p = and_predicates (info->conds, &bb_predicate,
2474 &will_be_nonconstant);
2475 else
2476 p = true_predicate ();
2477
2478 if (!false_predicate_p (&p))
2479 {
2480 time += this_time;
2481 size += this_size;
2482 if (time > MAX_TIME * INLINE_TIME_SCALE)
2483 time = MAX_TIME * INLINE_TIME_SCALE;
2484 }
2485
2486 /* We account everything but the calls. Calls have their own
2487 size/time info attached to cgraph edges. This is necessary
2488 in order to make the cost disappear after inlining. */
2489 if (!is_gimple_call (stmt))
2490 {
2491 if (prob)
2492 {
2493 struct predicate ip = not_inlined_predicate ();
2494 ip = and_predicates (info->conds, &ip, &p);
2495 account_size_time (info, this_size * prob,
2496 this_time * prob, &ip);
2497 }
2498 if (prob != 2)
2499 account_size_time (info, this_size * (2 - prob),
2500 this_time * (2 - prob), &p);
2501 }
2502
2503 gcc_assert (time >= 0);
2504 gcc_assert (size >= 0);
2505 }
2506 }
2507 }
2508 set_hint_predicate (&inline_summary (node)->array_index, array_index);
2509 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2510 if (time > MAX_TIME)
2511 time = MAX_TIME;
2512 free (order);
2513
2514 if (!early && nonconstant_names.exists ())
2515 {
2516 struct loop *loop;
2517 loop_iterator li;
2518 predicate loop_iterations = true_predicate ();
2519 predicate loop_stride = true_predicate ();
2520
2521 if (dump_file && (dump_flags & TDF_DETAILS))
2522 flow_loops_dump (dump_file, NULL, 0);
2523 scev_initialize ();
2524 FOR_EACH_LOOP (li, loop, 0)
2525 {
2526 vec<edge> exits;
2527 edge ex;
2528 unsigned int j, i;
2529 struct tree_niter_desc niter_desc;
2530 basic_block *body = get_loop_body (loop);
2531 bb_predicate = *(struct predicate *) loop->header->aux;
2532
2533 exits = get_loop_exit_edges (loop);
2534 FOR_EACH_VEC_ELT (exits, j, ex)
2535 if (number_of_iterations_exit (loop, ex, &niter_desc, false)
2536 && !is_gimple_min_invariant (niter_desc.niter))
2537 {
2538 predicate will_be_nonconstant
2539 = will_be_nonconstant_expr_predicate (parms_info, info,
2540 niter_desc.niter,
2541 nonconstant_names);
2542 if (!true_predicate_p (&will_be_nonconstant))
2543 will_be_nonconstant = and_predicates (info->conds,
2544 &bb_predicate,
2545 &will_be_nonconstant);
2546 if (!true_predicate_p (&will_be_nonconstant)
2547 && !false_predicate_p (&will_be_nonconstant))
2548 /* This is slightly inprecise. We may want to represent each
2549 loop with independent predicate. */
2550 loop_iterations =
2551 and_predicates (info->conds, &loop_iterations,
2552 &will_be_nonconstant);
2553 }
2554 exits.release ();
2555
2556 for (i = 0; i < loop->num_nodes; i++)
2557 {
2558 gimple_stmt_iterator gsi;
2559 bb_predicate = *(struct predicate *) body[i]->aux;
2560 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi);
2561 gsi_next (&gsi))
2562 {
2563 gimple stmt = gsi_stmt (gsi);
2564 affine_iv iv;
2565 ssa_op_iter iter;
2566 tree use;
2567
2568 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2569 {
2570 predicate will_be_nonconstant;
2571
2572 if (!simple_iv
2573 (loop, loop_containing_stmt (stmt), use, &iv, true)
2574 || is_gimple_min_invariant (iv.step))
2575 continue;
2576 will_be_nonconstant
2577 = will_be_nonconstant_expr_predicate (parms_info, info,
2578 iv.step,
2579 nonconstant_names);
2580 if (!true_predicate_p (&will_be_nonconstant))
2581 will_be_nonconstant
2582 = and_predicates (info->conds,
2583 &bb_predicate,
2584 &will_be_nonconstant);
2585 if (!true_predicate_p (&will_be_nonconstant)
2586 && !false_predicate_p (&will_be_nonconstant))
2587 /* This is slightly inprecise. We may want to represent
2588 each loop with independent predicate. */
2589 loop_stride =
2590 and_predicates (info->conds, &loop_stride,
2591 &will_be_nonconstant);
2592 }
2593 }
2594 }
2595 free (body);
2596 }
2597 set_hint_predicate (&inline_summary (node)->loop_iterations,
2598 loop_iterations);
2599 set_hint_predicate (&inline_summary (node)->loop_stride, loop_stride);
2600 scev_finalize ();
2601 }
2602 FOR_ALL_BB_FN (bb, my_function)
2603 {
2604 edge e;
2605 edge_iterator ei;
2606
2607 if (bb->aux)
2608 pool_free (edge_predicate_pool, bb->aux);
2609 bb->aux = NULL;
2610 FOR_EACH_EDGE (e, ei, bb->succs)
2611 {
2612 if (e->aux)
2613 pool_free (edge_predicate_pool, e->aux);
2614 e->aux = NULL;
2615 }
2616 }
2617 inline_summary (node)->self_time = time;
2618 inline_summary (node)->self_size = size;
2619 nonconstant_names.release ();
2620 if (optimize && !early)
2621 {
2622 loop_optimizer_finalize ();
2623 free_dominance_info (CDI_DOMINATORS);
2624 }
2625 if (dump_file)
2626 {
2627 fprintf (dump_file, "\n");
2628 dump_inline_summary (dump_file, node);
2629 }
2630 }
2631
2632
2633 /* Compute parameters of functions used by inliner.
2634 EARLY is true when we compute parameters for the early inliner */
2635
2636 void
compute_inline_parameters(struct cgraph_node * node,bool early)2637 compute_inline_parameters (struct cgraph_node *node, bool early)
2638 {
2639 HOST_WIDE_INT self_stack_size;
2640 struct cgraph_edge *e;
2641 struct inline_summary *info;
2642
2643 gcc_assert (!node->global.inlined_to);
2644
2645 inline_summary_alloc ();
2646
2647 info = inline_summary (node);
2648 reset_inline_summary (node);
2649
2650 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2651 Once this happen, we will need to more curefully predict call
2652 statement size. */
2653 if (node->thunk.thunk_p)
2654 {
2655 struct inline_edge_summary *es = inline_edge_summary (node->callees);
2656 struct predicate t = true_predicate ();
2657
2658 info->inlinable = 0;
2659 node->callees->call_stmt_cannot_inline_p = true;
2660 node->local.can_change_signature = false;
2661 es->call_stmt_time = 1;
2662 es->call_stmt_size = 1;
2663 account_size_time (info, 0, 0, &t);
2664 return;
2665 }
2666
2667 /* Even is_gimple_min_invariant rely on current_function_decl. */
2668 push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
2669
2670 /* Estimate the stack size for the function if we're optimizing. */
2671 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
2672 info->estimated_self_stack_size = self_stack_size;
2673 info->estimated_stack_size = self_stack_size;
2674 info->stack_frame_offset = 0;
2675
2676 /* Can this function be inlined at all? */
2677 info->inlinable = tree_inlinable_function_p (node->symbol.decl);
2678
2679 /* Type attributes can use parameter indices to describe them. */
2680 if (TYPE_ATTRIBUTES (TREE_TYPE (node->symbol.decl)))
2681 node->local.can_change_signature = false;
2682 else
2683 {
2684 /* Otherwise, inlinable functions always can change signature. */
2685 if (info->inlinable)
2686 node->local.can_change_signature = true;
2687 else
2688 {
2689 /* Functions calling builtin_apply can not change signature. */
2690 for (e = node->callees; e; e = e->next_callee)
2691 {
2692 tree cdecl = e->callee->symbol.decl;
2693 if (DECL_BUILT_IN (cdecl)
2694 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2695 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2696 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
2697 break;
2698 }
2699 node->local.can_change_signature = !e;
2700 }
2701 }
2702 estimate_function_body_sizes (node, early);
2703
2704 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2705 info->time = info->self_time;
2706 info->size = info->self_size;
2707 info->stack_frame_offset = 0;
2708 info->estimated_stack_size = info->estimated_self_stack_size;
2709 #ifdef ENABLE_CHECKING
2710 inline_update_overall_summary (node);
2711 gcc_assert (info->time == info->self_time && info->size == info->self_size);
2712 #endif
2713
2714 pop_cfun ();
2715 }
2716
2717
2718 /* Compute parameters of functions used by inliner using
2719 current_function_decl. */
2720
2721 static unsigned int
compute_inline_parameters_for_current(void)2722 compute_inline_parameters_for_current (void)
2723 {
2724 compute_inline_parameters (cgraph_get_node (current_function_decl), true);
2725 return 0;
2726 }
2727
2728 struct gimple_opt_pass pass_inline_parameters =
2729 {
2730 {
2731 GIMPLE_PASS,
2732 "inline_param", /* name */
2733 OPTGROUP_INLINE, /* optinfo_flags */
2734 NULL, /* gate */
2735 compute_inline_parameters_for_current, /* execute */
2736 NULL, /* sub */
2737 NULL, /* next */
2738 0, /* static_pass_number */
2739 TV_INLINE_PARAMETERS, /* tv_id */
2740 0, /* properties_required */
2741 0, /* properties_provided */
2742 0, /* properties_destroyed */
2743 0, /* todo_flags_start */
2744 0 /* todo_flags_finish */
2745 }
2746 };
2747
2748
2749 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2750 KNOWN_BINFOS. */
2751
2752 static bool
estimate_edge_devirt_benefit(struct cgraph_edge * ie,int * size,int * time,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs)2753 estimate_edge_devirt_benefit (struct cgraph_edge *ie,
2754 int *size, int *time,
2755 vec<tree> known_vals,
2756 vec<tree> known_binfos,
2757 vec<ipa_agg_jump_function_p> known_aggs)
2758 {
2759 tree target;
2760 struct cgraph_node *callee;
2761 struct inline_summary *isummary;
2762
2763 if (!known_vals.exists () && !known_binfos.exists ())
2764 return false;
2765 if (!flag_indirect_inlining)
2766 return false;
2767
2768 target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos,
2769 known_aggs);
2770 if (!target)
2771 return false;
2772
2773 /* Account for difference in cost between indirect and direct calls. */
2774 *size -= (eni_size_weights.indirect_call_cost - eni_size_weights.call_cost);
2775 *time -= (eni_time_weights.indirect_call_cost - eni_time_weights.call_cost);
2776 gcc_checking_assert (*time >= 0);
2777 gcc_checking_assert (*size >= 0);
2778
2779 callee = cgraph_get_node (target);
2780 if (!callee || !callee->analyzed)
2781 return false;
2782 isummary = inline_summary (callee);
2783 return isummary->inlinable;
2784 }
2785
2786 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2787
2788 static inline void
estimate_edge_size_and_time(struct cgraph_edge * e,int * size,int * time,int prob,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs,inline_hints * hints)2789 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
2790 int prob,
2791 vec<tree> known_vals,
2792 vec<tree> known_binfos,
2793 vec<ipa_agg_jump_function_p> known_aggs,
2794 inline_hints *hints)
2795 {
2796 struct inline_edge_summary *es = inline_edge_summary (e);
2797 int call_size = es->call_stmt_size;
2798 int call_time = es->call_stmt_time;
2799 if (!e->callee
2800 && estimate_edge_devirt_benefit (e, &call_size, &call_time,
2801 known_vals, known_binfos, known_aggs)
2802 && hints && cgraph_maybe_hot_edge_p (e))
2803 *hints |= INLINE_HINT_indirect_call;
2804 *size += call_size * INLINE_SIZE_SCALE;
2805 *time += call_time * prob / REG_BR_PROB_BASE
2806 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE);
2807 if (*time > MAX_TIME * INLINE_TIME_SCALE)
2808 *time = MAX_TIME * INLINE_TIME_SCALE;
2809 }
2810
2811
2812
2813 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
2814 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
2815 site. */
2816
2817 static void
estimate_calls_size_and_time(struct cgraph_node * node,int * size,int * time,inline_hints * hints,clause_t possible_truths,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs)2818 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
2819 inline_hints *hints,
2820 clause_t possible_truths,
2821 vec<tree> known_vals,
2822 vec<tree> known_binfos,
2823 vec<ipa_agg_jump_function_p> known_aggs)
2824 {
2825 struct cgraph_edge *e;
2826 for (e = node->callees; e; e = e->next_callee)
2827 {
2828 struct inline_edge_summary *es = inline_edge_summary (e);
2829 if (!es->predicate
2830 || evaluate_predicate (es->predicate, possible_truths))
2831 {
2832 if (e->inline_failed)
2833 {
2834 /* Predicates of calls shall not use NOT_CHANGED codes,
2835 sowe do not need to compute probabilities. */
2836 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE,
2837 known_vals, known_binfos,
2838 known_aggs, hints);
2839 }
2840 else
2841 estimate_calls_size_and_time (e->callee, size, time, hints,
2842 possible_truths,
2843 known_vals, known_binfos,
2844 known_aggs);
2845 }
2846 }
2847 for (e = node->indirect_calls; e; e = e->next_callee)
2848 {
2849 struct inline_edge_summary *es = inline_edge_summary (e);
2850 if (!es->predicate
2851 || evaluate_predicate (es->predicate, possible_truths))
2852 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE,
2853 known_vals, known_binfos, known_aggs,
2854 hints);
2855 }
2856 }
2857
2858
2859 /* Estimate size and time needed to execute NODE assuming
2860 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
2861 about NODE's arguments. */
2862
2863 static void
estimate_node_size_and_time(struct cgraph_node * node,clause_t possible_truths,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs,int * ret_size,int * ret_time,inline_hints * ret_hints,vec<inline_param_summary_t> inline_param_summary)2864 estimate_node_size_and_time (struct cgraph_node *node,
2865 clause_t possible_truths,
2866 vec<tree> known_vals,
2867 vec<tree> known_binfos,
2868 vec<ipa_agg_jump_function_p> known_aggs,
2869 int *ret_size, int *ret_time,
2870 inline_hints *ret_hints,
2871 vec<inline_param_summary_t>
2872 inline_param_summary)
2873 {
2874 struct inline_summary *info = inline_summary (node);
2875 size_time_entry *e;
2876 int size = 0;
2877 int time = 0;
2878 inline_hints hints = 0;
2879 int i;
2880
2881 if (dump_file && (dump_flags & TDF_DETAILS))
2882 {
2883 bool found = false;
2884 fprintf (dump_file, " Estimating body: %s/%i\n"
2885 " Known to be false: ", cgraph_node_name (node), node->uid);
2886
2887 for (i = predicate_not_inlined_condition;
2888 i < (predicate_first_dynamic_condition
2889 + (int) vec_safe_length (info->conds)); i++)
2890 if (!(possible_truths & (1 << i)))
2891 {
2892 if (found)
2893 fprintf (dump_file, ", ");
2894 found = true;
2895 dump_condition (dump_file, info->conds, i);
2896 }
2897 }
2898
2899 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
2900 if (evaluate_predicate (&e->predicate, possible_truths))
2901 {
2902 size += e->size;
2903 gcc_checking_assert (e->time >= 0);
2904 gcc_checking_assert (time >= 0);
2905 if (!inline_param_summary.exists ())
2906 time += e->time;
2907 else
2908 {
2909 int prob = predicate_probability (info->conds,
2910 &e->predicate,
2911 possible_truths,
2912 inline_param_summary);
2913 gcc_checking_assert (prob >= 0);
2914 gcc_checking_assert (prob <= REG_BR_PROB_BASE);
2915 time += ((gcov_type) e->time * prob) / REG_BR_PROB_BASE;
2916 }
2917 if (time > MAX_TIME * INLINE_TIME_SCALE)
2918 time = MAX_TIME * INLINE_TIME_SCALE;
2919 gcc_checking_assert (time >= 0);
2920
2921 }
2922 gcc_checking_assert (size >= 0);
2923 gcc_checking_assert (time >= 0);
2924
2925 if (info->loop_iterations
2926 && !evaluate_predicate (info->loop_iterations, possible_truths))
2927 hints |= INLINE_HINT_loop_iterations;
2928 if (info->loop_stride
2929 && !evaluate_predicate (info->loop_stride, possible_truths))
2930 hints |= INLINE_HINT_loop_stride;
2931 if (info->array_index
2932 && !evaluate_predicate (info->array_index, possible_truths))
2933 hints |= INLINE_HINT_array_index;
2934 if (info->scc_no)
2935 hints |= INLINE_HINT_in_scc;
2936 if (DECL_DECLARED_INLINE_P (node->symbol.decl))
2937 hints |= INLINE_HINT_declared_inline;
2938
2939 estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
2940 known_vals, known_binfos, known_aggs);
2941 gcc_checking_assert (size >= 0);
2942 gcc_checking_assert (time >= 0);
2943 time = RDIV (time, INLINE_TIME_SCALE);
2944 size = RDIV (size, INLINE_SIZE_SCALE);
2945
2946 if (dump_file && (dump_flags & TDF_DETAILS))
2947 fprintf (dump_file, "\n size:%i time:%i\n", (int) size, (int) time);
2948 if (ret_time)
2949 *ret_time = time;
2950 if (ret_size)
2951 *ret_size = size;
2952 if (ret_hints)
2953 *ret_hints = hints;
2954 return;
2955 }
2956
2957
2958 /* Estimate size and time needed to execute callee of EDGE assuming that
2959 parameters known to be constant at caller of EDGE are propagated.
2960 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
2961 and types for parameters. */
2962
2963 void
estimate_ipcp_clone_size_and_time(struct cgraph_node * node,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs,int * ret_size,int * ret_time,inline_hints * hints)2964 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
2965 vec<tree> known_vals,
2966 vec<tree> known_binfos,
2967 vec<ipa_agg_jump_function_p> known_aggs,
2968 int *ret_size, int *ret_time,
2969 inline_hints *hints)
2970 {
2971 clause_t clause;
2972
2973 clause = evaluate_conditions_for_known_args (node, false, known_vals,
2974 known_aggs);
2975 estimate_node_size_and_time (node, clause, known_vals, known_binfos,
2976 known_aggs, ret_size, ret_time, hints, vNULL);
2977 }
2978
2979 /* Translate all conditions from callee representation into caller
2980 representation and symbolically evaluate predicate P into new predicate.
2981
2982 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
2983 is summary of function predicate P is from. OPERAND_MAP is array giving
2984 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
2985 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
2986 predicate under which callee is executed. OFFSET_MAP is an array of of
2987 offsets that need to be added to conditions, negative offset means that
2988 conditions relying on values passed by reference have to be discarded
2989 because they might not be preserved (and should be considered offset zero
2990 for other purposes). */
2991
2992 static struct predicate
remap_predicate(struct inline_summary * info,struct inline_summary * callee_info,struct predicate * p,vec<int> operand_map,vec<int> offset_map,clause_t possible_truths,struct predicate * toplev_predicate)2993 remap_predicate (struct inline_summary *info,
2994 struct inline_summary *callee_info,
2995 struct predicate *p,
2996 vec<int> operand_map,
2997 vec<int> offset_map,
2998 clause_t possible_truths, struct predicate *toplev_predicate)
2999 {
3000 int i;
3001 struct predicate out = true_predicate ();
3002
3003 /* True predicate is easy. */
3004 if (true_predicate_p (p))
3005 return *toplev_predicate;
3006 for (i = 0; p->clause[i]; i++)
3007 {
3008 clause_t clause = p->clause[i];
3009 int cond;
3010 struct predicate clause_predicate = false_predicate ();
3011
3012 gcc_assert (i < MAX_CLAUSES);
3013
3014 for (cond = 0; cond < NUM_CONDITIONS; cond++)
3015 /* Do we have condition we can't disprove? */
3016 if (clause & possible_truths & (1 << cond))
3017 {
3018 struct predicate cond_predicate;
3019 /* Work out if the condition can translate to predicate in the
3020 inlined function. */
3021 if (cond >= predicate_first_dynamic_condition)
3022 {
3023 struct condition *c;
3024
3025 c = &(*callee_info->conds)[cond
3026 -
3027 predicate_first_dynamic_condition];
3028 /* See if we can remap condition operand to caller's operand.
3029 Otherwise give up. */
3030 if (!operand_map.exists ()
3031 || (int) operand_map.length () <= c->operand_num
3032 || operand_map[c->operand_num] == -1
3033 /* TODO: For non-aggregate conditions, adding an offset is
3034 basically an arithmetic jump function processing which
3035 we should support in future. */
3036 || ((!c->agg_contents || !c->by_ref)
3037 && offset_map[c->operand_num] > 0)
3038 || (c->agg_contents && c->by_ref
3039 && offset_map[c->operand_num] < 0))
3040 cond_predicate = true_predicate ();
3041 else
3042 {
3043 struct agg_position_info ap;
3044 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
3045 if (offset_delta < 0)
3046 {
3047 gcc_checking_assert (!c->agg_contents || !c->by_ref);
3048 offset_delta = 0;
3049 }
3050 gcc_assert (!c->agg_contents
3051 || c->by_ref || offset_delta == 0);
3052 ap.offset = c->offset + offset_delta;
3053 ap.agg_contents = c->agg_contents;
3054 ap.by_ref = c->by_ref;
3055 cond_predicate = add_condition (info,
3056 operand_map[c->operand_num],
3057 &ap, c->code, c->val);
3058 }
3059 }
3060 /* Fixed conditions remains same, construct single
3061 condition predicate. */
3062 else
3063 {
3064 cond_predicate.clause[0] = 1 << cond;
3065 cond_predicate.clause[1] = 0;
3066 }
3067 clause_predicate = or_predicates (info->conds, &clause_predicate,
3068 &cond_predicate);
3069 }
3070 out = and_predicates (info->conds, &out, &clause_predicate);
3071 }
3072 return and_predicates (info->conds, &out, toplev_predicate);
3073 }
3074
3075
3076 /* Update summary information of inline clones after inlining.
3077 Compute peak stack usage. */
3078
3079 static void
inline_update_callee_summaries(struct cgraph_node * node,int depth)3080 inline_update_callee_summaries (struct cgraph_node *node, int depth)
3081 {
3082 struct cgraph_edge *e;
3083 struct inline_summary *callee_info = inline_summary (node);
3084 struct inline_summary *caller_info = inline_summary (node->callers->caller);
3085 HOST_WIDE_INT peak;
3086
3087 callee_info->stack_frame_offset
3088 = caller_info->stack_frame_offset
3089 + caller_info->estimated_self_stack_size;
3090 peak = callee_info->stack_frame_offset
3091 + callee_info->estimated_self_stack_size;
3092 if (inline_summary (node->global.inlined_to)->estimated_stack_size < peak)
3093 inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
3094 cgraph_propagate_frequency (node);
3095 for (e = node->callees; e; e = e->next_callee)
3096 {
3097 if (!e->inline_failed)
3098 inline_update_callee_summaries (e->callee, depth);
3099 inline_edge_summary (e)->loop_depth += depth;
3100 }
3101 for (e = node->indirect_calls; e; e = e->next_callee)
3102 inline_edge_summary (e)->loop_depth += depth;
3103 }
3104
3105 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3106 When functoin A is inlined in B and A calls C with parameter that
3107 changes with probability PROB1 and C is known to be passthroug
3108 of argument if B that change with probability PROB2, the probability
3109 of change is now PROB1*PROB2. */
3110
3111 static void
remap_edge_change_prob(struct cgraph_edge * inlined_edge,struct cgraph_edge * edge)3112 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
3113 struct cgraph_edge *edge)
3114 {
3115 if (ipa_node_params_vector.exists ())
3116 {
3117 int i;
3118 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
3119 struct inline_edge_summary *es = inline_edge_summary (edge);
3120 struct inline_edge_summary *inlined_es
3121 = inline_edge_summary (inlined_edge);
3122
3123 for (i = 0; i < ipa_get_cs_argument_count (args); i++)
3124 {
3125 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
3126 if (jfunc->type == IPA_JF_PASS_THROUGH
3127 && (ipa_get_jf_pass_through_formal_id (jfunc)
3128 < (int) inlined_es->param.length ()))
3129 {
3130 int jf_formal_id = ipa_get_jf_pass_through_formal_id (jfunc);
3131 int prob1 = es->param[i].change_prob;
3132 int prob2 = inlined_es->param[jf_formal_id].change_prob;
3133 int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2)
3134 / REG_BR_PROB_BASE);
3135
3136 if (prob1 && prob2 && !prob)
3137 prob = 1;
3138
3139 es->param[i].change_prob = prob;
3140 }
3141 }
3142 }
3143 }
3144
3145 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3146
3147 Remap predicates of callees of NODE. Rest of arguments match
3148 remap_predicate.
3149
3150 Also update change probabilities. */
3151
3152 static void
remap_edge_summaries(struct cgraph_edge * inlined_edge,struct cgraph_node * node,struct inline_summary * info,struct inline_summary * callee_info,vec<int> operand_map,vec<int> offset_map,clause_t possible_truths,struct predicate * toplev_predicate)3153 remap_edge_summaries (struct cgraph_edge *inlined_edge,
3154 struct cgraph_node *node,
3155 struct inline_summary *info,
3156 struct inline_summary *callee_info,
3157 vec<int> operand_map,
3158 vec<int> offset_map,
3159 clause_t possible_truths,
3160 struct predicate *toplev_predicate)
3161 {
3162 struct cgraph_edge *e;
3163 for (e = node->callees; e; e = e->next_callee)
3164 {
3165 struct inline_edge_summary *es = inline_edge_summary (e);
3166 struct predicate p;
3167
3168 if (e->inline_failed)
3169 {
3170 remap_edge_change_prob (inlined_edge, e);
3171
3172 if (es->predicate)
3173 {
3174 p = remap_predicate (info, callee_info,
3175 es->predicate, operand_map, offset_map,
3176 possible_truths, toplev_predicate);
3177 edge_set_predicate (e, &p);
3178 /* TODO: We should remove the edge for code that will be
3179 optimized out, but we need to keep verifiers and tree-inline
3180 happy. Make it cold for now. */
3181 if (false_predicate_p (&p))
3182 {
3183 e->count = 0;
3184 e->frequency = 0;
3185 }
3186 }
3187 else
3188 edge_set_predicate (e, toplev_predicate);
3189 }
3190 else
3191 remap_edge_summaries (inlined_edge, e->callee, info, callee_info,
3192 operand_map, offset_map, possible_truths,
3193 toplev_predicate);
3194 }
3195 for (e = node->indirect_calls; e; e = e->next_callee)
3196 {
3197 struct inline_edge_summary *es = inline_edge_summary (e);
3198 struct predicate p;
3199
3200 remap_edge_change_prob (inlined_edge, e);
3201 if (es->predicate)
3202 {
3203 p = remap_predicate (info, callee_info,
3204 es->predicate, operand_map, offset_map,
3205 possible_truths, toplev_predicate);
3206 edge_set_predicate (e, &p);
3207 /* TODO: We should remove the edge for code that will be optimized
3208 out, but we need to keep verifiers and tree-inline happy.
3209 Make it cold for now. */
3210 if (false_predicate_p (&p))
3211 {
3212 e->count = 0;
3213 e->frequency = 0;
3214 }
3215 }
3216 else
3217 edge_set_predicate (e, toplev_predicate);
3218 }
3219 }
3220
3221 /* Same as remap_predicate, but set result into hint *HINT. */
3222
3223 static void
remap_hint_predicate(struct inline_summary * info,struct inline_summary * callee_info,struct predicate ** hint,vec<int> operand_map,vec<int> offset_map,clause_t possible_truths,struct predicate * toplev_predicate)3224 remap_hint_predicate (struct inline_summary *info,
3225 struct inline_summary *callee_info,
3226 struct predicate **hint,
3227 vec<int> operand_map,
3228 vec<int> offset_map,
3229 clause_t possible_truths,
3230 struct predicate *toplev_predicate)
3231 {
3232 predicate p;
3233
3234 if (!*hint)
3235 return;
3236 p = remap_predicate (info, callee_info,
3237 *hint,
3238 operand_map, offset_map,
3239 possible_truths, toplev_predicate);
3240 if (!false_predicate_p (&p) && !true_predicate_p (&p))
3241 {
3242 if (!*hint)
3243 set_hint_predicate (hint, p);
3244 else
3245 **hint = and_predicates (info->conds, *hint, &p);
3246 }
3247 }
3248
3249 /* We inlined EDGE. Update summary of the function we inlined into. */
3250
3251 void
inline_merge_summary(struct cgraph_edge * edge)3252 inline_merge_summary (struct cgraph_edge *edge)
3253 {
3254 struct inline_summary *callee_info = inline_summary (edge->callee);
3255 struct cgraph_node *to = (edge->caller->global.inlined_to
3256 ? edge->caller->global.inlined_to : edge->caller);
3257 struct inline_summary *info = inline_summary (to);
3258 clause_t clause = 0; /* not_inline is known to be false. */
3259 size_time_entry *e;
3260 vec<int> operand_map = vNULL;
3261 vec<int> offset_map = vNULL;
3262 int i;
3263 struct predicate toplev_predicate;
3264 struct predicate true_p = true_predicate ();
3265 struct inline_edge_summary *es = inline_edge_summary (edge);
3266
3267 if (es->predicate)
3268 toplev_predicate = *es->predicate;
3269 else
3270 toplev_predicate = true_predicate ();
3271
3272 if (ipa_node_params_vector.exists () && callee_info->conds)
3273 {
3274 struct ipa_edge_args *args = IPA_EDGE_REF (edge);
3275 int count = ipa_get_cs_argument_count (args);
3276 int i;
3277
3278 evaluate_properties_for_edge (edge, true, &clause, NULL, NULL, NULL);
3279 if (count)
3280 {
3281 operand_map.safe_grow_cleared (count);
3282 offset_map.safe_grow_cleared (count);
3283 }
3284 for (i = 0; i < count; i++)
3285 {
3286 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
3287 int map = -1;
3288
3289 /* TODO: handle non-NOPs when merging. */
3290 if (jfunc->type == IPA_JF_PASS_THROUGH)
3291 {
3292 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3293 map = ipa_get_jf_pass_through_formal_id (jfunc);
3294 if (!ipa_get_jf_pass_through_agg_preserved (jfunc))
3295 offset_map[i] = -1;
3296 }
3297 else if (jfunc->type == IPA_JF_ANCESTOR)
3298 {
3299 HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc);
3300 if (offset >= 0 && offset < INT_MAX)
3301 {
3302 map = ipa_get_jf_ancestor_formal_id (jfunc);
3303 if (!ipa_get_jf_ancestor_agg_preserved (jfunc))
3304 offset = -1;
3305 offset_map[i] = offset;
3306 }
3307 }
3308 operand_map[i] = map;
3309 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
3310 }
3311 }
3312 for (i = 0; vec_safe_iterate (callee_info->entry, i, &e); i++)
3313 {
3314 struct predicate p = remap_predicate (info, callee_info,
3315 &e->predicate, operand_map,
3316 offset_map, clause,
3317 &toplev_predicate);
3318 if (!false_predicate_p (&p))
3319 {
3320 gcov_type add_time = ((gcov_type) e->time * edge->frequency
3321 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
3322 int prob = predicate_probability (callee_info->conds,
3323 &e->predicate,
3324 clause, es->param);
3325 add_time = ((gcov_type) add_time * prob) / REG_BR_PROB_BASE;
3326 if (add_time > MAX_TIME * INLINE_TIME_SCALE)
3327 add_time = MAX_TIME * INLINE_TIME_SCALE;
3328 if (prob != REG_BR_PROB_BASE
3329 && dump_file && (dump_flags & TDF_DETAILS))
3330 {
3331 fprintf (dump_file, "\t\tScaling time by probability:%f\n",
3332 (double) prob / REG_BR_PROB_BASE);
3333 }
3334 account_size_time (info, e->size, add_time, &p);
3335 }
3336 }
3337 remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
3338 offset_map, clause, &toplev_predicate);
3339 remap_hint_predicate (info, callee_info,
3340 &callee_info->loop_iterations,
3341 operand_map, offset_map, clause, &toplev_predicate);
3342 remap_hint_predicate (info, callee_info,
3343 &callee_info->loop_stride,
3344 operand_map, offset_map, clause, &toplev_predicate);
3345 remap_hint_predicate (info, callee_info,
3346 &callee_info->array_index,
3347 operand_map, offset_map, clause, &toplev_predicate);
3348
3349 inline_update_callee_summaries (edge->callee,
3350 inline_edge_summary (edge)->loop_depth);
3351
3352 /* We do not maintain predicates of inlined edges, free it. */
3353 edge_set_predicate (edge, &true_p);
3354 /* Similarly remove param summaries. */
3355 es->param.release ();
3356 operand_map.release ();
3357 offset_map.release ();
3358 }
3359
3360 /* For performance reasons inline_merge_summary is not updating overall size
3361 and time. Recompute it. */
3362
3363 void
inline_update_overall_summary(struct cgraph_node * node)3364 inline_update_overall_summary (struct cgraph_node *node)
3365 {
3366 struct inline_summary *info = inline_summary (node);
3367 size_time_entry *e;
3368 int i;
3369
3370 info->size = 0;
3371 info->time = 0;
3372 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
3373 {
3374 info->size += e->size, info->time += e->time;
3375 if (info->time > MAX_TIME * INLINE_TIME_SCALE)
3376 info->time = MAX_TIME * INLINE_TIME_SCALE;
3377 }
3378 estimate_calls_size_and_time (node, &info->size, &info->time, NULL,
3379 ~(clause_t) (1 << predicate_false_condition),
3380 vNULL, vNULL, vNULL);
3381 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
3382 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
3383 }
3384
3385 /* Return hints derrived from EDGE. */
3386 int
simple_edge_hints(struct cgraph_edge * edge)3387 simple_edge_hints (struct cgraph_edge *edge)
3388 {
3389 int hints = 0;
3390 struct cgraph_node *to = (edge->caller->global.inlined_to
3391 ? edge->caller->global.inlined_to : edge->caller);
3392 if (inline_summary (to)->scc_no
3393 && inline_summary (to)->scc_no == inline_summary (edge->callee)->scc_no
3394 && !cgraph_edge_recursive_p (edge))
3395 hints |= INLINE_HINT_same_scc;
3396
3397 if (to->symbol.lto_file_data && edge->callee->symbol.lto_file_data
3398 && to->symbol.lto_file_data != edge->callee->symbol.lto_file_data)
3399 hints |= INLINE_HINT_cross_module;
3400
3401 return hints;
3402 }
3403
3404 /* Estimate the time cost for the caller when inlining EDGE.
3405 Only to be called via estimate_edge_time, that handles the
3406 caching mechanism.
3407
3408 When caching, also update the cache entry. Compute both time and
3409 size, since we always need both metrics eventually. */
3410
3411 int
do_estimate_edge_time(struct cgraph_edge * edge)3412 do_estimate_edge_time (struct cgraph_edge *edge)
3413 {
3414 int time;
3415 int size;
3416 inline_hints hints;
3417 struct cgraph_node *callee;
3418 clause_t clause;
3419 vec<tree> known_vals;
3420 vec<tree> known_binfos;
3421 vec<ipa_agg_jump_function_p> known_aggs;
3422 struct inline_edge_summary *es = inline_edge_summary (edge);
3423
3424 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3425
3426 gcc_checking_assert (edge->inline_failed);
3427 evaluate_properties_for_edge (edge, true,
3428 &clause, &known_vals, &known_binfos,
3429 &known_aggs);
3430 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3431 known_aggs, &size, &time, &hints, es->param);
3432 known_vals.release ();
3433 known_binfos.release ();
3434 known_aggs.release ();
3435 gcc_checking_assert (size >= 0);
3436 gcc_checking_assert (time >= 0);
3437
3438 /* When caching, update the cache entry. */
3439 if (edge_growth_cache.exists ())
3440 {
3441 if ((int) edge_growth_cache.length () <= edge->uid)
3442 edge_growth_cache.safe_grow_cleared (cgraph_edge_max_uid);
3443 edge_growth_cache[edge->uid].time = time + (time >= 0);
3444
3445 edge_growth_cache[edge->uid].size = size + (size >= 0);
3446 hints |= simple_edge_hints (edge);
3447 edge_growth_cache[edge->uid].hints = hints + 1;
3448 }
3449 return time;
3450 }
3451
3452
3453 /* Return estimated callee growth after inlining EDGE.
3454 Only to be called via estimate_edge_size. */
3455
3456 int
do_estimate_edge_size(struct cgraph_edge * edge)3457 do_estimate_edge_size (struct cgraph_edge *edge)
3458 {
3459 int size;
3460 struct cgraph_node *callee;
3461 clause_t clause;
3462 vec<tree> known_vals;
3463 vec<tree> known_binfos;
3464 vec<ipa_agg_jump_function_p> known_aggs;
3465
3466 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3467
3468 if (edge_growth_cache.exists ())
3469 {
3470 do_estimate_edge_time (edge);
3471 size = edge_growth_cache[edge->uid].size;
3472 gcc_checking_assert (size);
3473 return size - (size > 0);
3474 }
3475
3476 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3477
3478 /* Early inliner runs without caching, go ahead and do the dirty work. */
3479 gcc_checking_assert (edge->inline_failed);
3480 evaluate_properties_for_edge (edge, true,
3481 &clause, &known_vals, &known_binfos,
3482 &known_aggs);
3483 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3484 known_aggs, &size, NULL, NULL, vNULL);
3485 known_vals.release ();
3486 known_binfos.release ();
3487 known_aggs.release ();
3488 return size;
3489 }
3490
3491
3492 /* Estimate the growth of the caller when inlining EDGE.
3493 Only to be called via estimate_edge_size. */
3494
3495 inline_hints
do_estimate_edge_hints(struct cgraph_edge * edge)3496 do_estimate_edge_hints (struct cgraph_edge *edge)
3497 {
3498 inline_hints hints;
3499 struct cgraph_node *callee;
3500 clause_t clause;
3501 vec<tree> known_vals;
3502 vec<tree> known_binfos;
3503 vec<ipa_agg_jump_function_p> known_aggs;
3504
3505 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3506
3507 if (edge_growth_cache.exists ())
3508 {
3509 do_estimate_edge_time (edge);
3510 hints = edge_growth_cache[edge->uid].hints;
3511 gcc_checking_assert (hints);
3512 return hints - 1;
3513 }
3514
3515 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
3516
3517 /* Early inliner runs without caching, go ahead and do the dirty work. */
3518 gcc_checking_assert (edge->inline_failed);
3519 evaluate_properties_for_edge (edge, true,
3520 &clause, &known_vals, &known_binfos,
3521 &known_aggs);
3522 estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
3523 known_aggs, NULL, NULL, &hints, vNULL);
3524 known_vals.release ();
3525 known_binfos.release ();
3526 known_aggs.release ();
3527 hints |= simple_edge_hints (edge);
3528 return hints;
3529 }
3530
3531
3532 /* Estimate self time of the function NODE after inlining EDGE. */
3533
3534 int
estimate_time_after_inlining(struct cgraph_node * node,struct cgraph_edge * edge)3535 estimate_time_after_inlining (struct cgraph_node *node,
3536 struct cgraph_edge *edge)
3537 {
3538 struct inline_edge_summary *es = inline_edge_summary (edge);
3539 if (!es->predicate || !false_predicate_p (es->predicate))
3540 {
3541 gcov_type time =
3542 inline_summary (node)->time + estimate_edge_time (edge);
3543 if (time < 0)
3544 time = 0;
3545 if (time > MAX_TIME)
3546 time = MAX_TIME;
3547 return time;
3548 }
3549 return inline_summary (node)->time;
3550 }
3551
3552
3553 /* Estimate the size of NODE after inlining EDGE which should be an
3554 edge to either NODE or a call inlined into NODE. */
3555
3556 int
estimate_size_after_inlining(struct cgraph_node * node,struct cgraph_edge * edge)3557 estimate_size_after_inlining (struct cgraph_node *node,
3558 struct cgraph_edge *edge)
3559 {
3560 struct inline_edge_summary *es = inline_edge_summary (edge);
3561 if (!es->predicate || !false_predicate_p (es->predicate))
3562 {
3563 int size = inline_summary (node)->size + estimate_edge_growth (edge);
3564 gcc_assert (size >= 0);
3565 return size;
3566 }
3567 return inline_summary (node)->size;
3568 }
3569
3570
3571 struct growth_data
3572 {
3573 bool self_recursive;
3574 int growth;
3575 };
3576
3577
3578 /* Worker for do_estimate_growth. Collect growth for all callers. */
3579
3580 static bool
do_estimate_growth_1(struct cgraph_node * node,void * data)3581 do_estimate_growth_1 (struct cgraph_node *node, void *data)
3582 {
3583 struct cgraph_edge *e;
3584 struct growth_data *d = (struct growth_data *) data;
3585
3586 for (e = node->callers; e; e = e->next_caller)
3587 {
3588 gcc_checking_assert (e->inline_failed);
3589
3590 if (e->caller == node
3591 || (e->caller->global.inlined_to
3592 && e->caller->global.inlined_to == node))
3593 d->self_recursive = true;
3594 d->growth += estimate_edge_growth (e);
3595 }
3596 return false;
3597 }
3598
3599
3600 /* Estimate the growth caused by inlining NODE into all callees. */
3601
3602 int
do_estimate_growth(struct cgraph_node * node)3603 do_estimate_growth (struct cgraph_node *node)
3604 {
3605 struct growth_data d = { 0, false };
3606 struct inline_summary *info = inline_summary (node);
3607
3608 cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
3609
3610 /* For self recursive functions the growth estimation really should be
3611 infinity. We don't want to return very large values because the growth
3612 plays various roles in badness computation fractions. Be sure to not
3613 return zero or negative growths. */
3614 if (d.self_recursive)
3615 d.growth = d.growth < info->size ? info->size : d.growth;
3616 else if (DECL_EXTERNAL (node->symbol.decl))
3617 ;
3618 else
3619 {
3620 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node))
3621 d.growth -= info->size;
3622 /* COMDAT functions are very often not shared across multiple units
3623 since they come from various template instantiations.
3624 Take this into account. */
3625 else if (DECL_COMDAT (node->symbol.decl)
3626 && cgraph_can_remove_if_no_direct_calls_p (node))
3627 d.growth -= (info->size
3628 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
3629 + 50) / 100;
3630 }
3631
3632 if (node_growth_cache.exists ())
3633 {
3634 if ((int) node_growth_cache.length () <= node->uid)
3635 node_growth_cache.safe_grow_cleared (cgraph_max_uid);
3636 node_growth_cache[node->uid] = d.growth + (d.growth >= 0);
3637 }
3638 return d.growth;
3639 }
3640
3641
3642 /* This function performs intraprocedural analysis in NODE that is required to
3643 inline indirect calls. */
3644
3645 static void
inline_indirect_intraprocedural_analysis(struct cgraph_node * node)3646 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
3647 {
3648 ipa_analyze_node (node);
3649 if (dump_file && (dump_flags & TDF_DETAILS))
3650 {
3651 ipa_print_node_params (dump_file, node);
3652 ipa_print_node_jump_functions (dump_file, node);
3653 }
3654 }
3655
3656
3657 /* Note function body size. */
3658
3659 static void
inline_analyze_function(struct cgraph_node * node)3660 inline_analyze_function (struct cgraph_node *node)
3661 {
3662 push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
3663
3664 if (dump_file)
3665 fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
3666 cgraph_node_name (node), node->uid);
3667 if (optimize && !node->thunk.thunk_p)
3668 inline_indirect_intraprocedural_analysis (node);
3669 compute_inline_parameters (node, false);
3670
3671 pop_cfun ();
3672 }
3673
3674
3675 /* Called when new function is inserted to callgraph late. */
3676
3677 static void
add_new_function(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)3678 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
3679 {
3680 inline_analyze_function (node);
3681 }
3682
3683
3684 /* Note function body size. */
3685
3686 void
inline_generate_summary(void)3687 inline_generate_summary (void)
3688 {
3689 struct cgraph_node *node;
3690
3691 function_insertion_hook_holder =
3692 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3693
3694 ipa_register_cgraph_hooks ();
3695 inline_free_summary ();
3696
3697 FOR_EACH_DEFINED_FUNCTION (node)
3698 if (!node->alias)
3699 inline_analyze_function (node);
3700 }
3701
3702
3703 /* Read predicate from IB. */
3704
3705 static struct predicate
read_predicate(struct lto_input_block * ib)3706 read_predicate (struct lto_input_block *ib)
3707 {
3708 struct predicate out;
3709 clause_t clause;
3710 int k = 0;
3711
3712 do
3713 {
3714 gcc_assert (k <= MAX_CLAUSES);
3715 clause = out.clause[k++] = streamer_read_uhwi (ib);
3716 }
3717 while (clause);
3718
3719 /* Zero-initialize the remaining clauses in OUT. */
3720 while (k <= MAX_CLAUSES)
3721 out.clause[k++] = 0;
3722
3723 return out;
3724 }
3725
3726
3727 /* Write inline summary for edge E to OB. */
3728
3729 static void
read_inline_edge_summary(struct lto_input_block * ib,struct cgraph_edge * e)3730 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
3731 {
3732 struct inline_edge_summary *es = inline_edge_summary (e);
3733 struct predicate p;
3734 int length, i;
3735
3736 es->call_stmt_size = streamer_read_uhwi (ib);
3737 es->call_stmt_time = streamer_read_uhwi (ib);
3738 es->loop_depth = streamer_read_uhwi (ib);
3739 p = read_predicate (ib);
3740 edge_set_predicate (e, &p);
3741 length = streamer_read_uhwi (ib);
3742 if (length)
3743 {
3744 es->param.safe_grow_cleared (length);
3745 for (i = 0; i < length; i++)
3746 es->param[i].change_prob = streamer_read_uhwi (ib);
3747 }
3748 }
3749
3750
3751 /* Stream in inline summaries from the section. */
3752
3753 static void
inline_read_section(struct lto_file_decl_data * file_data,const char * data,size_t len)3754 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
3755 size_t len)
3756 {
3757 const struct lto_function_header *header =
3758 (const struct lto_function_header *) data;
3759 const int cfg_offset = sizeof (struct lto_function_header);
3760 const int main_offset = cfg_offset + header->cfg_size;
3761 const int string_offset = main_offset + header->main_size;
3762 struct data_in *data_in;
3763 struct lto_input_block ib;
3764 unsigned int i, count2, j;
3765 unsigned int f_count;
3766
3767 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
3768 header->main_size);
3769
3770 data_in =
3771 lto_data_in_create (file_data, (const char *) data + string_offset,
3772 header->string_size, vNULL);
3773 f_count = streamer_read_uhwi (&ib);
3774 for (i = 0; i < f_count; i++)
3775 {
3776 unsigned int index;
3777 struct cgraph_node *node;
3778 struct inline_summary *info;
3779 lto_symtab_encoder_t encoder;
3780 struct bitpack_d bp;
3781 struct cgraph_edge *e;
3782 predicate p;
3783
3784 index = streamer_read_uhwi (&ib);
3785 encoder = file_data->symtab_node_encoder;
3786 node = cgraph (lto_symtab_encoder_deref (encoder, index));
3787 info = inline_summary (node);
3788
3789 info->estimated_stack_size
3790 = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
3791 info->size = info->self_size = streamer_read_uhwi (&ib);
3792 info->time = info->self_time = streamer_read_uhwi (&ib);
3793
3794 bp = streamer_read_bitpack (&ib);
3795 info->inlinable = bp_unpack_value (&bp, 1);
3796
3797 count2 = streamer_read_uhwi (&ib);
3798 gcc_assert (!info->conds);
3799 for (j = 0; j < count2; j++)
3800 {
3801 struct condition c;
3802 c.operand_num = streamer_read_uhwi (&ib);
3803 c.code = (enum tree_code) streamer_read_uhwi (&ib);
3804 c.val = stream_read_tree (&ib, data_in);
3805 bp = streamer_read_bitpack (&ib);
3806 c.agg_contents = bp_unpack_value (&bp, 1);
3807 c.by_ref = bp_unpack_value (&bp, 1);
3808 if (c.agg_contents)
3809 c.offset = streamer_read_uhwi (&ib);
3810 vec_safe_push (info->conds, c);
3811 }
3812 count2 = streamer_read_uhwi (&ib);
3813 gcc_assert (!info->entry);
3814 for (j = 0; j < count2; j++)
3815 {
3816 struct size_time_entry e;
3817
3818 e.size = streamer_read_uhwi (&ib);
3819 e.time = streamer_read_uhwi (&ib);
3820 e.predicate = read_predicate (&ib);
3821
3822 vec_safe_push (info->entry, e);
3823 }
3824
3825 p = read_predicate (&ib);
3826 set_hint_predicate (&info->loop_iterations, p);
3827 p = read_predicate (&ib);
3828 set_hint_predicate (&info->loop_stride, p);
3829 p = read_predicate (&ib);
3830 set_hint_predicate (&info->array_index, p);
3831 for (e = node->callees; e; e = e->next_callee)
3832 read_inline_edge_summary (&ib, e);
3833 for (e = node->indirect_calls; e; e = e->next_callee)
3834 read_inline_edge_summary (&ib, e);
3835 }
3836
3837 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
3838 len);
3839 lto_data_in_delete (data_in);
3840 }
3841
3842
3843 /* Read inline summary. Jump functions are shared among ipa-cp
3844 and inliner, so when ipa-cp is active, we don't need to write them
3845 twice. */
3846
3847 void
inline_read_summary(void)3848 inline_read_summary (void)
3849 {
3850 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
3851 struct lto_file_decl_data *file_data;
3852 unsigned int j = 0;
3853
3854 inline_summary_alloc ();
3855
3856 while ((file_data = file_data_vec[j++]))
3857 {
3858 size_t len;
3859 const char *data = lto_get_section_data (file_data,
3860 LTO_section_inline_summary,
3861 NULL, &len);
3862 if (data)
3863 inline_read_section (file_data, data, len);
3864 else
3865 /* Fatal error here. We do not want to support compiling ltrans units
3866 with different version of compiler or different flags than the WPA
3867 unit, so this should never happen. */
3868 fatal_error ("ipa inline summary is missing in input file");
3869 }
3870 if (optimize)
3871 {
3872 ipa_register_cgraph_hooks ();
3873 if (!flag_ipa_cp)
3874 ipa_prop_read_jump_functions ();
3875 }
3876 function_insertion_hook_holder =
3877 cgraph_add_function_insertion_hook (&add_new_function, NULL);
3878 }
3879
3880
3881 /* Write predicate P to OB. */
3882
3883 static void
write_predicate(struct output_block * ob,struct predicate * p)3884 write_predicate (struct output_block *ob, struct predicate *p)
3885 {
3886 int j;
3887 if (p)
3888 for (j = 0; p->clause[j]; j++)
3889 {
3890 gcc_assert (j < MAX_CLAUSES);
3891 streamer_write_uhwi (ob, p->clause[j]);
3892 }
3893 streamer_write_uhwi (ob, 0);
3894 }
3895
3896
3897 /* Write inline summary for edge E to OB. */
3898
3899 static void
write_inline_edge_summary(struct output_block * ob,struct cgraph_edge * e)3900 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
3901 {
3902 struct inline_edge_summary *es = inline_edge_summary (e);
3903 int i;
3904
3905 streamer_write_uhwi (ob, es->call_stmt_size);
3906 streamer_write_uhwi (ob, es->call_stmt_time);
3907 streamer_write_uhwi (ob, es->loop_depth);
3908 write_predicate (ob, es->predicate);
3909 streamer_write_uhwi (ob, es->param.length ());
3910 for (i = 0; i < (int) es->param.length (); i++)
3911 streamer_write_uhwi (ob, es->param[i].change_prob);
3912 }
3913
3914
3915 /* Write inline summary for node in SET.
3916 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3917 active, we don't need to write them twice. */
3918
3919 void
inline_write_summary(void)3920 inline_write_summary (void)
3921 {
3922 struct cgraph_node *node;
3923 struct output_block *ob = create_output_block (LTO_section_inline_summary);
3924 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
3925 unsigned int count = 0;
3926 int i;
3927
3928 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
3929 {
3930 symtab_node snode = lto_symtab_encoder_deref (encoder, i);
3931 cgraph_node *cnode = dyn_cast <cgraph_node> (snode);
3932 if (cnode && cnode->analyzed)
3933 count++;
3934 }
3935 streamer_write_uhwi (ob, count);
3936
3937 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
3938 {
3939 symtab_node snode = lto_symtab_encoder_deref (encoder, i);
3940 cgraph_node *cnode = dyn_cast <cgraph_node> (snode);
3941 if (cnode && (node = cnode)->analyzed)
3942 {
3943 struct inline_summary *info = inline_summary (node);
3944 struct bitpack_d bp;
3945 struct cgraph_edge *edge;
3946 int i;
3947 size_time_entry *e;
3948 struct condition *c;
3949
3950 streamer_write_uhwi (ob,
3951 lto_symtab_encoder_encode (encoder,
3952 (symtab_node)
3953 node));
3954 streamer_write_hwi (ob, info->estimated_self_stack_size);
3955 streamer_write_hwi (ob, info->self_size);
3956 streamer_write_hwi (ob, info->self_time);
3957 bp = bitpack_create (ob->main_stream);
3958 bp_pack_value (&bp, info->inlinable, 1);
3959 streamer_write_bitpack (&bp);
3960 streamer_write_uhwi (ob, vec_safe_length (info->conds));
3961 for (i = 0; vec_safe_iterate (info->conds, i, &c); i++)
3962 {
3963 streamer_write_uhwi (ob, c->operand_num);
3964 streamer_write_uhwi (ob, c->code);
3965 stream_write_tree (ob, c->val, true);
3966 bp = bitpack_create (ob->main_stream);
3967 bp_pack_value (&bp, c->agg_contents, 1);
3968 bp_pack_value (&bp, c->by_ref, 1);
3969 streamer_write_bitpack (&bp);
3970 if (c->agg_contents)
3971 streamer_write_uhwi (ob, c->offset);
3972 }
3973 streamer_write_uhwi (ob, vec_safe_length (info->entry));
3974 for (i = 0; vec_safe_iterate (info->entry, i, &e); i++)
3975 {
3976 streamer_write_uhwi (ob, e->size);
3977 streamer_write_uhwi (ob, e->time);
3978 write_predicate (ob, &e->predicate);
3979 }
3980 write_predicate (ob, info->loop_iterations);
3981 write_predicate (ob, info->loop_stride);
3982 write_predicate (ob, info->array_index);
3983 for (edge = node->callees; edge; edge = edge->next_callee)
3984 write_inline_edge_summary (ob, edge);
3985 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
3986 write_inline_edge_summary (ob, edge);
3987 }
3988 }
3989 streamer_write_char_stream (ob->main_stream, 0);
3990 produce_asm (ob, NULL);
3991 destroy_output_block (ob);
3992
3993 if (optimize && !flag_ipa_cp)
3994 ipa_prop_write_jump_functions ();
3995 }
3996
3997
3998 /* Release inline summary. */
3999
4000 void
inline_free_summary(void)4001 inline_free_summary (void)
4002 {
4003 struct cgraph_node *node;
4004 if (!inline_edge_summary_vec.exists ())
4005 return;
4006 FOR_EACH_DEFINED_FUNCTION (node)
4007 reset_inline_summary (node);
4008 if (function_insertion_hook_holder)
4009 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
4010 function_insertion_hook_holder = NULL;
4011 if (node_removal_hook_holder)
4012 cgraph_remove_node_removal_hook (node_removal_hook_holder);
4013 node_removal_hook_holder = NULL;
4014 if (edge_removal_hook_holder)
4015 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
4016 edge_removal_hook_holder = NULL;
4017 if (node_duplication_hook_holder)
4018 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
4019 node_duplication_hook_holder = NULL;
4020 if (edge_duplication_hook_holder)
4021 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
4022 edge_duplication_hook_holder = NULL;
4023 vec_free (inline_summary_vec);
4024 inline_edge_summary_vec.release ();
4025 if (edge_predicate_pool)
4026 free_alloc_pool (edge_predicate_pool);
4027 edge_predicate_pool = 0;
4028 }
4029