At linktime, consider linkonces as ones that will go away

At linktime, consider linkonces as ones that will go away

[Jan Hubicka]

Hi,
this patch makes us more aggressive at optimizing COMDAT functions in LTO and
whole program mode.  Unlike in local compilation, we do not need to worry that
linking many units together will duplicate function very many times as we are
going to have duplication at most in between program and library that is not
too bad or in between DSOs that is even less problem since dynamic linking
does not discard linkonces anyway and we save relocations this way.

In addition to hidden symbol patch this has just small effect on Mozilla (0.2%)
but should help for programs that do not play with visibilities.

The patch probaby has longest function name I ever invented, but I can't think
of something shorter that would not be unreadable.

Bootstrapped/regtested x86_64-linux, will commit it later today.
Honza

	* cgraph.c (cgraph_will_be_removed_from_program_if_no_direct_calls):
	New function.
	* cgraph.h (cgraph_will_be_removed_from_program_if_no_direct_calls):
	Declare.
	* ipa-cp.c (ipcp_estimate_growth): Use it.
	* ipa-inline.c (cgraph_estimate_growth, cgraph_decide_inlining):
	Likewise.
	
Index: cgraph.c
===================================================================
*** cgraph.c	(revision 161905)
--- cgraph.c	(working copy)
*************** cgraph_edge_cannot_lead_to_return (struc
*** 2650,2653 ****
--- 2651,2679 ----
      return cgraph_node_cannot_return (e->callee);
  }
  
+ /* Return true when function NODE can be excpected to be removed
+    from program when direct calls in this compilation unit are removed.
+ 
+    As a special case COMDAT functions are
+    cgraph_can_remove_if_no_direct_calls_p while the are not
+    cgraph_only_called_directly_p (it is possible they are called from other
+    unit)
+ 
+    This function behaves as cgraph_only_called_directly_p because eliminating
+    all uses of COMDAT function does not make it neccesarily disappear from
+    the program unless we are compiling whole program or we do LTO.  In this
+    case we know we win since dynamic linking will not really discard the
+    linkonce section.  */
+ 
+ bool
+ cgraph_will_be_removed_from_program_if_no_direct_calls (struct cgraph_node *node)
+ {
+   if (node->local.used_from_object_file)
+     return false;
+   if (!in_lto_p && !flag_whole_program)
+     return cgraph_only_called_directly_p (node);
+   else
+     return cgraph_can_remove_if_no_direct_calls_p (node);
+ }
+ 
  #include "gt-cgraph.h"
Index: cgraph.h
===================================================================
*** cgraph.h	(revision 161905)
--- cgraph.h	(working copy)
*************** void cgraph_remove_node_duplication_hook
*** 664,669 ****
--- 664,671 ----
  void cgraph_materialize_all_clones (void);
  gimple cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *);
  bool cgraph_propagate_frequency (struct cgraph_node *node);
+ bool cgraph_will_be_removed_from_program_if_no_direct_calls
+   (struct cgraph_node *node);
  /* In cgraphbuild.c  */
  unsigned int rebuild_cgraph_edges (void);
  void cgraph_rebuild_references (void);
Index: ipa-cp.c
===================================================================
*** ipa-cp.c	(revision 161905)
--- ipa-cp.c	(working copy)
*************** ipcp_estimate_growth (struct cgraph_node
*** 951,957 ****
    struct cgraph_edge *cs;
    int redirectable_node_callers = 0;
    int removable_args = 0;
!   bool need_original = !cgraph_only_called_directly_p (node);
    struct ipa_node_params *info;
    int i, count;
    int growth;
--- 951,958 ----
    struct cgraph_edge *cs;
    int redirectable_node_callers = 0;
    int removable_args = 0;
!   bool need_original
!      = !cgraph_will_be_removed_from_program_if_no_direct_calls (node);
    struct ipa_node_params *info;
    int i, count;
    int growth;
*************** ipcp_insert_stage (void)
*** 1134,1140 ****
        for (cs = node->callers; cs != NULL; cs = cs->next_caller)
  	if (cs->caller == node || ipcp_need_redirect_p (cs))
  	  break;
!       if (!cs && cgraph_only_called_directly_p (node))
  	bitmap_set_bit (dead_nodes, node->uid);
  
        info = IPA_NODE_REF (node);
--- 1135,1141 ----
        for (cs = node->callers; cs != NULL; cs = cs->next_caller)
  	if (cs->caller == node || ipcp_need_redirect_p (cs))
  	  break;
!       if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
  	bitmap_set_bit (dead_nodes, node->uid);
  
        info = IPA_NODE_REF (node);
Index: ipa-inline.c
===================================================================
*** ipa-inline.c	(revision 161905)
--- ipa-inline.c	(working copy)
*************** cgraph_estimate_growth (struct cgraph_no
*** 389,395 ****
       we decide to not inline for different reasons, but it is not big deal
       as in that case we will keep the body around, but we will also avoid
       some inlining.  */
!   if (cgraph_only_called_directly_p (node)
        && !DECL_EXTERNAL (node->decl) && !self_recursive)
      growth -= node->global.size;
  
--- 389,395 ----
       we decide to not inline for different reasons, but it is not big deal
       as in that case we will keep the body around, but we will also avoid
       some inlining.  */
!   if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
        && !DECL_EXTERNAL (node->decl) && !self_recursive)
      growth -= node->global.size;
  
*************** cgraph_decide_inlining (void)
*** 1496,1509 ****
  
  	  if (node->callers
  	      && !node->callers->next_caller
! 	      && cgraph_only_called_directly_p (node)
  	      && node->local.inlinable
  	      && node->callers->inline_failed
  	      && node->callers->caller != node
  	      && node->callers->caller->global.inlined_to != node
  	      && !node->callers->call_stmt_cannot_inline_p
! 	      && !DECL_EXTERNAL (node->decl)
! 	      && !DECL_COMDAT (node->decl))
  	    {
  	      cgraph_inline_failed_t reason;
  	      old_size = overall_size;
--- 1496,1508 ----
  
  	  if (node->callers
  	      && !node->callers->next_caller
! 	      && cgraph_will_be_removed_from_program_if_no_direct_calls (node)
  	      && node->local.inlinable
  	      && node->callers->inline_failed
  	      && node->callers->caller != node
  	      && node->callers->caller->global.inlined_to != node
  	      && !node->callers->call_stmt_cannot_inline_p
! 	      && !DECL_EXTERNAL (node->decl))
  	    {
  	      cgraph_inline_failed_t reason;
  	      old_size = overall_size;

Re: At linktime, consider linkonces as ones that will go away

[Michael Matz]

Hi,

On Thu, 8 Jul 2010, Jan Hubicka wrote:

> 
> The patch probaby has longest function name I ever invented, but I can't 
> think of something shorter that would not be unreadable.

The _from_program seems superfluous, _will_be --> _p, _if_no_direct_calls 
also seems superfluous (it's IMO not so important why it will be removed, 
only that it is, for the why you always can look at that functions 
definition).  Hence, how about cgraph_removed_p, or if too concise maybe 
cgraph_removed_from_program_p ?


Ciao,
Michael.

Re: At linktime, consider linkonces as ones that will go away

[Jan Hubicka]

> Hi,
> 
> On Thu, 8 Jul 2010, Jan Hubicka wrote:
> 
> > 
> > The patch probaby has longest function name I ever invented, but I can't 
> > think of something shorter that would not be unreadable.
> 
> The _from_program seems superfluous, _will_be --> _p, _if_no_direct_calls 
> also seems superfluous (it's IMO not so important why it will be removed, 
> only that it is, for the why you always can look at that functions 
> definition).  Hence, how about cgraph_removed_p, or if too concise maybe 
> cgraph_removed_from_program_p ?

Well, there are several situations each stubbly different.  I concluded things
will be cleaner if the checks will be hidden in predicates with nice descriptive
names, so I ended up with the following:

cgraph_only_called_directly_p when we know function is only called directly
and we see all the calls.  I.e. it is not having address taken, not externally
visible and not used in funnny way (alias, __attribute__ ((used)) etc.).
Such functions go away when all direct calls disappear.

This is used for deciding when function is local and some other cases.

Then we have cgraph_can_remove_if_no_direct_calls_p that in addition
knows that COMDAT functions can disappear even when they can be called
in hidden way from other unit if they are there.  This is used i.e. by
inliner to decide whether offline copy is needed after all calls are inlined.

Then there is cgraph_can_remove_if_no_direct_calls_and_refs_p that
is stronger by not checking for addresses taken and is used by unreachable
function removal.

And finally we have new predicate that is somewhere in between these two.

So cgraph_removed_p name does not make it very clear how that predicate
differs from other.  Also it is not removed from program at the timewe call
it, only will be removed as consequence of transformation and unreachable
function removal later...

I will be happy to rename existing predicates too :))

Honza
> 
> 
> Ciao,
> Michael.

Re: At linktime, consider linkonces as ones that will go away

[Michael Matz]

Hi,

On Thu, 8 Jul 2010, Jan Hubicka wrote:

> cgraph_only_called_directly_p when we know function is only called directly
> and we see all the calls.  I.e. it is not having address taken, not externally
> visible and not used in funnny way (alias, __attribute__ ((used)) etc.).
> Such functions go away when all direct calls disappear.
> 
> This is used for deciding when function is local and some other cases.

So this one is only a sub-predicate with many users, not all of them 
related to "will the function go away?" questions.

> Then we have cgraph_can_remove_if_no_direct_calls_p that in addition 
> knows that COMDAT functions can disappear even when they can be called 
> in hidden way from other unit if they are there.  This is used i.e. by 
> inliner to decide whether offline copy is needed after all calls are 
> inlined.
> 
> Then there is cgraph_can_remove_if_no_direct_calls_and_refs_p that is 
> stronger by not checking for addresses taken and is used by unreachable 
> function removal.
> 
> And finally we have new predicate that is somewhere in between these 
> two.

What differentiates the users of the first predicate from those of the 
second two?  The first case reads to me like "decide if offline copy is 
needed".  The second case reads the same to me.  And the third case too.  
Why do you need three predicates, aren't you always asking "do I need an 
offline copy of this function, even if I can resolve all calls?"

The circumstance should always be the same.  They depend on compilation 
modes and several computed flags.  But I don't see how different questions 
than the above are to be asked.

For instance even your first predicate 
(cgraph_can_remove_if_no_direct_calls_p) needs to take into account 
non-dead references (aka address-takens) to the function (in which case we 
need an offline copy).  Your second predicate seemingly doesn't take
node->address_taken into account, which I find strange.

And the third predicate also just adds a variant for answering the 
question "will this function be removed?".

In addition the pre-existing two predicates are each used exactly once, 
and all uses are itself in between a number of conditions.  This just adds 
the confusion between the different predicates (for instance why the 
surrounding condition isn't part of the predicate), e.g. here:

      if (!e->callee->callers->next_caller
          && cgraph_can_remove_if_no_direct_calls_p (e->callee)
          /* Don't reuse if more than one function shares a comdat group.
             If the other function(s) are needed, we need to emit even
             this function out of line.  */
          && !e->callee->same_comdat_group

So, why do you need three cgraph_can_remove predicates (and why don't they 
contain all conditions necessary?)

> So cgraph_removed_p name does not make it very clear how that predicate 
> differs from other.  Also it is not removed from program at the timewe 
> call it, only will be removed as consequence of transformation and 
> unreachable function removal later...

(that's what the _p is for, isn't it?)


Ciao,
Michael.

Re: At linktime, consider linkonces as ones that will go away

[Jan Hubicka]

> Hi,
> 
> On Thu, 8 Jul 2010, Jan Hubicka wrote:
> 
> > cgraph_only_called_directly_p when we know function is only called directly
> > and we see all the calls.  I.e. it is not having address taken, not externally
> > visible and not used in funnny way (alias, __attribute__ ((used)) etc.).
> > Such functions go away when all direct calls disappear.
> > 
> > This is used for deciding when function is local and some other cases.
> 
> So this one is only a sub-predicate with many users, not all of them 
> related to "will the function go away?" questions.
> 
> > Then we have cgraph_can_remove_if_no_direct_calls_p that in addition 
> > knows that COMDAT functions can disappear even when they can be called 
> > in hidden way from other unit if they are there.  This is used i.e. by 
> > inliner to decide whether offline copy is needed after all calls are 
> > inlined.
> > 
> > Then there is cgraph_can_remove_if_no_direct_calls_and_refs_p that is 
> > stronger by not checking for addresses taken and is used by unreachable 
> > function removal.
> > 
> > And finally we have new predicate that is somewhere in between these 
> > two.
> 
> What differentiates the users of the first predicate from those of the 
> second two?  The first case reads to me like "decide if offline copy is 
> needed".  The second case reads the same to me.  And the third case too.  
> Why do you need three predicates, aren't you always asking "do I need an 
> offline copy of this function, even if I can resolve all calls?"

Well, it is all about stuble differences ;)) Sadly those differences matter
a lot in practice, this is why I worry about them at first place.

Function that is only caled directly can have API changes, i.e. one can take
some code from function body and move it into all callers.  (or propagate
constant into it in ipa-cp, or let ipa-pta to compute PTA sets of its argument)

You can't do that with cgraph_can_remove_if_no_direct_calls_p function since it
would break with COMDAT function without address taken that is called from
other unit (but won't if you eliminate all direct calls as it will die).

So cgraph_only_called_directly is used to guard transofrms that are only safe
if you know all the callers (thus no removing in name),
cgraph_can_remove_if_no_direct_calls_p is used by dead function elimination,
in ipa-inline.

The difference in between cgraph_can_remove_if_no_direct_calls_p and
cgraph_can_remove_if_no_direct_calls_and_refs_p is whether pass cares of
indirect calls too.  I could make ipa-inline to use
cgraph_can_remove_if_no_direct_calls_and_refs_p and test if address is taken,
but since the former existed longer and I think it could be useful elsewhere I
decided to keep it.

The new predicate is used in cases where you want to see if doing code
duplication eliminating direct calls to given function will make the function
to disappear from program (not only current unit as
cgraph_can_remove_if_no_direct_calls_p).  So it is useful for metrics deciding
on how those transforms affect program size, but not for actual removal of
function.

Currently we use cgraph_only_called_directly_p for that but it is too
conservative in LTO and whole program mode where we know that COMDAT functions
won't exist in unbounded number of copies. 
> 
> The circumstance should always be the same.  They depend on compilation 
> modes and several computed flags.  But I don't see how different questions 
> than the above are to be asked.
> 
> For instance even your first predicate 
> (cgraph_can_remove_if_no_direct_calls_p) needs to take into account 
> non-dead references (aka address-takens) to the function (in which case we 
> need an offline copy).  Your second predicate seemingly doesn't take
> node->address_taken into account, which I find strange.
> 
> And the third predicate also just adds a variant for answering the 
> question "will this function be removed?".
> 
> In addition the pre-existing two predicates are each used exactly once, 
> and all uses are itself in between a number of conditions.  This just adds 
> the confusion between the different predicates (for instance why the 
> surrounding condition isn't part of the predicate), e.g. here:
> 
>       if (!e->callee->callers->next_caller
>           && cgraph_can_remove_if_no_direct_calls_p (e->callee)
>           /* Don't reuse if more than one function shares a comdat group.
>              If the other function(s) are needed, we need to emit even
>              this function out of line.  */
>           && !e->callee->same_comdat_group
> 
> So, why do you need three cgraph_can_remove predicates (and why don't they 
> contain all conditions necessary?)

Well the code test if the function can be removed and has precisely 1 call and
has no comdat group.  First test is because we know we are going to inline that
last call and the second test because inliner is stupid and is not able to deal
with comdat groups well.

This probably can't be broken up into independent predicate with resonable
meaning.

> 
> > So cgraph_removed_p name does not make it very clear how that predicate 
> > differs from other.  Also it is not removed from program at the timewe 
> > call it, only will be removed as consequence of transformation and 
> > unreachable function removal later...
> 
> (that's what the _p is for, isn't it?)

_p is shorcut for predicate ;) I would read the function as predicate testing
if my pointer to node points to node that has been removed from cgraph.
cgraph_removable_p would probably work better for my Czenglish, but that won't
make much diference above.

Honza
> 
> 
> Ciao,
> Michael.

Re: At linktime, consider linkonces as ones that will go away

[Michael Matz]

Hi,

On Thu, 8 Jul 2010, Jan Hubicka wrote:

> Well, it is all about stuble differences ;)) Sadly those differences 
> matter a lot in practice, this is why I worry about them at first place.
> 
> Function that is only caled directly can have API changes,

I wasn't talking about the other predicates which are for uses other than 
determining the removability.  I was only talking about the three 
_can_remove_ predicates and why there are three of them.

> So cgraph_only_called_directly

In particular I wasn't asking about this predicate.

> The difference in between cgraph_can_remove_if_no_direct_calls_p and 
> cgraph_can_remove_if_no_direct_calls_and_refs_p is whether pass cares of 
> indirect calls too.  I could make ipa-inline to use 
> cgraph_can_remove_if_no_direct_calls_and_refs_p and test if address is 
> taken, but since the former existed longer and I think it could be 
> useful elsewhere I decided to keep it.

What's completely confusing is, why _and_refs does _not_ take into account 
node.address_taken.  After all if the address is taken (from whereever) we 
can not remove the function (no matter if no direct calls, or other refs, 
or anything else remains or can be ignored), but still 
cgraph_can_remove_if_no_direct_calls_and_refs_p could return true.  

The two _can_remove (and the new one) are confusing 
because they seem to be strange conditional predicates, where certain 
conditions are established at the callers of those predicates and I have 
a hard time figuring out what those conditions are exactly, and why the 
predicates are named in a way that doesn't reflect what they say, and why 
there are different such sets of condition (requiring different can_remove 
predicates).

> The new predicate is used in cases where you want to see if doing code 
> duplication eliminating direct calls to given function will make the 
> function to disappear from program (not only current unit as 
> cgraph_can_remove_if_no_direct_calls_p).  So it is useful for metrics 
> deciding on how those transforms affect program size, but not for actual 
> removal of function.

Okay, so the _from_program in your initial name did make sense (as in 
different to a hypothetical _from_unit).  So my 
cgraph_remove_from_program_p suggestion still stands.  You could then at 
least rename cgraph_can_remove_if_no_direct_calls_p into 
cgraph_remove_from_unit_p (and I hope that remove_from_program 
implies remove_from_unit).

As for the difference between _and_refs_p to the one without _and_refs_p 
see above for my confusion.

> > In addition the pre-existing two predicates are each used exactly once, 
> > and all uses are itself in between a number of conditions.  This just adds 
> > the confusion between the different predicates (for instance why the 
> > surrounding condition isn't part of the predicate), e.g. here:
> > 
> >       if (!e->callee->callers->next_caller
> >           && cgraph_can_remove_if_no_direct_calls_p (e->callee)
> >           /* Don't reuse if more than one function shares a comdat group.
> >              If the other function(s) are needed, we need to emit even
> >              this function out of line.  */
> >           && !e->callee->same_comdat_group
> > 
> > So, why do you need three cgraph_can_remove predicates (and why don't they 
> > contain all conditions necessary?)
> 
> Well the code test if the function can be removed and has precisely 1 
> call and has no comdat group.  First test is because we know we are 
> going to inline that last call and the second test because inliner is 
> stupid and is not able to deal with comdat groups well.
> 
> This probably can't be broken up into independent predicate with 
> resonable meaning.

As this is the only user of cgraph_can_remove_if_no_direct_calls_p() the 
last test (!e->callee->same_comdat_group) can be merged into the predicate 
itself.  After all, it does belong into it: with inliner being 
stupid we cannot remove the function if e->callee->same_comdat_group.


Ciao,
Michael.

Re: At linktime, consider linkonces as ones that will go away

[Jan Hubicka]

> > The difference in between cgraph_can_remove_if_no_direct_calls_p and 
> > cgraph_can_remove_if_no_direct_calls_and_refs_p is whether pass cares of 
> > indirect calls too.  I could make ipa-inline to use 
> > cgraph_can_remove_if_no_direct_calls_and_refs_p and test if address is 
> > taken, but since the former existed longer and I think it could be 
> > useful elsewhere I decided to keep it.
> 
> What's completely confusing is, why _and_refs does _not_ take into account 
> node.address_taken.  After all if the address is taken (from whereever) we 
> can not remove the function (no matter if no direct calls, or other refs, 
> or anything else remains or can be ignored), but still 
> cgraph_can_remove_if_no_direct_calls_and_refs_p could return true.  

Because of "and_refs_p". Refs reffers to ipa-ref references that includes all
places function has addess taken.

Unreachable function removal is usual mark&sweep algorithm. We start with
functions/vars that are not removable even if all direct calls and references
disappear and mark everything referenced or called from that.  If it was part
of this algorithm only, I would probably call it "trivially_needed_node_p" (or
obviously_neccesary_node_p as tree-ssa-dce does), but this name has no meaning
outside context of mark&sweep.

Name is not exact WRT comdat groups (it is older than comdat group code),
basically you are asking:

"If I arrange the following:

  1) no direct calls to FN
  2) no references to FN (if use and_refs_p variant)
  3) all functions within the same comdat group must meet
     cgraph_can_remove_if_no_direct_calls_and_refs_p, 1) and 2)

can I remove function FN from the compilation unit then?"

(As a historical note, this is reason why "needed" flag on cgraph nodes exist
and is named this way.  It however turned out that notion of neededness change
during compilatoin.  First difference is whether we are finalizing source code
unit or compilation unit, second difference makes whole program and third
difference if we are before or after inlining.  Before inlining all extern
inline functions that are referenced or called are not removed, while after
inlining all of those are removable from current unit.  With devirutalization
this is even funnier, since we want to also hold those)
> 
> The two _can_remove (and the new one) are confusing 
> because they seem to be strange conditional predicates, where certain 
> conditions are established at the callers of those predicates and I have 
> a hard time figuring out what those conditions are exactly, and why the 
> predicates are named in a way that doesn't reflect what they say, and why 
> there are different such sets of condition (requiring different can_remove 
> predicates).

Well, the predicates must be conditional, so they are called so.
In dead code removal neither other places we can't first do the transforms
and then ask if function disappeared, because decision on what transforms
you do depends if you will end up removing that function or not.
> 
> > The new predicate is used in cases where you want to see if doing code 
> > duplication eliminating direct calls to given function will make the 
> > function to disappear from program (not only current unit as 
> > cgraph_can_remove_if_no_direct_calls_p).  So it is useful for metrics 
> > deciding on how those transforms affect program size, but not for actual 
> > removal of function.
> 
> Okay, so the _from_program in your initial name did make sense (as in 
> different to a hypothetical _from_unit).  So my 
> cgraph_remove_from_program_p suggestion still stands.  You could then at 
> least rename cgraph_can_remove_if_no_direct_calls_p into 
> cgraph_remove_from_unit_p (and I hope that remove_from_program 
> implies remove_from_unit).

Well, remove_from_program_p would read for me as question
"shall I remove function FN form the program now?"
This is not how it works...
> 
> As this is the only user of cgraph_can_remove_if_no_direct_calls_p() the 
> last test (!e->callee->same_comdat_group) can be merged into the predicate 
> itself.  After all, it does belong into it: with inliner being 
> stupid we cannot remove the function if e->callee->same_comdat_group.

Well, I do not want more divergence in between those two predicates than
what their name suggest.  In my Czenglish I would end up with
cgraph_can_remove_if_node_direct_calls_or_nodes_in_same_comdat_group_p

Thanks for suggestions, I was always having concerns that many various
functions with stuble semantics differences makes cgrpah code difficult to
read.  So suggestions are welcome ;)
Honza