Patchwork Devirtualization within ipa-cp

login
register
mail settings
Submitter Martin Jambor
Date Aug. 4, 2010, 7:06 p.m.
Message ID <20100804190612.GA6199@virgil.arch.suse.de>
Download mbox | patch
Permalink /patch/60884/
State New
Headers show

Comments

Martin Jambor - Aug. 4, 2010, 7:06 p.m.
Hi,

this patch adds devirtualization capabilities to the IPA_CP pass.  In
addition to gathering standard constant-propagation lattices it also
keeps a list of all possible types an argument can have whenever we
can track all of them and if their number is smaller than a newly
introduced parameter devirt-type-list-size.  The pass then goes over
the (outgoing) indirect call graph edges and if the type information
can make them direct - it is a virtual call, the object is a parameter
of known types and the called method is the same for all of them - it
is made direct.  Finally, cgraph_redirect_edge_call_stmt_to_callee in
cgraphunit.c is taught to change the function declarations in call
statements accordingly.

The default value of devirt-type-list-size is 8.  This is so far only
a rather wild guess, I intend to change it after I looked at how big
the lists get when compiling firefox with whopr. 

Bootstrapped and tested on x86_64-linux without any problems.  I'm
sure there will be comments and requests for changes, nevertheless
after I address those, I'd like to commit it to trunk.

Thanks,

Martin


2010-08-03  Martin Jambor  <mjambor@suse.cz>

	* ipa-prop.h (enum ipa_lattice_type): Changed comments.
	(struct ipa_param_descriptor): New fields types and
	cannot_devirtualize.
	(ipa_param_cannot_devirtualize_p): New function.
	(ipa_param_types_vec_empty): Likewise.
	(ipa_make_edge_direct_to_target): Declare.
	* ipa-cp.c: Fixed first stage driver name in initial comment,
	described devirtualization there too.
	(ipcp_analyze_node): Call ipa_analyze_params_uses.
	(ipcp_print_all_lattices): Print devirtualization info.
	(ipa_set_param_cannot_devirtualize): New function.
	(ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
	lattice to BOTTOM.
	(ipcp_init_stage): Merged into...
	(ipcp_generate_summary): ...its caller.
	(ipcp_change_tops_to_bottom): Also process type lists.
	(ipcp_add_param_type): New function.
	(ipcp_copy_types): Likewise.
	(ipcp_propagate_types): Likewise.
	(ipcp_propagate_stage): Also propagate types.
	(ipcp_need_redirect_p): Variable jump_func moved to its scope block.
	Also return true if propagated types require it.
	(ipcp_update_callgraph): Dump redirection info.
	(ipcp_process_devirtualization_opportunities): New function.
	(ipcp_const_param_count): Include known type information.
	(ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
	on new node.  Fixed formatting.
	* ipa-prop.c (make_edge_direct_to_target): Renamed to
	ipa_make_edge_direct_to_target and changed all callers.  Made
	externally visible.
	(ipa_node_duplication_hook): Duplicate types vector.
	* cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
	redirect outgoing calls for which we can't get a decl from the
	statement.  Check that we can get a decl from the call statement.
	* ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
	ipa_analyze_params_uses only when ipa-cp is disabled.
	* tree-inline.c (get_indirect_callee_fndecl): Removed.
	(expand_call_inline): Do not call get_indirect_callee_fndecl.
	* params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.

	* testsuite/g++.dg/ipa/devirt-1.C: New test.
	* testsuite/g++.dg/ipa/devirt-2.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-3.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-4.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-5.C: Likewise.
	* testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
Jan Hubicka - Aug. 5, 2010, 8:35 a.m.
> 2010-08-03  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-prop.h (enum ipa_lattice_type): Changed comments.
> 	(struct ipa_param_descriptor): New fields types and
> 	cannot_devirtualize.
> 	(ipa_param_cannot_devirtualize_p): New function.
> 	(ipa_param_types_vec_empty): Likewise.
> 	(ipa_make_edge_direct_to_target): Declare.
> 	* ipa-cp.c: Fixed first stage driver name in initial comment,
> 	described devirtualization there too.
> 	(ipcp_analyze_node): Call ipa_analyze_params_uses.
> 	(ipcp_print_all_lattices): Print devirtualization info.
> 	(ipa_set_param_cannot_devirtualize): New function.
> 	(ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
> 	lattice to BOTTOM.
> 	(ipcp_init_stage): Merged into...
> 	(ipcp_generate_summary): ...its caller.
> 	(ipcp_change_tops_to_bottom): Also process type lists.
> 	(ipcp_add_param_type): New function.
> 	(ipcp_copy_types): Likewise.
> 	(ipcp_propagate_types): Likewise.
> 	(ipcp_propagate_stage): Also propagate types.
> 	(ipcp_need_redirect_p): Variable jump_func moved to its scope block.
> 	Also return true if propagated types require it.
> 	(ipcp_update_callgraph): Dump redirection info.
> 	(ipcp_process_devirtualization_opportunities): New function.
> 	(ipcp_const_param_count): Include known type information.
> 	(ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
> 	on new node.  Fixed formatting.
> 	* ipa-prop.c (make_edge_direct_to_target): Renamed to
> 	ipa_make_edge_direct_to_target and changed all callers.  Made
> 	externally visible.
> 	(ipa_node_duplication_hook): Duplicate types vector.
> 	* cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
> 	redirect outgoing calls for which we can't get a decl from the
> 	statement.  Check that we can get a decl from the call statement.
> 	* ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
> 	ipa_analyze_params_uses only when ipa-cp is disabled.
> 	* tree-inline.c (get_indirect_callee_fndecl): Removed.
> 	(expand_call_inline): Do not call get_indirect_callee_fndecl.
> 	* params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.
> 
> 	* testsuite/g++.dg/ipa/devirt-1.C: New test.
> 	* testsuite/g++.dg/ipa/devirt-2.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-3.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-4.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-5.C: Likewise.
> 	* testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
> 
> @@ -393,12 +405,17 @@ ipcp_print_all_lattices (FILE * f)
>  		  print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
>  						       0);
>  		}
> -	      fprintf (f, "\n");
>  	    }
>  	  else if (lat->type == IPA_TOP)
> -	    fprintf (f, "type is TOP\n");
> +	    fprintf (f, "type is TOP");
> +	  else
> +	    fprintf (f, "type is BOTTOM");
> +	  if (ipa_param_cannot_devirtualize_p (info, i))
> +	    fprintf (f, " - cannot_devirtualize set\n");
> +	  else if (ipa_param_types_vec_empty (info, i))
> +	    fprintf (f, " - type list empty\n");

Should not we print the non-empty list somewhere here? Or is the dump useless?
> +/* Mark parameter with index I of function described by INFO as unsuitable for
> +   devirtualization.  */
> +
> +static bool
> +ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
> +{
> +  bool ret = info->params[i].cannot_devirtualize;
> +  info->params[i].cannot_devirtualize = 1;
                                           true?

OK, thanks!
Honza
Martin Jambor - Aug. 5, 2010, 9:01 a.m.
Hi,

On Thu, Aug 05, 2010 at 10:35:18AM +0200, Jan Hubicka wrote:
> > 2010-08-03  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	* ipa-prop.h (enum ipa_lattice_type): Changed comments.
> > 	(struct ipa_param_descriptor): New fields types and
> > 	cannot_devirtualize.
> > 	(ipa_param_cannot_devirtualize_p): New function.
> > 	(ipa_param_types_vec_empty): Likewise.
> > 	(ipa_make_edge_direct_to_target): Declare.
> > 	* ipa-cp.c: Fixed first stage driver name in initial comment,
> > 	described devirtualization there too.
> > 	(ipcp_analyze_node): Call ipa_analyze_params_uses.
> > 	(ipcp_print_all_lattices): Print devirtualization info.
> > 	(ipa_set_param_cannot_devirtualize): New function.
> > 	(ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
> > 	lattice to BOTTOM.
> > 	(ipcp_init_stage): Merged into...
> > 	(ipcp_generate_summary): ...its caller.
> > 	(ipcp_change_tops_to_bottom): Also process type lists.
> > 	(ipcp_add_param_type): New function.
> > 	(ipcp_copy_types): Likewise.
> > 	(ipcp_propagate_types): Likewise.
> > 	(ipcp_propagate_stage): Also propagate types.
> > 	(ipcp_need_redirect_p): Variable jump_func moved to its scope block.
> > 	Also return true if propagated types require it.
> > 	(ipcp_update_callgraph): Dump redirection info.
> > 	(ipcp_process_devirtualization_opportunities): New function.
> > 	(ipcp_const_param_count): Include known type information.
> > 	(ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
> > 	on new node.  Fixed formatting.
> > 	* ipa-prop.c (make_edge_direct_to_target): Renamed to
> > 	ipa_make_edge_direct_to_target and changed all callers.  Made
> > 	externally visible.
> > 	(ipa_node_duplication_hook): Duplicate types vector.
> > 	* cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
> > 	redirect outgoing calls for which we can't get a decl from the
> > 	statement.  Check that we can get a decl from the call statement.
> > 	* ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
> > 	ipa_analyze_params_uses only when ipa-cp is disabled.
> > 	* tree-inline.c (get_indirect_callee_fndecl): Removed.
> > 	(expand_call_inline): Do not call get_indirect_callee_fndecl.
> > 	* params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.
> > 
> > 	* testsuite/g++.dg/ipa/devirt-1.C: New test.
> > 	* testsuite/g++.dg/ipa/devirt-2.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-3.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-4.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-5.C: Likewise.
> > 	* testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
> > 
> > @@ -393,12 +405,17 @@ ipcp_print_all_lattices (FILE * f)
> >  		  print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
> >  						       0);
> >  		}
> > -	      fprintf (f, "\n");
> >  	    }
> >  	  else if (lat->type == IPA_TOP)
> > -	    fprintf (f, "type is TOP\n");
> > +	    fprintf (f, "type is TOP");
> > +	  else
> > +	    fprintf (f, "type is BOTTOM");
> > +	  if (ipa_param_cannot_devirtualize_p (info, i))
> > +	    fprintf (f, " - cannot_devirtualize set\n");
> > +	  else if (ipa_param_types_vec_empty (info, i))
> > +	    fprintf (f, " - type list empty\n");
> 
> Should not we print the non-empty list somewhere here? Or is the dump useless?

The dump certainly isn't useless.  On the other hand, the list of
types (well, actually BINFOs), is not that much useful on its own
because then you have to look up actual methods in all of them.  And
so far the cannot_devirtualize and type list empty was enough to do
the necessary debugging.

> > +/* Mark parameter with index I of function described by INFO as unsuitable for
> > +   devirtualization.  */
> > +
> > +static bool
> > +ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
> > +{
> > +  bool ret = info->params[i].cannot_devirtualize;
> > +  info->params[i].cannot_devirtualize = 1;
>                                            true?
> 
> OK, thanks!

Thanks, I will commit the patches shortly.

Martin
H.J. Lu - Sept. 21, 2010, 2:47 p.m.
On Wed, Aug 4, 2010 at 12:06 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> this patch adds devirtualization capabilities to the IPA_CP pass.  In
> addition to gathering standard constant-propagation lattices it also
> keeps a list of all possible types an argument can have whenever we
> can track all of them and if their number is smaller than a newly
> introduced parameter devirt-type-list-size.  The pass then goes over
> the (outgoing) indirect call graph edges and if the type information
> can make them direct - it is a virtual call, the object is a parameter
> of known types and the called method is the same for all of them - it
> is made direct.  Finally, cgraph_redirect_edge_call_stmt_to_callee in
> cgraphunit.c is taught to change the function declarations in call
> statements accordingly.
>
> The default value of devirt-type-list-size is 8.  This is so far only
> a rather wild guess, I intend to change it after I looked at how big
> the lists get when compiling firefox with whopr.
>
> Bootstrapped and tested on x86_64-linux without any problems.  I'm
> sure there will be comments and requests for changes, nevertheless
> after I address those, I'd like to commit it to trunk.
>
> Thanks,
>
> Martin
>
>
> 2010-08-03  Martin Jambor  <mjambor@suse.cz>
>
>        * ipa-prop.h (enum ipa_lattice_type): Changed comments.
>        (struct ipa_param_descriptor): New fields types and
>        cannot_devirtualize.
>        (ipa_param_cannot_devirtualize_p): New function.
>        (ipa_param_types_vec_empty): Likewise.
>        (ipa_make_edge_direct_to_target): Declare.
>        * ipa-cp.c: Fixed first stage driver name in initial comment,
>        described devirtualization there too.
>        (ipcp_analyze_node): Call ipa_analyze_params_uses.
>        (ipcp_print_all_lattices): Print devirtualization info.
>        (ipa_set_param_cannot_devirtualize): New function.
>        (ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
>        lattice to BOTTOM.
>        (ipcp_init_stage): Merged into...
>        (ipcp_generate_summary): ...its caller.
>        (ipcp_change_tops_to_bottom): Also process type lists.
>        (ipcp_add_param_type): New function.
>        (ipcp_copy_types): Likewise.
>        (ipcp_propagate_types): Likewise.
>        (ipcp_propagate_stage): Also propagate types.
>        (ipcp_need_redirect_p): Variable jump_func moved to its scope block.
>        Also return true if propagated types require it.
>        (ipcp_update_callgraph): Dump redirection info.
>        (ipcp_process_devirtualization_opportunities): New function.
>        (ipcp_const_param_count): Include known type information.
>        (ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
>        on new node.  Fixed formatting.
>        * ipa-prop.c (make_edge_direct_to_target): Renamed to
>        ipa_make_edge_direct_to_target and changed all callers.  Made
>        externally visible.
>        (ipa_node_duplication_hook): Duplicate types vector.
>        * cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
>        redirect outgoing calls for which we can't get a decl from the
>        statement.  Check that we can get a decl from the call statement.
>        * ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
>        ipa_analyze_params_uses only when ipa-cp is disabled.
>        * tree-inline.c (get_indirect_callee_fndecl): Removed.
>        (expand_call_inline): Do not call get_indirect_callee_fndecl.
>        * params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.
>
>        * testsuite/g++.dg/ipa/devirt-1.C: New test.
>        * testsuite/g++.dg/ipa/devirt-2.C: Likewise.
>        * testsuite/g++.dg/ipa/devirt-3.C: Likewise.
>        * testsuite/g++.dg/ipa/devirt-4.C: Likewise.
>        * testsuite/g++.dg/ipa/devirt-5.C: Likewise.
>        * testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
>
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45563


H.J.
H.J. Lu - Sept. 21, 2010, 2:54 p.m.
On Tue, Sep 21, 2010 at 7:47 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Wed, Aug 4, 2010 at 12:06 PM, Martin Jambor <mjambor@suse.cz> wrote:
>> Hi,
>>
>> this patch adds devirtualization capabilities to the IPA_CP pass.  In
>> addition to gathering standard constant-propagation lattices it also
>> keeps a list of all possible types an argument can have whenever we
>> can track all of them and if their number is smaller than a newly
>> introduced parameter devirt-type-list-size.  The pass then goes over
>> the (outgoing) indirect call graph edges and if the type information
>> can make them direct - it is a virtual call, the object is a parameter
>> of known types and the called method is the same for all of them - it
>> is made direct.  Finally, cgraph_redirect_edge_call_stmt_to_callee in
>> cgraphunit.c is taught to change the function declarations in call
>> statements accordingly.
>>
>> The default value of devirt-type-list-size is 8.  This is so far only
>> a rather wild guess, I intend to change it after I looked at how big
>> the lists get when compiling firefox with whopr.
>>
>> Bootstrapped and tested on x86_64-linux without any problems.  I'm
>> sure there will be comments and requests for changes, nevertheless
>> after I address those, I'd like to commit it to trunk.
>>
>> Thanks,
>>
>> Martin
>>
>>
>> 2010-08-03  Martin Jambor  <mjambor@suse.cz>
>>
>>        * ipa-prop.h (enum ipa_lattice_type): Changed comments.
>>        (struct ipa_param_descriptor): New fields types and
>>        cannot_devirtualize.
>>        (ipa_param_cannot_devirtualize_p): New function.
>>        (ipa_param_types_vec_empty): Likewise.
>>        (ipa_make_edge_direct_to_target): Declare.
>>        * ipa-cp.c: Fixed first stage driver name in initial comment,
>>        described devirtualization there too.
>>        (ipcp_analyze_node): Call ipa_analyze_params_uses.
>>        (ipcp_print_all_lattices): Print devirtualization info.
>>        (ipa_set_param_cannot_devirtualize): New function.
>>        (ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
>>        lattice to BOTTOM.
>>        (ipcp_init_stage): Merged into...
>>        (ipcp_generate_summary): ...its caller.
>>        (ipcp_change_tops_to_bottom): Also process type lists.
>>        (ipcp_add_param_type): New function.
>>        (ipcp_copy_types): Likewise.
>>        (ipcp_propagate_types): Likewise.
>>        (ipcp_propagate_stage): Also propagate types.
>>        (ipcp_need_redirect_p): Variable jump_func moved to its scope block.
>>        Also return true if propagated types require it.
>>        (ipcp_update_callgraph): Dump redirection info.
>>        (ipcp_process_devirtualization_opportunities): New function.
>>        (ipcp_const_param_count): Include known type information.
>>        (ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
>>        on new node.  Fixed formatting.
>>        * ipa-prop.c (make_edge_direct_to_target): Renamed to
>>        ipa_make_edge_direct_to_target and changed all callers.  Made
>>        externally visible.
>>        (ipa_node_duplication_hook): Duplicate types vector.
>>        * cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
>>        redirect outgoing calls for which we can't get a decl from the
>>        statement.  Check that we can get a decl from the call statement.
>>        * ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
>>        ipa_analyze_params_uses only when ipa-cp is disabled.
>>        * tree-inline.c (get_indirect_callee_fndecl): Removed.
>>        (expand_call_inline): Do not call get_indirect_callee_fndecl.
>>        * params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.
>>
>>        * testsuite/g++.dg/ipa/devirt-1.C: New test.
>>        * testsuite/g++.dg/ipa/devirt-2.C: Likewise.
>>        * testsuite/g++.dg/ipa/devirt-3.C: Likewise.
>>        * testsuite/g++.dg/ipa/devirt-4.C: Likewise.
>>        * testsuite/g++.dg/ipa/devirt-5.C: Likewise.
>>        * testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
>>
>>
>
> This caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45563
>


It also caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45562
H.J. Lu - Jan. 19, 2011, 4 a.m.
On Tue, Sep 21, 2010 at 7:54 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Tue, Sep 21, 2010 at 7:47 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
>> On Wed, Aug 4, 2010 at 12:06 PM, Martin Jambor <mjambor@suse.cz> wrote:
>>> Hi,
>>>
>>> this patch adds devirtualization capabilities to the IPA_CP pass.  In
>>> addition to gathering standard constant-propagation lattices it also
>>> keeps a list of all possible types an argument can have whenever we
>>> can track all of them and if their number is smaller than a newly
>>> introduced parameter devirt-type-list-size.  The pass then goes over
>>> the (outgoing) indirect call graph edges and if the type information
>>> can make them direct - it is a virtual call, the object is a parameter
>>> of known types and the called method is the same for all of them - it
>>> is made direct.  Finally, cgraph_redirect_edge_call_stmt_to_callee in
>>> cgraphunit.c is taught to change the function declarations in call
>>> statements accordingly.
>>>
>>> The default value of devirt-type-list-size is 8.  This is so far only
>>> a rather wild guess, I intend to change it after I looked at how big
>>> the lists get when compiling firefox with whopr.
>>>
>>> Bootstrapped and tested on x86_64-linux without any problems.  I'm
>>> sure there will be comments and requests for changes, nevertheless
>>> after I address those, I'd like to commit it to trunk.
>>>
>>> Thanks,
>>>
>>> Martin
>>>
>>>
>>> 2010-08-03  Martin Jambor  <mjambor@suse.cz>
>>>
>>>        * ipa-prop.h (enum ipa_lattice_type): Changed comments.
>>>        (struct ipa_param_descriptor): New fields types and
>>>        cannot_devirtualize.
>>>        (ipa_param_cannot_devirtualize_p): New function.
>>>        (ipa_param_types_vec_empty): Likewise.
>>>        (ipa_make_edge_direct_to_target): Declare.
>>>        * ipa-cp.c: Fixed first stage driver name in initial comment,
>>>        described devirtualization there too.
>>>        (ipcp_analyze_node): Call ipa_analyze_params_uses.
>>>        (ipcp_print_all_lattices): Print devirtualization info.
>>>        (ipa_set_param_cannot_devirtualize): New function.
>>>        (ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
>>>        lattice to BOTTOM.
>>>        (ipcp_init_stage): Merged into...
>>>        (ipcp_generate_summary): ...its caller.
>>>        (ipcp_change_tops_to_bottom): Also process type lists.
>>>        (ipcp_add_param_type): New function.
>>>        (ipcp_copy_types): Likewise.
>>>        (ipcp_propagate_types): Likewise.
>>>        (ipcp_propagate_stage): Also propagate types.
>>>        (ipcp_need_redirect_p): Variable jump_func moved to its scope block.
>>>        Also return true if propagated types require it.
>>>        (ipcp_update_callgraph): Dump redirection info.
>>>        (ipcp_process_devirtualization_opportunities): New function.
>>>        (ipcp_const_param_count): Include known type information.
>>>        (ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
>>>        on new node.  Fixed formatting.
>>>        * ipa-prop.c (make_edge_direct_to_target): Renamed to
>>>        ipa_make_edge_direct_to_target and changed all callers.  Made
>>>        externally visible.
>>>        (ipa_node_duplication_hook): Duplicate types vector.
>>>        * cgraphunit.c (cgraph_redirect_edge_call_stmt_to_callee): Also try to
>>>        redirect outgoing calls for which we can't get a decl from the
>>>        statement.  Check that we can get a decl from the call statement.
>>>        * ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
>>>        ipa_analyze_params_uses only when ipa-cp is disabled.
>>>        * tree-inline.c (get_indirect_callee_fndecl): Removed.
>>>        (expand_call_inline): Do not call get_indirect_callee_fndecl.
>>>        * params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): New parameter.
>>>
>>>        * testsuite/g++.dg/ipa/devirt-1.C: New test.
>>>        * testsuite/g++.dg/ipa/devirt-2.C: Likewise.
>>>        * testsuite/g++.dg/ipa/devirt-3.C: Likewise.
>>>        * testsuite/g++.dg/ipa/devirt-4.C: Likewise.
>>>        * testsuite/g++.dg/ipa/devirt-5.C: Likewise.
>>>        * testsuite/gcc.dg/ipa/iinline-3.c: Likewise.
>>>
>>>
>>
>> This caused:
>>
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45563
>>
>
>
> It also caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45562

This also caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47355

Patch

Index: icln/gcc/ipa-cp.c
===================================================================
--- icln.orig/gcc/ipa-cp.c
+++ icln/gcc/ipa-cp.c
@@ -70,7 +70,7 @@  along with GCC; see the file COPYING3.
    modified_flags are defined in ipa_node_params structure
    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
 
-   -ipcp_init_stage() is the first stage driver.
+   -ipcp_generate_summary() is the first stage driver.
 
    Second stage - interprocedural analysis
    ========================================
@@ -117,6 +117,17 @@  along with GCC; see the file COPYING3.
 
    -ipcp_insert_stage() is the third phase driver.
 
+
+   This pass also performs devirtualization - turns virtual calls into direct
+   ones if it can prove that all invocations of the function call the same
+   callee.  This is achieved by building a list of all base types (actually,
+   their BINFOs) that individual parameters can have in an iterative matter
+   just like propagating scalar constants and then examining whether virtual
+   calls which take a parameter as their object fold to the same target for all
+   these types.  If we cannot enumerate all types or there is a type which does
+   not have any BINFO associated with it, cannot_devirtualize of the associated
+   parameter descriptor is set which is an equivalent of BOTTOM lattice value
+   in standard IPA constant propagation.
 */
 
 #include "config.h"
@@ -124,6 +135,7 @@  along with GCC; see the file COPYING3.
 #include "coretypes.h"
 #include "tree.h"
 #include "target.h"
+#include "gimple.h"
 #include "cgraph.h"
 #include "ipa-prop.h"
 #include "tree-flow.h"
@@ -393,12 +405,17 @@  ipcp_print_all_lattices (FILE * f)
 		  print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
 						       0);
 		}
-	      fprintf (f, "\n");
 	    }
 	  else if (lat->type == IPA_TOP)
-	    fprintf (f, "type is TOP\n");
+	    fprintf (f, "type is TOP");
+	  else
+	    fprintf (f, "type is BOTTOM");
+	  if (ipa_param_cannot_devirtualize_p (info, i))
+	    fprintf (f, " - cannot_devirtualize set\n");
+	  else if (ipa_param_types_vec_empty (info, i))
+	    fprintf (f, " - type list empty\n");
 	  else
-	    fprintf (f, "type is BOTTOM\n");
+	    fprintf (f, "\n");
 	}
     }
 }
@@ -523,6 +540,19 @@  ipcp_cloning_candidate_p (struct cgraph_
   return true;
 }
 
+/* Mark parameter with index I of function described by INFO as unsuitable for
+   devirtualization.  */
+
+static bool
+ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
+{
+  bool ret = info->params[i].cannot_devirtualize;
+  info->params[i].cannot_devirtualize = 1;
+  if (info->params[i].types)
+    VEC_free (tree, heap, info->params[i].types);
+  return ret;
+}
+
 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
    types (integers, real types and Fortran constants defined as const_decls)
    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
@@ -545,7 +575,11 @@  ipcp_initialize_node_lattices (struct cg
     type = IPA_BOTTOM;
 
   for (i = 0; i < ipa_get_param_count (info) ; i++)
-    ipcp_get_lattice (info, i)->type = type;
+    {
+      ipcp_get_lattice (info, i)->type = type;
+      if (type == IPA_BOTTOM)
+	ipa_set_param_cannot_devirtualize (info, i);
+    }
 }
 
 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
@@ -599,26 +633,6 @@  ipcp_compute_node_scale (struct cgraph_n
     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
 }
 
-/* Initialization and computation of IPCP data structures.  This is the initial
-   intraprocedural analysis of functions, which gathers information to be
-   propagated later on.  */
-
-static void
-ipcp_init_stage (void)
-{
-  struct cgraph_node *node;
-
-  for (node = cgraph_nodes; node; node = node->next)
-    if (node->analyzed)
-      {
-	/* Unreachable nodes should have been eliminated before ipcp.  */
-	gcc_assert (node->needed || node->reachable);
-
-	node->local.versionable = tree_versionable_function_p (node->decl);
-	ipa_analyze_node (node);
-      }
-}
-
 /* Return true if there are some formal parameters whose value is IPA_TOP (in
    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
    most probably get their values from outside of this compilation unit.  */
@@ -649,11 +663,148 @@  ipcp_change_tops_to_bottom (void)
 		}
 	      lat->type = IPA_BOTTOM;
 	    }
+	  if (!ipa_param_cannot_devirtualize_p (info, i)
+	      && ipa_param_types_vec_empty (info, i))
+	    {
+	      prop_again = true;
+	      ipa_set_param_cannot_devirtualize (info, i);
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "Marking param ");
+		  print_generic_expr (dump_file, ipa_get_param (info, i), 0);
+		  fprintf (dump_file, " of node %s as unusable for "
+			   "devirtualization.\n",
+			   cgraph_node_name (node));
+		}
+	    }
 	}
     }
   return prop_again;
 }
 
+/* Insert BINFO to the list of known types of parameter number I of the
+   function described by CALLEE_INFO.  Return true iff the type information
+   associated with the callee parameter changed in any way.  */
+
+static bool
+ipcp_add_param_type (struct ipa_node_params *callee_info, int i, tree binfo)
+{
+  int j, count;
+
+  if (ipa_param_cannot_devirtualize_p (callee_info, i))
+    return false;
+
+  if (callee_info->params[i].types)
+    {
+      count = VEC_length (tree, callee_info->params[i].types);
+      for (j = 0; j < count; j++)
+	if (VEC_index (tree, callee_info->params[i].types, j) == binfo)
+	  return false;
+    }
+
+  if (VEC_length (tree, callee_info->params[i].types)
+      == (unsigned) PARAM_VALUE (PARAM_DEVIRT_TYPE_LIST_SIZE))
+    return !ipa_set_param_cannot_devirtualize (callee_info, i);
+
+  VEC_safe_push (tree, heap, callee_info->params[i].types, binfo);
+  return true;
+}
+
+/* Copy known types information for parameter number CALLEE_IDX of CALLEE_INFO
+   from a parameter of CALLER_INFO as described by JF.  Return true iff the
+   type information changed in any way.  JF must be a pass-through or an
+   ancestor jump function.  */
+
+static bool
+ipcp_copy_types (struct ipa_node_params *caller_info,
+		 struct ipa_node_params *callee_info,
+		 int callee_idx, struct ipa_jump_func *jf)
+{
+  int caller_idx, j, count;
+  bool res;
+
+  if (ipa_param_cannot_devirtualize_p (callee_info, callee_idx))
+    return false;
+
+  if (jf->type == IPA_JF_PASS_THROUGH)
+    {
+      if (jf->value.pass_through.operation != NOP_EXPR)
+	{
+	  ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+	  return true;
+	}
+      caller_idx = jf->value.pass_through.formal_id;
+    }
+  else
+    caller_idx = jf->value.ancestor.formal_id;
+
+  if (ipa_param_cannot_devirtualize_p (caller_info, caller_idx))
+    {
+      ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+      return true;
+    }
+
+  if (!caller_info->params[caller_idx].types)
+    return false;
+
+  res = false;
+  count = VEC_length (tree, caller_info->params[caller_idx].types);
+  for (j = 0; j < count; j++)
+    {
+      tree binfo = VEC_index (tree, caller_info->params[caller_idx].types, j);
+      if (jf->type == IPA_JF_ANCESTOR)
+	{
+	  binfo = get_binfo_at_offset (binfo, jf->value.ancestor.offset,
+				       jf->value.ancestor.type);
+	  if (!binfo)
+	    {
+	      ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+	      return true;
+	    }
+	}
+      res |= ipcp_add_param_type (callee_info, callee_idx, binfo);
+    }
+  return res;
+}
+
+/* Propagate type information for parameter of CALLEE_INFO number I as
+   described by JF.  CALLER_INFO describes the caller.  Return true iff the
+   type information changed in any way.  */
+
+static bool
+ipcp_propagate_types (struct ipa_node_params *caller_info,
+		      struct ipa_node_params *callee_info,
+		      struct ipa_jump_func *jf, int i)
+{
+  tree cst, binfo;
+
+  switch (jf->type)
+    {
+    case IPA_JF_UNKNOWN:
+    case IPA_JF_CONST_MEMBER_PTR:
+      break;
+
+    case IPA_JF_KNOWN_TYPE:
+      return ipcp_add_param_type (callee_info, i, jf->value.base_binfo);
+
+    case IPA_JF_CONST:
+      cst = jf->value.constant;
+      if (TREE_CODE (cst) != ADDR_EXPR)
+	break;
+      binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0), NULL_TREE);
+      if (!binfo)
+	break;
+      return ipcp_add_param_type (callee_info, i, binfo);
+
+    case IPA_JF_PASS_THROUGH:
+    case IPA_JF_ANCESTOR:
+      return ipcp_copy_types (caller_info, callee_info, i, jf);
+    }
+
+  /* If we reach this we cannot use this parameter for devirtualization.  */
+  return !ipa_set_param_cannot_devirtualize (callee_info, i);
+}
+
 /* Interprocedural analysis. The algorithm propagates constants from the
    caller's parameters to the callee's arguments.  */
 static void
@@ -701,6 +852,9 @@  ipcp_propagate_stage (void)
 		  dest_lat->constant = new_lat.constant;
 		  ipa_push_func_to_list (&wl, cs->callee);
 		}
+
+	      if (ipcp_propagate_types (info, callee_info, jump_func, i))
+		ipa_push_func_to_list (&wl, cs->callee);
 	    }
 	}
     }
@@ -852,7 +1006,6 @@  ipcp_need_redirect_p (struct cgraph_edge
 {
   struct ipa_node_params *orig_callee_info;
   int i, count;
-  struct ipa_jump_func *jump_func;
   struct cgraph_node *node = cs->callee, *orig;
 
   if (!n_cloning_candidates)
@@ -868,12 +1021,16 @@  ipcp_need_redirect_p (struct cgraph_edge
   for (i = 0; i < count; i++)
     {
       struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
-      if (ipcp_lat_is_const (lat))
-	{
-	  jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
-	  if (jump_func->type != IPA_JF_CONST)
-	    return true;
-	}
+      struct ipa_jump_func *jump_func;
+
+      jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
+      if ((ipcp_lat_is_const (lat)
+	   && jump_func->type != IPA_JF_CONST)
+	  || (!ipa_param_cannot_devirtualize_p (orig_callee_info, i)
+	      && !ipa_param_types_vec_empty (orig_callee_info, i)
+	      && jump_func->type != IPA_JF_CONST
+	      && jump_func->type != IPA_JF_KNOWN_TYPE))
+	return true;
     }
 
   return false;
@@ -912,7 +1069,15 @@  ipcp_update_callgraph (void)
 	  {
 	    next = cs->next_caller;
 	    if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
-	      cgraph_redirect_edge_callee (cs, orig_node);
+	      {
+		if (dump_file)
+		  fprintf (dump_file, "Redirecting edge %s/%i -> %s/%i "
+			   "back to %s/%i.",
+			   cgraph_node_name (cs->caller), cs->caller->uid,
+			   cgraph_node_name (cs->callee), cs->callee->uid,
+			   cgraph_node_name (orig_node), orig_node->uid);
+		cgraph_redirect_edge_callee (cs, orig_node);
+	      }
 	  }
       }
 }
@@ -1031,6 +1196,57 @@  ipcp_estimate_cloning_cost (struct cgrap
   return cost + 1;
 }
 
+/* Walk indirect calls of NODE and if any polymorphic can be turned into a
+   direct one now, do so.  */
+
+static void
+ipcp_process_devirtualization_opportunities (struct cgraph_node *node)
+{
+  struct ipa_node_params *info = IPA_NODE_REF (node);
+  struct cgraph_edge *ie, *next_ie;
+
+  for (ie = node->indirect_calls; ie; ie = next_ie)
+    {
+      int param_index, types_count, j;
+      HOST_WIDE_INT token;
+      tree target;
+
+      next_ie = ie->next_callee;
+      if (!ie->indirect_info->polymorphic)
+	continue;
+      param_index = ie->indirect_info->param_index;
+      if (param_index == -1
+	  || ipa_param_cannot_devirtualize_p (info, param_index)
+	  || ipa_param_types_vec_empty (info, param_index))
+	continue;
+
+      token = ie->indirect_info->otr_token;
+      target = NULL_TREE;
+      types_count = VEC_length (tree, info->params[param_index].types);
+      for (j = 0; j < types_count; j++)
+	{
+	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
+	  tree t = gimple_fold_obj_type_ref_known_binfo (token, binfo);
+
+	  if (!t)
+	    {
+	      target = NULL_TREE;
+	      break;
+	    }
+	  else if (!target)
+	    target = t;
+	  else if (target != t)
+	    {
+	      target = NULL_TREE;
+	      break;
+	    }
+	}
+
+      if (target)
+	ipa_make_edge_direct_to_target (ie, target);
+    }
+}
+
 /* Return number of live constant parameters.  */
 static int
 ipcp_const_param_count (struct cgraph_node *node)
@@ -1043,9 +1259,11 @@  ipcp_const_param_count (struct cgraph_no
   for (i = 0; i < count; i++)
     {
       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
-      if (ipcp_lat_is_insertable (lat)
+      if ((ipcp_lat_is_insertable (lat)
 	  /* Do not count obviously unused arguments.  */
-          && ipa_is_param_used (info, i))
+	   && ipa_is_param_used (info, i))
+	  || (!ipa_param_cannot_devirtualize_p (info, i)
+	      && !ipa_param_types_vec_empty (info, i)))
 	const_param++;
     }
   return const_param;
@@ -1087,7 +1305,8 @@  ipcp_insert_stage (void)
     max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
   max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
 
-  /* First collect all functions we proved to have constant arguments to heap.  */
+  /* First collect all functions we proved to have constant arguments to
+     heap.  */
   heap = fibheap_new ();
   for (node = cgraph_nodes; node; node = node->next)
     {
@@ -1099,7 +1318,8 @@  ipcp_insert_stage (void)
       if (ipa_is_called_with_var_arguments (info))
 	continue;
       if (ipcp_const_param_count (node))
-	node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
+	node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node),
+				    node);
      }
 
   /* Now clone in priority order until code size growth limits are met or
@@ -1183,6 +1403,8 @@  ipcp_insert_stage (void)
 
       if (node1 == NULL)
 	continue;
+      ipcp_process_devirtualization_opportunities (node1);
+
       if (dump_file)
 	fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
 		 cgraph_node_name (node), (int)growth, (int)new_size);
@@ -1245,18 +1467,30 @@  ipcp_driver (void)
   return 0;
 }
 
-/* Note function body size.  */
+/* Initialization and computation of IPCP data structures.  This is the initial
+   intraprocedural analysis of functions, which gathers information to be
+   propagated later on.  */
+
 static void
 ipcp_generate_summary (void)
 {
+  struct cgraph_node *node;
+
   if (dump_file)
     fprintf (dump_file, "\nIPA constant propagation start:\n");
   ipa_check_create_node_params ();
   ipa_check_create_edge_args ();
   ipa_register_cgraph_hooks ();
-  /* 1. Call the init stage to initialize
-     the ipa_node_params and ipa_edge_args structures.  */
-  ipcp_init_stage ();
+
+  for (node = cgraph_nodes; node; node = node->next)
+    if (node->analyzed)
+      {
+	/* Unreachable nodes should have been eliminated before ipcp.  */
+	gcc_assert (node->needed || node->reachable);
+
+	node->local.versionable = tree_versionable_function_p (node->decl);
+	ipa_analyze_node (node);
+      }
 }
 
 /* Write ipcp summary for nodes in SET.  */
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -133,11 +133,12 @@  struct GTY (()) ipa_jump_func
    computed by the interprocedural stage of IPCP.
    There are three main values of the lattice:
    IPA_TOP - unknown,
-   IPA_BOTTOM - non constant,
+   IPA_BOTTOM - variable,
    IPA_CONST_VALUE - simple scalar constant,
-   Cval of formal f will have a constant value if all callsites to this
-   function have the same constant value passed to f.
-   Integer and real constants are represented as IPA_CONST_VALUE.  */
+
+   We also use this type to propagate types accross the call graph for the
+   purpose of devirtualization.  In that case, IPA_CONST_VALUE denotes a known
+   type, rather than a constant.  */
 enum ipa_lattice_type
 {
   IPA_BOTTOM,
@@ -161,8 +162,14 @@  struct ipa_param_descriptor
   struct ipcp_lattice ipcp_lattice;
   /* PARAM_DECL of this parameter.  */
   tree decl;
+  /* Vector of BINFOs of types that this argument might encounter.  NULL
+     basically means a top value, bottom is marked by the cannot_devirtualize
+     flag below.*/
+  VEC (tree, heap) *types;
   /* The parameter is used.  */
   unsigned used : 1;
+  /* Set when parameter type cannot be used for devirtualization.  */
+  unsigned cannot_devirtualize : 1;
 };
 
 /* ipa_node_params stores information related to formal parameters of functions
@@ -232,6 +239,25 @@  ipa_is_param_used (struct ipa_node_param
   return info->params[i].used;
 }
 
+/* Return the cannot_devirtualize flag corresponding to the Ith formal
+   parameter of the function associated with INFO.  The corresponding function
+   to set the flag is ipa_set_param_cannot_devirtualize.  */
+
+static inline bool
+ipa_param_cannot_devirtualize_p (struct ipa_node_params *info, int i)
+{
+  return info->params[i].cannot_devirtualize;
+}
+
+/* Return true iff the vector of possible types of the Ith formal parameter of
+   the function associated with INFO is empty.  */
+
+static inline bool
+ipa_param_types_vec_empty (struct ipa_node_params *info, int i)
+{
+  return info->params[i].types == NULL;
+}
+
 /* Flag this node as having callers with variable number of arguments.  */
 
 static inline void
@@ -402,6 +428,10 @@  void ipa_initialize_node_params (struct
 bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
 					VEC (cgraph_edge_p, heap) **new_edges);
 
+/* Indirect edge and binfo processing.  */
+struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree);
+
+
 /* Debugging interface.  */
 void ipa_print_node_params (FILE *, struct cgraph_node *node);
 void ipa_print_all_params (FILE *);
Index: icln/gcc/cgraphunit.c
===================================================================
--- icln.orig/gcc/cgraphunit.c
+++ icln/gcc/cgraphunit.c
@@ -2362,14 +2362,18 @@  cgraph_redirect_edge_call_stmt_to_callee
   struct cgraph_node *node;
 #endif
 
-  if (!decl || decl == e->callee->decl
+  if (e->indirect_unknown_callee
+      || decl == e->callee->decl
       /* Don't update call from same body alias to the real function.  */
-      || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
+      || (decl && cgraph_get_node (decl) == cgraph_get_node (e->callee->decl)))
     return e->call_stmt;
 
 #ifdef ENABLE_CHECKING
-  node = cgraph_get_node (decl);
-  gcc_assert (!node || !node->clone.combined_args_to_skip);
+  if (decl)
+    {
+      node = cgraph_get_node (decl);
+      gcc_assert (!node || !node->clone.combined_args_to_skip);
+    }
 #endif
 
   if (cgraph_dump_file)
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -1430,8 +1430,8 @@  update_jump_functions_after_inlining (st
 /* If TARGET is an addr_expr of a function declaration, make it the destination
    of an indirect edge IE and return the edge.  Otherwise, return NULL.  */
 
-static struct cgraph_edge *
-make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
+struct cgraph_edge *
+ipa_make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
 {
   struct cgraph_node *callee;
 
@@ -1484,7 +1484,7 @@  try_make_edge_direct_simple_call (struct
   else
     return NULL;
 
-  return make_edge_direct_to_target (ie, target);
+  return ipa_make_edge_direct_to_target (ie, target);
 }
 
 /* Try to find a destination for indirect edge IE that corresponds to a
@@ -1525,7 +1525,7 @@  try_make_edge_direct_virtual_call (struc
     return NULL;
 
   if (target)
-    return make_edge_direct_to_target (ie, target);
+    return ipa_make_edge_direct_to_target (ie, target);
   else
     return NULL;
 }
@@ -1794,7 +1794,7 @@  ipa_node_duplication_hook (struct cgraph
 			   __attribute__((unused)) void *data)
 {
   struct ipa_node_params *old_info, *new_info;
-  int param_count;
+  int param_count, i;
 
   ipa_check_create_node_params ();
   old_info = IPA_NODE_REF (src);
@@ -1805,8 +1805,15 @@  ipa_node_duplication_hook (struct cgraph
   new_info->params = (struct ipa_param_descriptor *)
     duplicate_array (old_info->params,
 		     sizeof (struct ipa_param_descriptor) * param_count);
+  for (i = 0; i < param_count; i++)
+    new_info->params[i].types = VEC_copy (tree, heap,
+ 					  old_info->params[i].types);
   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
   new_info->count_scale = old_info->count_scale;
+
+  new_info->called_with_var_arguments = old_info->called_with_var_arguments;
+  new_info->uses_analysis_done = old_info->uses_analysis_done;
+  new_info->node_enqueued = old_info->node_enqueued;
 }
 
 /* Register our cgraph hooks if they are not already there.  */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-1.C
@@ -0,0 +1,62 @@ 
+/* Verify that simple virtual calls are converted to direct calls by ipa-cp.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int C::foo (int i)
+{
+  return i + 3;
+}
+
+static int middleman (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+  if (middleman (&b, get_input ()) != 3)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-2.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-2.C
@@ -0,0 +1,62 @@ 
+/* Verify that simple virtual calls using this pointer are converted
+   to direct calls by ipa-cp.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp"  } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+  int middleman (int i)
+  {
+    return foo (i);
+  }
+};
+
+class B : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int C::foo (int i)
+{
+  return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+  int i;
+  for (i = 0; i < get_input(); i++)
+    if (b.middleman (get_input ()) != 3)
+      abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-3.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-3.C
@@ -0,0 +1,63 @@ 
+/* Verify that simple virtual calls on an object refrence are
+   converted to simple calls by ipa-cp.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int C::foo (int i)
+{
+  return i + 3;
+}
+
+static int middleman (class A &obj, int i)
+{
+  return obj.foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+  if (middleman (b, get_input ()) != 3)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-4.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-4.C
@@ -0,0 +1,68 @@ 
+/* Verify that ipa-co can convert virtual calls to direct ones even
+   when a typecast to an ancestor is involved along the way.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int C::foo (int i)
+{
+  return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+  return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+  if (middleman_2 (&b, get_input ()) != 3)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-5.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-5.C
@@ -0,0 +1,79 @@ 
+/* Verify that ipa-cp can convert simple virtual calls to a direct
+   ones even when a typecast to an ancestor is involved along the way
+   and that ancestor is not the first one with virtual functions.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
+
+extern "C" void abort (void);
+
+class Distraction
+{
+public:
+  float f;
+  double d;
+  Distraction ()
+  {
+    f = 8.3;
+    d = 10.2;
+  }
+  virtual float bar (float z);
+};
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+  virtual int foo (int i);
+};
+
+float Distraction::bar (float z)
+{
+  f += z;
+  return f/2;
+}
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+  return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+
+  if (middleman_2 (&b, get_input ()) != 3)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/gcc.dg/ipa/iinline-3.c
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/gcc.dg/ipa/iinline-3.c
@@ -0,0 +1,33 @@ 
+/* Verify that call declarations are not redirected according to indirect
+   inlining edges too early.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining"  } */
+
+extern void abort (void);
+
+int bar (int k)
+{
+  return k+2;
+}
+
+int baz (int k)
+{
+  return k+1;
+}
+
+static int foo (int (*p)(int), int i)
+{
+  return p (i+1);
+}
+
+int (*g)(int) = baz;
+
+int main (int argc, char *argv[])
+{
+  if (foo (bar, 0) != 3)
+    abort ();
+  if (foo (g, 1) != 3)
+    abort ();
+
+  return 0;
+}
Index: icln/gcc/tree-inline.c
===================================================================
--- icln.orig/gcc/tree-inline.c
+++ icln/gcc/tree-inline.c
@@ -3707,20 +3707,6 @@  add_local_variables (struct function *ca
       }
 }
 
-/* Fetch callee declaration from the call graph edge going from NODE and
-   associated with STMR call statement.  Return NULL_TREE if not found.  */
-static tree
-get_indirect_callee_fndecl (struct cgraph_node *node, gimple stmt)
-{
-  struct cgraph_edge *cs;
-
-  cs = cgraph_edge (node, stmt);
-  if (cs && !cs->indirect_unknown_callee)
-    return cs->callee->decl;
-
-  return NULL_TREE;
-}
-
 /* If STMT is a GIMPLE_CALL, replace it with its inline expansion.  */
 
 static bool
@@ -3754,11 +3740,7 @@  expand_call_inline (basic_block bb, gimp
      If we cannot, then there is no hope of inlining the function.  */
   fn = gimple_call_fndecl (stmt);
   if (!fn)
-    {
-      fn = get_indirect_callee_fndecl (id->dst_node, stmt);
-      if (!fn)
-	goto egress;
-    }
+    goto egress;
 
   /* Turn forward declarations into real ones.  */
   fn = cgraph_node (fn)->decl;
Index: icln/gcc/Makefile.in
===================================================================
--- icln.orig/gcc/Makefile.in
+++ icln/gcc/Makefile.in
@@ -3016,7 +3016,7 @@  ipa-cp.o : ipa-cp.c $(CONFIG_H) $(SYSTEM
    $(TREE_PASS_H) $(FLAGS_H) $(TIMEVAR_H) $(DIAGNOSTIC_H) $(TREE_DUMP_H) \
    $(TREE_INLINE_H) $(FIBHEAP_H) $(PARAMS_H) tree-pretty-print.h
 ipa-split.o : ipa-split.c $(CONFIG_H) $(SYSTEM_H) coretypes.h  \
-   $(TREE_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(TREE_FLOW_H) \
+   $(TREE_H) $(TARGET_H) $(GIMPLE_H) $(CGRAPH_H) $(IPA_PROP_H) $(TREE_FLOW_H) \
    $(TREE_PASS_H) $(FLAGS_H) $(TIMEVAR_H) $(DIAGNOSTIC_H) $(TREE_DUMP_H) \
    $(TREE_INLINE_H) $(FIBHEAP_H) $(PARAMS_H)
 matrix-reorg.o : matrix-reorg.c $(CONFIG_H) $(SYSTEM_H) coretypes.h  \
Index: icln/gcc/params.def
===================================================================
--- icln.orig/gcc/params.def
+++ icln/gcc/params.def
@@ -832,6 +832,12 @@  DEFPARAM (PARAM_IPA_SRA_PTR_GROWTH_FACTO
 	  "a pointer to an aggregate with",
 	  2, 0, 0)
 
+DEFPARAM (PARAM_DEVIRT_TYPE_LIST_SIZE,
+	  "devirt-type-list-size",
+	  "Maximum size of a type list associated with each parameter for "
+	  "devirtualization",
+	  8, 0, 0)
+
 /*
 Local variables:
 mode:c
Index: icln/gcc/doc/invoke.texi
===================================================================
--- icln.orig/gcc/doc/invoke.texi
+++ icln/gcc/doc/invoke.texi
@@ -8708,6 +8708,12 @@  loop in the loop nest by a given number
 length can be changed using the @option{loop-block-tile-size}
 parameter.  The default value is 51 iterations.
 
+@item devirt-type-list-size
+IPA-CP attempts to track all possible types passed to a function's
+parameter in order to perform devirtualization.
+@option{devirt-type-list-size} is the maximum number of types it
+stores per a single formal parameter of a function.
+
 @end table
 @end table