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