Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / ipa-prop.c
1 /* Interprocedural analyses.
2    Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
3    Free Software Foundation, Inc.
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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "langhooks.h"
26 #include "ggc.h"
27 #include "target.h"
28 #include "cgraph.h"
29 #include "ipa-prop.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-inline.h"
33 #include "gimple.h"
34 #include "flags.h"
35 #include "timevar.h"
36 #include "flags.h"
37 #include "diagnostic.h"
38 #include "tree-pretty-print.h"
39 #include "gimple-pretty-print.h"
40 #include "lto-streamer.h"
41 #include "data-streamer.h"
42 #include "tree-streamer.h"
43
44
45 /* Intermediate information about a parameter that is only useful during the
46    run of ipa_analyze_node and is not kept afterwards.  */
47
48 struct param_analysis_info
49 {
50   bool modified;
51   bitmap visited_statements;
52 };
53
54 /* Vector where the parameter infos are actually stored. */
55 VEC (ipa_node_params_t, heap) *ipa_node_params_vector;
56 /* Vector where the parameter infos are actually stored. */
57 VEC (ipa_edge_args_t, gc) *ipa_edge_args_vector;
58
59 /* Holders of ipa cgraph hooks: */
60 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
61 static struct cgraph_node_hook_list *node_removal_hook_holder;
62 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
63 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
64 static struct cgraph_node_hook_list *function_insertion_hook_holder;
65
66 /* Return index of the formal whose tree is PTREE in function which corresponds
67    to INFO.  */
68
69 int
70 ipa_get_param_decl_index (struct ipa_node_params *info, tree ptree)
71 {
72   int i, count;
73
74   count = ipa_get_param_count (info);
75   for (i = 0; i < count; i++)
76     if (ipa_get_param (info, i) == ptree)
77       return i;
78
79   return -1;
80 }
81
82 /* Populate the param_decl field in parameter descriptors of INFO that
83    corresponds to NODE.  */
84
85 static void
86 ipa_populate_param_decls (struct cgraph_node *node,
87                           struct ipa_node_params *info)
88 {
89   tree fndecl;
90   tree fnargs;
91   tree parm;
92   int param_num;
93
94   fndecl = node->decl;
95   fnargs = DECL_ARGUMENTS (fndecl);
96   param_num = 0;
97   for (parm = fnargs; parm; parm = DECL_CHAIN (parm))
98     {
99       VEC_index (ipa_param_descriptor_t,
100                  info->descriptors, param_num)->decl = parm;
101       param_num++;
102     }
103 }
104
105 /* Return how many formal parameters FNDECL has.  */
106
107 static inline int
108 count_formal_params (tree fndecl)
109 {
110   tree parm;
111   int count = 0;
112
113   for (parm = DECL_ARGUMENTS (fndecl); parm; parm = DECL_CHAIN (parm))
114     count++;
115
116   return count;
117 }
118
119 /* Initialize the ipa_node_params structure associated with NODE by counting
120    the function parameters, creating the descriptors and populating their
121    param_decls.  */
122
123 void
124 ipa_initialize_node_params (struct cgraph_node *node)
125 {
126   struct ipa_node_params *info = IPA_NODE_REF (node);
127
128   if (!info->descriptors)
129     {
130       int param_count;
131
132       param_count = count_formal_params (node->decl);
133       if (param_count)
134         {
135           VEC_safe_grow_cleared (ipa_param_descriptor_t, heap,
136                                  info->descriptors, param_count);
137           ipa_populate_param_decls (node, info);
138         }
139     }
140 }
141
142 /* Print the jump functions associated with call graph edge CS to file F.  */
143
144 static void
145 ipa_print_node_jump_functions_for_edge (FILE *f, struct cgraph_edge *cs)
146 {
147   int i, count;
148
149   count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
150   for (i = 0; i < count; i++)
151     {
152       struct ipa_jump_func *jump_func;
153       enum jump_func_type type;
154
155       jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
156       type = jump_func->type;
157
158       fprintf (f, "       param %d: ", i);
159       if (type == IPA_JF_UNKNOWN)
160         fprintf (f, "UNKNOWN\n");
161       else if (type == IPA_JF_KNOWN_TYPE)
162         {
163           fprintf (f, "KNOWN TYPE: base  ");
164           print_generic_expr (f, jump_func->value.known_type.base_type, 0);
165           fprintf (f, ", offset "HOST_WIDE_INT_PRINT_DEC", component ",
166                    jump_func->value.known_type.offset);
167           print_generic_expr (f, jump_func->value.known_type.component_type, 0);
168           fprintf (f, "\n");
169         }
170       else if (type == IPA_JF_CONST)
171         {
172           tree val = jump_func->value.constant;
173           fprintf (f, "CONST: ");
174           print_generic_expr (f, val, 0);
175           if (TREE_CODE (val) == ADDR_EXPR
176               && TREE_CODE (TREE_OPERAND (val, 0)) == CONST_DECL)
177             {
178               fprintf (f, " -> ");
179               print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (val, 0)),
180                                   0);
181             }
182           fprintf (f, "\n");
183         }
184       else if (type == IPA_JF_CONST_MEMBER_PTR)
185         {
186           fprintf (f, "CONST MEMBER PTR: ");
187           print_generic_expr (f, jump_func->value.member_cst.pfn, 0);
188           fprintf (f, ", ");
189           print_generic_expr (f, jump_func->value.member_cst.delta, 0);
190           fprintf (f, "\n");
191         }
192       else if (type == IPA_JF_PASS_THROUGH)
193         {
194           fprintf (f, "PASS THROUGH: ");
195           fprintf (f, "%d, op %s ",
196                    jump_func->value.pass_through.formal_id,
197                    tree_code_name[(int)
198                                   jump_func->value.pass_through.operation]);
199           if (jump_func->value.pass_through.operation != NOP_EXPR)
200             print_generic_expr (f,
201                                 jump_func->value.pass_through.operand, 0);
202           fprintf (f, "\n");
203         }
204       else if (type == IPA_JF_ANCESTOR)
205         {
206           fprintf (f, "ANCESTOR: ");
207           fprintf (f, "%d, offset "HOST_WIDE_INT_PRINT_DEC", ",
208                    jump_func->value.ancestor.formal_id,
209                    jump_func->value.ancestor.offset);
210           print_generic_expr (f, jump_func->value.ancestor.type, 0);
211           fprintf (f, "\n");
212         }
213     }
214 }
215
216
217 /* Print the jump functions of all arguments on all call graph edges going from
218    NODE to file F.  */
219
220 void
221 ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node)
222 {
223   struct cgraph_edge *cs;
224   int i;
225
226   fprintf (f, "  Jump functions of caller  %s:\n", cgraph_node_name (node));
227   for (cs = node->callees; cs; cs = cs->next_callee)
228     {
229       if (!ipa_edge_args_info_available_for_edge_p (cs))
230         continue;
231
232       fprintf (f, "    callsite  %s/%i -> %s/%i : \n",
233                xstrdup (cgraph_node_name (node)), node->uid,
234                xstrdup (cgraph_node_name (cs->callee)), cs->callee->uid);
235       ipa_print_node_jump_functions_for_edge (f, cs);
236     }
237
238   for (cs = node->indirect_calls, i = 0; cs; cs = cs->next_callee, i++)
239     {
240       if (!ipa_edge_args_info_available_for_edge_p (cs))
241         continue;
242
243       if (cs->call_stmt)
244         {
245           fprintf (f, "    indirect callsite %d for stmt ", i);
246           print_gimple_stmt (f, cs->call_stmt, 0, TDF_SLIM);
247         }
248       else
249         fprintf (f, "    indirect callsite %d :\n", i);
250       ipa_print_node_jump_functions_for_edge (f, cs);
251
252     }
253 }
254
255 /* Print ipa_jump_func data structures of all nodes in the call graph to F.  */
256
257 void
258 ipa_print_all_jump_functions (FILE *f)
259 {
260   struct cgraph_node *node;
261
262   fprintf (f, "\nJump functions:\n");
263   for (node = cgraph_nodes; node; node = node->next)
264     {
265       ipa_print_node_jump_functions (f, node);
266     }
267 }
268
269 /* Structure to be passed in between detect_type_change and
270    check_stmt_for_type_change.  */
271
272 struct type_change_info
273 {
274   /* Offset into the object where there is the virtual method pointer we are
275      looking for.  */
276   HOST_WIDE_INT offset;
277   /* The declaration or SSA_NAME pointer of the base that we are checking for
278      type change.  */
279   tree object;
280   /* If we actually can tell the type that the object has changed to, it is
281      stored in this field.  Otherwise it remains NULL_TREE.  */
282   tree known_current_type;
283   /* Set to true if dynamic type change has been detected.  */
284   bool type_maybe_changed;
285   /* Set to true if multiple types have been encountered.  known_current_type
286      must be disregarded in that case.  */
287   bool multiple_types_encountered;
288 };
289
290 /* Return true if STMT can modify a virtual method table pointer.
291
292    This function makes special assumptions about both constructors and
293    destructors which are all the functions that are allowed to alter the VMT
294    pointers.  It assumes that destructors begin with assignment into all VMT
295    pointers and that constructors essentially look in the following way:
296
297    1) The very first thing they do is that they call constructors of ancestor
298    sub-objects that have them.
299
300    2) Then VMT pointers of this and all its ancestors is set to new values
301    corresponding to the type corresponding to the constructor.
302
303    3) Only afterwards, other stuff such as constructor of member sub-objects
304    and the code written by the user is run.  Only this may include calling
305    virtual functions, directly or indirectly.
306
307    There is no way to call a constructor of an ancestor sub-object in any
308    other way.
309
310    This means that we do not have to care whether constructors get the correct
311    type information because they will always change it (in fact, if we define
312    the type to be given by the VMT pointer, it is undefined).
313
314    The most important fact to derive from the above is that if, for some
315    statement in the section 3, we try to detect whether the dynamic type has
316    changed, we can safely ignore all calls as we examine the function body
317    backwards until we reach statements in section 2 because these calls cannot
318    be ancestor constructors or destructors (if the input is not bogus) and so
319    do not change the dynamic type (this holds true only for automatically
320    allocated objects but at the moment we devirtualize only these).  We then
321    must detect that statements in section 2 change the dynamic type and can try
322    to derive the new type.  That is enough and we can stop, we will never see
323    the calls into constructors of sub-objects in this code.  Therefore we can
324    safely ignore all call statements that we traverse.
325   */
326
327 static bool
328 stmt_may_be_vtbl_ptr_store (gimple stmt)
329 {
330   if (is_gimple_call (stmt))
331     return false;
332   else if (is_gimple_assign (stmt))
333     {
334       tree lhs = gimple_assign_lhs (stmt);
335
336       if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
337         {
338           if (flag_strict_aliasing
339               && !POINTER_TYPE_P (TREE_TYPE (lhs)))
340             return false;
341
342           if (TREE_CODE (lhs) == COMPONENT_REF
343               && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
344             return false;
345           /* In the future we might want to use get_base_ref_and_offset to find
346              if there is a field corresponding to the offset and if so, proceed
347              almost like if it was a component ref.  */
348         }
349     }
350   return true;
351 }
352
353 /* If STMT can be proved to be an assignment to the virtual method table
354    pointer of ANALYZED_OBJ and the type associated with the new table
355    identified, return the type.  Otherwise return NULL_TREE.  */
356
357 static tree
358 extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci)
359 {
360   HOST_WIDE_INT offset, size, max_size;
361   tree lhs, rhs, base;
362
363   if (!gimple_assign_single_p (stmt))
364     return NULL_TREE;
365
366   lhs = gimple_assign_lhs (stmt);
367   rhs = gimple_assign_rhs1 (stmt);
368   if (TREE_CODE (lhs) != COMPONENT_REF
369       || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
370       || TREE_CODE (rhs) != ADDR_EXPR)
371     return NULL_TREE;
372   rhs = get_base_address (TREE_OPERAND (rhs, 0));
373   if (!rhs
374       || TREE_CODE (rhs) != VAR_DECL
375       || !DECL_VIRTUAL_P (rhs))
376     return NULL_TREE;
377
378   base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
379   if (offset != tci->offset
380       || size != POINTER_SIZE
381       || max_size != POINTER_SIZE)
382     return NULL_TREE;
383   if (TREE_CODE (base) == MEM_REF)
384     {
385       if (TREE_CODE (tci->object) != MEM_REF
386           || TREE_OPERAND (tci->object, 0) != TREE_OPERAND (base, 0)
387           || !tree_int_cst_equal (TREE_OPERAND (tci->object, 1),
388                                   TREE_OPERAND (base, 1)))
389         return NULL_TREE;
390     }
391   else if (tci->object != base)
392     return NULL_TREE;
393
394   return DECL_CONTEXT (rhs);
395 }
396
397 /* Callback of walk_aliased_vdefs and a helper function for
398    detect_type_change to check whether a particular statement may modify
399    the virtual table pointer, and if possible also determine the new type of
400    the (sub-)object.  It stores its result into DATA, which points to a
401    type_change_info structure.  */
402
403 static bool
404 check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
405 {
406   gimple stmt = SSA_NAME_DEF_STMT (vdef);
407   struct type_change_info *tci = (struct type_change_info *) data;
408
409   if (stmt_may_be_vtbl_ptr_store (stmt))
410     {
411       tree type;
412       type = extr_type_from_vtbl_ptr_store (stmt, tci);
413       if (tci->type_maybe_changed
414           && type != tci->known_current_type)
415         tci->multiple_types_encountered = true;
416       tci->known_current_type = type;
417       tci->type_maybe_changed = true;
418       return true;
419     }
420   else
421     return false;
422 }
423
424
425
426 /* Like detect_type_change but with extra argument COMP_TYPE which will become
427    the component type part of new JFUNC of dynamic type change is detected and
428    the new base type is identified.  */
429
430 static bool
431 detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call,
432                       struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
433 {
434   struct type_change_info tci;
435   ao_ref ao;
436
437   gcc_checking_assert (DECL_P (arg)
438                        || TREE_CODE (arg) == MEM_REF
439                        || handled_component_p (arg));
440   /* Const calls cannot call virtual methods through VMT and so type changes do
441      not matter.  */
442   if (!flag_devirtualize || !gimple_vuse (call))
443     return false;
444
445   ao_ref_init (&ao, arg);
446   ao.base = base;
447   ao.offset = offset;
448   ao.size = POINTER_SIZE;
449   ao.max_size = ao.size;
450
451   tci.offset = offset;
452   tci.object = get_base_address (arg);
453   tci.known_current_type = NULL_TREE;
454   tci.type_maybe_changed = false;
455   tci.multiple_types_encountered = false;
456
457   walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
458                       &tci, NULL);
459   if (!tci.type_maybe_changed)
460     return false;
461
462   if (!tci.known_current_type
463       || tci.multiple_types_encountered
464       || offset != 0)
465     jfunc->type = IPA_JF_UNKNOWN;
466   else
467     {
468       jfunc->type = IPA_JF_KNOWN_TYPE;
469       jfunc->value.known_type.base_type = tci.known_current_type;
470       jfunc->value.known_type.component_type = comp_type;
471     }
472
473   return true;
474 }
475
476 /* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
477    looking for assignments to its virtual table pointer.  If it is, return true
478    and fill in the jump function JFUNC with relevant type information or set it
479    to unknown.  ARG is the object itself (not a pointer to it, unless
480    dereferenced).  BASE is the base of the memory access as returned by
481    get_ref_base_and_extent, as is the offset.  */
482
483 static bool
484 detect_type_change (tree arg, tree base, gimple call,
485                     struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
486 {
487   return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset);
488 }
489
490 /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
491    SSA name (its dereference will become the base and the offset is assumed to
492    be zero).  */
493
494 static bool
495 detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
496 {
497   tree comp_type;
498
499   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
500   if (!flag_devirtualize
501       || !POINTER_TYPE_P (TREE_TYPE (arg))
502       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
503     return false;
504
505   comp_type = TREE_TYPE (TREE_TYPE (arg));
506   arg = build2 (MEM_REF, ptr_type_node, arg,
507                 build_int_cst (ptr_type_node, 0));
508
509   return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0);
510 }
511
512 /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the
513    boolean variable pointed to by DATA.  */
514
515 static bool
516 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
517                      void *data)
518 {
519   bool *b = (bool *) data;
520   *b = true;
521   return true;
522 }
523
524 /* Return true if the formal parameter PARM might have been modified in this
525    function before reaching the statement STMT.  PARM_AINFO is a pointer to a
526    structure containing temporary information about PARM.  */
527
528 static bool
529 is_parm_modified_before_stmt (struct param_analysis_info *parm_ainfo,
530                               gimple stmt, tree parm)
531 {
532   bool modified = false;
533   ao_ref refd;
534
535   if (parm_ainfo->modified)
536     return true;
537
538   gcc_checking_assert (gimple_vuse (stmt) != NULL_TREE);
539   ao_ref_init (&refd, parm);
540   walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified,
541                       &modified, &parm_ainfo->visited_statements);
542   if (modified)
543     {
544       parm_ainfo->modified = true;
545       return true;
546     }
547   return false;
548 }
549
550 /* If STMT is an assignment that loads a value from an parameter declaration,
551    return the index of the parameter in ipa_node_params which has not been
552    modified.  Otherwise return -1.  */
553
554 static int
555 load_from_unmodified_param (struct ipa_node_params *info,
556                             struct param_analysis_info *parms_ainfo,
557                             gimple stmt)
558 {
559   int index;
560   tree op1;
561
562   if (!gimple_assign_single_p (stmt))
563     return -1;
564
565   op1 = gimple_assign_rhs1 (stmt);
566   if (TREE_CODE (op1) != PARM_DECL)
567     return -1;
568
569   index = ipa_get_param_decl_index (info, op1);
570   if (index < 0
571       || is_parm_modified_before_stmt (&parms_ainfo[index], stmt, op1))
572     return -1;
573
574   return index;
575 }
576
577 /* Given that an actual argument is an SSA_NAME (given in NAME) and is a result
578    of an assignment statement STMT, try to determine whether we are actually
579    handling any of the following cases and construct an appropriate jump
580    function into JFUNC if so:
581
582    1) The passed value is loaded from a formal parameter which is not a gimple
583    register (most probably because it is addressable, the value has to be
584    scalar) and we can guarantee the value has not changed.  This case can
585    therefore be described by a simple pass-through jump function.  For example:
586
587       foo (int a)
588       {
589         int a.0;
590
591         a.0_2 = a;
592         bar (a.0_2);
593
594    2) The passed value can be described by a simple arithmetic pass-through
595    jump function. E.g.
596
597       foo (int a)
598       {
599         int D.2064;
600
601         D.2064_4 = a.1(D) + 4;
602         bar (D.2064_4);
603
604    This case can also occur in combination of the previous one, e.g.:
605
606       foo (int a, int z)
607       {
608         int a.0;
609         int D.2064;
610
611         a.0_3 = a;
612         D.2064_4 = a.0_3 + 4;
613         foo (D.2064_4);
614
615    3) The passed value is an address of an object within another one (which
616    also passed by reference).  Such situations are described by an ancestor
617    jump function and describe situations such as:
618
619      B::foo() (struct B * const this)
620      {
621        struct A * D.1845;
622
623        D.1845_2 = &this_1(D)->D.1748;
624        A::bar (D.1845_2);
625
626    INFO is the structure describing individual parameters access different
627    stages of IPA optimizations.  PARMS_AINFO contains the information that is
628    only needed for intraprocedural analysis.  */
629
630 static void
631 compute_complex_assign_jump_func (struct ipa_node_params *info,
632                                   struct param_analysis_info *parms_ainfo,
633                                   struct ipa_jump_func *jfunc,
634                                   gimple call, gimple stmt, tree name)
635 {
636   HOST_WIDE_INT offset, size, max_size;
637   tree op1, tc_ssa, base, ssa;
638   int index;
639
640   op1 = gimple_assign_rhs1 (stmt);
641
642   if (TREE_CODE (op1) == SSA_NAME)
643     {
644       if (SSA_NAME_IS_DEFAULT_DEF (op1))
645         index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
646       else
647         index = load_from_unmodified_param (info, parms_ainfo,
648                                             SSA_NAME_DEF_STMT (op1));
649       tc_ssa = op1;
650     }
651   else
652     {
653       index = load_from_unmodified_param (info, parms_ainfo, stmt);
654       tc_ssa = gimple_assign_lhs (stmt);
655     }
656
657   if (index >= 0)
658     {
659       tree op2 = gimple_assign_rhs2 (stmt);
660
661       if (op2)
662         {
663           if (!is_gimple_ip_invariant (op2)
664               || (TREE_CODE_CLASS (gimple_expr_code (stmt)) != tcc_comparison
665                   && !useless_type_conversion_p (TREE_TYPE (name),
666                                                  TREE_TYPE (op1))))
667             return;
668
669           jfunc->type = IPA_JF_PASS_THROUGH;
670           jfunc->value.pass_through.formal_id = index;
671           jfunc->value.pass_through.operation = gimple_assign_rhs_code (stmt);
672           jfunc->value.pass_through.operand = op2;
673         }
674       else if (gimple_assign_single_p (stmt)
675                && !detect_type_change_ssa (tc_ssa, call, jfunc))
676         {
677           jfunc->type = IPA_JF_PASS_THROUGH;
678           jfunc->value.pass_through.formal_id = index;
679           jfunc->value.pass_through.operation = NOP_EXPR;
680         }
681       return;
682     }
683
684   if (TREE_CODE (op1) != ADDR_EXPR)
685     return;
686   op1 = TREE_OPERAND (op1, 0);
687   if (TREE_CODE (TREE_TYPE (op1)) != RECORD_TYPE)
688     return;
689   base = get_ref_base_and_extent (op1, &offset, &size, &max_size);
690   if (TREE_CODE (base) != MEM_REF
691       /* If this is a varying address, punt.  */
692       || max_size == -1
693       || max_size != size)
694     return;
695   offset += mem_ref_offset (base).low * BITS_PER_UNIT;
696   ssa = TREE_OPERAND (base, 0);
697   if (TREE_CODE (ssa) != SSA_NAME
698       || !SSA_NAME_IS_DEFAULT_DEF (ssa)
699       || offset < 0)
700     return;
701
702   /* Dynamic types are changed only in constructors and destructors and  */
703   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (ssa));
704   if (index >= 0
705       && !detect_type_change (op1, base, call, jfunc, offset))
706     {
707       jfunc->type = IPA_JF_ANCESTOR;
708       jfunc->value.ancestor.formal_id = index;
709       jfunc->value.ancestor.offset = offset;
710       jfunc->value.ancestor.type = TREE_TYPE (op1);
711     }
712 }
713
714 /* Extract the base, offset and MEM_REF expression from a statement ASSIGN if
715    it looks like:
716
717    iftmp.1_3 = &obj_2(D)->D.1762;
718
719    The base of the MEM_REF must be a default definition SSA NAME of a
720    parameter.  Return NULL_TREE if it looks otherwise.  If case of success, the
721    whole MEM_REF expression is returned and the offset calculated from any
722    handled components and the MEM_REF itself is stored into *OFFSET.  The whole
723    RHS stripped off the ADDR_EXPR is stored into *OBJ_P.  */
724
725 static tree
726 get_ancestor_addr_info (gimple assign, tree *obj_p, HOST_WIDE_INT *offset)
727 {
728   HOST_WIDE_INT size, max_size;
729   tree expr, parm, obj;
730
731   if (!gimple_assign_single_p (assign))
732     return NULL_TREE;
733   expr = gimple_assign_rhs1 (assign);
734
735   if (TREE_CODE (expr) != ADDR_EXPR)
736     return NULL_TREE;
737   expr = TREE_OPERAND (expr, 0);
738   obj = expr;
739   expr = get_ref_base_and_extent (expr, offset, &size, &max_size);
740
741   if (TREE_CODE (expr) != MEM_REF
742       /* If this is a varying address, punt.  */
743       || max_size == -1
744       || max_size != size
745       || *offset < 0)
746     return NULL_TREE;
747   parm = TREE_OPERAND (expr, 0);
748   if (TREE_CODE (parm) != SSA_NAME
749       || !SSA_NAME_IS_DEFAULT_DEF (parm)
750       || TREE_CODE (SSA_NAME_VAR (parm)) != PARM_DECL)
751     return NULL_TREE;
752
753   *offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
754   *obj_p = obj;
755   return expr;
756 }
757
758
759 /* Given that an actual argument is an SSA_NAME that is a result of a phi
760    statement PHI, try to find out whether NAME is in fact a
761    multiple-inheritance typecast from a descendant into an ancestor of a formal
762    parameter and thus can be described by an ancestor jump function and if so,
763    write the appropriate function into JFUNC.
764
765    Essentially we want to match the following pattern:
766
767      if (obj_2(D) != 0B)
768        goto <bb 3>;
769      else
770        goto <bb 4>;
771
772    <bb 3>:
773      iftmp.1_3 = &obj_2(D)->D.1762;
774
775    <bb 4>:
776      # iftmp.1_1 = PHI <iftmp.1_3(3), 0B(2)>
777      D.1879_6 = middleman_1 (iftmp.1_1, i_5(D));
778      return D.1879_6;  */
779
780 static void
781 compute_complex_ancestor_jump_func (struct ipa_node_params *info,
782                                     struct ipa_jump_func *jfunc,
783                                     gimple call, gimple phi)
784 {
785   HOST_WIDE_INT offset;
786   gimple assign, cond;
787   basic_block phi_bb, assign_bb, cond_bb;
788   tree tmp, parm, expr, obj;
789   int index, i;
790
791   if (gimple_phi_num_args (phi) != 2)
792     return;
793
794   if (integer_zerop (PHI_ARG_DEF (phi, 1)))
795     tmp = PHI_ARG_DEF (phi, 0);
796   else if (integer_zerop (PHI_ARG_DEF (phi, 0)))
797     tmp = PHI_ARG_DEF (phi, 1);
798   else
799     return;
800   if (TREE_CODE (tmp) != SSA_NAME
801       || SSA_NAME_IS_DEFAULT_DEF (tmp)
802       || !POINTER_TYPE_P (TREE_TYPE (tmp))
803       || TREE_CODE (TREE_TYPE (TREE_TYPE (tmp))) != RECORD_TYPE)
804     return;
805
806   assign = SSA_NAME_DEF_STMT (tmp);
807   assign_bb = gimple_bb (assign);
808   if (!single_pred_p (assign_bb))
809     return;
810   expr = get_ancestor_addr_info (assign, &obj, &offset);
811   if (!expr)
812     return;
813   parm = TREE_OPERAND (expr, 0);
814   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
815   if (index < 0)
816     return;
817
818   cond_bb = single_pred (assign_bb);
819   cond = last_stmt (cond_bb);
820   if (!cond
821       || gimple_code (cond) != GIMPLE_COND
822       || gimple_cond_code (cond) != NE_EXPR
823       || gimple_cond_lhs (cond) != parm
824       || !integer_zerop (gimple_cond_rhs (cond)))
825     return;
826
827   phi_bb = gimple_bb (phi);
828   for (i = 0; i < 2; i++)
829     {
830       basic_block pred = EDGE_PRED (phi_bb, i)->src;
831       if (pred != assign_bb && pred != cond_bb)
832         return;
833     }
834
835   if (!detect_type_change (obj, expr, call, jfunc, offset))
836     {
837       jfunc->type = IPA_JF_ANCESTOR;
838       jfunc->value.ancestor.formal_id = index;
839       jfunc->value.ancestor.offset = offset;
840       jfunc->value.ancestor.type = TREE_TYPE (obj);
841     }
842 }
843
844 /* Given OP which is passed as an actual argument to a called function,
845    determine if it is possible to construct a KNOWN_TYPE jump function for it
846    and if so, create one and store it to JFUNC.  */
847
848 static void
849 compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc,
850                               gimple call)
851 {
852   HOST_WIDE_INT offset, size, max_size;
853   tree base;
854
855   if (!flag_devirtualize
856       || TREE_CODE (op) != ADDR_EXPR
857       || TREE_CODE (TREE_TYPE (TREE_TYPE (op))) != RECORD_TYPE)
858     return;
859
860   op = TREE_OPERAND (op, 0);
861   base = get_ref_base_and_extent (op, &offset, &size, &max_size);
862   if (!DECL_P (base)
863       || max_size == -1
864       || max_size != size
865       || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
866       || is_global_var (base))
867     return;
868
869   if (!TYPE_BINFO (TREE_TYPE (base))
870       || detect_type_change (op, base, call, jfunc, offset))
871     return;
872
873   jfunc->type = IPA_JF_KNOWN_TYPE;
874   jfunc->value.known_type.base_type = TREE_TYPE (base);
875   jfunc->value.known_type.offset = offset;
876   jfunc->value.known_type.component_type = TREE_TYPE (op);
877 }
878
879
880 /* Determine the jump functions of scalar arguments.  Scalar means SSA names
881    and constants of a number of selected types.  INFO is the ipa_node_params
882    structure associated with the caller, PARMS_AINFO describes state of
883    analysis with respect to individual formal parameters.  ARGS is the
884    ipa_edge_args structure describing the callsite CALL which is the call
885    statement being examined.*/
886
887 static void
888 compute_scalar_jump_functions (struct ipa_node_params *info,
889                                struct param_analysis_info *parms_ainfo,
890                                struct ipa_edge_args *args,
891                                gimple call)
892 {
893   tree arg;
894   unsigned num = 0;
895
896   for (num = 0; num < gimple_call_num_args (call); num++)
897     {
898       struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, num);
899       arg = gimple_call_arg (call, num);
900
901       if (is_gimple_ip_invariant (arg))
902         {
903           jfunc->type = IPA_JF_CONST;
904           jfunc->value.constant = arg;
905         }
906       else if (TREE_CODE (arg) == SSA_NAME)
907         {
908           if (SSA_NAME_IS_DEFAULT_DEF (arg))
909             {
910               int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
911
912               if (index >= 0
913                   && !detect_type_change_ssa (arg, call, jfunc))
914                 {
915                   jfunc->type = IPA_JF_PASS_THROUGH;
916                   jfunc->value.pass_through.formal_id = index;
917                   jfunc->value.pass_through.operation = NOP_EXPR;
918                 }
919             }
920           else
921             {
922               gimple stmt = SSA_NAME_DEF_STMT (arg);
923               if (is_gimple_assign (stmt))
924                 compute_complex_assign_jump_func (info, parms_ainfo, jfunc,
925                                                   call, stmt, arg);
926               else if (gimple_code (stmt) == GIMPLE_PHI)
927                 compute_complex_ancestor_jump_func (info, jfunc, call, stmt);
928             }
929         }
930       else
931         compute_known_type_jump_func (arg, jfunc, call);
932     }
933 }
934
935 /* Inspect the given TYPE and return true iff it has the same structure (the
936    same number of fields of the same types) as a C++ member pointer.  If
937    METHOD_PTR and DELTA are non-NULL, store the trees representing the
938    corresponding fields there.  */
939
940 static bool
941 type_like_member_ptr_p (tree type, tree *method_ptr, tree *delta)
942 {
943   tree fld;
944
945   if (TREE_CODE (type) != RECORD_TYPE)
946     return false;
947
948   fld = TYPE_FIELDS (type);
949   if (!fld || !POINTER_TYPE_P (TREE_TYPE (fld))
950       || TREE_CODE (TREE_TYPE (TREE_TYPE (fld))) != METHOD_TYPE)
951     return false;
952
953   if (method_ptr)
954     *method_ptr = fld;
955
956   fld = DECL_CHAIN (fld);
957   if (!fld || INTEGRAL_TYPE_P (fld))
958     return false;
959   if (delta)
960     *delta = fld;
961
962   if (DECL_CHAIN (fld))
963     return false;
964
965   return true;
966 }
967
968 /* Go through arguments of the CALL and for every one that looks like a member
969    pointer, check whether it can be safely declared pass-through and if so,
970    mark that to the corresponding item of jump FUNCTIONS.  Return true iff
971    there are non-pass-through member pointers within the arguments.  INFO
972    describes formal parameters of the caller.  PARMS_INFO is a pointer to a
973    vector containing intermediate information about each formal parameter.  */
974
975 static bool
976 compute_pass_through_member_ptrs (struct ipa_node_params *info,
977                                   struct param_analysis_info *parms_ainfo,
978                                   struct ipa_edge_args *args,
979                                   gimple call)
980 {
981   bool undecided_members = false;
982   unsigned num;
983   tree arg;
984
985   for (num = 0; num < gimple_call_num_args (call); num++)
986     {
987       arg = gimple_call_arg (call, num);
988
989       if (type_like_member_ptr_p (TREE_TYPE (arg), NULL, NULL))
990         {
991           if (TREE_CODE (arg) == PARM_DECL)
992             {
993               int index = ipa_get_param_decl_index (info, arg);
994
995               gcc_assert (index >=0);
996               if (!is_parm_modified_before_stmt (&parms_ainfo[index], call,
997                                                  arg))
998                 {
999                   struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args,
1000                                                                        num);
1001                   jfunc->type = IPA_JF_PASS_THROUGH;
1002                   jfunc->value.pass_through.formal_id = index;
1003                   jfunc->value.pass_through.operation = NOP_EXPR;
1004                 }
1005               else
1006                 undecided_members = true;
1007             }
1008           else
1009             undecided_members = true;
1010         }
1011     }
1012
1013   return undecided_members;
1014 }
1015
1016 /* Simple function filling in a member pointer constant jump function (with PFN
1017    and DELTA as the constant value) into JFUNC.  */
1018
1019 static void
1020 fill_member_ptr_cst_jump_function (struct ipa_jump_func *jfunc,
1021                                    tree pfn, tree delta)
1022 {
1023   jfunc->type = IPA_JF_CONST_MEMBER_PTR;
1024   jfunc->value.member_cst.pfn = pfn;
1025   jfunc->value.member_cst.delta = delta;
1026 }
1027
1028 /* If RHS is an SSA_NAME and it is defined by a simple copy assign statement,
1029    return the rhs of its defining statement.  */
1030
1031 static inline tree
1032 get_ssa_def_if_simple_copy (tree rhs)
1033 {
1034   while (TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (rhs))
1035     {
1036       gimple def_stmt = SSA_NAME_DEF_STMT (rhs);
1037
1038       if (gimple_assign_single_p (def_stmt))
1039         rhs = gimple_assign_rhs1 (def_stmt);
1040       else
1041         break;
1042     }
1043   return rhs;
1044 }
1045
1046 /* Traverse statements from CALL backwards, scanning whether the argument ARG
1047    which is a member pointer is filled in with constant values.  If it is, fill
1048    the jump function JFUNC in appropriately.  METHOD_FIELD and DELTA_FIELD are
1049    fields of the record type of the member pointer.  To give an example, we
1050    look for a pattern looking like the following:
1051
1052      D.2515.__pfn ={v} printStuff;
1053      D.2515.__delta ={v} 0;
1054      i_1 = doprinting (D.2515);  */
1055
1056 static void
1057 determine_cst_member_ptr (gimple call, tree arg, tree method_field,
1058                           tree delta_field, struct ipa_jump_func *jfunc)
1059 {
1060   gimple_stmt_iterator gsi;
1061   tree method = NULL_TREE;
1062   tree delta = NULL_TREE;
1063
1064   gsi = gsi_for_stmt (call);
1065
1066   gsi_prev (&gsi);
1067   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
1068     {
1069       gimple stmt = gsi_stmt (gsi);
1070       tree lhs, rhs, fld;
1071
1072       if (!stmt_may_clobber_ref_p (stmt, arg))
1073         continue;
1074       if (!gimple_assign_single_p (stmt))
1075         return;
1076
1077       lhs = gimple_assign_lhs (stmt);
1078       rhs = gimple_assign_rhs1 (stmt);
1079
1080       if (TREE_CODE (lhs) != COMPONENT_REF
1081           || TREE_OPERAND (lhs, 0) != arg)
1082         return;
1083
1084       fld = TREE_OPERAND (lhs, 1);
1085       if (!method && fld == method_field)
1086         {
1087           rhs = get_ssa_def_if_simple_copy (rhs);
1088           if (TREE_CODE (rhs) == ADDR_EXPR
1089               && TREE_CODE (TREE_OPERAND (rhs, 0)) == FUNCTION_DECL
1090               && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs, 0))) == METHOD_TYPE)
1091             {
1092               method = TREE_OPERAND (rhs, 0);
1093               if (delta)
1094                 {
1095                   fill_member_ptr_cst_jump_function (jfunc, rhs, delta);
1096                   return;
1097                 }
1098             }
1099           else
1100             return;
1101         }
1102
1103       if (!delta && fld == delta_field)
1104         {
1105           rhs = get_ssa_def_if_simple_copy (rhs);
1106           if (TREE_CODE (rhs) == INTEGER_CST)
1107             {
1108               delta = rhs;
1109               if (method)
1110                 {
1111                   fill_member_ptr_cst_jump_function (jfunc, rhs, delta);
1112                   return;
1113                 }
1114             }
1115           else
1116             return;
1117         }
1118     }
1119
1120   return;
1121 }
1122
1123 /* Go through the arguments of the CALL and for every member pointer within
1124    tries determine whether it is a constant.  If it is, create a corresponding
1125    constant jump function in FUNCTIONS which is an array of jump functions
1126    associated with the call.  */
1127
1128 static void
1129 compute_cst_member_ptr_arguments (struct ipa_edge_args *args,
1130                                   gimple call)
1131 {
1132   unsigned num;
1133   tree arg, method_field, delta_field;
1134
1135   for (num = 0; num < gimple_call_num_args (call); num++)
1136     {
1137       struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, num);
1138       arg = gimple_call_arg (call, num);
1139
1140       if (jfunc->type == IPA_JF_UNKNOWN
1141           && type_like_member_ptr_p (TREE_TYPE (arg), &method_field,
1142                                      &delta_field))
1143         determine_cst_member_ptr (call, arg, method_field, delta_field, jfunc);
1144     }
1145 }
1146
1147 /* Compute jump function for all arguments of callsite CS and insert the
1148    information in the jump_functions array in the ipa_edge_args corresponding
1149    to this callsite.  */
1150
1151 static void
1152 ipa_compute_jump_functions_for_edge (struct param_analysis_info *parms_ainfo,
1153                                      struct cgraph_edge *cs)
1154 {
1155   struct ipa_node_params *info = IPA_NODE_REF (cs->caller);
1156   struct ipa_edge_args *args = IPA_EDGE_REF (cs);
1157   gimple call = cs->call_stmt;
1158   int arg_num = gimple_call_num_args (call);
1159
1160   if (arg_num == 0 || args->jump_functions)
1161     return;
1162   VEC_safe_grow_cleared (ipa_jump_func_t, gc, args->jump_functions, arg_num);
1163
1164   /* We will deal with constants and SSA scalars first:  */
1165   compute_scalar_jump_functions (info, parms_ainfo, args, call);
1166
1167   /* Let's check whether there are any potential member pointers and if so,
1168      whether we can determine their functions as pass_through.  */
1169   if (!compute_pass_through_member_ptrs (info, parms_ainfo, args, call))
1170     return;
1171
1172   /* Finally, let's check whether we actually pass a new constant member
1173      pointer here...  */
1174   compute_cst_member_ptr_arguments (args, call);
1175 }
1176
1177 /* Compute jump functions for all edges - both direct and indirect - outgoing
1178    from NODE.  Also count the actual arguments in the process.  */
1179
1180 static void
1181 ipa_compute_jump_functions (struct cgraph_node *node,
1182                             struct param_analysis_info *parms_ainfo)
1183 {
1184   struct cgraph_edge *cs;
1185
1186   for (cs = node->callees; cs; cs = cs->next_callee)
1187     {
1188       struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee,
1189                                                                   NULL);
1190       /* We do not need to bother analyzing calls to unknown
1191          functions unless they may become known during lto/whopr.  */
1192       if (!callee->analyzed && !flag_lto)
1193         continue;
1194       ipa_compute_jump_functions_for_edge (parms_ainfo, cs);
1195     }
1196
1197   for (cs = node->indirect_calls; cs; cs = cs->next_callee)
1198     ipa_compute_jump_functions_for_edge (parms_ainfo, cs);
1199 }
1200
1201 /* If RHS looks like a rhs of a statement loading pfn from a member
1202    pointer formal parameter, return the parameter, otherwise return
1203    NULL.  If USE_DELTA, then we look for a use of the delta field
1204    rather than the pfn.  */
1205
1206 static tree
1207 ipa_get_member_ptr_load_param (tree rhs, bool use_delta)
1208 {
1209   tree rec, ref_field, ref_offset, fld, fld_offset, ptr_field, delta_field;
1210
1211   if (TREE_CODE (rhs) == COMPONENT_REF)
1212     {
1213       ref_field = TREE_OPERAND (rhs, 1);
1214       rhs = TREE_OPERAND (rhs, 0);
1215     }
1216   else
1217     ref_field = NULL_TREE;
1218   if (TREE_CODE (rhs) != MEM_REF)
1219     return NULL_TREE;
1220   rec = TREE_OPERAND (rhs, 0);
1221   if (TREE_CODE (rec) != ADDR_EXPR)
1222     return NULL_TREE;
1223   rec = TREE_OPERAND (rec, 0);
1224   if (TREE_CODE (rec) != PARM_DECL
1225       || !type_like_member_ptr_p (TREE_TYPE (rec), &ptr_field, &delta_field))
1226     return NULL_TREE;
1227
1228   ref_offset = TREE_OPERAND (rhs, 1);
1229
1230   if (ref_field)
1231     {
1232       if (integer_nonzerop (ref_offset))
1233         return NULL_TREE;
1234
1235       if (use_delta)
1236         fld = delta_field;
1237       else
1238         fld = ptr_field;
1239
1240       return ref_field == fld ? rec : NULL_TREE;
1241     }
1242
1243   if (use_delta)
1244     fld_offset = byte_position (delta_field);
1245   else
1246     fld_offset = byte_position (ptr_field);
1247
1248   return tree_int_cst_equal (ref_offset, fld_offset) ? rec : NULL_TREE;
1249 }
1250
1251 /* If STMT looks like a statement loading a value from a member pointer formal
1252    parameter, this function returns that parameter.  */
1253
1254 static tree
1255 ipa_get_stmt_member_ptr_load_param (gimple stmt, bool use_delta)
1256 {
1257   tree rhs;
1258
1259   if (!gimple_assign_single_p (stmt))
1260     return NULL_TREE;
1261
1262   rhs = gimple_assign_rhs1 (stmt);
1263   return ipa_get_member_ptr_load_param (rhs, use_delta);
1264 }
1265
1266 /* Returns true iff T is an SSA_NAME defined by a statement.  */
1267
1268 static bool
1269 ipa_is_ssa_with_stmt_def (tree t)
1270 {
1271   if (TREE_CODE (t) == SSA_NAME
1272       && !SSA_NAME_IS_DEFAULT_DEF (t))
1273     return true;
1274   else
1275     return false;
1276 }
1277
1278 /* Find the indirect call graph edge corresponding to STMT and mark it as a
1279    call to a parameter number PARAM_INDEX.  NODE is the caller.  Return the
1280    indirect call graph edge.  */
1281
1282 static struct cgraph_edge *
1283 ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt)
1284 {
1285   struct cgraph_edge *cs;
1286
1287   cs = cgraph_edge (node, stmt);
1288   cs->indirect_info->param_index = param_index;
1289   cs->indirect_info->anc_offset = 0;
1290   cs->indirect_info->polymorphic = 0;
1291   return cs;
1292 }
1293
1294 /* Analyze the CALL and examine uses of formal parameters of the caller NODE
1295    (described by INFO).  PARMS_AINFO is a pointer to a vector containing
1296    intermediate information about each formal parameter.  Currently it checks
1297    whether the call calls a pointer that is a formal parameter and if so, the
1298    parameter is marked with the called flag and an indirect call graph edge
1299    describing the call is created.  This is very simple for ordinary pointers
1300    represented in SSA but not-so-nice when it comes to member pointers.  The
1301    ugly part of this function does nothing more than trying to match the
1302    pattern of such a call.  An example of such a pattern is the gimple dump
1303    below, the call is on the last line:
1304
1305      <bb 2>:
1306        f$__delta_5 = f.__delta;
1307        f$__pfn_24 = f.__pfn;
1308
1309    or
1310      <bb 2>:
1311        f$__delta_5 = MEM[(struct  *)&f];
1312        f$__pfn_24 = MEM[(struct  *)&f + 4B];
1313
1314    and a few lines below:
1315
1316      <bb 5>
1317        D.2496_3 = (int) f$__pfn_24;
1318        D.2497_4 = D.2496_3 & 1;
1319        if (D.2497_4 != 0)
1320          goto <bb 3>;
1321        else
1322          goto <bb 4>;
1323
1324      <bb 6>:
1325        D.2500_7 = (unsigned int) f$__delta_5;
1326        D.2501_8 = &S + D.2500_7;
1327        D.2502_9 = (int (*__vtbl_ptr_type) (void) * *) D.2501_8;
1328        D.2503_10 = *D.2502_9;
1329        D.2504_12 = f$__pfn_24 + -1;
1330        D.2505_13 = (unsigned int) D.2504_12;
1331        D.2506_14 = D.2503_10 + D.2505_13;
1332        D.2507_15 = *D.2506_14;
1333        iftmp.11_16 = (String:: *) D.2507_15;
1334
1335      <bb 7>:
1336        # iftmp.11_1 = PHI <iftmp.11_16(3), f$__pfn_24(2)>
1337        D.2500_19 = (unsigned int) f$__delta_5;
1338        D.2508_20 = &S + D.2500_19;
1339        D.2493_21 = iftmp.11_1 (D.2508_20, 4);
1340
1341    Such patterns are results of simple calls to a member pointer:
1342
1343      int doprinting (int (MyString::* f)(int) const)
1344      {
1345        MyString S ("somestring");
1346
1347        return (S.*f)(4);
1348      }
1349 */
1350
1351 static void
1352 ipa_analyze_indirect_call_uses (struct cgraph_node *node,
1353                                 struct ipa_node_params *info,
1354                                 struct param_analysis_info *parms_ainfo,
1355                                 gimple call, tree target)
1356 {
1357   gimple def;
1358   tree n1, n2;
1359   gimple d1, d2;
1360   tree rec, rec2, cond;
1361   gimple branch;
1362   int index;
1363   basic_block bb, virt_bb, join;
1364
1365   if (SSA_NAME_IS_DEFAULT_DEF (target))
1366     {
1367       tree var = SSA_NAME_VAR (target);
1368       index = ipa_get_param_decl_index (info, var);
1369       if (index >= 0)
1370         ipa_note_param_call (node, index, call);
1371       return;
1372     }
1373
1374   /* Now we need to try to match the complex pattern of calling a member
1375      pointer. */
1376
1377   if (!POINTER_TYPE_P (TREE_TYPE (target))
1378       || TREE_CODE (TREE_TYPE (TREE_TYPE (target))) != METHOD_TYPE)
1379     return;
1380
1381   def = SSA_NAME_DEF_STMT (target);
1382   if (gimple_code (def) != GIMPLE_PHI)
1383     return;
1384
1385   if (gimple_phi_num_args (def) != 2)
1386     return;
1387
1388   /* First, we need to check whether one of these is a load from a member
1389      pointer that is a parameter to this function. */
1390   n1 = PHI_ARG_DEF (def, 0);
1391   n2 = PHI_ARG_DEF (def, 1);
1392   if (!ipa_is_ssa_with_stmt_def (n1) || !ipa_is_ssa_with_stmt_def (n2))
1393     return;
1394   d1 = SSA_NAME_DEF_STMT (n1);
1395   d2 = SSA_NAME_DEF_STMT (n2);
1396
1397   join = gimple_bb (def);
1398   if ((rec = ipa_get_stmt_member_ptr_load_param (d1, false)))
1399     {
1400       if (ipa_get_stmt_member_ptr_load_param (d2, false))
1401         return;
1402
1403       bb = EDGE_PRED (join, 0)->src;
1404       virt_bb = gimple_bb (d2);
1405     }
1406   else if ((rec = ipa_get_stmt_member_ptr_load_param (d2, false)))
1407     {
1408       bb = EDGE_PRED (join, 1)->src;
1409       virt_bb = gimple_bb (d1);
1410     }
1411   else
1412     return;
1413
1414   /* Second, we need to check that the basic blocks are laid out in the way
1415      corresponding to the pattern. */
1416
1417   if (!single_pred_p (virt_bb) || !single_succ_p (virt_bb)
1418       || single_pred (virt_bb) != bb
1419       || single_succ (virt_bb) != join)
1420     return;
1421
1422   /* Third, let's see that the branching is done depending on the least
1423      significant bit of the pfn. */
1424
1425   branch = last_stmt (bb);
1426   if (!branch || gimple_code (branch) != GIMPLE_COND)
1427     return;
1428
1429   if ((gimple_cond_code (branch) != NE_EXPR
1430        && gimple_cond_code (branch) != EQ_EXPR)
1431       || !integer_zerop (gimple_cond_rhs (branch)))
1432     return;
1433
1434   cond = gimple_cond_lhs (branch);
1435   if (!ipa_is_ssa_with_stmt_def (cond))
1436     return;
1437
1438   def = SSA_NAME_DEF_STMT (cond);
1439   if (!is_gimple_assign (def)
1440       || gimple_assign_rhs_code (def) != BIT_AND_EXPR
1441       || !integer_onep (gimple_assign_rhs2 (def)))
1442     return;
1443
1444   cond = gimple_assign_rhs1 (def);
1445   if (!ipa_is_ssa_with_stmt_def (cond))
1446     return;
1447
1448   def = SSA_NAME_DEF_STMT (cond);
1449
1450   if (is_gimple_assign (def)
1451       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
1452     {
1453       cond = gimple_assign_rhs1 (def);
1454       if (!ipa_is_ssa_with_stmt_def (cond))
1455         return;
1456       def = SSA_NAME_DEF_STMT (cond);
1457     }
1458
1459   rec2 = ipa_get_stmt_member_ptr_load_param (def,
1460                                              (TARGET_PTRMEMFUNC_VBIT_LOCATION
1461                                               == ptrmemfunc_vbit_in_delta));
1462
1463   if (rec != rec2)
1464     return;
1465
1466   index = ipa_get_param_decl_index (info, rec);
1467   if (index >= 0 && !is_parm_modified_before_stmt (&parms_ainfo[index],
1468                                                    call, rec))
1469     ipa_note_param_call (node, index, call);
1470
1471   return;
1472 }
1473
1474 /* Analyze a CALL to an OBJ_TYPE_REF which is passed in TARGET and if the
1475    object referenced in the expression is a formal parameter of the caller
1476    (described by INFO), create a call note for the statement. */
1477
1478 static void
1479 ipa_analyze_virtual_call_uses (struct cgraph_node *node,
1480                                struct ipa_node_params *info, gimple call,
1481                                tree target)
1482 {
1483   struct cgraph_edge *cs;
1484   struct cgraph_indirect_call_info *ii;
1485   struct ipa_jump_func jfunc;
1486   tree obj = OBJ_TYPE_REF_OBJECT (target);
1487   int index;
1488   HOST_WIDE_INT anc_offset;
1489
1490   if (!flag_devirtualize)
1491     return;
1492
1493   if (TREE_CODE (obj) != SSA_NAME)
1494     return;
1495
1496   if (SSA_NAME_IS_DEFAULT_DEF (obj))
1497     {
1498       if (TREE_CODE (SSA_NAME_VAR (obj)) != PARM_DECL)
1499         return;
1500
1501       anc_offset = 0;
1502       index = ipa_get_param_decl_index (info, SSA_NAME_VAR (obj));
1503       gcc_assert (index >= 0);
1504       if (detect_type_change_ssa (obj, call, &jfunc))
1505         return;
1506     }
1507   else
1508     {
1509       gimple stmt = SSA_NAME_DEF_STMT (obj);
1510       tree expr;
1511
1512       expr = get_ancestor_addr_info (stmt, &obj, &anc_offset);
1513       if (!expr)
1514         return;
1515       index = ipa_get_param_decl_index (info,
1516                                         SSA_NAME_VAR (TREE_OPERAND (expr, 0)));
1517       gcc_assert (index >= 0);
1518       if (detect_type_change (obj, expr, call, &jfunc, anc_offset))
1519         return;
1520     }
1521
1522   cs = ipa_note_param_call (node, index, call);
1523   ii = cs->indirect_info;
1524   ii->anc_offset = anc_offset;
1525   ii->otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1);
1526   ii->otr_type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (target)));
1527   ii->polymorphic = 1;
1528 }
1529
1530 /* Analyze a call statement CALL whether and how it utilizes formal parameters
1531    of the caller (described by INFO).  PARMS_AINFO is a pointer to a vector
1532    containing intermediate information about each formal parameter.  */
1533
1534 static void
1535 ipa_analyze_call_uses (struct cgraph_node *node,
1536                        struct ipa_node_params *info,
1537                        struct param_analysis_info *parms_ainfo, gimple call)
1538 {
1539   tree target = gimple_call_fn (call);
1540
1541   if (!target)
1542     return;
1543   if (TREE_CODE (target) == SSA_NAME)
1544     ipa_analyze_indirect_call_uses (node, info, parms_ainfo, call, target);
1545   else if (TREE_CODE (target) == OBJ_TYPE_REF)
1546     ipa_analyze_virtual_call_uses (node, info, call, target);
1547 }
1548
1549
1550 /* Analyze the call statement STMT with respect to formal parameters (described
1551    in INFO) of caller given by NODE.  Currently it only checks whether formal
1552    parameters are called.  PARMS_AINFO is a pointer to a vector containing
1553    intermediate information about each formal parameter.  */
1554
1555 static void
1556 ipa_analyze_stmt_uses (struct cgraph_node *node, struct ipa_node_params *info,
1557                        struct param_analysis_info *parms_ainfo, gimple stmt)
1558 {
1559   if (is_gimple_call (stmt))
1560     ipa_analyze_call_uses (node, info, parms_ainfo, stmt);
1561 }
1562
1563 /* Callback of walk_stmt_load_store_addr_ops for the visit_load.
1564    If OP is a parameter declaration, mark it as used in the info structure
1565    passed in DATA.  */
1566
1567 static bool
1568 visit_ref_for_mod_analysis (gimple stmt ATTRIBUTE_UNUSED,
1569                              tree op, void *data)
1570 {
1571   struct ipa_node_params *info = (struct ipa_node_params *) data;
1572
1573   op = get_base_address (op);
1574   if (op
1575       && TREE_CODE (op) == PARM_DECL)
1576     {
1577       int index = ipa_get_param_decl_index (info, op);
1578       gcc_assert (index >= 0);
1579       ipa_set_param_used (info, index, true);
1580     }
1581
1582   return false;
1583 }
1584
1585 /* Scan the function body of NODE and inspect the uses of formal parameters.
1586    Store the findings in various structures of the associated ipa_node_params
1587    structure, such as parameter flags, notes etc.  PARMS_AINFO is a pointer to a
1588    vector containing intermediate information about each formal parameter.   */
1589
1590 static void
1591 ipa_analyze_params_uses (struct cgraph_node *node,
1592                          struct param_analysis_info *parms_ainfo)
1593 {
1594   tree decl = node->decl;
1595   basic_block bb;
1596   struct function *func;
1597   gimple_stmt_iterator gsi;
1598   struct ipa_node_params *info = IPA_NODE_REF (node);
1599   int i;
1600
1601   if (ipa_get_param_count (info) == 0 || info->uses_analysis_done)
1602     return;
1603
1604   for (i = 0; i < ipa_get_param_count (info); i++)
1605     {
1606       tree parm = ipa_get_param (info, i);
1607       /* For SSA regs see if parameter is used.  For non-SSA we compute
1608          the flag during modification analysis.  */
1609       if (is_gimple_reg (parm)
1610           && gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), parm))
1611         ipa_set_param_used (info, i, true);
1612     }
1613
1614   func = DECL_STRUCT_FUNCTION (decl);
1615   FOR_EACH_BB_FN (bb, func)
1616     {
1617       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1618         {
1619           gimple stmt = gsi_stmt (gsi);
1620
1621           if (is_gimple_debug (stmt))
1622             continue;
1623
1624           ipa_analyze_stmt_uses (node, info, parms_ainfo, stmt);
1625           walk_stmt_load_store_addr_ops (stmt, info,
1626                                          visit_ref_for_mod_analysis,
1627                                          visit_ref_for_mod_analysis,
1628                                          visit_ref_for_mod_analysis);
1629         }
1630       for (gsi = gsi_start (phi_nodes (bb)); !gsi_end_p (gsi); gsi_next (&gsi))
1631         walk_stmt_load_store_addr_ops (gsi_stmt (gsi), info,
1632                                        visit_ref_for_mod_analysis,
1633                                        visit_ref_for_mod_analysis,
1634                                        visit_ref_for_mod_analysis);
1635     }
1636
1637   info->uses_analysis_done = 1;
1638 }
1639
1640 /* Initialize the array describing properties of of formal parameters
1641    of NODE, analyze their uses and compute jump functions associated
1642    with actual arguments of calls from within NODE.  */
1643
1644 void
1645 ipa_analyze_node (struct cgraph_node *node)
1646 {
1647   struct ipa_node_params *info;
1648   struct param_analysis_info *parms_ainfo;
1649   int i, param_count;
1650
1651   ipa_check_create_node_params ();
1652   ipa_check_create_edge_args ();
1653   info = IPA_NODE_REF (node);
1654   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1655   current_function_decl = node->decl;
1656   ipa_initialize_node_params (node);
1657
1658   param_count = ipa_get_param_count (info);
1659   parms_ainfo = XALLOCAVEC (struct param_analysis_info, param_count);
1660   memset (parms_ainfo, 0, sizeof (struct param_analysis_info) * param_count);
1661
1662   ipa_analyze_params_uses (node, parms_ainfo);
1663   ipa_compute_jump_functions (node, parms_ainfo);
1664
1665   for (i = 0; i < param_count; i++)
1666     if (parms_ainfo[i].visited_statements)
1667       BITMAP_FREE (parms_ainfo[i].visited_statements);
1668
1669   current_function_decl = NULL;
1670   pop_cfun ();
1671 }
1672
1673
1674 /* Update the jump function DST when the call graph edge corresponding to SRC is
1675    is being inlined, knowing that DST is of type ancestor and src of known
1676    type.  */
1677
1678 static void
1679 combine_known_type_and_ancestor_jfs (struct ipa_jump_func *src,
1680                                      struct ipa_jump_func *dst)
1681 {
1682   HOST_WIDE_INT combined_offset;
1683   tree combined_type;
1684
1685   combined_offset = src->value.known_type.offset + dst->value.ancestor.offset;
1686   combined_type = dst->value.ancestor.type;
1687
1688   dst->type = IPA_JF_KNOWN_TYPE;
1689   dst->value.known_type.base_type = src->value.known_type.base_type;
1690   dst->value.known_type.offset = combined_offset;
1691   dst->value.known_type.component_type = combined_type;
1692 }
1693
1694 /* Update the jump functions associated with call graph edge E when the call
1695    graph edge CS is being inlined, assuming that E->caller is already (possibly
1696    indirectly) inlined into CS->callee and that E has not been inlined.  */
1697
1698 static void
1699 update_jump_functions_after_inlining (struct cgraph_edge *cs,
1700                                       struct cgraph_edge *e)
1701 {
1702   struct ipa_edge_args *top = IPA_EDGE_REF (cs);
1703   struct ipa_edge_args *args = IPA_EDGE_REF (e);
1704   int count = ipa_get_cs_argument_count (args);
1705   int i;
1706
1707   for (i = 0; i < count; i++)
1708     {
1709       struct ipa_jump_func *dst = ipa_get_ith_jump_func (args, i);
1710
1711       if (dst->type == IPA_JF_ANCESTOR)
1712         {
1713           struct ipa_jump_func *src;
1714
1715           /* Variable number of arguments can cause havoc if we try to access
1716              one that does not exist in the inlined edge.  So make sure we
1717              don't.  */
1718           if (dst->value.ancestor.formal_id >= ipa_get_cs_argument_count (top))
1719             {
1720               dst->type = IPA_JF_UNKNOWN;
1721               continue;
1722             }
1723
1724           src = ipa_get_ith_jump_func (top, dst->value.ancestor.formal_id);
1725           if (src->type == IPA_JF_KNOWN_TYPE)
1726             combine_known_type_and_ancestor_jfs (src, dst);
1727           else if (src->type == IPA_JF_PASS_THROUGH
1728                    && src->value.pass_through.operation == NOP_EXPR)
1729             dst->value.ancestor.formal_id = src->value.pass_through.formal_id;
1730           else if (src->type == IPA_JF_ANCESTOR)
1731             {
1732               dst->value.ancestor.formal_id = src->value.ancestor.formal_id;
1733               dst->value.ancestor.offset += src->value.ancestor.offset;
1734             }
1735           else
1736             dst->type = IPA_JF_UNKNOWN;
1737         }
1738       else if (dst->type == IPA_JF_PASS_THROUGH)
1739         {
1740           struct ipa_jump_func *src;
1741           /* We must check range due to calls with variable number of arguments
1742              and we cannot combine jump functions with operations.  */
1743           if (dst->value.pass_through.operation == NOP_EXPR
1744               && (dst->value.pass_through.formal_id
1745                   < ipa_get_cs_argument_count (top)))
1746             {
1747               src = ipa_get_ith_jump_func (top,
1748                                            dst->value.pass_through.formal_id);
1749               *dst = *src;
1750             }
1751           else
1752             dst->type = IPA_JF_UNKNOWN;
1753         }
1754     }
1755 }
1756
1757 /* If TARGET is an addr_expr of a function declaration, make it the destination
1758    of an indirect edge IE and return the edge.  Otherwise, return NULL.  */
1759
1760 struct cgraph_edge *
1761 ipa_make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
1762 {
1763   struct cgraph_node *callee;
1764
1765   if (TREE_CODE (target) == ADDR_EXPR)
1766     target = TREE_OPERAND (target, 0);
1767   if (TREE_CODE (target) != FUNCTION_DECL)
1768     return NULL;
1769   callee = cgraph_get_node (target);
1770   if (!callee)
1771     return NULL;
1772   ipa_check_create_node_params ();
1773
1774   /* We can not make edges to inline clones.  It is bug that someone removed
1775      the cgraph node too early.  */
1776   gcc_assert (!callee->global.inlined_to);
1777
1778   cgraph_make_edge_direct (ie, callee);
1779   if (dump_file)
1780     {
1781       fprintf (dump_file, "ipa-prop: Discovered %s call to a known target "
1782                "(%s/%i -> %s/%i), for stmt ",
1783                ie->indirect_info->polymorphic ? "a virtual" : "an indirect",
1784                xstrdup (cgraph_node_name (ie->caller)), ie->caller->uid,
1785                xstrdup (cgraph_node_name (ie->callee)), ie->callee->uid);
1786       if (ie->call_stmt)
1787         print_gimple_stmt (dump_file, ie->call_stmt, 2, TDF_SLIM);
1788       else
1789         fprintf (dump_file, "with uid %i\n", ie->lto_stmt_uid);
1790     }
1791   callee = cgraph_function_or_thunk_node (callee, NULL);
1792
1793   return ie;
1794 }
1795
1796 /* Try to find a destination for indirect edge IE that corresponds to a simple
1797    call or a call of a member function pointer and where the destination is a
1798    pointer formal parameter described by jump function JFUNC.  If it can be
1799    determined, return the newly direct edge, otherwise return NULL.  */
1800
1801 static struct cgraph_edge *
1802 try_make_edge_direct_simple_call (struct cgraph_edge *ie,
1803                                   struct ipa_jump_func *jfunc)
1804 {
1805   tree target;
1806
1807   if (jfunc->type == IPA_JF_CONST)
1808     target = jfunc->value.constant;
1809   else if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
1810     target = jfunc->value.member_cst.pfn;
1811   else
1812     return NULL;
1813
1814   return ipa_make_edge_direct_to_target (ie, target);
1815 }
1816
1817 /* Try to find a destination for indirect edge IE that corresponds to a
1818    virtual call based on a formal parameter which is described by jump
1819    function JFUNC and if it can be determined, make it direct and return the
1820    direct edge.  Otherwise, return NULL.  */
1821
1822 static struct cgraph_edge *
1823 try_make_edge_direct_virtual_call (struct cgraph_edge *ie,
1824                                    struct ipa_jump_func *jfunc)
1825 {
1826   tree binfo, target;
1827
1828   if (jfunc->type != IPA_JF_KNOWN_TYPE)
1829     return NULL;
1830
1831   binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
1832   gcc_checking_assert (binfo);
1833   binfo = get_binfo_at_offset (binfo, jfunc->value.known_type.offset
1834                                + ie->indirect_info->anc_offset,
1835                                ie->indirect_info->otr_type);
1836   if (binfo)
1837     target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
1838                                                binfo);
1839   else
1840     return NULL;
1841
1842   if (target)
1843     return ipa_make_edge_direct_to_target (ie, target);
1844   else
1845     return NULL;
1846 }
1847
1848 /* Update the param called notes associated with NODE when CS is being inlined,
1849    assuming NODE is (potentially indirectly) inlined into CS->callee.
1850    Moreover, if the callee is discovered to be constant, create a new cgraph
1851    edge for it.  Newly discovered indirect edges will be added to *NEW_EDGES,
1852    unless NEW_EDGES is NULL.  Return true iff a new edge(s) were created.  */
1853
1854 static bool
1855 update_indirect_edges_after_inlining (struct cgraph_edge *cs,
1856                                       struct cgraph_node *node,
1857                                       VEC (cgraph_edge_p, heap) **new_edges)
1858 {
1859   struct ipa_edge_args *top;
1860   struct cgraph_edge *ie, *next_ie, *new_direct_edge;
1861   bool res = false;
1862
1863   ipa_check_create_edge_args ();
1864   top = IPA_EDGE_REF (cs);
1865
1866   for (ie = node->indirect_calls; ie; ie = next_ie)
1867     {
1868       struct cgraph_indirect_call_info *ici = ie->indirect_info;
1869       struct ipa_jump_func *jfunc;
1870
1871       next_ie = ie->next_callee;
1872
1873       if (ici->param_index == -1)
1874         continue;
1875
1876       /* We must check range due to calls with variable number of arguments:  */
1877       if (ici->param_index >= ipa_get_cs_argument_count (top))
1878         {
1879           ici->param_index = -1;
1880           continue;
1881         }
1882
1883       jfunc = ipa_get_ith_jump_func (top, ici->param_index);
1884       if (jfunc->type == IPA_JF_PASS_THROUGH
1885           && jfunc->value.pass_through.operation == NOP_EXPR)
1886         ici->param_index = jfunc->value.pass_through.formal_id;
1887       else if (jfunc->type == IPA_JF_ANCESTOR)
1888         {
1889           ici->param_index = jfunc->value.ancestor.formal_id;
1890           ici->anc_offset += jfunc->value.ancestor.offset;
1891         }
1892       else
1893         /* Either we can find a destination for this edge now or never. */
1894         ici->param_index = -1;
1895
1896       if (!flag_indirect_inlining)
1897         continue;
1898
1899       if (ici->polymorphic)
1900         new_direct_edge = try_make_edge_direct_virtual_call (ie, jfunc);
1901       else
1902         new_direct_edge = try_make_edge_direct_simple_call (ie, jfunc);
1903
1904       if (new_direct_edge)
1905         {
1906           new_direct_edge->indirect_inlining_edge = 1;
1907           if (new_direct_edge->call_stmt)
1908             new_direct_edge->call_stmt_cannot_inline_p
1909               = !gimple_check_call_matching_types (new_direct_edge->call_stmt,
1910                                                    new_direct_edge->callee->decl);
1911           if (new_edges)
1912             {
1913               VEC_safe_push (cgraph_edge_p, heap, *new_edges,
1914                              new_direct_edge);
1915               top = IPA_EDGE_REF (cs);
1916               res = true;
1917             }
1918         }
1919     }
1920
1921   return res;
1922 }
1923
1924 /* Recursively traverse subtree of NODE (including node) made of inlined
1925    cgraph_edges when CS has been inlined and invoke
1926    update_indirect_edges_after_inlining on all nodes and
1927    update_jump_functions_after_inlining on all non-inlined edges that lead out
1928    of this subtree.  Newly discovered indirect edges will be added to
1929    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were
1930    created.  */
1931
1932 static bool
1933 propagate_info_to_inlined_callees (struct cgraph_edge *cs,
1934                                    struct cgraph_node *node,
1935                                    VEC (cgraph_edge_p, heap) **new_edges)
1936 {
1937   struct cgraph_edge *e;
1938   bool res;
1939
1940   res = update_indirect_edges_after_inlining (cs, node, new_edges);
1941
1942   for (e = node->callees; e; e = e->next_callee)
1943     if (!e->inline_failed)
1944       res |= propagate_info_to_inlined_callees (cs, e->callee, new_edges);
1945     else
1946       update_jump_functions_after_inlining (cs, e);
1947   for (e = node->indirect_calls; e; e = e->next_callee)
1948     update_jump_functions_after_inlining (cs, e);
1949
1950   return res;
1951 }
1952
1953 /* Update jump functions and call note functions on inlining the call site CS.
1954    CS is expected to lead to a node already cloned by
1955    cgraph_clone_inline_nodes.  Newly discovered indirect edges will be added to
1956    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were +
1957    created.  */
1958
1959 bool
1960 ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
1961                                    VEC (cgraph_edge_p, heap) **new_edges)
1962 {
1963   bool changed;
1964   /* Do nothing if the preparation phase has not been carried out yet
1965      (i.e. during early inlining).  */
1966   if (!ipa_node_params_vector)
1967     return false;
1968   gcc_assert (ipa_edge_args_vector);
1969
1970   changed = propagate_info_to_inlined_callees (cs, cs->callee, new_edges);
1971
1972   /* We do not keep jump functions of inlined edges up to date. Better to free
1973      them so we do not access them accidentally.  */
1974   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
1975   return changed;
1976 }
1977
1978 /* Frees all dynamically allocated structures that the argument info points
1979    to.  */
1980
1981 void
1982 ipa_free_edge_args_substructures (struct ipa_edge_args *args)
1983 {
1984   if (args->jump_functions)
1985     ggc_free (args->jump_functions);
1986
1987   memset (args, 0, sizeof (*args));
1988 }
1989
1990 /* Free all ipa_edge structures.  */
1991
1992 void
1993 ipa_free_all_edge_args (void)
1994 {
1995   int i;
1996   struct ipa_edge_args *args;
1997
1998   FOR_EACH_VEC_ELT (ipa_edge_args_t, ipa_edge_args_vector, i, args)
1999     ipa_free_edge_args_substructures (args);
2000
2001   VEC_free (ipa_edge_args_t, gc, ipa_edge_args_vector);
2002   ipa_edge_args_vector = NULL;
2003 }
2004
2005 /* Frees all dynamically allocated structures that the param info points
2006    to.  */
2007
2008 void
2009 ipa_free_node_params_substructures (struct ipa_node_params *info)
2010 {
2011   VEC_free (ipa_param_descriptor_t, heap, info->descriptors);
2012   free (info->lattices);
2013   /* Lattice values and their sources are deallocated with their alocation
2014      pool.  */
2015   VEC_free (tree, heap, info->known_vals);
2016   memset (info, 0, sizeof (*info));
2017 }
2018
2019 /* Free all ipa_node_params structures.  */
2020
2021 void
2022 ipa_free_all_node_params (void)
2023 {
2024   int i;
2025   struct ipa_node_params *info;
2026
2027   FOR_EACH_VEC_ELT (ipa_node_params_t, ipa_node_params_vector, i, info)
2028     ipa_free_node_params_substructures (info);
2029
2030   VEC_free (ipa_node_params_t, heap, ipa_node_params_vector);
2031   ipa_node_params_vector = NULL;
2032 }
2033
2034 /* Hook that is called by cgraph.c when an edge is removed.  */
2035
2036 static void
2037 ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
2038 {
2039   /* During IPA-CP updating we can be called on not-yet analyze clones.  */
2040   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
2041       <= (unsigned)cs->uid)
2042     return;
2043   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
2044 }
2045
2046 /* Hook that is called by cgraph.c when a node is removed.  */
2047
2048 static void
2049 ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2050 {
2051   /* During IPA-CP updating we can be called on not-yet analyze clones.  */
2052   if (VEC_length (ipa_node_params_t, ipa_node_params_vector)
2053       <= (unsigned)node->uid)
2054     return;
2055   ipa_free_node_params_substructures (IPA_NODE_REF (node));
2056 }
2057
2058 /* Hook that is called by cgraph.c when a node is duplicated.  */
2059
2060 static void
2061 ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
2062                            __attribute__((unused)) void *data)
2063 {
2064   struct ipa_edge_args *old_args, *new_args;
2065
2066   ipa_check_create_edge_args ();
2067
2068   old_args = IPA_EDGE_REF (src);
2069   new_args = IPA_EDGE_REF (dst);
2070
2071   new_args->jump_functions = VEC_copy (ipa_jump_func_t, gc,
2072                                        old_args->jump_functions);
2073 }
2074
2075 /* Hook that is called by cgraph.c when a node is duplicated.  */
2076
2077 static void
2078 ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
2079                            ATTRIBUTE_UNUSED void *data)
2080 {
2081   struct ipa_node_params *old_info, *new_info;
2082
2083   ipa_check_create_node_params ();
2084   old_info = IPA_NODE_REF (src);
2085   new_info = IPA_NODE_REF (dst);
2086
2087   new_info->descriptors = VEC_copy (ipa_param_descriptor_t, heap,
2088                                     old_info->descriptors);
2089   new_info->lattices = NULL;
2090   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
2091
2092   new_info->uses_analysis_done = old_info->uses_analysis_done;
2093   new_info->node_enqueued = old_info->node_enqueued;
2094 }
2095
2096
2097 /* Analyze newly added function into callgraph.  */
2098
2099 static void
2100 ipa_add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2101 {
2102   ipa_analyze_node (node);
2103 }
2104
2105 /* Register our cgraph hooks if they are not already there.  */
2106
2107 void
2108 ipa_register_cgraph_hooks (void)
2109 {
2110   if (!edge_removal_hook_holder)
2111     edge_removal_hook_holder =
2112       cgraph_add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
2113   if (!node_removal_hook_holder)
2114     node_removal_hook_holder =
2115       cgraph_add_node_removal_hook (&ipa_node_removal_hook, NULL);
2116   if (!edge_duplication_hook_holder)
2117     edge_duplication_hook_holder =
2118       cgraph_add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
2119   if (!node_duplication_hook_holder)
2120     node_duplication_hook_holder =
2121       cgraph_add_node_duplication_hook (&ipa_node_duplication_hook, NULL);
2122   function_insertion_hook_holder =
2123       cgraph_add_function_insertion_hook (&ipa_add_new_function, NULL);
2124 }
2125
2126 /* Unregister our cgraph hooks if they are not already there.  */
2127
2128 static void
2129 ipa_unregister_cgraph_hooks (void)
2130 {
2131   cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
2132   edge_removal_hook_holder = NULL;
2133   cgraph_remove_node_removal_hook (node_removal_hook_holder);
2134   node_removal_hook_holder = NULL;
2135   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2136   edge_duplication_hook_holder = NULL;
2137   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
2138   node_duplication_hook_holder = NULL;
2139   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
2140   function_insertion_hook_holder = NULL;
2141 }
2142
2143 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
2144    longer needed after ipa-cp.  */
2145
2146 void
2147 ipa_free_all_structures_after_ipa_cp (void)
2148 {
2149   if (!optimize)
2150     {
2151       ipa_free_all_edge_args ();
2152       ipa_free_all_node_params ();
2153       free_alloc_pool (ipcp_sources_pool);
2154       free_alloc_pool (ipcp_values_pool);
2155       ipa_unregister_cgraph_hooks ();
2156     }
2157 }
2158
2159 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
2160    longer needed after indirect inlining.  */
2161
2162 void
2163 ipa_free_all_structures_after_iinln (void)
2164 {
2165   ipa_free_all_edge_args ();
2166   ipa_free_all_node_params ();
2167   ipa_unregister_cgraph_hooks ();
2168   if (ipcp_sources_pool)
2169     free_alloc_pool (ipcp_sources_pool);
2170   if (ipcp_values_pool)
2171     free_alloc_pool (ipcp_values_pool);
2172 }
2173
2174 /* Print ipa_tree_map data structures of all functions in the
2175    callgraph to F.  */
2176
2177 void
2178 ipa_print_node_params (FILE * f, struct cgraph_node *node)
2179 {
2180   int i, count;
2181   tree temp;
2182   struct ipa_node_params *info;
2183
2184   if (!node->analyzed)
2185     return;
2186   info = IPA_NODE_REF (node);
2187   fprintf (f, "  function  %s parameter descriptors:\n",
2188            cgraph_node_name (node));
2189   count = ipa_get_param_count (info);
2190   for (i = 0; i < count; i++)
2191     {
2192       temp = ipa_get_param (info, i);
2193       if (TREE_CODE (temp) == PARM_DECL)
2194         fprintf (f, "    param %d : %s", i,
2195                  (DECL_NAME (temp)
2196                   ? (*lang_hooks.decl_printable_name) (temp, 2)
2197                   : "(unnamed)"));
2198       if (ipa_is_param_used (info, i))
2199         fprintf (f, " used");
2200       fprintf (f, "\n");
2201     }
2202 }
2203
2204 /* Print ipa_tree_map data structures of all functions in the
2205    callgraph to F.  */
2206
2207 void
2208 ipa_print_all_params (FILE * f)
2209 {
2210   struct cgraph_node *node;
2211
2212   fprintf (f, "\nFunction parameters:\n");
2213   for (node = cgraph_nodes; node; node = node->next)
2214     ipa_print_node_params (f, node);
2215 }
2216
2217 /* Return a heap allocated vector containing formal parameters of FNDECL.  */
2218
2219 VEC(tree, heap) *
2220 ipa_get_vector_of_formal_parms (tree fndecl)
2221 {
2222   VEC(tree, heap) *args;
2223   int count;
2224   tree parm;
2225
2226   count = count_formal_params (fndecl);
2227   args = VEC_alloc (tree, heap, count);
2228   for (parm = DECL_ARGUMENTS (fndecl); parm; parm = DECL_CHAIN (parm))
2229     VEC_quick_push (tree, args, parm);
2230
2231   return args;
2232 }
2233
2234 /* Return a heap allocated vector containing types of formal parameters of
2235    function type FNTYPE.  */
2236
2237 static inline VEC(tree, heap) *
2238 get_vector_of_formal_parm_types (tree fntype)
2239 {
2240   VEC(tree, heap) *types;
2241   int count = 0;
2242   tree t;
2243
2244   for (t = TYPE_ARG_TYPES (fntype); t; t = TREE_CHAIN (t))
2245     count++;
2246
2247   types = VEC_alloc (tree, heap, count);
2248   for (t = TYPE_ARG_TYPES (fntype); t; t = TREE_CHAIN (t))
2249     VEC_quick_push (tree, types, TREE_VALUE (t));
2250
2251   return types;
2252 }
2253
2254 /* Modify the function declaration FNDECL and its type according to the plan in
2255    ADJUSTMENTS.  It also sets base fields of individual adjustments structures
2256    to reflect the actual parameters being modified which are determined by the
2257    base_index field.  */
2258
2259 void
2260 ipa_modify_formal_parameters (tree fndecl, ipa_parm_adjustment_vec adjustments,
2261                               const char *synth_parm_prefix)
2262 {
2263   VEC(tree, heap) *oparms, *otypes;
2264   tree orig_type, new_type = NULL;
2265   tree old_arg_types, t, new_arg_types = NULL;
2266   tree parm, *link = &DECL_ARGUMENTS (fndecl);
2267   int i, len = VEC_length (ipa_parm_adjustment_t, adjustments);
2268   tree new_reversed = NULL;
2269   bool care_for_types, last_parm_void;
2270
2271   if (!synth_parm_prefix)
2272     synth_parm_prefix = "SYNTH";
2273
2274   oparms = ipa_get_vector_of_formal_parms (fndecl);
2275   orig_type = TREE_TYPE (fndecl);
2276   old_arg_types = TYPE_ARG_TYPES (orig_type);
2277
2278   /* The following test is an ugly hack, some functions simply don't have any
2279      arguments in their type.  This is probably a bug but well... */
2280   care_for_types = (old_arg_types != NULL_TREE);
2281   if (care_for_types)
2282     {
2283       last_parm_void = (TREE_VALUE (tree_last (old_arg_types))
2284                         == void_type_node);
2285       otypes = get_vector_of_formal_parm_types (orig_type);
2286       if (last_parm_void)
2287         gcc_assert (VEC_length (tree, oparms) + 1 == VEC_length (tree, otypes));
2288       else
2289         gcc_assert (VEC_length (tree, oparms) == VEC_length (tree, otypes));
2290     }
2291   else
2292     {
2293       last_parm_void = false;
2294       otypes = NULL;
2295     }
2296
2297   for (i = 0; i < len; i++)
2298     {
2299       struct ipa_parm_adjustment *adj;
2300       gcc_assert (link);
2301
2302       adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
2303       parm = VEC_index (tree, oparms, adj->base_index);
2304       adj->base = parm;
2305
2306       if (adj->copy_param)
2307         {
2308           if (care_for_types)
2309             new_arg_types = tree_cons (NULL_TREE, VEC_index (tree, otypes,
2310                                                              adj->base_index),
2311                                        new_arg_types);
2312           *link = parm;
2313           link = &DECL_CHAIN (parm);
2314         }
2315       else if (!adj->remove_param)
2316         {
2317           tree new_parm;
2318           tree ptype;
2319
2320           if (adj->by_ref)
2321             ptype = build_pointer_type (adj->type);
2322           else
2323             ptype = adj->type;
2324
2325           if (care_for_types)
2326             new_arg_types = tree_cons (NULL_TREE, ptype, new_arg_types);
2327
2328           new_parm = build_decl (UNKNOWN_LOCATION, PARM_DECL, NULL_TREE,
2329                                  ptype);
2330           DECL_NAME (new_parm) = create_tmp_var_name (synth_parm_prefix);
2331
2332           DECL_ARTIFICIAL (new_parm) = 1;
2333           DECL_ARG_TYPE (new_parm) = ptype;
2334           DECL_CONTEXT (new_parm) = fndecl;
2335           TREE_USED (new_parm) = 1;
2336           DECL_IGNORED_P (new_parm) = 1;
2337           layout_decl (new_parm, 0);
2338
2339           add_referenced_var (new_parm);
2340           mark_sym_for_renaming (new_parm);
2341           adj->base = parm;
2342           adj->reduction = new_parm;
2343
2344           *link = new_parm;
2345
2346           link = &DECL_CHAIN (new_parm);
2347         }
2348     }
2349
2350   *link = NULL_TREE;
2351
2352   if (care_for_types)
2353     {
2354       new_reversed = nreverse (new_arg_types);
2355       if (last_parm_void)
2356         {
2357           if (new_reversed)
2358             TREE_CHAIN (new_arg_types) = void_list_node;
2359           else
2360             new_reversed = void_list_node;
2361         }
2362     }
2363
2364   /* Use copy_node to preserve as much as possible from original type
2365      (debug info, attribute lists etc.)
2366      Exception is METHOD_TYPEs must have THIS argument.
2367      When we are asked to remove it, we need to build new FUNCTION_TYPE
2368      instead.  */
2369   if (TREE_CODE (orig_type) != METHOD_TYPE
2370        || (VEC_index (ipa_parm_adjustment_t, adjustments, 0)->copy_param
2371          && VEC_index (ipa_parm_adjustment_t, adjustments, 0)->base_index == 0))
2372     {
2373       new_type = build_distinct_type_copy (orig_type);
2374       TYPE_ARG_TYPES (new_type) = new_reversed;
2375     }
2376   else
2377     {
2378       new_type
2379         = build_distinct_type_copy (build_function_type (TREE_TYPE (orig_type),
2380                                                          new_reversed));
2381       TYPE_CONTEXT (new_type) = TYPE_CONTEXT (orig_type);
2382       DECL_VINDEX (fndecl) = NULL_TREE;
2383     }
2384
2385   /* When signature changes, we need to clear builtin info.  */
2386   if (DECL_BUILT_IN (fndecl))
2387     {
2388       DECL_BUILT_IN_CLASS (fndecl) = NOT_BUILT_IN;
2389       DECL_FUNCTION_CODE (fndecl) = (enum built_in_function) 0;
2390     }
2391
2392   /* This is a new type, not a copy of an old type.  Need to reassociate
2393      variants.  We can handle everything except the main variant lazily.  */
2394   t = TYPE_MAIN_VARIANT (orig_type);
2395   if (orig_type != t)
2396     {
2397       TYPE_MAIN_VARIANT (new_type) = t;
2398       TYPE_NEXT_VARIANT (new_type) = TYPE_NEXT_VARIANT (t);
2399       TYPE_NEXT_VARIANT (t) = new_type;
2400     }
2401   else
2402     {
2403       TYPE_MAIN_VARIANT (new_type) = new_type;
2404       TYPE_NEXT_VARIANT (new_type) = NULL;
2405     }
2406
2407   TREE_TYPE (fndecl) = new_type;
2408   DECL_VIRTUAL_P (fndecl) = 0;
2409   if (otypes)
2410     VEC_free (tree, heap, otypes);
2411   VEC_free (tree, heap, oparms);
2412 }
2413
2414 /* Modify actual arguments of a function call CS as indicated in ADJUSTMENTS.
2415    If this is a directly recursive call, CS must be NULL.  Otherwise it must
2416    contain the corresponding call graph edge.  */
2417
2418 void
2419 ipa_modify_call_arguments (struct cgraph_edge *cs, gimple stmt,
2420                            ipa_parm_adjustment_vec adjustments)
2421 {
2422   VEC(tree, heap) *vargs;
2423   VEC(tree, gc) **debug_args = NULL;
2424   gimple new_stmt;
2425   gimple_stmt_iterator gsi;
2426   tree callee_decl;
2427   int i, len;
2428
2429   len = VEC_length (ipa_parm_adjustment_t, adjustments);
2430   vargs = VEC_alloc (tree, heap, len);
2431   callee_decl = !cs ? gimple_call_fndecl (stmt) : cs->callee->decl;
2432
2433   gsi = gsi_for_stmt (stmt);
2434   for (i = 0; i < len; i++)
2435     {
2436       struct ipa_parm_adjustment *adj;
2437
2438       adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
2439
2440       if (adj->copy_param)
2441         {
2442           tree arg = gimple_call_arg (stmt, adj->base_index);
2443
2444           VEC_quick_push (tree, vargs, arg);
2445         }
2446       else if (!adj->remove_param)
2447         {
2448           tree expr, base, off;
2449           location_t loc;
2450
2451           /* We create a new parameter out of the value of the old one, we can
2452              do the following kind of transformations:
2453
2454              - A scalar passed by reference is converted to a scalar passed by
2455                value.  (adj->by_ref is false and the type of the original
2456                actual argument is a pointer to a scalar).
2457
2458              - A part of an aggregate is passed instead of the whole aggregate.
2459                The part can be passed either by value or by reference, this is
2460                determined by value of adj->by_ref.  Moreover, the code below
2461                handles both situations when the original aggregate is passed by
2462                value (its type is not a pointer) and when it is passed by
2463                reference (it is a pointer to an aggregate).
2464
2465              When the new argument is passed by reference (adj->by_ref is true)
2466              it must be a part of an aggregate and therefore we form it by
2467              simply taking the address of a reference inside the original
2468              aggregate.  */
2469
2470           gcc_checking_assert (adj->offset % BITS_PER_UNIT == 0);
2471           base = gimple_call_arg (stmt, adj->base_index);
2472           loc = EXPR_LOCATION (base);
2473
2474           if (TREE_CODE (base) != ADDR_EXPR
2475               && POINTER_TYPE_P (TREE_TYPE (base)))
2476             off = build_int_cst (adj->alias_ptr_type,
2477                                  adj->offset / BITS_PER_UNIT);
2478           else
2479             {
2480               HOST_WIDE_INT base_offset;
2481               tree prev_base;
2482
2483               if (TREE_CODE (base) == ADDR_EXPR)
2484                 base = TREE_OPERAND (base, 0);
2485               prev_base = base;
2486               base = get_addr_base_and_unit_offset (base, &base_offset);
2487               /* Aggregate arguments can have non-invariant addresses.  */
2488               if (!base)
2489                 {
2490                   base = build_fold_addr_expr (prev_base);
2491                   off = build_int_cst (adj->alias_ptr_type,
2492                                        adj->offset / BITS_PER_UNIT);
2493                 }
2494               else if (TREE_CODE (base) == MEM_REF)
2495                 {
2496                   off = build_int_cst (adj->alias_ptr_type,
2497                                        base_offset
2498                                        + adj->offset / BITS_PER_UNIT);
2499                   off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1),
2500                                          off);
2501                   base = TREE_OPERAND (base, 0);
2502                 }
2503               else
2504                 {
2505                   off = build_int_cst (adj->alias_ptr_type,
2506                                        base_offset
2507                                        + adj->offset / BITS_PER_UNIT);
2508                   base = build_fold_addr_expr (base);
2509                 }
2510             }
2511
2512           if (!adj->by_ref)
2513             {
2514               tree type = adj->type;
2515               unsigned int align;
2516               unsigned HOST_WIDE_INT misalign;
2517               align = get_pointer_alignment_1 (base, &misalign);
2518               misalign += (double_int_sext (tree_to_double_int (off),
2519                                             TYPE_PRECISION (TREE_TYPE (off))).low
2520                            * BITS_PER_UNIT);
2521               misalign = misalign & (align - 1);
2522               if (misalign != 0)
2523                 align = (misalign & -misalign);
2524               if (align < TYPE_ALIGN (type))
2525                 type = build_aligned_type (type, align);
2526               expr = fold_build2_loc (loc, MEM_REF, type, base, off);
2527             }
2528           else
2529             {
2530               expr = fold_build2_loc (loc, MEM_REF, adj->type, base, off);
2531               expr = build_fold_addr_expr (expr);
2532             }
2533
2534           expr = force_gimple_operand_gsi (&gsi, expr,
2535                                            adj->by_ref
2536                                            || is_gimple_reg_type (adj->type),
2537                                            NULL, true, GSI_SAME_STMT);
2538           VEC_quick_push (tree, vargs, expr);
2539         }
2540       if (!adj->copy_param && MAY_HAVE_DEBUG_STMTS)
2541         {
2542           unsigned int ix;
2543           tree ddecl = NULL_TREE, origin = DECL_ORIGIN (adj->base), arg;
2544           gimple def_temp;
2545
2546           arg = gimple_call_arg (stmt, adj->base_index);
2547           if (!useless_type_conversion_p (TREE_TYPE (origin), TREE_TYPE (arg)))
2548             {
2549               if (!fold_convertible_p (TREE_TYPE (origin), arg))
2550                 continue;
2551               arg = fold_convert_loc (gimple_location (stmt),
2552                                       TREE_TYPE (origin), arg);
2553             }
2554           if (debug_args == NULL)
2555             debug_args = decl_debug_args_insert (callee_decl);
2556           for (ix = 0; VEC_iterate (tree, *debug_args, ix, ddecl); ix += 2)
2557             if (ddecl == origin)
2558               {
2559                 ddecl = VEC_index (tree, *debug_args, ix + 1);
2560                 break;
2561               }
2562           if (ddecl == NULL)
2563             {
2564               ddecl = make_node (DEBUG_EXPR_DECL);
2565               DECL_ARTIFICIAL (ddecl) = 1;
2566               TREE_TYPE (ddecl) = TREE_TYPE (origin);
2567               DECL_MODE (ddecl) = DECL_MODE (origin);
2568
2569               VEC_safe_push (tree, gc, *debug_args, origin);
2570               VEC_safe_push (tree, gc, *debug_args, ddecl);
2571             }
2572           def_temp = gimple_build_debug_bind (ddecl, unshare_expr (arg),
2573                                               stmt);
2574           gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
2575         }
2576     }
2577
2578   if (dump_file && (dump_flags & TDF_DETAILS))
2579     {
2580       fprintf (dump_file, "replacing stmt:");
2581       print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
2582     }
2583
2584   new_stmt = gimple_build_call_vec (callee_decl, vargs);
2585   VEC_free (tree, heap, vargs);
2586   if (gimple_call_lhs (stmt))
2587     gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
2588
2589   gimple_set_block (new_stmt, gimple_block (stmt));
2590   if (gimple_has_location (stmt))
2591     gimple_set_location (new_stmt, gimple_location (stmt));
2592   gimple_call_set_chain (new_stmt, gimple_call_chain (stmt));
2593   gimple_call_copy_flags (new_stmt, stmt);
2594
2595   if (dump_file && (dump_flags & TDF_DETAILS))
2596     {
2597       fprintf (dump_file, "with stmt:");
2598       print_gimple_stmt (dump_file, new_stmt, 0, 0);
2599       fprintf (dump_file, "\n");
2600     }
2601   gsi_replace (&gsi, new_stmt, true);
2602   if (cs)
2603     cgraph_set_call_stmt (cs, new_stmt);
2604   update_ssa (TODO_update_ssa);
2605   free_dominance_info (CDI_DOMINATORS);
2606 }
2607
2608 /* Return true iff BASE_INDEX is in ADJUSTMENTS more than once.  */
2609
2610 static bool
2611 index_in_adjustments_multiple_times_p (int base_index,
2612                                        ipa_parm_adjustment_vec adjustments)
2613 {
2614   int i, len = VEC_length (ipa_parm_adjustment_t, adjustments);
2615   bool one = false;
2616
2617   for (i = 0; i < len; i++)
2618     {
2619       struct ipa_parm_adjustment *adj;
2620       adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
2621
2622       if (adj->base_index == base_index)
2623         {
2624           if (one)
2625             return true;
2626           else
2627             one = true;
2628         }
2629     }
2630   return false;
2631 }
2632
2633
2634 /* Return adjustments that should have the same effect on function parameters
2635    and call arguments as if they were first changed according to adjustments in
2636    INNER and then by adjustments in OUTER.  */
2637
2638 ipa_parm_adjustment_vec
2639 ipa_combine_adjustments (ipa_parm_adjustment_vec inner,
2640                          ipa_parm_adjustment_vec outer)
2641 {
2642   int i, outlen = VEC_length (ipa_parm_adjustment_t, outer);
2643   int inlen = VEC_length (ipa_parm_adjustment_t, inner);
2644   int removals = 0;
2645   ipa_parm_adjustment_vec adjustments, tmp;
2646
2647   tmp = VEC_alloc (ipa_parm_adjustment_t, heap, inlen);
2648   for (i = 0; i < inlen; i++)
2649     {
2650       struct ipa_parm_adjustment *n;
2651       n = VEC_index (ipa_parm_adjustment_t, inner, i);
2652
2653       if (n->remove_param)
2654         removals++;
2655       else
2656         VEC_quick_push (ipa_parm_adjustment_t, tmp, n);
2657     }
2658
2659   adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, outlen + removals);
2660   for (i = 0; i < outlen; i++)
2661     {
2662       struct ipa_parm_adjustment *r;
2663       struct ipa_parm_adjustment *out = VEC_index (ipa_parm_adjustment_t,
2664                                                    outer, i);
2665       struct ipa_parm_adjustment *in = VEC_index (ipa_parm_adjustment_t, tmp,
2666                                                   out->base_index);
2667
2668       gcc_assert (!in->remove_param);
2669       if (out->remove_param)
2670         {
2671           if (!index_in_adjustments_multiple_times_p (in->base_index, tmp))
2672             {
2673               r = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
2674               memset (r, 0, sizeof (*r));
2675               r->remove_param = true;
2676             }
2677           continue;
2678         }
2679
2680       r = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
2681       memset (r, 0, sizeof (*r));
2682       r->base_index = in->base_index;
2683       r->type = out->type;
2684
2685       /* FIXME:  Create nonlocal value too.  */
2686
2687       if (in->copy_param && out->copy_param)
2688         r->copy_param = true;
2689       else if (in->copy_param)
2690         r->offset = out->offset;
2691       else if (out->copy_param)
2692         r->offset = in->offset;
2693       else
2694         r->offset = in->offset + out->offset;
2695     }
2696
2697   for (i = 0; i < inlen; i++)
2698     {
2699       struct ipa_parm_adjustment *n = VEC_index (ipa_parm_adjustment_t,
2700                                                  inner, i);
2701
2702       if (n->remove_param)
2703         VEC_quick_push (ipa_parm_adjustment_t, adjustments, n);
2704     }
2705
2706   VEC_free (ipa_parm_adjustment_t, heap, tmp);
2707   return adjustments;
2708 }
2709
2710 /* Dump the adjustments in the vector ADJUSTMENTS to dump_file in a human
2711    friendly way, assuming they are meant to be applied to FNDECL.  */
2712
2713 void
2714 ipa_dump_param_adjustments (FILE *file, ipa_parm_adjustment_vec adjustments,
2715                             tree fndecl)
2716 {
2717   int i, len = VEC_length (ipa_parm_adjustment_t, adjustments);
2718   bool first = true;
2719   VEC(tree, heap) *parms = ipa_get_vector_of_formal_parms (fndecl);
2720
2721   fprintf (file, "IPA param adjustments: ");
2722   for (i = 0; i < len; i++)
2723     {
2724       struct ipa_parm_adjustment *adj;
2725       adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
2726
2727       if (!first)
2728         fprintf (file, "                 ");
2729       else
2730         first = false;
2731
2732       fprintf (file, "%i. base_index: %i - ", i, adj->base_index);
2733       print_generic_expr (file, VEC_index (tree, parms, adj->base_index), 0);
2734       if (adj->base)
2735         {
2736           fprintf (file, ", base: ");
2737           print_generic_expr (file, adj->base, 0);
2738         }
2739       if (adj->reduction)
2740         {
2741           fprintf (file, ", reduction: ");
2742           print_generic_expr (file, adj->reduction, 0);
2743         }
2744       if (adj->new_ssa_base)
2745         {
2746           fprintf (file, ", new_ssa_base: ");
2747           print_generic_expr (file, adj->new_ssa_base, 0);
2748         }
2749
2750       if (adj->copy_param)
2751         fprintf (file, ", copy_param");
2752       else if (adj->remove_param)
2753         fprintf (file, ", remove_param");
2754       else
2755         fprintf (file, ", offset %li", (long) adj->offset);
2756       if (adj->by_ref)
2757         fprintf (file, ", by_ref");
2758       print_node_brief (file, ", type: ", adj->type, 0);
2759       fprintf (file, "\n");
2760     }
2761   VEC_free (tree, heap, parms);
2762 }
2763
2764 /* Stream out jump function JUMP_FUNC to OB.  */
2765
2766 static void
2767 ipa_write_jump_function (struct output_block *ob,
2768                          struct ipa_jump_func *jump_func)
2769 {
2770   streamer_write_uhwi (ob, jump_func->type);
2771
2772   switch (jump_func->type)
2773     {
2774     case IPA_JF_UNKNOWN:
2775       break;
2776     case IPA_JF_KNOWN_TYPE:
2777       streamer_write_uhwi (ob, jump_func->value.known_type.offset);
2778       stream_write_tree (ob, jump_func->value.known_type.base_type, true);
2779       stream_write_tree (ob, jump_func->value.known_type.component_type, true);
2780       break;
2781     case IPA_JF_CONST:
2782       stream_write_tree (ob, jump_func->value.constant, true);
2783       break;
2784     case IPA_JF_PASS_THROUGH:
2785       stream_write_tree (ob, jump_func->value.pass_through.operand, true);
2786       streamer_write_uhwi (ob, jump_func->value.pass_through.formal_id);
2787       streamer_write_uhwi (ob, jump_func->value.pass_through.operation);
2788       break;
2789     case IPA_JF_ANCESTOR:
2790       streamer_write_uhwi (ob, jump_func->value.ancestor.offset);
2791       stream_write_tree (ob, jump_func->value.ancestor.type, true);
2792       streamer_write_uhwi (ob, jump_func->value.ancestor.formal_id);
2793       break;
2794     case IPA_JF_CONST_MEMBER_PTR:
2795       stream_write_tree (ob, jump_func->value.member_cst.pfn, true);
2796       stream_write_tree (ob, jump_func->value.member_cst.delta, false);
2797       break;
2798     }
2799 }
2800
2801 /* Read in jump function JUMP_FUNC from IB.  */
2802
2803 static void
2804 ipa_read_jump_function (struct lto_input_block *ib,
2805                         struct ipa_jump_func *jump_func,
2806                         struct data_in *data_in)
2807 {
2808   jump_func->type = (enum jump_func_type) streamer_read_uhwi (ib);
2809
2810   switch (jump_func->type)
2811     {
2812     case IPA_JF_UNKNOWN:
2813       break;
2814     case IPA_JF_KNOWN_TYPE:
2815       jump_func->value.known_type.offset = streamer_read_uhwi (ib);
2816       jump_func->value.known_type.base_type = stream_read_tree (ib, data_in);
2817       jump_func->value.known_type.component_type = stream_read_tree (ib,
2818                                                                      data_in);
2819       break;
2820     case IPA_JF_CONST:
2821       jump_func->value.constant = stream_read_tree (ib, data_in);
2822       break;
2823     case IPA_JF_PASS_THROUGH:
2824       jump_func->value.pass_through.operand = stream_read_tree (ib, data_in);
2825       jump_func->value.pass_through.formal_id = streamer_read_uhwi (ib);
2826       jump_func->value.pass_through.operation
2827         = (enum tree_code) streamer_read_uhwi (ib);
2828       break;
2829     case IPA_JF_ANCESTOR:
2830       jump_func->value.ancestor.offset = streamer_read_uhwi (ib);
2831       jump_func->value.ancestor.type = stream_read_tree (ib, data_in);
2832       jump_func->value.ancestor.formal_id = streamer_read_uhwi (ib);
2833       break;
2834     case IPA_JF_CONST_MEMBER_PTR:
2835       jump_func->value.member_cst.pfn = stream_read_tree (ib, data_in);
2836       jump_func->value.member_cst.delta = stream_read_tree (ib, data_in);
2837       break;
2838     }
2839 }
2840
2841 /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are
2842    relevant to indirect inlining to OB.  */
2843
2844 static void
2845 ipa_write_indirect_edge_info (struct output_block *ob,
2846                               struct cgraph_edge *cs)
2847 {
2848   struct cgraph_indirect_call_info *ii = cs->indirect_info;
2849   struct bitpack_d bp;
2850
2851   streamer_write_hwi (ob, ii->param_index);
2852   streamer_write_hwi (ob, ii->anc_offset);
2853   bp = bitpack_create (ob->main_stream);
2854   bp_pack_value (&bp, ii->polymorphic, 1);
2855   streamer_write_bitpack (&bp);
2856
2857   if (ii->polymorphic)
2858     {
2859       streamer_write_hwi (ob, ii->otr_token);
2860       stream_write_tree (ob, ii->otr_type, true);
2861     }
2862 }
2863
2864 /* Read in parts of cgraph_indirect_call_info corresponding to CS that are
2865    relevant to indirect inlining from IB.  */
2866
2867 static void
2868 ipa_read_indirect_edge_info (struct lto_input_block *ib,
2869                              struct data_in *data_in ATTRIBUTE_UNUSED,
2870                              struct cgraph_edge *cs)
2871 {
2872   struct cgraph_indirect_call_info *ii = cs->indirect_info;
2873   struct bitpack_d bp;
2874
2875   ii->param_index = (int) streamer_read_hwi (ib);
2876   ii->anc_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
2877   bp = streamer_read_bitpack (ib);
2878   ii->polymorphic = bp_unpack_value (&bp, 1);
2879   if (ii->polymorphic)
2880     {
2881       ii->otr_token = (HOST_WIDE_INT) streamer_read_hwi (ib);
2882       ii->otr_type = stream_read_tree (ib, data_in);
2883     }
2884 }
2885
2886 /* Stream out NODE info to OB.  */
2887
2888 static void
2889 ipa_write_node_info (struct output_block *ob, struct cgraph_node *node)
2890 {
2891   int node_ref;
2892   lto_cgraph_encoder_t encoder;
2893   struct ipa_node_params *info = IPA_NODE_REF (node);
2894   int j;
2895   struct cgraph_edge *e;
2896   struct bitpack_d bp;
2897
2898   encoder = ob->decl_state->cgraph_node_encoder;
2899   node_ref = lto_cgraph_encoder_encode (encoder, node);
2900   streamer_write_uhwi (ob, node_ref);
2901
2902   bp = bitpack_create (ob->main_stream);
2903   gcc_assert (info->uses_analysis_done
2904               || ipa_get_param_count (info) == 0);
2905   gcc_assert (!info->node_enqueued);
2906   gcc_assert (!info->ipcp_orig_node);
2907   for (j = 0; j < ipa_get_param_count (info); j++)
2908     bp_pack_value (&bp, ipa_is_param_used (info, j), 1);
2909   streamer_write_bitpack (&bp);
2910   for (e = node->callees; e; e = e->next_callee)
2911     {
2912       struct ipa_edge_args *args = IPA_EDGE_REF (e);
2913
2914       streamer_write_uhwi (ob, ipa_get_cs_argument_count (args));
2915       for (j = 0; j < ipa_get_cs_argument_count (args); j++)
2916         ipa_write_jump_function (ob, ipa_get_ith_jump_func (args, j));
2917     }
2918   for (e = node->indirect_calls; e; e = e->next_callee)
2919     {
2920       struct ipa_edge_args *args = IPA_EDGE_REF (e);
2921
2922       streamer_write_uhwi (ob, ipa_get_cs_argument_count (args));
2923       for (j = 0; j < ipa_get_cs_argument_count (args); j++)
2924         ipa_write_jump_function (ob, ipa_get_ith_jump_func (args, j));
2925       ipa_write_indirect_edge_info (ob, e);
2926     }
2927 }
2928
2929 /* Stream in NODE info from IB.  */
2930
2931 static void
2932 ipa_read_node_info (struct lto_input_block *ib, struct cgraph_node *node,
2933                     struct data_in *data_in)
2934 {
2935   struct ipa_node_params *info = IPA_NODE_REF (node);
2936   int k;
2937   struct cgraph_edge *e;
2938   struct bitpack_d bp;
2939
2940   ipa_initialize_node_params (node);
2941
2942   bp = streamer_read_bitpack (ib);
2943   if (ipa_get_param_count (info) != 0)
2944     info->uses_analysis_done = true;
2945   info->node_enqueued = false;
2946   for (k = 0; k < ipa_get_param_count (info); k++)
2947     ipa_set_param_used (info, k, bp_unpack_value (&bp, 1));
2948   for (e = node->callees; e; e = e->next_callee)
2949     {
2950       struct ipa_edge_args *args = IPA_EDGE_REF (e);
2951       int count = streamer_read_uhwi (ib);
2952
2953       if (!count)
2954         continue;
2955       VEC_safe_grow_cleared (ipa_jump_func_t, gc, args->jump_functions, count);
2956
2957       for (k = 0; k < ipa_get_cs_argument_count (args); k++)
2958         ipa_read_jump_function (ib, ipa_get_ith_jump_func (args, k), data_in);
2959     }
2960   for (e = node->indirect_calls; e; e = e->next_callee)
2961     {
2962       struct ipa_edge_args *args = IPA_EDGE_REF (e);
2963       int count = streamer_read_uhwi (ib);
2964
2965       if (count)
2966         {
2967           VEC_safe_grow_cleared (ipa_jump_func_t, gc, args->jump_functions,
2968                                  count);
2969           for (k = 0; k < ipa_get_cs_argument_count (args); k++)
2970             ipa_read_jump_function (ib, ipa_get_ith_jump_func (args, k),
2971                                     data_in);
2972         }
2973       ipa_read_indirect_edge_info (ib, data_in, e);
2974     }
2975 }
2976
2977 /* Write jump functions for nodes in SET.  */
2978
2979 void
2980 ipa_prop_write_jump_functions (cgraph_node_set set)
2981 {
2982   struct cgraph_node *node;
2983   struct output_block *ob;
2984   unsigned int count = 0;
2985   cgraph_node_set_iterator csi;
2986
2987   if (!ipa_node_params_vector)
2988     return;
2989
2990   ob = create_output_block (LTO_section_jump_functions);
2991   ob->cgraph_node = NULL;
2992   for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
2993     {
2994       node = csi_node (csi);
2995       if (cgraph_function_with_gimple_body_p (node)
2996           && IPA_NODE_REF (node) != NULL)
2997         count++;
2998     }
2999
3000   streamer_write_uhwi (ob, count);
3001
3002   /* Process all of the functions.  */
3003   for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
3004     {
3005       node = csi_node (csi);
3006       if (cgraph_function_with_gimple_body_p (node)
3007           && IPA_NODE_REF (node) != NULL)
3008         ipa_write_node_info (ob, node);
3009     }
3010   streamer_write_char_stream (ob->main_stream, 0);
3011   produce_asm (ob, NULL);
3012   destroy_output_block (ob);
3013 }
3014
3015 /* Read section in file FILE_DATA of length LEN with data DATA.  */
3016
3017 static void
3018 ipa_prop_read_section (struct lto_file_decl_data *file_data, const char *data,
3019                        size_t len)
3020 {
3021   const struct lto_function_header *header =
3022     (const struct lto_function_header *) data;
3023   const int cfg_offset = sizeof (struct lto_function_header);
3024   const int main_offset = cfg_offset + header->cfg_size;
3025   const int string_offset = main_offset + header->main_size;
3026   struct data_in *data_in;
3027   struct lto_input_block ib_main;
3028   unsigned int i;
3029   unsigned int count;
3030
3031   LTO_INIT_INPUT_BLOCK (ib_main, (const char *) data + main_offset, 0,
3032                         header->main_size);
3033
3034   data_in =
3035     lto_data_in_create (file_data, (const char *) data + string_offset,
3036                         header->string_size, NULL);
3037   count = streamer_read_uhwi (&ib_main);
3038
3039   for (i = 0; i < count; i++)
3040     {
3041       unsigned int index;
3042       struct cgraph_node *node;
3043       lto_cgraph_encoder_t encoder;
3044
3045       index = streamer_read_uhwi (&ib_main);
3046       encoder = file_data->cgraph_node_encoder;
3047       node = lto_cgraph_encoder_deref (encoder, index);
3048       gcc_assert (node->analyzed);
3049       ipa_read_node_info (&ib_main, node, data_in);
3050     }
3051   lto_free_section_data (file_data, LTO_section_jump_functions, NULL, data,
3052                          len);
3053   lto_data_in_delete (data_in);
3054 }
3055
3056 /* Read ipcp jump functions.  */
3057
3058 void
3059 ipa_prop_read_jump_functions (void)
3060 {
3061   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
3062   struct lto_file_decl_data *file_data;
3063   unsigned int j = 0;
3064
3065   ipa_check_create_node_params ();
3066   ipa_check_create_edge_args ();
3067   ipa_register_cgraph_hooks ();
3068
3069   while ((file_data = file_data_vec[j++]))
3070     {
3071       size_t len;
3072       const char *data = lto_get_section_data (file_data, LTO_section_jump_functions, NULL, &len);
3073
3074       if (data)
3075         ipa_prop_read_section (file_data, data, len);
3076     }
3077 }
3078
3079 /* After merging units, we can get mismatch in argument counts.
3080    Also decl merging might've rendered parameter lists obsolete.
3081    Also compute called_with_variable_arg info.  */
3082
3083 void
3084 ipa_update_after_lto_read (void)
3085 {
3086   struct cgraph_node *node;
3087
3088   ipa_check_create_node_params ();
3089   ipa_check_create_edge_args ();
3090
3091   for (node = cgraph_nodes; node; node = node->next)
3092     if (node->analyzed)
3093       ipa_initialize_node_params (node);
3094 }