OSDN Git Service

2011-11-09 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / ipa-inline-analysis.c
1 /* Inlining decision heuristics.
2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /* Analysis used by the inliner and other passes limiting code size growth.
23
24    We estimate for each function
25      - function body size
26      - average function execution time
27      - inlining size benefit (that is how much of function body size
28        and its call sequence is expected to disappear by inlining)
29      - inlining time benefit
30      - function frame size
31    For each call
32      - call statement size and time
33
34    inlinie_summary datastructures store above information locally (i.e.
35    parameters of the function itself) and globally (i.e. parameters of
36    the function created by applying all the inline decisions already
37    present in the callgraph).
38
39    We provide accestor to the inline_summary datastructure and
40    basic logic updating the parameters when inlining is performed. 
41
42    The summaries are context sensitive.  Context means
43      1) partial assignment of known constant values of operands
44      2) whether function is inlined into the call or not.
45    It is easy to add more variants.  To represent function size and time
46    that depends on context (i.e. it is known to be optimized away when
47    context is known either by inlining or from IP-CP and clonning),
48    we use predicates. Predicates are logical formulas in
49    conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
50    specifying what conditions must be true. Conditions are simple test
51    of the form described above.
52
53    In order to make predicate (possibly) true, all of its clauses must
54    be (possibly) true. To make clause (possibly) true, one of conditions
55    it mentions must be (possibly) true.  There are fixed bounds on
56    number of clauses and conditions and all the manipulation functions
57    are conservative in positive direction. I.e. we may lose precision
58    by thinking that predicate may be true even when it is not.
59
60    estimate_edge_size and estimate_edge_growth can be used to query
61    function size/time in the given context.  inline_merge_summary merges
62    properties of caller and callee after inlining.
63
64    Finally pass_inline_parameters is exported.  This is used to drive
65    computation of function parameters used by the early inliner. IPA
66    inlined performs analysis via its analyze_function method. */
67
68 #include "config.h"
69 #include "system.h"
70 #include "coretypes.h"
71 #include "tm.h"
72 #include "tree.h"
73 #include "tree-inline.h"
74 #include "langhooks.h"
75 #include "flags.h"
76 #include "cgraph.h"
77 #include "diagnostic.h"
78 #include "gimple-pretty-print.h"
79 #include "timevar.h"
80 #include "params.h"
81 #include "tree-pass.h"
82 #include "coverage.h"
83 #include "ggc.h"
84 #include "tree-flow.h"
85 #include "ipa-prop.h"
86 #include "lto-streamer.h"
87 #include "data-streamer.h"
88 #include "tree-streamer.h"
89 #include "ipa-inline.h"
90 #include "alloc-pool.h"
91
92 /* Estimate runtime of function can easilly run into huge numbers with many
93    nested loops.  Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
94    integer.  For anything larger we use gcov_type.  */
95 #define MAX_TIME 500000
96
97 /* Number of bits in integer, but we really want to be stable across different
98    hosts.  */
99 #define NUM_CONDITIONS 32
100
101 enum predicate_conditions
102 {
103   predicate_false_condition = 0,
104   predicate_not_inlined_condition = 1,
105   predicate_first_dynamic_condition = 2
106 };
107
108 /* Special condition code we use to represent test that operand is compile time
109    constant.  */
110 #define IS_NOT_CONSTANT ERROR_MARK
111 /* Special condition code we use to represent test that operand is not changed
112    across invocation of the function.  When operand IS_NOT_CONSTANT it is always
113    CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
114    of executions even when they are not compile time constants.  */
115 #define CHANGED IDENTIFIER_NODE
116
117 /* Holders of ipa cgraph hooks: */
118 static struct cgraph_node_hook_list *function_insertion_hook_holder;
119 static struct cgraph_node_hook_list *node_removal_hook_holder;
120 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
121 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
122 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
123 static void inline_node_removal_hook (struct cgraph_node *, void *);
124 static void inline_node_duplication_hook (struct cgraph_node *,
125                                           struct cgraph_node *, void *);
126 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
127 static void inline_edge_duplication_hook (struct cgraph_edge *,
128                                           struct cgraph_edge *,
129                                           void *);
130
131 /* VECtor holding inline summaries.  
132    In GGC memory because conditions might point to constant trees.  */
133 VEC(inline_summary_t,gc) *inline_summary_vec;
134 VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
135
136 /* Cached node/edge growths.  */
137 VEC(int,heap) *node_growth_cache;
138 VEC(edge_growth_cache_entry,heap) *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
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
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
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
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
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 static inline struct predicate
202 not_inlined_predicate (void)
203 {
204   return single_cond_predicate (predicate_not_inlined_condition);
205 }
206
207
208 /* Add condition to condition list CONDS.  */
209
210 static struct predicate
211 add_condition (struct inline_summary *summary, int operand_num,
212                enum tree_code code, tree val)
213 {
214   int i;
215   struct condition *c;
216   struct condition new_cond;
217
218   for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++)
219     {
220       if (c->operand_num == operand_num
221           && c->code == code
222           && c->val == val)
223         return single_cond_predicate (i + predicate_first_dynamic_condition);
224     }
225   /* Too many conditions.  Give up and return constant true.  */
226   if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
227     return true_predicate ();
228
229   new_cond.operand_num = operand_num;
230   new_cond.code = code;
231   new_cond.val = val;
232   VEC_safe_push (condition, gc, summary->conds, &new_cond);
233   return single_cond_predicate (i + predicate_first_dynamic_condition);
234 }
235
236
237 /* Add clause CLAUSE into the predicate P.  */
238
239 static inline void
240 add_clause (conditions conditions, struct predicate *p, clause_t clause)
241 {
242   int i;
243   int i2;
244   int insert_here = -1;
245   int c1, c2;
246
247   /* True clause.  */
248   if (!clause)
249     return;
250
251   /* False clause makes the whole predicate false.  Kill the other variants.  */
252   if (clause == (1 << predicate_false_condition))
253     {
254       p->clause[0] = (1 << predicate_false_condition);
255       p->clause[1] = 0;
256       return;
257     }
258   if (false_predicate_p (p))
259     return;
260
261   /* No one should be sily enough to add false into nontrivial clauses.  */
262   gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
263
264   /* Look where to insert the clause.  At the same time prune out
265      clauses of P that are implied by the new clause and thus
266      redundant.  */
267   for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
268     {
269       p->clause[i2] = p->clause[i];
270
271       if (!p->clause[i])
272         break;
273
274       /* If p->clause[i] implies clause, there is nothing to add.  */
275       if ((p->clause[i] & clause) == p->clause[i])
276         {
277           /* We had nothing to add, none of clauses should've become
278              redundant.  */
279           gcc_checking_assert (i == i2);
280           return;
281         }
282
283       if (p->clause[i] < clause && insert_here < 0)
284         insert_here = i2;
285
286       /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
287          Otherwise the p->clause[i] has to stay.  */
288       if ((p->clause[i] & clause) != clause)
289         i2++;
290     }
291
292   /* Look for clauses that are obviously true.  I.e.
293      op0 == 5 || op0 != 5.  */
294   for (c1 = predicate_first_dynamic_condition; c1 < NUM_CONDITIONS; c1++)
295     {
296       condition *cc1;
297       if (!(clause & (1 << c1)))
298         continue;
299       cc1 = VEC_index (condition,
300                        conditions,
301                        c1 - predicate_first_dynamic_condition);
302       /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
303          and thus there is no point for looking for them.  */
304       if (cc1->code == CHANGED
305           || cc1->code == IS_NOT_CONSTANT)
306         continue;
307       for (c2 = c1 + 1; c2 <= NUM_CONDITIONS; c2++)
308         if (clause & (1 << c2))
309           {
310             condition *cc1 = VEC_index (condition,
311                                         conditions,
312                                         c1 - predicate_first_dynamic_condition);
313             condition *cc2 = VEC_index (condition,
314                                         conditions,
315                                         c2 - predicate_first_dynamic_condition);
316             if (cc1->operand_num == cc2->operand_num
317                 && cc1->val == cc2->val
318                 && cc2->code != IS_NOT_CONSTANT
319                 && cc2->code != CHANGED
320                 && cc1->code == invert_tree_comparison 
321                     (cc2->code,
322                      HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1->val)))))
323               return;
324           }
325     }
326         
327
328   /* We run out of variants.  Be conservative in positive direction.  */
329   if (i2 == MAX_CLAUSES)
330     return;
331   /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
332   p->clause[i2 + 1] = 0;
333   if (insert_here >= 0)
334     for (;i2 > insert_here; i2--)
335       p->clause[i2] = p->clause[i2 - 1];
336   else
337     insert_here = i2;
338   p->clause[insert_here] = clause;
339 }
340
341
342 /* Return P & P2.  */
343
344 static struct predicate
345 and_predicates (conditions conditions,
346                 struct predicate *p, struct predicate *p2)
347 {
348   struct predicate out = *p;
349   int i;
350
351   /* Avoid busy work.  */
352   if (false_predicate_p (p2) || true_predicate_p (p))
353     return *p2;
354   if (false_predicate_p (p) || true_predicate_p (p2))
355     return *p;
356
357   /* See how far predicates match.  */
358   for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
359     {
360       gcc_checking_assert (i < MAX_CLAUSES);
361     }
362     
363   /* Combine the predicates rest.  */
364   for (; p2->clause[i]; i++)
365     {
366       gcc_checking_assert (i < MAX_CLAUSES);
367       add_clause (conditions, &out, p2->clause[i]);
368     }
369   return out;
370 }
371
372
373 /* Return true if predicates are obviously equal.  */
374
375 static inline bool
376 predicates_equal_p (struct predicate *p, struct predicate *p2)
377 {
378   int i;
379   for (i = 0; p->clause[i]; i++)
380     {
381       gcc_checking_assert (i < MAX_CLAUSES);
382       gcc_checking_assert (p->clause [i] > p->clause[i + 1]);
383       gcc_checking_assert (!p2->clause[i]
384                            || p2->clause [i] > p2->clause[i + 1]);
385       if (p->clause[i] != p2->clause[i])
386         return false;
387     }
388   return !p2->clause[i];
389 }
390
391
392 /* Return P | P2.  */
393
394 static struct predicate
395 or_predicates (conditions conditions, struct predicate *p, struct predicate *p2)
396 {
397   struct predicate out = true_predicate ();
398   int i,j;
399
400   /* Avoid busy work.  */
401   if (false_predicate_p (p2) || true_predicate_p (p))
402     return *p;
403   if (false_predicate_p (p) || true_predicate_p (p2))
404     return *p2;
405   if (predicates_equal_p (p, p2))
406     return *p;
407
408   /* OK, combine the predicates.  */
409   for (i = 0; p->clause[i]; i++)
410     for (j = 0; p2->clause[j]; j++)
411       {
412         gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
413         add_clause (conditions, &out, p->clause[i] | p2->clause[j]);
414       }
415   return out;
416 }
417
418
419 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
420    if predicate P is known to be false.  */
421
422 static bool
423 evaluate_predicate (struct predicate *p, clause_t possible_truths)
424 {
425   int i;
426
427   /* True remains true.  */
428   if (true_predicate_p (p))
429     return true;
430
431   gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
432
433   /* See if we can find clause we can disprove.  */
434   for (i = 0; p->clause[i]; i++)
435     {
436       gcc_checking_assert (i < MAX_CLAUSES);
437       if (!(p->clause[i] & possible_truths))
438         return false;
439     }
440   return true;
441 }
442
443 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
444    instruction will be recomputed per invocation of the inlined call.  */
445
446 static int
447 predicate_probability (conditions conds,
448                        struct predicate *p, clause_t possible_truths,
449                        VEC (inline_param_summary_t, heap) *inline_param_summary)
450 {
451   int i;
452   int combined_prob = REG_BR_PROB_BASE;
453
454   /* True remains true.  */
455   if (true_predicate_p (p))
456     return REG_BR_PROB_BASE;
457
458   if (false_predicate_p (p))
459     return 0;
460
461   gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
462
463   /* See if we can find clause we can disprove.  */
464   for (i = 0; p->clause[i]; i++)
465     {
466       gcc_checking_assert (i < MAX_CLAUSES);
467       if (!(p->clause[i] & possible_truths))
468         return 0;
469       else
470         {
471           int this_prob = 0;
472           int i2;
473           if (!inline_param_summary)
474             return REG_BR_PROB_BASE;
475           for (i2 = 0; i2 < NUM_CONDITIONS; i2++)
476             if ((p->clause[i] & possible_truths) & (1 << i2))
477               {
478                 if (i2 >= predicate_first_dynamic_condition)
479                   {
480                     condition *c = VEC_index
481                                     (condition, conds,
482                                      i2 - predicate_first_dynamic_condition);
483                     if (c->code == CHANGED
484                         && (c->operand_num
485                             < (int) VEC_length (inline_param_summary_t,
486                                                 inline_param_summary)))
487                       {
488                         int iprob = VEC_index (inline_param_summary_t,
489                                                inline_param_summary,
490                                                c->operand_num)->change_prob;
491                         this_prob = MAX (this_prob, iprob);
492                       }
493                     else
494                       this_prob = REG_BR_PROB_BASE;
495                    }
496                  else
497                    this_prob = REG_BR_PROB_BASE;
498               }
499           combined_prob = MIN (this_prob, combined_prob);
500           if (!combined_prob)
501             return 0;
502         }
503     }
504   return combined_prob;
505 }
506
507
508 /* Dump conditional COND.  */
509
510 static void
511 dump_condition (FILE *f, conditions conditions, int cond)
512 {
513   condition *c;
514   if (cond == predicate_false_condition)
515     fprintf (f, "false");
516   else if (cond == predicate_not_inlined_condition)
517     fprintf (f, "not inlined");
518   else
519     {
520       c = VEC_index (condition, conditions,
521                      cond - predicate_first_dynamic_condition);
522       fprintf (f, "op%i", c->operand_num);
523       if (c->code == IS_NOT_CONSTANT)
524         {
525           fprintf (f, " not constant");
526           return;
527         }
528       if (c->code == CHANGED)
529         {
530           fprintf (f, " changed");
531           return;
532         }
533       fprintf (f, " %s ", op_symbol_code (c->code));
534       print_generic_expr (f, c->val, 1);
535     }
536 }
537
538
539 /* Dump clause CLAUSE.  */
540
541 static void
542 dump_clause (FILE *f, conditions conds, clause_t clause)
543 {
544   int i;
545   bool found = false;
546   fprintf (f, "(");
547   if (!clause)
548     fprintf (f, "true");
549   for (i = 0; i < NUM_CONDITIONS; i++)
550     if (clause & (1 << i))
551       {
552         if (found)
553           fprintf (f, " || ");
554         found = true;
555         dump_condition (f, conds, i);
556       }
557   fprintf (f, ")");
558 }
559
560
561 /* Dump predicate PREDICATE.  */
562
563 static void
564 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
565 {
566   int i;
567   if (true_predicate_p (pred))
568     dump_clause (f, conds, 0);
569   else
570     for (i = 0; pred->clause[i]; i++)
571       {
572         if (i)
573           fprintf (f, " && ");
574         dump_clause (f, conds, pred->clause[i]);
575       }
576   fprintf (f, "\n");
577 }
578
579
580 /* Record SIZE and TIME under condition PRED into the inline summary.  */
581
582 static void
583 account_size_time (struct inline_summary *summary, int size, int time,
584                    struct predicate *pred)
585 {
586   size_time_entry *e;
587   bool found = false;
588   int i;
589
590   if (false_predicate_p (pred))
591     return;
592
593   /* We need to create initial empty unconitional clause, but otherwie
594      we don't need to account empty times and sizes.  */
595   if (!size && !time && summary->entry)
596     return;
597
598   /* Watch overflow that might result from insane profiles.  */
599   if (time > MAX_TIME * INLINE_TIME_SCALE)
600     time = MAX_TIME * INLINE_TIME_SCALE;
601   gcc_assert (time >= 0);
602
603   for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
604     if (predicates_equal_p (&e->predicate, pred))
605       {
606         found = true;
607         break;
608       }
609   if (i == 32)
610     {
611       i = 0;
612       found = true;
613       e = VEC_index (size_time_entry, summary->entry, 0);
614       gcc_assert (!e->predicate.clause[0]);
615     }
616   if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
617     {
618       fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
619                ((double)size) / INLINE_SIZE_SCALE,
620                ((double)time) / INLINE_TIME_SCALE,
621                found ? "" : "new ");
622       dump_predicate (dump_file, summary->conds, pred);
623     }
624   if (!found)
625     {
626       struct size_time_entry new_entry;
627       new_entry.size = size;
628       new_entry.time = time;
629       new_entry.predicate = *pred;
630       VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry);
631     }
632   else
633     {
634       e->size += size;
635       e->time += time;
636       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
637         e->time = MAX_TIME * INLINE_TIME_SCALE;
638     }
639 }
640
641 /* Set predicate for edge E.  */
642
643 static void
644 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
645 {
646   struct inline_edge_summary *es = inline_edge_summary (e);
647   if (predicate && !true_predicate_p (predicate))
648     {
649       if (!es->predicate)
650         es->predicate = (struct predicate *)pool_alloc (edge_predicate_pool);
651       *es->predicate = *predicate;
652     }
653   else
654     {
655       if (es->predicate)
656         pool_free (edge_predicate_pool, es->predicate);
657       es->predicate = NULL;
658     }
659 }
660
661
662 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
663    Return clause of possible truths. When INLINE_P is true, assume that
664    we are inlining. 
665
666    ERROR_MARK means compile time invariant.  */
667
668 static clause_t
669 evaluate_conditions_for_known_args (struct cgraph_node *node,
670                                     bool inline_p,
671                                     VEC (tree, heap) *known_vals)
672 {
673   clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
674   struct inline_summary *info = inline_summary (node);
675   int i;
676   struct condition *c;
677
678   for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
679     {
680       tree val;
681       tree res;
682
683       /* We allow call stmt to have fewer arguments than the callee
684          function (especially for K&R style programs).  So bound
685          check here.  */
686       if (c->operand_num < (int)VEC_length (tree, known_vals))
687         val = VEC_index (tree, known_vals, c->operand_num);
688       else
689         val = NULL;
690
691       if (val == error_mark_node && c->code != CHANGED)
692         val = NULL;
693
694       if (!val)
695         {
696           clause |= 1 << (i + predicate_first_dynamic_condition);
697           continue;
698         }
699       if (c->code == IS_NOT_CONSTANT || c->code == CHANGED)
700         continue;
701       res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
702       if (res
703           && integer_zerop (res))
704         continue;
705       clause |= 1 << (i + predicate_first_dynamic_condition);
706     }
707   return clause;
708 }
709
710
711 /* Work out what conditions might be true at invocation of E.  */
712
713 static clause_t
714 evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
715 {
716   clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
717   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
718   struct inline_summary *info = inline_summary (callee);
719   int i;
720
721   if (ipa_node_params_vector && info->conds)
722     {
723       struct ipa_node_params *parms_info;
724       struct ipa_edge_args *args = IPA_EDGE_REF (e);
725       struct inline_edge_summary *es = inline_edge_summary (e);
726       int i, count = ipa_get_cs_argument_count (args);
727       VEC (tree, heap) *known_vals = NULL;
728
729       if (e->caller->global.inlined_to)
730         parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
731       else
732         parms_info = IPA_NODE_REF (e->caller);
733
734       if (count)
735         VEC_safe_grow_cleared (tree, heap, known_vals, count);
736       for (i = 0; i < count; i++)
737         {
738           tree cst = ipa_cst_from_jfunc (parms_info,
739                                          ipa_get_ith_jump_func (args, i));
740           if (cst)
741             VEC_replace (tree, known_vals, i, cst);
742           else if (inline_p
743                    && !VEC_index (inline_param_summary_t,
744                                   es->param,
745                                   i)->change_prob)
746             VEC_replace (tree, known_vals, i, error_mark_node);
747         }
748       clause = evaluate_conditions_for_known_args (callee,
749                                                    inline_p, known_vals);
750       VEC_free (tree, heap, known_vals);
751     }
752   else
753     for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
754       clause |= 1 << (i + predicate_first_dynamic_condition);
755
756   return clause;
757 }
758
759
760 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
761
762 static void
763 inline_summary_alloc (void)
764 {
765   if (!node_removal_hook_holder)
766     node_removal_hook_holder =
767       cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
768   if (!edge_removal_hook_holder)
769     edge_removal_hook_holder =
770       cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
771   if (!node_duplication_hook_holder)
772     node_duplication_hook_holder =
773       cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
774   if (!edge_duplication_hook_holder)
775     edge_duplication_hook_holder =
776       cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
777
778   if (VEC_length (inline_summary_t, inline_summary_vec)
779       <= (unsigned) cgraph_max_uid)
780     VEC_safe_grow_cleared (inline_summary_t, gc,
781                            inline_summary_vec, cgraph_max_uid + 1);
782   if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec)
783       <= (unsigned) cgraph_edge_max_uid)
784     VEC_safe_grow_cleared (inline_edge_summary_t, heap,
785                            inline_edge_summary_vec, cgraph_edge_max_uid + 1);
786   if (!edge_predicate_pool)
787     edge_predicate_pool = create_alloc_pool ("edge predicates",
788                                              sizeof (struct predicate),
789                                              10);
790 }
791
792 /* We are called multiple time for given function; clear
793    data from previous run so they are not cumulated.  */
794
795 static void
796 reset_inline_edge_summary (struct cgraph_edge *e)
797 {
798   if (e->uid
799       < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec))
800     {
801       struct inline_edge_summary *es = inline_edge_summary (e);
802
803       es->call_stmt_size = es->call_stmt_time =0;
804       if (es->predicate)
805         pool_free (edge_predicate_pool, es->predicate);
806       es->predicate = NULL;
807       VEC_free (inline_param_summary_t, heap, es->param);
808     }
809 }
810
811 /* We are called multiple time for given function; clear
812    data from previous run so they are not cumulated.  */
813
814 static void
815 reset_inline_summary (struct cgraph_node *node)
816 {
817   struct inline_summary *info = inline_summary (node);
818   struct cgraph_edge *e;
819
820   info->self_size = info->self_time = 0;
821   info->estimated_stack_size = 0;
822   info->estimated_self_stack_size = 0;
823   info->stack_frame_offset = 0;
824   info->size = 0;
825   info->time = 0;
826   VEC_free (condition, gc, info->conds);
827   VEC_free (size_time_entry,gc, info->entry);
828   for (e = node->callees; e; e = e->next_callee)
829     reset_inline_edge_summary (e);
830   for (e = node->indirect_calls; e; e = e->next_callee)
831     reset_inline_edge_summary (e);
832 }
833
834 /* Hook that is called by cgraph.c when a node is removed.  */
835
836 static void
837 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
838 {
839   struct inline_summary *info;
840   if (VEC_length (inline_summary_t, inline_summary_vec)
841       <= (unsigned)node->uid)
842     return;
843   info = inline_summary (node);
844   reset_inline_summary (node);
845   memset (info, 0, sizeof (inline_summary_t));
846 }
847
848
849 /* Hook that is called by cgraph.c when a node is duplicated.  */
850
851 static void
852 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
853                               ATTRIBUTE_UNUSED void *data)
854 {
855   struct inline_summary *info;
856   inline_summary_alloc ();
857   info = inline_summary (dst);
858   memcpy (info, inline_summary (src),
859           sizeof (struct inline_summary));
860   /* TODO: as an optimization, we may avoid copying conditions
861      that are known to be false or true.  */
862   info->conds = VEC_copy (condition, gc, info->conds);
863
864   /* When there are any replacements in the function body, see if we can figure
865      out that something was optimized out.  */
866   if (ipa_node_params_vector && dst->clone.tree_map)
867     {
868       VEC(size_time_entry,gc) *entry = info->entry;
869       /* Use SRC parm info since it may not be copied yet.  */
870       struct ipa_node_params *parms_info = IPA_NODE_REF (src);
871       VEC (tree, heap) *known_vals = NULL;
872       int count = ipa_get_param_count (parms_info);
873       int i,j;
874       clause_t possible_truths;
875       struct predicate true_pred = true_predicate ();
876       size_time_entry *e;
877       int optimized_out_size = 0;
878       gcov_type optimized_out_time = 0;
879       bool inlined_to_p = false;
880       struct cgraph_edge *edge;
881
882       info->entry = 0;
883       VEC_safe_grow_cleared (tree, heap, known_vals, count);
884       for (i = 0; i < count; i++)
885         {
886           tree t = ipa_get_param (parms_info, i);
887           struct ipa_replace_map *r;
888
889           for (j = 0;
890                VEC_iterate (ipa_replace_map_p, dst->clone.tree_map, j, r);
891                j++)
892             {
893               if (r->old_tree == t
894                   && r->replace_p
895                   && !r->ref_p)
896                 {
897                   VEC_replace (tree, known_vals, i, r->new_tree);
898                   break;
899                 }
900             }
901         }
902       possible_truths = evaluate_conditions_for_known_args (dst,
903                                                             false, known_vals);
904       VEC_free (tree, heap, known_vals);
905
906       account_size_time (info, 0, 0, &true_pred);
907
908       /* Remap size_time vectors.
909          Simplify the predicate by prunning out alternatives that are known
910          to be false.
911          TODO: as on optimization, we can also eliminate conditions known
912          to be true.  */
913       for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
914         {
915           struct predicate new_predicate = true_predicate ();
916           for (j = 0; e->predicate.clause[j]; j++)
917             if (!(possible_truths & e->predicate.clause[j]))
918               {
919                 new_predicate = false_predicate ();
920                 break;
921               }
922             else
923               add_clause (info->conds, &new_predicate,
924                           possible_truths & e->predicate.clause[j]);
925           if (false_predicate_p (&new_predicate))
926             {
927               optimized_out_size += e->size;
928               optimized_out_time += e->time;
929             }
930           else
931             account_size_time (info, e->size, e->time, &new_predicate);
932         }
933
934       /* Remap edge predicates with the same simplification as above.
935          Also copy constantness arrays.   */
936       for (edge = dst->callees; edge; edge = edge->next_callee)
937         {
938           struct predicate new_predicate = true_predicate ();
939           struct inline_edge_summary *es = inline_edge_summary (edge);
940
941           if (!edge->inline_failed)
942             inlined_to_p = true;
943           if (!es->predicate)
944             continue;
945           for (j = 0; es->predicate->clause[j]; j++)
946             if (!(possible_truths & es->predicate->clause[j]))
947               {
948                 new_predicate = false_predicate ();
949                 break;
950               }
951             else
952               add_clause (info->conds, &new_predicate,
953                           possible_truths & es->predicate->clause[j]);
954           if (false_predicate_p (&new_predicate)
955               && !false_predicate_p (es->predicate))
956             {
957               optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
958               optimized_out_time += (es->call_stmt_time
959                                      * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
960                                      * edge->frequency);
961               edge->frequency = 0;
962             }
963           *es->predicate = new_predicate;
964         }
965
966       /* Remap indirect edge predicates with the same simplificaiton as above. 
967          Also copy constantness arrays.   */
968       for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
969         {
970           struct predicate new_predicate = true_predicate ();
971           struct inline_edge_summary *es = inline_edge_summary (edge);
972
973           if (!edge->inline_failed)
974             inlined_to_p = true;
975           if (!es->predicate)
976             continue;
977           for (j = 0; es->predicate->clause[j]; j++)
978             if (!(possible_truths & es->predicate->clause[j]))
979               {
980                 new_predicate = false_predicate ();
981                 break;
982               }
983             else
984               add_clause (info->conds, &new_predicate,
985                           possible_truths & es->predicate->clause[j]);
986           if (false_predicate_p (&new_predicate)
987               && !false_predicate_p (es->predicate))
988             {
989               optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
990               optimized_out_time += (es->call_stmt_time
991                                      * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
992                                      * edge->frequency);
993               edge->frequency = 0;
994             }
995           *es->predicate = new_predicate;
996         }
997
998       /* If inliner or someone after inliner will ever start producing
999          non-trivial clones, we will get trouble with lack of information
1000          about updating self sizes, because size vectors already contains
1001          sizes of the calees.  */
1002       gcc_assert (!inlined_to_p 
1003                   || (!optimized_out_size && !optimized_out_time));
1004
1005       info->size -= optimized_out_size / INLINE_SIZE_SCALE;
1006       info->self_size -= optimized_out_size / INLINE_SIZE_SCALE;
1007       gcc_assert (info->size > 0);
1008       gcc_assert (info->self_size > 0);
1009
1010       optimized_out_time /= INLINE_TIME_SCALE;
1011       if (optimized_out_time > MAX_TIME)
1012         optimized_out_time = MAX_TIME;
1013       info->time -= optimized_out_time;
1014       info->self_time -= optimized_out_time;
1015       if (info->time < 0)
1016         info->time = 0;
1017       if (info->self_time < 0)
1018         info->self_time = 0;
1019     }
1020   else
1021     info->entry = VEC_copy (size_time_entry, gc, info->entry);
1022 }
1023
1024
1025 /* Hook that is called by cgraph.c when a node is duplicated.  */
1026
1027 static void
1028 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1029                               ATTRIBUTE_UNUSED void *data)
1030 {
1031   struct inline_edge_summary *info;
1032   struct inline_edge_summary *srcinfo;
1033   inline_summary_alloc ();
1034   info = inline_edge_summary (dst);
1035   srcinfo = inline_edge_summary (src);
1036   memcpy (info, srcinfo,
1037           sizeof (struct inline_edge_summary));
1038   info->predicate = NULL;
1039   edge_set_predicate (dst, srcinfo->predicate);
1040   info->param = VEC_copy (inline_param_summary_t, heap, srcinfo->param);
1041 }
1042
1043
1044 /* Keep edge cache consistent across edge removal.  */
1045
1046 static void
1047 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
1048 {
1049   if (edge_growth_cache)
1050     reset_edge_growth_cache (edge);
1051   reset_inline_edge_summary (edge);
1052 }
1053
1054
1055 /* Initialize growth caches.  */
1056
1057 void
1058 initialize_growth_caches (void)
1059 {
1060   if (cgraph_edge_max_uid)
1061     VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
1062                            cgraph_edge_max_uid);
1063   if (cgraph_max_uid)
1064     VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
1065 }
1066
1067
1068 /* Free growth caches.  */
1069
1070 void
1071 free_growth_caches (void)
1072 {
1073   VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
1074   edge_growth_cache = 0;
1075   VEC_free (int, heap, node_growth_cache);
1076   node_growth_cache = 0;
1077 }
1078
1079
1080 /* Dump edge summaries associated to NODE and recursively to all clones.
1081    Indent by INDENT.  */
1082
1083 static void
1084 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node,
1085                           struct inline_summary *info)
1086 {
1087   struct cgraph_edge *edge;
1088   for (edge = node->callees; edge; edge = edge->next_callee)
1089     {
1090       struct inline_edge_summary *es = inline_edge_summary (edge);
1091       struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1092       int i;
1093
1094       fprintf (f, "%*s%s/%i %s\n%*s  loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
1095                indent, "", cgraph_node_name (callee),
1096                callee->uid, 
1097                !edge->inline_failed ? "inlined"
1098                : cgraph_inline_failed_string (edge->inline_failed),
1099                indent, "",
1100                es->loop_depth,  
1101                edge->frequency,
1102                es->call_stmt_size,
1103                es->call_stmt_time,
1104                (int)inline_summary (callee)->size / INLINE_SIZE_SCALE,
1105                (int)inline_summary (callee)->estimated_stack_size);
1106
1107       if (es->predicate)
1108         {
1109           fprintf (f, " predicate: ");
1110           dump_predicate (f, info->conds, es->predicate);
1111         }
1112       else
1113           fprintf (f, "\n");
1114       if (es->param)
1115         for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param);
1116              i++)
1117           {
1118             int prob = VEC_index (inline_param_summary_t,
1119                                   es->param, i)->change_prob;
1120
1121             if (!prob)
1122               fprintf (f, "%*s op%i is compile time invariant\n",
1123                        indent + 2, "", i);
1124             else if (prob != REG_BR_PROB_BASE)
1125               fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i,
1126                        prob * 100.0 / REG_BR_PROB_BASE);
1127           }
1128       if (!edge->inline_failed)
1129         {
1130           fprintf (f, "%*sStack frame offset %i, callee self size %i,"
1131                    " callee size %i\n",
1132                    indent+2, "",
1133                    (int)inline_summary (callee)->stack_frame_offset,
1134                    (int)inline_summary (callee)->estimated_self_stack_size,
1135                    (int)inline_summary (callee)->estimated_stack_size);
1136           dump_inline_edge_summary (f, indent+2, callee, info);
1137         }
1138     }
1139   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1140     {
1141       struct inline_edge_summary *es = inline_edge_summary (edge);
1142       fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1143                " time: %2i",
1144                indent, "",
1145                es->loop_depth,  
1146                edge->frequency,
1147                es->call_stmt_size,
1148                es->call_stmt_time);
1149       if (es->predicate)
1150         {
1151           fprintf (f, "predicate: ");
1152           dump_predicate (f, info->conds, es->predicate);
1153         }
1154       else
1155         fprintf (f, "\n");
1156     }
1157 }
1158
1159
1160 void
1161 dump_inline_summary (FILE * f, struct cgraph_node *node)
1162 {
1163   if (node->analyzed)
1164     {
1165       struct inline_summary *s = inline_summary (node);
1166       size_time_entry *e;
1167       int i;
1168       fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
1169                node->uid);
1170       if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1171         fprintf (f, " always_inline");
1172       if (s->inlinable)
1173         fprintf (f, " inlinable");
1174       fprintf (f, "\n  self time:       %i\n",
1175                s->self_time);
1176       fprintf (f, "  global time:     %i\n", s->time);
1177       fprintf (f, "  self size:       %i\n",
1178                s->self_size);
1179       fprintf (f, "  global size:     %i\n", s->size);
1180       fprintf (f, "  self stack:      %i\n",
1181                (int) s->estimated_self_stack_size);
1182       fprintf (f, "  global stack:    %i\n",
1183                (int) s->estimated_stack_size);
1184       for (i = 0;
1185            VEC_iterate (size_time_entry, s->entry, i, e);
1186            i++)
1187         {
1188           fprintf (f, "    size:%f, time:%f, predicate:",
1189                    (double) e->size / INLINE_SIZE_SCALE,
1190                    (double) e->time / INLINE_TIME_SCALE);
1191           dump_predicate (f, s->conds, &e->predicate);
1192         }
1193       fprintf (f, "  calls:\n");
1194       dump_inline_edge_summary (f, 4, node, s);
1195       fprintf (f, "\n");
1196     }
1197 }
1198
1199 DEBUG_FUNCTION void
1200 debug_inline_summary (struct cgraph_node *node)
1201 {
1202   dump_inline_summary (stderr, node);
1203 }
1204
1205 void
1206 dump_inline_summaries (FILE *f)
1207 {
1208   struct cgraph_node *node;
1209
1210   for (node = cgraph_nodes; node; node = node->next)
1211     if (node->analyzed && !node->global.inlined_to)
1212       dump_inline_summary (f, node);
1213 }
1214
1215 /* Give initial reasons why inlining would fail on EDGE.  This gets either
1216    nullified or usually overwritten by more precise reasons later.  */
1217
1218 void
1219 initialize_inline_failed (struct cgraph_edge *e)
1220 {
1221   struct cgraph_node *callee = e->callee;
1222
1223   if (e->indirect_unknown_callee)
1224     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1225   else if (!callee->analyzed)
1226     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1227   else if (callee->local.redefined_extern_inline)
1228     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1229   else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
1230     e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1231   else
1232     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1233 }
1234
1235 /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the
1236    boolean variable pointed to by DATA.  */
1237
1238 static bool
1239 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
1240                      void *data)
1241 {
1242   bool *b = (bool *) data;
1243   *b = true;
1244   return true;
1245 }
1246
1247 /* If OP reffers to value of function parameter, return 
1248    the corresponding parameter.  */
1249
1250 static tree
1251 unmodified_parm (gimple stmt, tree op)
1252 {
1253   /* SSA_NAME referring to parm default def?  */
1254   if (TREE_CODE (op) == SSA_NAME
1255       && SSA_NAME_IS_DEFAULT_DEF (op)
1256       && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL)
1257     return SSA_NAME_VAR (op);
1258   /* Non-SSA parm reference?  */
1259   if (TREE_CODE (op) == PARM_DECL)
1260     {
1261       bool modified = false;
1262
1263       ao_ref refd;
1264       ao_ref_init (&refd, op);
1265       walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
1266                           NULL);
1267       if (!modified)
1268         return op;
1269     }
1270   /* Assignment from a parameter?  */
1271   if (TREE_CODE (op) == SSA_NAME
1272       && !SSA_NAME_IS_DEFAULT_DEF (op)
1273       && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
1274     return unmodified_parm (SSA_NAME_DEF_STMT (op),
1275                             gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)));
1276   return NULL;
1277 }
1278
1279 /* See if statement might disappear after inlining.
1280    0 - means not eliminated
1281    1 - half of statements goes away
1282    2 - for sure it is eliminated.
1283    We are not terribly sophisticated, basically looking for simple abstraction
1284    penalty wrappers.  */
1285
1286 static int
1287 eliminated_by_inlining_prob (gimple stmt)
1288 {
1289   enum gimple_code code = gimple_code (stmt);
1290
1291   if (!optimize)
1292     return 0;
1293
1294   switch (code)
1295     {
1296       case GIMPLE_RETURN:
1297         return 2;
1298       case GIMPLE_ASSIGN:
1299         if (gimple_num_ops (stmt) != 2)
1300           return 0;
1301
1302         /* Casts of parameters, loads from parameters passed by reference
1303            and stores to return value or parameters are often free after
1304            inlining dua to SRA and further combining.
1305            Assume that half of statements goes away.  */
1306         if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1307             || gimple_assign_rhs_code (stmt) == NOP_EXPR
1308             || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1309             || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1310           {
1311             tree rhs = gimple_assign_rhs1 (stmt);
1312             tree lhs = gimple_assign_lhs (stmt);
1313             tree inner_rhs = get_base_address (rhs);
1314             tree inner_lhs = get_base_address (lhs);
1315             bool rhs_free = false;
1316             bool lhs_free = false;
1317
1318             if (!inner_rhs)
1319               inner_rhs = rhs;
1320             if (!inner_lhs)
1321               inner_lhs = lhs;
1322
1323             /* Reads of parameter are expected to be free.  */
1324             if (unmodified_parm (stmt, inner_rhs))
1325               rhs_free = true;
1326
1327             /* When parameter is not SSA register because its address is taken
1328                and it is just copied into one, the statement will be completely
1329                free after inlining (we will copy propagate backward).   */
1330             if (rhs_free && is_gimple_reg (lhs))
1331               return 2;
1332
1333             /* Reads of parameters passed by reference
1334                expected to be free (i.e. optimized out after inlining).  */
1335             if (TREE_CODE(inner_rhs) == MEM_REF
1336                 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0)))
1337               rhs_free = true;
1338
1339             /* Copying parameter passed by reference into gimple register is
1340                probably also going to copy propagate, but we can't be quite
1341                sure.  */
1342             if (rhs_free && is_gimple_reg (lhs))
1343               lhs_free = true;
1344            
1345             /* Writes to parameters, parameters passed by value and return value
1346                (either dirrectly or passed via invisible reference) are free.  
1347
1348                TODO: We ought to handle testcase like
1349                struct a {int a,b;};
1350                struct a
1351                retrurnsturct (void)
1352                  {
1353                    struct a a ={1,2};
1354                    return a;
1355                  }
1356
1357                This translate into:
1358
1359                retrurnsturct ()
1360                  {
1361                    int a$b;
1362                    int a$a;
1363                    struct a a;
1364                    struct a D.2739;
1365
1366                  <bb 2>:
1367                    D.2739.a = 1;
1368                    D.2739.b = 2;
1369                    return D.2739;
1370
1371                  }
1372                For that we either need to copy ipa-split logic detecting writes
1373                to return value.  */
1374             if (TREE_CODE (inner_lhs) == PARM_DECL
1375                 || TREE_CODE (inner_lhs) == RESULT_DECL
1376                 || (TREE_CODE(inner_lhs) == MEM_REF
1377                      && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0))
1378                          || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
1379                              && TREE_CODE (SSA_NAME_VAR
1380                                             (TREE_OPERAND (inner_lhs, 0)))
1381                              == RESULT_DECL))))
1382               lhs_free = true;
1383             if (lhs_free
1384                 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1385               rhs_free = true;
1386             if (lhs_free && rhs_free)
1387               return 1;
1388           }
1389         return 0;
1390       default:
1391         return 0;
1392     }
1393 }
1394
1395
1396 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1397    predicates to the CFG edges.   */
1398
1399 static void
1400 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1401                                    struct inline_summary *summary,
1402                                    basic_block bb)
1403 {
1404   gimple last;
1405   tree op;
1406   int index;
1407   enum tree_code code, inverted_code;
1408   edge e;
1409   edge_iterator ei;
1410   gimple set_stmt;
1411   tree op2;
1412   tree parm;
1413   tree base;
1414
1415   last = last_stmt (bb);
1416   if (!last
1417       || gimple_code (last) != GIMPLE_COND)
1418     return;
1419   if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1420     return;
1421   op = gimple_cond_lhs (last);
1422   /* TODO: handle conditionals like
1423      var = op0 < 4;
1424      if (var != 0).  */
1425   parm = unmodified_parm (last, op);
1426   if (parm)
1427     {
1428       index = ipa_get_param_decl_index (info, parm);
1429       if (index == -1)
1430         return;
1431       code = gimple_cond_code (last);
1432       inverted_code
1433          = invert_tree_comparison (code,
1434                                    HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1435
1436       FOR_EACH_EDGE (e, ei, bb->succs)
1437         {
1438           struct predicate p = add_condition (summary,
1439                                               index,
1440                                               e->flags & EDGE_TRUE_VALUE
1441                                               ? code : inverted_code,
1442                                               gimple_cond_rhs (last));
1443           e->aux = pool_alloc (edge_predicate_pool);
1444           *(struct predicate *)e->aux = p;
1445         }
1446     }
1447
1448   if (TREE_CODE (op) != SSA_NAME)
1449     return;
1450   /* Special case
1451      if (builtin_constant_p (op))
1452        constant_code
1453      else
1454        nonconstant_code.
1455      Here we can predicate nonconstant_code.  We can't
1456      really handle constant_code since we have no predicate
1457      for this and also the constant code is not known to be
1458      optimized away when inliner doen't see operand is constant.
1459      Other optimizers might think otherwise.  */
1460   set_stmt = SSA_NAME_DEF_STMT (op);
1461   if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1462       || gimple_call_num_args (set_stmt) != 1)
1463     return;
1464   op2 = gimple_call_arg (set_stmt, 0);
1465   base = get_base_address (op2);
1466   parm = unmodified_parm (set_stmt, base ? base : op2);
1467   if (!parm)
1468     return;
1469   index = ipa_get_param_decl_index (info, parm);
1470   if (index == -1)
1471     return;
1472   if (gimple_cond_code (last) != NE_EXPR
1473       || !integer_zerop (gimple_cond_rhs (last)))
1474     return;
1475   FOR_EACH_EDGE (e, ei, bb->succs)
1476     if (e->flags & EDGE_FALSE_VALUE)
1477       {
1478         struct predicate p = add_condition (summary,
1479                                             index,
1480                                             IS_NOT_CONSTANT,
1481                                             NULL);
1482         e->aux = pool_alloc (edge_predicate_pool);
1483         *(struct predicate *)e->aux = p;
1484       }
1485 }
1486
1487
1488 /* If BB ends by a switch we can turn into predicates, attach corresponding
1489    predicates to the CFG edges.   */
1490
1491 static void
1492 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1493                                    struct inline_summary *summary,
1494                                    basic_block bb)
1495 {
1496   gimple last;
1497   tree op;
1498   int index;
1499   edge e;
1500   edge_iterator ei;
1501   size_t n;
1502   size_t case_idx;
1503   tree parm;
1504
1505   last = last_stmt (bb);
1506   if (!last
1507       || gimple_code (last) != GIMPLE_SWITCH)
1508     return;
1509   op = gimple_switch_index (last);
1510   parm = unmodified_parm (last, op);
1511   if (!parm)
1512     return;
1513   index = ipa_get_param_decl_index (info, parm);
1514   if (index == -1)
1515     return;
1516
1517   FOR_EACH_EDGE (e, ei, bb->succs)
1518     {
1519       e->aux = pool_alloc (edge_predicate_pool);
1520       *(struct predicate *)e->aux = false_predicate ();
1521     }
1522   n = gimple_switch_num_labels(last);
1523   for (case_idx = 0; case_idx < n; ++case_idx)
1524     {
1525       tree cl = gimple_switch_label (last, case_idx);
1526       tree min, max;
1527       struct predicate p;
1528
1529       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1530       min = CASE_LOW (cl);
1531       max = CASE_HIGH (cl);
1532
1533       /* For default we might want to construct predicate that none
1534          of cases is met, but it is bit hard to do not having negations
1535          of conditionals handy.  */
1536       if (!min && !max)
1537         p = true_predicate ();
1538       else if (!max)
1539         p = add_condition (summary, index,
1540                            EQ_EXPR,
1541                            min);
1542       else
1543         {
1544           struct predicate p1, p2;
1545           p1 = add_condition (summary, index,
1546                               GE_EXPR,
1547                               min);
1548           p2 = add_condition (summary, index,
1549                               LE_EXPR,
1550                               max);
1551           p = and_predicates (summary->conds, &p1, &p2);
1552         }
1553       *(struct predicate *)e->aux
1554         = or_predicates (summary->conds, &p, (struct predicate *)e->aux);
1555     }
1556 }
1557
1558
1559 /* For each BB in NODE attach to its AUX pointer predicate under
1560    which it is executable.  */
1561
1562 static void
1563 compute_bb_predicates (struct cgraph_node *node,
1564                        struct ipa_node_params *parms_info,
1565                        struct inline_summary *summary)
1566 {
1567   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1568   bool done = false;
1569   basic_block bb;
1570
1571   FOR_EACH_BB_FN (bb, my_function)
1572     {
1573       set_cond_stmt_execution_predicate (parms_info, summary, bb);
1574       set_switch_stmt_execution_predicate (parms_info, summary, bb);
1575     }
1576
1577   /* Entry block is always executable.  */
1578   ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1579     = pool_alloc (edge_predicate_pool);
1580   *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1581     = true_predicate ();
1582
1583   /* A simple dataflow propagation of predicates forward in the CFG.
1584      TODO: work in reverse postorder.  */
1585   while (!done)
1586     {
1587       done = true;
1588       FOR_EACH_BB_FN (bb, my_function)
1589         {
1590           struct predicate p = false_predicate ();
1591           edge e;
1592           edge_iterator ei;
1593           FOR_EACH_EDGE (e, ei, bb->preds)
1594             {
1595               if (e->src->aux)
1596                 {
1597                   struct predicate this_bb_predicate
1598                      = *(struct predicate *)e->src->aux;
1599                   if (e->aux)
1600                     this_bb_predicate
1601                        = and_predicates (summary->conds, &this_bb_predicate,
1602                                          (struct predicate *)e->aux);
1603                   p = or_predicates (summary->conds, &p, &this_bb_predicate);
1604                   if (true_predicate_p (&p))
1605                     break;
1606                 }
1607             }
1608           if (false_predicate_p (&p))
1609             gcc_assert (!bb->aux);
1610           else
1611             {
1612               if (!bb->aux)
1613                 {
1614                   done = false;
1615                   bb->aux = pool_alloc (edge_predicate_pool);
1616                   *((struct predicate *)bb->aux) = p;
1617                 }
1618               else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
1619                 {
1620                   done = false;
1621                   *((struct predicate *)bb->aux) = p;
1622                 }
1623             }
1624         }
1625     }
1626 }
1627
1628
1629 /* We keep info about constantness of SSA names.  */
1630
1631 typedef struct predicate predicate_t;
1632 DEF_VEC_O (predicate_t);
1633 DEF_VEC_ALLOC_O (predicate_t, heap);
1634
1635
1636 /* Return predicate specifying when the STMT might have result that is not
1637    a compile time constant.  */
1638
1639 static struct predicate
1640 will_be_nonconstant_predicate (struct ipa_node_params *info,
1641                                struct inline_summary *summary,
1642                                gimple stmt,
1643                                VEC (predicate_t, heap) *nonconstant_names)
1644                               
1645 {
1646   struct predicate p = true_predicate ();
1647   ssa_op_iter iter;
1648   tree use;
1649   struct predicate op_non_const;
1650   bool is_load;
1651
1652   /* What statments might be optimized away
1653      when their arguments are constant
1654      TODO: also trivial builtins.
1655      builtin_constant_p is already handled later.  */
1656   if (gimple_code (stmt) != GIMPLE_ASSIGN
1657       && gimple_code (stmt) != GIMPLE_COND
1658       && gimple_code (stmt) != GIMPLE_SWITCH)
1659     return p;
1660
1661   /* Stores will stay anyway.  */
1662   if (gimple_vdef (stmt))
1663     return p;
1664
1665   is_load = gimple_vuse (stmt) != NULL;
1666
1667   /* Loads can be optimized when the value is known.  */
1668   if (is_load)
1669     {
1670       tree op = gimple_assign_rhs1 (stmt);
1671       tree base = get_base_address (op);
1672       tree parm;
1673
1674       gcc_assert (gimple_assign_single_p (stmt));
1675       if (!base)
1676         return p;
1677       parm = unmodified_parm (stmt, base);
1678       if (!parm )
1679         return p;
1680       if (ipa_get_param_decl_index (info, parm) < 0)
1681         return p;
1682     }
1683
1684   /* See if we understand all operands before we start
1685      adding conditionals.  */
1686   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1687     {
1688       tree parm = unmodified_parm (stmt, use);
1689       /* For arguments we can build a condition.  */
1690       if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1691         continue;
1692       if (TREE_CODE (use) != SSA_NAME)
1693         return p;
1694       /* If we know when operand is constant,
1695          we still can say something useful.  */
1696       if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names,
1697                                         SSA_NAME_VERSION (use))))
1698         continue;
1699       return p;
1700     }
1701   op_non_const = false_predicate ();
1702   if (is_load)
1703     {
1704       tree parm = unmodified_parm
1705                     (stmt, get_base_address (gimple_assign_rhs1 (stmt)));
1706       p = add_condition (summary,
1707                          ipa_get_param_decl_index (info, parm),
1708                          CHANGED, NULL);
1709       op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1710     }
1711   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1712     {
1713       tree parm = unmodified_parm (stmt, use);
1714       if (parm && ipa_get_param_decl_index (info, parm) >= 0)
1715         p = add_condition (summary,
1716                            ipa_get_param_decl_index (info, parm),
1717                            CHANGED, NULL);
1718       else
1719         p = *VEC_index (predicate_t, nonconstant_names,
1720                         SSA_NAME_VERSION (use));
1721       op_non_const = or_predicates (summary->conds, &p, &op_non_const);
1722     }
1723   if (gimple_code (stmt) == GIMPLE_ASSIGN
1724       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
1725     VEC_replace (predicate_t, nonconstant_names,
1726                  SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const);
1727   return op_non_const;
1728 }
1729
1730 struct record_modified_bb_info
1731 {
1732   bitmap bb_set;
1733   gimple stmt;
1734 };
1735
1736 /* Callback of walk_aliased_vdefs.  Records basic blocks where the value may be
1737    set except for info->stmt.  */
1738
1739 static bool
1740 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef,
1741                  void *data)
1742 {
1743   struct record_modified_bb_info *info = (struct record_modified_bb_info *) data;
1744   if (SSA_NAME_DEF_STMT (vdef) == info->stmt)
1745     return false;
1746   bitmap_set_bit (info->bb_set,
1747                   SSA_NAME_IS_DEFAULT_DEF (vdef)
1748                   ? ENTRY_BLOCK_PTR->index : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index);
1749   return false;
1750 }
1751
1752 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
1753    will change since last invocation of STMT. 
1754
1755    Value 0 is reserved for compile time invariants.
1756    For common parameters it is REG_BR_PROB_BASE.  For loop invariants it
1757    ought to be REG_BR_PROB_BASE / estimated_iters.  */
1758
1759 static int
1760 param_change_prob (gimple stmt, int i)
1761 {
1762   tree op = gimple_call_arg (stmt, i);
1763   basic_block bb = gimple_bb (stmt);
1764   tree base;
1765
1766   if (is_gimple_min_invariant (op))
1767     return 0;
1768   /* We would have to do non-trivial analysis to really work out what
1769      is the probability of value to change (i.e. when init statement
1770      is in a sibling loop of the call). 
1771
1772      We do an conservative estimate: when call is executed N times more often
1773      than the statement defining value, we take the frequency 1/N.  */
1774   if (TREE_CODE (op) == SSA_NAME)
1775     {
1776       int init_freq;
1777
1778       if (!bb->frequency)
1779         return REG_BR_PROB_BASE;
1780
1781       if (SSA_NAME_IS_DEFAULT_DEF (op))
1782         init_freq = ENTRY_BLOCK_PTR->frequency;
1783       else
1784         init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency;
1785
1786       if (!init_freq)
1787         init_freq = 1;
1788       if (init_freq < bb->frequency)
1789         return MAX ((init_freq * REG_BR_PROB_BASE +
1790                     bb->frequency / 2) / bb->frequency, 1);
1791       else
1792         return REG_BR_PROB_BASE;
1793     }
1794
1795   base = get_base_address (op);
1796   if (base)
1797     {
1798       ao_ref refd;
1799       int max;
1800       struct record_modified_bb_info info;
1801       bitmap_iterator bi;
1802       unsigned index;
1803
1804       if (const_value_known_p (base))
1805         return 0;
1806       if (!bb->frequency)
1807         return REG_BR_PROB_BASE;
1808       ao_ref_init (&refd, op);
1809       info.stmt = stmt;
1810       info.bb_set = BITMAP_ALLOC (NULL);
1811       walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
1812                           NULL);
1813       if (bitmap_bit_p (info.bb_set, bb->index))
1814         {
1815           BITMAP_FREE (info.bb_set);
1816           return REG_BR_PROB_BASE;
1817         }
1818
1819       /* Assume that every memory is initialized at entry.
1820          TODO: Can we easilly determine if value is always defined
1821          and thus we may skip entry block?  */
1822       if (ENTRY_BLOCK_PTR->frequency)
1823         max = ENTRY_BLOCK_PTR->frequency;
1824       else
1825         max = 1;
1826
1827       EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi)
1828         max = MIN (max, BASIC_BLOCK (index)->frequency);
1829       
1830       BITMAP_FREE (info.bb_set);
1831       if (max < bb->frequency)
1832         return MAX ((max * REG_BR_PROB_BASE +
1833                      bb->frequency / 2) / bb->frequency, 1);
1834       else
1835         return REG_BR_PROB_BASE;
1836     }
1837   return REG_BR_PROB_BASE;
1838 }
1839
1840
1841 /* Compute function body size parameters for NODE.
1842    When EARLY is true, we compute only simple summaries without
1843    non-trivial predicates to drive the early inliner.  */
1844
1845 static void
1846 estimate_function_body_sizes (struct cgraph_node *node, bool early)
1847 {
1848   gcov_type time = 0;
1849   /* Estimate static overhead for function prologue/epilogue and alignment. */
1850   int size = 2;
1851   /* Benefits are scaled by probability of elimination that is in range
1852      <0,2>.  */
1853   basic_block bb;
1854   gimple_stmt_iterator bsi;
1855   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1856   int freq;
1857   struct inline_summary *info = inline_summary (node);
1858   struct predicate bb_predicate;
1859   struct ipa_node_params *parms_info = NULL;
1860   VEC (predicate_t, heap) *nonconstant_names = NULL;
1861
1862   if (ipa_node_params_vector && !early && optimize)
1863     {
1864       parms_info = IPA_NODE_REF (node);
1865       VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names,
1866                              VEC_length (tree, SSANAMES (my_function)));
1867     }
1868
1869   info->conds = 0;
1870   info->entry = 0;
1871
1872
1873   if (dump_file)
1874     fprintf (dump_file, "\nAnalyzing function body size: %s\n",
1875              cgraph_node_name (node));
1876
1877   /* When we run into maximal number of entries, we assign everything to the
1878      constant truth case.  Be sure to have it in list. */
1879   bb_predicate = true_predicate ();
1880   account_size_time (info, 0, 0, &bb_predicate);
1881
1882   bb_predicate = not_inlined_predicate ();
1883   account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
1884
1885   gcc_assert (my_function && my_function->cfg);
1886   if (parms_info)
1887     compute_bb_predicates (node, parms_info, info);
1888   FOR_EACH_BB_FN (bb, my_function)
1889     {
1890       freq = compute_call_stmt_bb_frequency (node->decl, bb);
1891
1892       /* TODO: Obviously predicates can be propagated down across CFG.  */
1893       if (parms_info)
1894         {
1895           if (bb->aux)
1896             bb_predicate = *(struct predicate *)bb->aux;
1897           else
1898             bb_predicate = false_predicate ();
1899         }
1900       else
1901         bb_predicate = true_predicate ();
1902
1903       if (dump_file && (dump_flags & TDF_DETAILS))
1904         {
1905           fprintf (dump_file, "\n BB %i predicate:", bb->index);
1906           dump_predicate (dump_file, info->conds, &bb_predicate);
1907         }
1908       
1909       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1910         {
1911           gimple stmt = gsi_stmt (bsi);
1912           int this_size = estimate_num_insns (stmt, &eni_size_weights);
1913           int this_time = estimate_num_insns (stmt, &eni_time_weights);
1914           int prob;
1915           struct predicate will_be_nonconstant;
1916
1917           if (dump_file && (dump_flags & TDF_DETAILS))
1918             {
1919               fprintf (dump_file, "  ");
1920               print_gimple_stmt (dump_file, stmt, 0, 0);
1921               fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1922                        ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
1923             }
1924
1925           if (is_gimple_call (stmt))
1926             {
1927               struct cgraph_edge *edge = cgraph_edge (node, stmt);
1928               struct inline_edge_summary *es = inline_edge_summary (edge);
1929
1930               /* Special case: results of BUILT_IN_CONSTANT_P will be always
1931                  resolved as constant.  We however don't want to optimize
1932                  out the cgraph edges.  */
1933               if (nonconstant_names
1934                   && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
1935                   && gimple_call_lhs (stmt)
1936                   && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
1937                 {
1938                   struct predicate false_p = false_predicate ();
1939                   VEC_replace (predicate_t, nonconstant_names,
1940                                SSA_NAME_VERSION (gimple_call_lhs (stmt)),
1941                                &false_p);
1942                 }
1943               if (ipa_node_params_vector)
1944                 {
1945                   int count = gimple_call_num_args (stmt);
1946                   int i;
1947
1948                   if (count)
1949                     VEC_safe_grow_cleared (inline_param_summary_t, heap,
1950                                            es->param, count);
1951                   for (i = 0; i < count; i++)
1952                     {
1953                       int prob = param_change_prob (stmt, i);
1954                       gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
1955                       VEC_index (inline_param_summary_t,
1956                                  es->param, i)->change_prob = prob;
1957                     }
1958                 }
1959
1960               es->call_stmt_size = this_size;
1961               es->call_stmt_time = this_time;
1962               es->loop_depth = bb->loop_depth;
1963               edge_set_predicate (edge, &bb_predicate);
1964             }
1965
1966           /* TODO: When conditional jump or swithc is known to be constant, but
1967              we did not translate it into the predicates, we really can account
1968              just maximum of the possible paths.  */
1969           if (parms_info)
1970             will_be_nonconstant
1971                = will_be_nonconstant_predicate (parms_info, info,
1972                                                 stmt, nonconstant_names);
1973           if (this_time || this_size)
1974             {
1975               struct predicate p;
1976
1977               this_time *= freq;
1978               time += this_time;
1979               size += this_size;
1980
1981               prob = eliminated_by_inlining_prob (stmt);
1982               if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
1983                 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
1984               if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
1985                 fprintf (dump_file, "\t\tWill be eliminated by inlining\n");
1986
1987               if (parms_info)
1988                 p = and_predicates (info->conds, &bb_predicate,
1989                                     &will_be_nonconstant);
1990               else
1991                 p = true_predicate ();
1992
1993               /* We account everything but the calls.  Calls have their own
1994                  size/time info attached to cgraph edges.  This is neccesary
1995                  in order to make the cost disappear after inlining.  */
1996               if (!is_gimple_call (stmt))
1997                 {
1998                   if (prob)
1999                     {
2000                       struct predicate ip = not_inlined_predicate ();
2001                       ip = and_predicates (info->conds, &ip, &p);
2002                       account_size_time (info, this_size * prob,
2003                                          this_time * prob, &ip);
2004                     }
2005                   if (prob != 2)
2006                     account_size_time (info, this_size * (2 - prob),
2007                                        this_time * (2 - prob), &p);
2008                 }
2009
2010               gcc_assert (time >= 0);
2011               gcc_assert (size >= 0);
2012             }
2013         }
2014     }
2015   FOR_ALL_BB_FN (bb, my_function)
2016     {
2017       edge e;
2018       edge_iterator ei;
2019
2020       if (bb->aux)
2021         pool_free (edge_predicate_pool, bb->aux);
2022       bb->aux = NULL;
2023       FOR_EACH_EDGE (e, ei, bb->succs)
2024         {
2025           if (e->aux)
2026             pool_free (edge_predicate_pool, e->aux);
2027           e->aux = NULL;
2028         }
2029     }
2030   time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2031   if (time > MAX_TIME)
2032     time = MAX_TIME;
2033   inline_summary (node)->self_time = time;
2034   inline_summary (node)->self_size = size;
2035   VEC_free (predicate_t, heap, nonconstant_names);
2036   if (dump_file)
2037     {
2038       fprintf (dump_file, "\n");
2039       dump_inline_summary (dump_file, node);
2040     }
2041 }
2042
2043
2044 /* Compute parameters of functions used by inliner.
2045    EARLY is true when we compute parameters for the early inliner  */
2046
2047 void
2048 compute_inline_parameters (struct cgraph_node *node, bool early)
2049 {
2050   HOST_WIDE_INT self_stack_size;
2051   struct cgraph_edge *e;
2052   struct inline_summary *info;
2053   tree old_decl = current_function_decl;
2054
2055   gcc_assert (!node->global.inlined_to);
2056
2057   inline_summary_alloc ();
2058
2059   info = inline_summary (node);
2060   reset_inline_summary (node);
2061
2062   /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2063      Once this happen, we will need to more curefully predict call
2064      statement size.  */
2065   if (node->thunk.thunk_p)
2066     {
2067       struct inline_edge_summary *es = inline_edge_summary (node->callees);
2068       struct predicate t = true_predicate ();
2069
2070       info->inlinable = 0;
2071       node->callees->call_stmt_cannot_inline_p = true;
2072       node->local.can_change_signature = false;
2073       es->call_stmt_time = 1;
2074       es->call_stmt_size = 1;
2075       account_size_time (info, 0, 0, &t);
2076       return;
2077     }
2078
2079   /* Even is_gimple_min_invariant rely on current_function_decl.  */
2080   current_function_decl = node->decl;
2081   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2082
2083   /* Estimate the stack size for the function if we're optimizing.  */
2084   self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
2085   info->estimated_self_stack_size = self_stack_size;
2086   info->estimated_stack_size = self_stack_size;
2087   info->stack_frame_offset = 0;
2088
2089   /* Can this function be inlined at all?  */
2090   info->inlinable = tree_inlinable_function_p (node->decl);
2091
2092   /* Type attributes can use parameter indices to describe them.  */
2093   if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
2094     node->local.can_change_signature = false;
2095   else
2096     {
2097       /* Otherwise, inlinable functions always can change signature.  */
2098       if (info->inlinable)
2099         node->local.can_change_signature = true;
2100       else
2101         {
2102           /* Functions calling builtin_apply can not change signature.  */
2103           for (e = node->callees; e; e = e->next_callee)
2104             {
2105               tree cdecl = e->callee->decl;
2106               if (DECL_BUILT_IN (cdecl)
2107                   && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2108                   && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2109                       || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
2110                 break;
2111             }
2112           node->local.can_change_signature = !e;
2113         }
2114     }
2115   estimate_function_body_sizes (node, early);
2116
2117   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
2118   info->time = info->self_time;
2119   info->size = info->self_size;
2120   info->stack_frame_offset = 0;
2121   info->estimated_stack_size = info->estimated_self_stack_size;
2122   current_function_decl = old_decl;
2123   pop_cfun ();
2124 }
2125
2126
2127 /* Compute parameters of functions used by inliner using
2128    current_function_decl.  */
2129
2130 static unsigned int
2131 compute_inline_parameters_for_current (void)
2132 {
2133   compute_inline_parameters (cgraph_get_node (current_function_decl), true);
2134   return 0;
2135 }
2136
2137 struct gimple_opt_pass pass_inline_parameters =
2138 {
2139  {
2140   GIMPLE_PASS,
2141   "inline_param",                       /* name */
2142   NULL,                                 /* gate */
2143   compute_inline_parameters_for_current,/* execute */
2144   NULL,                                 /* sub */
2145   NULL,                                 /* next */
2146   0,                                    /* static_pass_number */
2147   TV_INLINE_HEURISTICS,                 /* tv_id */
2148   0,                                    /* properties_required */
2149   0,                                    /* properties_provided */
2150   0,                                    /* properties_destroyed */
2151   0,                                    /* todo_flags_start */
2152   0                                     /* todo_flags_finish */
2153  }
2154 };
2155
2156
2157 /* Increase SIZE and TIME for size and time needed to handle edge E.  */
2158
2159 static void
2160 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
2161                              int prob)
2162 {
2163   struct inline_edge_summary *es = inline_edge_summary (e);
2164   *size += es->call_stmt_size * INLINE_SIZE_SCALE;
2165   *time += (es->call_stmt_time * prob / REG_BR_PROB_BASE
2166             * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
2167   if (*time > MAX_TIME * INLINE_TIME_SCALE)
2168     *time = MAX_TIME * INLINE_TIME_SCALE;
2169 }
2170
2171
2172 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.  */
2173
2174 static void
2175 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
2176                               clause_t possible_truths)
2177 {
2178   struct cgraph_edge *e;
2179   for (e = node->callees; e; e = e->next_callee)
2180     {
2181       struct inline_edge_summary *es = inline_edge_summary (e);
2182       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2183         {
2184           if (e->inline_failed)
2185             {
2186               /* Predicates of calls shall not use NOT_CHANGED codes,
2187                  sowe do not need to compute probabilities.  */
2188               estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2189             }
2190           else
2191             estimate_calls_size_and_time (e->callee, size, time,
2192                                           possible_truths);
2193         }
2194     }
2195   /* TODO: look for devirtualizing oppurtunities.  */
2196   for (e = node->indirect_calls; e; e = e->next_callee)
2197     {
2198       struct inline_edge_summary *es = inline_edge_summary (e);
2199       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
2200         estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
2201     }
2202 }
2203
2204
2205 /* Estimate size and time needed to execute NODE assuming
2206    POSSIBLE_TRUTHS clause. */
2207
2208 static void
2209 estimate_node_size_and_time (struct cgraph_node *node,
2210                              clause_t possible_truths,
2211                              int *ret_size, int *ret_time,
2212                              VEC (inline_param_summary_t, heap)
2213                                *inline_param_summary)
2214 {
2215   struct inline_summary *info = inline_summary (node);
2216   size_time_entry *e;
2217   int size = 0, time = 0;
2218   int i;
2219
2220   if (dump_file
2221       && (dump_flags & TDF_DETAILS))
2222     {
2223       bool found = false;
2224       fprintf (dump_file, "   Estimating body: %s/%i\n"
2225                           "   Known to be false: ",
2226                cgraph_node_name (node),
2227                node->uid);
2228
2229       for (i = predicate_not_inlined_condition;
2230            i < (predicate_first_dynamic_condition
2231                 + (int)VEC_length (condition, info->conds)); i++)
2232         if (!(possible_truths & (1 << i)))
2233           {
2234             if (found)
2235               fprintf (dump_file, ", ");
2236             found = true;
2237             dump_condition (dump_file, info->conds, i);
2238           }
2239     }
2240
2241   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2242     if (evaluate_predicate (&e->predicate, possible_truths))
2243       {
2244         size += e->size;
2245         if (!inline_param_summary)
2246           time += e->time;
2247         else
2248           {
2249             int prob = predicate_probability (info->conds,
2250                                               &e->predicate,
2251                                               possible_truths,
2252                                               inline_param_summary);
2253             time += e->time * prob / REG_BR_PROB_BASE;
2254           }
2255                                                  
2256       }
2257
2258   if (time > MAX_TIME * INLINE_TIME_SCALE)
2259     time = MAX_TIME * INLINE_TIME_SCALE;
2260
2261   estimate_calls_size_and_time (node, &size, &time, possible_truths);
2262   time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2263   size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2264
2265
2266   if (dump_file
2267       && (dump_flags & TDF_DETAILS))
2268     fprintf (dump_file, "\n   size:%i time:%i\n", size, time);
2269   if (ret_time)
2270     *ret_time = time;
2271   if (ret_size)
2272     *ret_size = size;
2273   return;
2274 }
2275
2276
2277 /* Estimate size and time needed to execute callee of EDGE assuming that
2278    parameters known to be constant at caller of EDGE are propagated.
2279    KNOWN_VALs is a vector of assumed known constant values for parameters.  */
2280
2281 void
2282 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
2283                                    VEC (tree, heap) *known_vals,
2284                                    int *ret_size, int *ret_time)
2285 {
2286   clause_t clause;
2287
2288   clause = evaluate_conditions_for_known_args (node, false, known_vals);
2289   estimate_node_size_and_time (node, clause, ret_size, ret_time,
2290                                NULL);
2291 }
2292
2293
2294 /* Translate all conditions from callee representation into caller
2295    representation and symbolically evaluate predicate P into new predicate.
2296
2297    INFO is inline_summary of function we are adding predicate into,
2298    CALLEE_INFO is summary of function predicate P is from. OPERAND_MAP is
2299    array giving callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is
2300    clausule of all callee conditions that may be true in caller context.
2301    TOPLEV_PREDICATE is predicate under which callee is executed.  */
2302
2303 static struct predicate
2304 remap_predicate (struct inline_summary *info,
2305                  struct inline_summary *callee_info,
2306                  struct predicate *p,
2307                  VEC (int, heap) *operand_map,
2308                  clause_t possible_truths,
2309                  struct predicate *toplev_predicate)
2310 {
2311   int i;
2312   struct predicate out = true_predicate ();
2313
2314   /* True predicate is easy.  */
2315   if (true_predicate_p (p))
2316     return *toplev_predicate;
2317   for (i = 0; p->clause[i]; i++)
2318     {
2319       clause_t clause = p->clause[i];
2320       int cond;
2321       struct predicate clause_predicate = false_predicate ();
2322
2323       gcc_assert (i < MAX_CLAUSES);
2324
2325       for (cond = 0; cond < NUM_CONDITIONS; cond ++)
2326         /* Do we have condition we can't disprove?   */
2327         if (clause & possible_truths & (1 << cond))
2328           {
2329             struct predicate cond_predicate;
2330             /* Work out if the condition can translate to predicate in the
2331                inlined function.  */
2332             if (cond >= predicate_first_dynamic_condition)
2333               {
2334                  struct condition *c;
2335
2336                  c = VEC_index (condition, callee_info->conds,
2337                                 cond - predicate_first_dynamic_condition);
2338                  /* See if we can remap condition operand to caller's operand.
2339                     Otherwise give up.  */
2340                  if (!operand_map
2341                      || (int)VEC_length (int, operand_map) <= c->operand_num
2342                      || VEC_index (int, operand_map, c->operand_num) == -1)
2343                    cond_predicate = true_predicate ();
2344                  else
2345                    cond_predicate = add_condition (info,
2346                                                    VEC_index (int, operand_map,
2347                                                               c->operand_num),
2348                                                    c->code, c->val);
2349               }
2350             /* Fixed conditions remains same, construct single
2351                condition predicate.  */
2352             else
2353               {
2354                 cond_predicate.clause[0] = 1 << cond;
2355                 cond_predicate.clause[1] = 0;
2356               }
2357             clause_predicate = or_predicates (info->conds, &clause_predicate,
2358                                               &cond_predicate);
2359           }
2360       out = and_predicates (info->conds, &out, &clause_predicate);
2361     }
2362   return and_predicates (info->conds, &out, toplev_predicate);
2363 }
2364
2365
2366 /* Update summary information of inline clones after inlining.
2367    Compute peak stack usage.  */
2368
2369 static void
2370 inline_update_callee_summaries (struct cgraph_node *node,
2371                                 int depth)
2372 {
2373   struct cgraph_edge *e;
2374   struct inline_summary *callee_info = inline_summary (node);
2375   struct inline_summary *caller_info = inline_summary (node->callers->caller);
2376   HOST_WIDE_INT peak;
2377
2378   callee_info->stack_frame_offset
2379     = caller_info->stack_frame_offset
2380       + caller_info->estimated_self_stack_size;
2381   peak = callee_info->stack_frame_offset
2382       + callee_info->estimated_self_stack_size;
2383   if (inline_summary (node->global.inlined_to)->estimated_stack_size
2384       < peak)
2385     inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
2386   cgraph_propagate_frequency (node);
2387   for (e = node->callees; e; e = e->next_callee)
2388     {
2389       if (!e->inline_failed)
2390         inline_update_callee_summaries (e->callee, depth);
2391       inline_edge_summary (e)->loop_depth += depth;
2392     }
2393   for (e = node->indirect_calls; e; e = e->next_callee)
2394     inline_edge_summary (e)->loop_depth += depth;
2395 }
2396
2397 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
2398    When functoin A is inlined in B and A calls C with parameter that
2399    changes with probability PROB1 and C is known to be passthroug
2400    of argument if B that change with probability PROB2, the probability
2401    of change is now PROB1*PROB2.  */
2402
2403 static void
2404 remap_edge_change_prob (struct cgraph_edge *inlined_edge,
2405                         struct cgraph_edge *edge)
2406 {
2407   if (ipa_node_params_vector)
2408     {
2409       int i;
2410       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2411       struct inline_edge_summary *es = inline_edge_summary (edge);
2412       struct inline_edge_summary *inlined_es
2413                                     = inline_edge_summary (inlined_edge);
2414
2415       for (i = 0; i < ipa_get_cs_argument_count (args); i++)
2416         {
2417           struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2418           if (jfunc->type == IPA_JF_PASS_THROUGH
2419               && (jfunc->value.pass_through.formal_id
2420                   < (int) VEC_length (inline_param_summary_t,
2421                                       inlined_es->param)))
2422             {
2423               int prob1 = VEC_index (inline_param_summary_t,
2424                                      es->param, i)->change_prob;
2425               int prob2 = VEC_index
2426                              (inline_param_summary_t,
2427                              inlined_es->param,
2428                              jfunc->value.pass_through.formal_id)->change_prob;
2429               int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2)
2430                           / REG_BR_PROB_BASE);
2431
2432               if (prob1 && prob2 && !prob)
2433                 prob = 1;
2434
2435               VEC_index (inline_param_summary_t,
2436                          es->param, i)->change_prob = prob;
2437             }
2438         }
2439   }
2440 }
2441
2442 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
2443
2444    Remap predicates of callees of NODE.  Rest of arguments match
2445    remap_predicate.
2446
2447    Also update change probabilities.  */
2448
2449 static void
2450 remap_edge_summaries  (struct cgraph_edge *inlined_edge,
2451                        struct cgraph_node *node,
2452                        struct inline_summary *info,
2453                        struct inline_summary *callee_info,
2454                        VEC (int, heap) *operand_map,
2455                        clause_t possible_truths,
2456                        struct predicate *toplev_predicate)
2457 {
2458   struct cgraph_edge *e;
2459   for (e = node->callees; e; e = e->next_callee)
2460     {
2461       struct inline_edge_summary *es = inline_edge_summary (e);
2462       struct predicate p;
2463
2464       if (e->inline_failed)
2465         {
2466           remap_edge_change_prob (inlined_edge, e);
2467
2468           if (es->predicate)
2469             {
2470               p = remap_predicate (info, callee_info,
2471                                    es->predicate, operand_map, possible_truths,
2472                                    toplev_predicate);
2473               edge_set_predicate (e, &p);
2474               /* TODO: We should remove the edge for code that will be
2475                  optimized out, but we need to keep verifiers and tree-inline
2476                  happy.  Make it cold for now.  */
2477               if (false_predicate_p (&p))
2478                 {
2479                   e->count = 0;
2480                   e->frequency = 0;
2481                 }
2482             }
2483           else
2484             edge_set_predicate (e, toplev_predicate);
2485         }
2486       else
2487         remap_edge_summaries (inlined_edge, e->callee, info, callee_info,
2488                               operand_map, possible_truths, toplev_predicate);
2489     }
2490   for (e = node->indirect_calls; e; e = e->next_callee)
2491     {
2492       struct inline_edge_summary *es = inline_edge_summary (e);
2493       struct predicate p;
2494
2495       remap_edge_change_prob (inlined_edge, e);
2496       if (es->predicate)
2497         {
2498           p = remap_predicate (info, callee_info,
2499                                es->predicate, operand_map, possible_truths,
2500                                toplev_predicate);
2501           edge_set_predicate (e, &p);
2502           /* TODO: We should remove the edge for code that will be optimized
2503              out, but we need to keep verifiers and tree-inline happy.
2504              Make it cold for now.  */
2505           if (false_predicate_p (&p))
2506             {
2507               e->count = 0;
2508               e->frequency = 0;
2509             }
2510         }
2511       else
2512         edge_set_predicate (e, toplev_predicate);
2513     }
2514 }
2515
2516
2517 /* We inlined EDGE.  Update summary of the function we inlined into.  */
2518
2519 void
2520 inline_merge_summary (struct cgraph_edge *edge)
2521 {
2522   struct inline_summary *callee_info = inline_summary (edge->callee);
2523   struct cgraph_node *to = (edge->caller->global.inlined_to
2524                             ? edge->caller->global.inlined_to : edge->caller);
2525   struct inline_summary *info = inline_summary (to);
2526   clause_t clause = 0;          /* not_inline is known to be false.  */
2527   size_time_entry *e;
2528   VEC (int, heap) *operand_map = NULL;
2529   int i;
2530   struct predicate toplev_predicate;
2531   struct predicate true_p = true_predicate ();
2532   struct inline_edge_summary *es = inline_edge_summary (edge);
2533
2534   if (es->predicate)
2535     toplev_predicate = *es->predicate;
2536   else
2537     toplev_predicate = true_predicate ();
2538
2539   if (ipa_node_params_vector && callee_info->conds)
2540     {
2541       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2542       int count = ipa_get_cs_argument_count (args);
2543       int i;
2544
2545       clause = evaluate_conditions_for_edge (edge, true);
2546       if (count)
2547         VEC_safe_grow_cleared (int, heap, operand_map, count);
2548       for (i = 0; i < count; i++)
2549         {
2550           struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2551           int map = -1;
2552           /* TODO: handle non-NOPs when merging.  */
2553           if (jfunc->type == IPA_JF_PASS_THROUGH
2554               && jfunc->value.pass_through.operation == NOP_EXPR)
2555             map = jfunc->value.pass_through.formal_id;
2556           VEC_replace (int, operand_map, i, map);
2557           gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
2558         }
2559     }
2560   for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
2561     {
2562       struct predicate p = remap_predicate (info, callee_info,
2563                                             &e->predicate, operand_map, clause,
2564                                             &toplev_predicate);
2565       if (!false_predicate_p (&p))
2566         {
2567           gcov_type add_time = ((gcov_type)e->time * edge->frequency
2568                                 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2569           int prob = predicate_probability (callee_info->conds,
2570                                             &e->predicate,
2571                                             clause, es->param);
2572           add_time = add_time * prob / REG_BR_PROB_BASE;
2573           if (add_time > MAX_TIME * INLINE_TIME_SCALE)
2574             add_time = MAX_TIME * INLINE_TIME_SCALE;
2575           if (prob != REG_BR_PROB_BASE
2576               && dump_file && (dump_flags & TDF_DETAILS))
2577             {
2578               fprintf (dump_file, "\t\tScaling time by probability:%f\n",
2579                        (double)prob / REG_BR_PROB_BASE);
2580             }
2581           account_size_time (info, e->size, add_time, &p);
2582         }
2583     }
2584   remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
2585                         clause, &toplev_predicate);
2586   info->size = 0;
2587   info->time = 0;
2588   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2589     info->size += e->size, info->time += e->time;
2590   estimate_calls_size_and_time (to, &info->size, &info->time,
2591                                 ~(clause_t)(1 << predicate_false_condition));
2592
2593   inline_update_callee_summaries (edge->callee,
2594                                   inline_edge_summary (edge)->loop_depth);
2595
2596   /* We do not maintain predicates of inlined edges, free it.  */
2597   edge_set_predicate (edge, &true_p);
2598   /* Similarly remove param summaries.  */
2599   VEC_free (inline_param_summary_t, heap, es->param);
2600
2601   info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2602   info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2603 }
2604
2605
2606 /* Estimate the time cost for the caller when inlining EDGE.
2607    Only to be called via estimate_edge_time, that handles the
2608    caching mechanism.
2609
2610    When caching, also update the cache entry.  Compute both time and
2611    size, since we always need both metrics eventually.  */
2612
2613 int
2614 do_estimate_edge_time (struct cgraph_edge *edge)
2615 {
2616   int time;
2617   int size;
2618   gcov_type ret;
2619   struct inline_edge_summary *es = inline_edge_summary (edge);
2620
2621   gcc_checking_assert (edge->inline_failed);
2622   estimate_node_size_and_time (cgraph_function_or_thunk_node (edge->callee,
2623                                                               NULL),
2624                                evaluate_conditions_for_edge (edge, true),
2625                                &size, &time, es->param);
2626
2627   ret = (((gcov_type)time
2628            - es->call_stmt_time) * edge->frequency
2629          + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2630
2631   /* When caching, update the cache entry.  */
2632   if (edge_growth_cache)
2633     {
2634       int ret_size;
2635       if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
2636           <= edge->uid)
2637         VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
2638                                cgraph_edge_max_uid);
2639       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
2640         = ret + (ret >= 0);
2641
2642       ret_size = size - es->call_stmt_size;
2643       gcc_checking_assert (es->call_stmt_size);
2644       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
2645         = ret_size + (ret_size >= 0);
2646     }
2647   return ret;
2648 }
2649
2650
2651 /* Estimate the growth of the caller when inlining EDGE.
2652    Only to be called via estimate_edge_size.  */
2653
2654 int
2655 do_estimate_edge_growth (struct cgraph_edge *edge)
2656 {
2657   int size;
2658   struct cgraph_node *callee;
2659
2660   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
2661
2662   if (edge_growth_cache)
2663     {
2664       do_estimate_edge_time (edge);
2665       size = VEC_index (edge_growth_cache_entry,
2666                         edge_growth_cache,
2667                         edge->uid)->size;
2668       gcc_checking_assert (size);
2669       return size - (size > 0);
2670     }
2671   callee = cgraph_function_or_thunk_node (edge->callee, NULL);
2672
2673   /* Early inliner runs without caching, go ahead and do the dirty work.  */
2674   gcc_checking_assert (edge->inline_failed);
2675   estimate_node_size_and_time (callee,
2676                                evaluate_conditions_for_edge (edge, true),
2677                                &size, NULL, NULL);
2678   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
2679   return size - inline_edge_summary (edge)->call_stmt_size;
2680 }
2681
2682
2683 /* Estimate self time of the function NODE after inlining EDGE.  */
2684
2685 int
2686 estimate_time_after_inlining (struct cgraph_node *node,
2687                               struct cgraph_edge *edge)
2688 {
2689   struct inline_edge_summary *es = inline_edge_summary (edge);
2690   if (!es->predicate || !false_predicate_p (es->predicate))
2691     {
2692       gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
2693       if (time < 0)
2694         time = 0;
2695       if (time > MAX_TIME)
2696         time = MAX_TIME;
2697       return time;
2698     }
2699   return inline_summary (node)->time;
2700 }
2701
2702
2703 /* Estimate the size of NODE after inlining EDGE which should be an
2704    edge to either NODE or a call inlined into NODE.  */
2705
2706 int
2707 estimate_size_after_inlining (struct cgraph_node *node,
2708                               struct cgraph_edge *edge)
2709 {
2710   struct inline_edge_summary *es = inline_edge_summary (edge);
2711   if (!es->predicate || !false_predicate_p (es->predicate))
2712     {
2713       int size = inline_summary (node)->size + estimate_edge_growth (edge);
2714       gcc_assert (size >= 0);
2715       return size;
2716     }
2717   return inline_summary (node)->size;
2718 }
2719
2720
2721 struct growth_data
2722 {
2723   bool self_recursive;
2724   int growth;
2725 };
2726
2727
2728 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
2729
2730 static bool
2731 do_estimate_growth_1 (struct cgraph_node *node, void *data)
2732 {
2733   struct cgraph_edge *e;
2734   struct growth_data *d = (struct growth_data *) data;
2735
2736   for (e = node->callers; e; e = e->next_caller)
2737     {
2738       gcc_checking_assert (e->inline_failed);
2739
2740       if (e->caller == node
2741           || (e->caller->global.inlined_to
2742               && e->caller->global.inlined_to == node))
2743         d->self_recursive = true;
2744       d->growth += estimate_edge_growth (e);
2745     }
2746   return false;
2747 }
2748
2749
2750 /* Estimate the growth caused by inlining NODE into all callees.  */
2751
2752 int
2753 do_estimate_growth (struct cgraph_node *node)
2754 {
2755   struct growth_data d = {0, false};
2756   struct inline_summary *info = inline_summary (node);
2757
2758   cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
2759
2760   /* For self recursive functions the growth estimation really should be
2761      infinity.  We don't want to return very large values because the growth
2762      plays various roles in badness computation fractions.  Be sure to not
2763      return zero or negative growths. */
2764   if (d.self_recursive)
2765     d.growth = d.growth < info->size ? info->size : d.growth;
2766   else
2767     {
2768       if (!DECL_EXTERNAL (node->decl)
2769           && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
2770         d.growth -= info->size;
2771       /* COMDAT functions are very often not shared across multiple units
2772          since they come from various template instantiations.
2773          Take this into account.  */
2774       else  if (DECL_COMDAT (node->decl)
2775                 && cgraph_can_remove_if_no_direct_calls_p (node))
2776         d.growth -= (info->size
2777                      * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
2778                      + 50) / 100;
2779     }
2780
2781   if (node_growth_cache)
2782     {
2783       if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2784         VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2785       VEC_replace (int, node_growth_cache, node->uid,
2786                    d.growth + (d.growth >= 0));
2787     }
2788   return d.growth;
2789 }
2790
2791
2792 /* This function performs intraprocedural analysis in NODE that is required to
2793    inline indirect calls.  */
2794
2795 static void
2796 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2797 {
2798   ipa_analyze_node (node);
2799   if (dump_file && (dump_flags & TDF_DETAILS))
2800     {
2801       ipa_print_node_params (dump_file, node);
2802       ipa_print_node_jump_functions (dump_file, node);
2803     }
2804 }
2805
2806
2807 /* Note function body size.  */
2808
2809 static void
2810 inline_analyze_function (struct cgraph_node *node)
2811 {
2812   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2813   current_function_decl = node->decl;
2814
2815   if (dump_file)
2816     fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2817              cgraph_node_name (node), node->uid);
2818   if (optimize && !node->thunk.thunk_p)
2819     inline_indirect_intraprocedural_analysis (node);
2820   compute_inline_parameters (node, false);
2821
2822   current_function_decl = NULL;
2823   pop_cfun ();
2824 }
2825
2826
2827 /* Called when new function is inserted to callgraph late.  */
2828
2829 static void
2830 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2831 {
2832   inline_analyze_function (node);
2833 }
2834
2835
2836 /* Note function body size.  */
2837
2838 void
2839 inline_generate_summary (void)
2840 {
2841   struct cgraph_node *node;
2842
2843   function_insertion_hook_holder =
2844       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2845
2846   ipa_register_cgraph_hooks ();
2847   inline_free_summary ();
2848
2849   FOR_EACH_DEFINED_FUNCTION (node)
2850     if (!node->alias)
2851       inline_analyze_function (node);
2852 }
2853
2854
2855 /* Read predicate from IB.  */
2856
2857 static struct predicate
2858 read_predicate (struct lto_input_block *ib)
2859 {
2860   struct predicate out;
2861   clause_t clause;
2862   int k = 0;
2863
2864   do 
2865     {
2866       gcc_assert (k <= MAX_CLAUSES);
2867       clause = out.clause[k++] = streamer_read_uhwi (ib);
2868     }
2869   while (clause);
2870
2871   /* Zero-initialize the remaining clauses in OUT.  */
2872   while (k <= MAX_CLAUSES)
2873     out.clause[k++] = 0;
2874
2875   return out;
2876 }
2877
2878
2879 /* Write inline summary for edge E to OB.  */
2880
2881 static void
2882 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2883 {
2884   struct inline_edge_summary *es = inline_edge_summary (e);
2885   struct predicate p;
2886   int length, i;
2887
2888   es->call_stmt_size = streamer_read_uhwi (ib);
2889   es->call_stmt_time = streamer_read_uhwi (ib);
2890   es->loop_depth = streamer_read_uhwi (ib);
2891   p = read_predicate (ib);
2892   edge_set_predicate (e, &p);
2893   length = streamer_read_uhwi (ib);
2894   if (length)
2895     {
2896       VEC_safe_grow_cleared (inline_param_summary_t, heap, es->param, length);
2897       for (i = 0; i < length; i++)
2898         VEC_index (inline_param_summary_t, es->param, i)->change_prob
2899           = streamer_read_uhwi (ib);
2900     }
2901 }
2902
2903
2904 /* Stream in inline summaries from the section.  */
2905
2906 static void
2907 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
2908                      size_t len)
2909 {
2910   const struct lto_function_header *header =
2911     (const struct lto_function_header *) data;
2912   const int32_t cfg_offset = sizeof (struct lto_function_header);
2913   const int32_t main_offset = cfg_offset + header->cfg_size;
2914   const int32_t string_offset = main_offset + header->main_size;
2915   struct data_in *data_in;
2916   struct lto_input_block ib;
2917   unsigned int i, count2, j;
2918   unsigned int f_count;
2919
2920   LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
2921                         header->main_size);
2922
2923   data_in =
2924     lto_data_in_create (file_data, (const char *) data + string_offset,
2925                         header->string_size, NULL);
2926   f_count = streamer_read_uhwi (&ib);
2927   for (i = 0; i < f_count; i++)
2928     {
2929       unsigned int index;
2930       struct cgraph_node *node;
2931       struct inline_summary *info;
2932       lto_cgraph_encoder_t encoder;
2933       struct bitpack_d bp;
2934       struct cgraph_edge *e;
2935
2936       index = streamer_read_uhwi (&ib);
2937       encoder = file_data->cgraph_node_encoder;
2938       node = lto_cgraph_encoder_deref (encoder, index);
2939       info = inline_summary (node);
2940
2941       info->estimated_stack_size
2942         = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
2943       info->size = info->self_size = streamer_read_uhwi (&ib);
2944       info->time = info->self_time = streamer_read_uhwi (&ib);
2945
2946       bp = streamer_read_bitpack (&ib);
2947       info->inlinable = bp_unpack_value (&bp, 1);
2948
2949       count2 = streamer_read_uhwi (&ib);
2950       gcc_assert (!info->conds);
2951       for (j = 0; j < count2; j++)
2952         {
2953           struct condition c;
2954           c.operand_num = streamer_read_uhwi (&ib);
2955           c.code = (enum tree_code) streamer_read_uhwi (&ib);
2956           c.val = stream_read_tree (&ib, data_in);
2957           VEC_safe_push (condition, gc, info->conds, &c);
2958         }
2959       count2 = streamer_read_uhwi (&ib);
2960       gcc_assert (!info->entry);
2961       for (j = 0; j < count2; j++)
2962         {
2963           struct size_time_entry e;
2964
2965           e.size = streamer_read_uhwi (&ib);
2966           e.time = streamer_read_uhwi (&ib);
2967           e.predicate = read_predicate (&ib);
2968
2969           VEC_safe_push (size_time_entry, gc, info->entry, &e);
2970         }
2971       for (e = node->callees; e; e = e->next_callee)
2972         read_inline_edge_summary (&ib, e);
2973       for (e = node->indirect_calls; e; e = e->next_callee)
2974         read_inline_edge_summary (&ib, e);
2975     }
2976
2977   lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
2978                          len);
2979   lto_data_in_delete (data_in);
2980 }
2981
2982
2983 /* Read inline summary.  Jump functions are shared among ipa-cp
2984    and inliner, so when ipa-cp is active, we don't need to write them
2985    twice.  */
2986
2987 void
2988 inline_read_summary (void)
2989 {
2990   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2991   struct lto_file_decl_data *file_data;
2992   unsigned int j = 0;
2993
2994   inline_summary_alloc ();
2995
2996   while ((file_data = file_data_vec[j++]))
2997     {
2998       size_t len;
2999       const char *data = lto_get_section_data (file_data,
3000                                                LTO_section_inline_summary,
3001                                                NULL, &len);
3002       if (data)
3003         inline_read_section (file_data, data, len);
3004       else
3005         /* Fatal error here.  We do not want to support compiling ltrans units
3006            with different version of compiler or different flags than the WPA
3007            unit, so this should never happen.  */
3008         fatal_error ("ipa inline summary is missing in input file");
3009     }
3010   if (optimize)
3011     {
3012       ipa_register_cgraph_hooks ();
3013       if (!flag_ipa_cp)
3014         ipa_prop_read_jump_functions ();
3015     }
3016   function_insertion_hook_holder =
3017       cgraph_add_function_insertion_hook (&add_new_function, NULL);
3018 }
3019
3020
3021 /* Write predicate P to OB.  */
3022
3023 static void
3024 write_predicate (struct output_block *ob, struct predicate *p)
3025 {
3026   int j;
3027   if (p)
3028     for (j = 0; p->clause[j]; j++)
3029       {
3030          gcc_assert (j < MAX_CLAUSES);
3031          streamer_write_uhwi (ob, p->clause[j]);
3032       }
3033   streamer_write_uhwi (ob, 0);
3034 }
3035
3036
3037 /* Write inline summary for edge E to OB.  */
3038
3039 static void
3040 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
3041 {
3042   struct inline_edge_summary *es = inline_edge_summary (e);
3043   int i;
3044
3045   streamer_write_uhwi (ob, es->call_stmt_size);
3046   streamer_write_uhwi (ob, es->call_stmt_time);
3047   streamer_write_uhwi (ob, es->loop_depth);
3048   write_predicate (ob, es->predicate);
3049   streamer_write_uhwi (ob, VEC_length (inline_param_summary_t, es->param));
3050   for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param); i++)
3051     streamer_write_uhwi (ob, VEC_index (inline_param_summary_t,
3052                                         es->param, i)->change_prob);
3053 }
3054
3055
3056 /* Write inline summary for node in SET.
3057    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3058    active, we don't need to write them twice.  */
3059
3060 void
3061 inline_write_summary (cgraph_node_set set,
3062                       varpool_node_set vset ATTRIBUTE_UNUSED)
3063 {
3064   struct cgraph_node *node;
3065   struct output_block *ob = create_output_block (LTO_section_inline_summary);
3066   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
3067   unsigned int count = 0;
3068   int i;
3069
3070   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3071     if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
3072       count++;
3073   streamer_write_uhwi (ob, count);
3074
3075   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
3076     {
3077       node = lto_cgraph_encoder_deref (encoder, i);
3078       if (node->analyzed)
3079         {
3080           struct inline_summary *info = inline_summary (node);
3081           struct bitpack_d bp;
3082           struct cgraph_edge *edge;
3083           int i;
3084           size_time_entry *e;
3085           struct condition *c;
3086
3087           streamer_write_uhwi (ob, lto_cgraph_encoder_encode (encoder, node));
3088           streamer_write_hwi (ob, info->estimated_self_stack_size);
3089           streamer_write_hwi (ob, info->self_size);
3090           streamer_write_hwi (ob, info->self_time);
3091           bp = bitpack_create (ob->main_stream);
3092           bp_pack_value (&bp, info->inlinable, 1);
3093           streamer_write_bitpack (&bp);
3094           streamer_write_uhwi (ob, VEC_length (condition, info->conds));
3095           for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
3096             {
3097               streamer_write_uhwi (ob, c->operand_num);
3098               streamer_write_uhwi (ob, c->code);
3099               stream_write_tree (ob, c->val, true);
3100             }
3101           streamer_write_uhwi (ob, VEC_length (size_time_entry, info->entry));
3102           for (i = 0;
3103                VEC_iterate (size_time_entry, info->entry, i, e);
3104                i++)
3105             {
3106               streamer_write_uhwi (ob, e->size);
3107               streamer_write_uhwi (ob, e->time);
3108               write_predicate (ob, &e->predicate);
3109             }
3110           for (edge = node->callees; edge; edge = edge->next_callee)
3111             write_inline_edge_summary (ob, edge);
3112           for (edge = node->indirect_calls; edge; edge = edge->next_callee)
3113             write_inline_edge_summary (ob, edge);
3114         }
3115     }
3116   streamer_write_char_stream (ob->main_stream, 0);
3117   produce_asm (ob, NULL);
3118   destroy_output_block (ob);
3119
3120   if (optimize && !flag_ipa_cp)
3121     ipa_prop_write_jump_functions (set);
3122 }
3123
3124
3125 /* Release inline summary.  */
3126
3127 void
3128 inline_free_summary (void)
3129 {
3130   struct cgraph_node *node;
3131   FOR_EACH_DEFINED_FUNCTION (node)
3132     reset_inline_summary (node);
3133   if (function_insertion_hook_holder)
3134     cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
3135   function_insertion_hook_holder = NULL;
3136   if (node_removal_hook_holder)
3137     cgraph_remove_node_removal_hook (node_removal_hook_holder);
3138   node_removal_hook_holder = NULL;
3139   if (edge_removal_hook_holder)
3140     cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
3141   edge_removal_hook_holder = NULL;
3142   if (node_duplication_hook_holder)
3143     cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
3144   node_duplication_hook_holder = NULL;
3145   if (edge_duplication_hook_holder)
3146     cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3147   edge_duplication_hook_holder = NULL;
3148   VEC_free (inline_summary_t, gc, inline_summary_vec);
3149   inline_summary_vec = NULL;
3150   VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
3151   inline_edge_summary_vec = NULL;
3152   if (edge_predicate_pool)
3153     free_alloc_pool (edge_predicate_pool);
3154   edge_predicate_pool = 0;
3155 }