Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Re: Removing dead code and unused functions

Reply
Thread Tools

Re: Removing dead code and unused functions

 
 
Greg
Guest
Posts: n/a
 
      06-21-2005
Richard Tobin wrote:
> In article <BEDB6241.5C02%(E-Mail Removed)>,
> Jean-Claude Arbaut <(E-Mail Removed)> wrote:
>
> >> Got a link ? The GNU linker at least only puts symbols that are included
> >> into the link map. No mention of it cataloging symbols it excludes.

>
> >I'm not sure but "nm" could be useful here.

>
> Linkers typically do not exclude functions in the user program that are
> unused. They only do that with libraries.
>
> More useful would be one of the many tools that generate call graphs.
>
> -- Richard


The Metrowerks linker, as an example, strips all unreferenced,
unexported functions from a build by default, and does so no matter
where such functions are found. What would be the point of a linker
leaving unreachable code and inaccessible data in a binary? And why
would programmers want to perform this tedious chore by hand themselves
rather than let the linker do it in a few seconds?

The algorithm to strip unused code is well-understood. All the linker
has to do is calculate the "transitive closure" for the set of
functions in the object code to be linked, that includes main(). In
fact calculating the transitive closure is no doubt how Apple was able
to add the "-dead-strip" switch to GNU's ld linker on OS X; and the
reason they did so is clear: many developers are understandably
reluctant to use a linker that bloats their final builds.

Greg

 
Reply With Quote
 
 
 
 
Geronimo W. Christ Esq
Guest
Posts: n/a
 
      06-22-2005
Greg wrote:

> The Metrowerks linker, as an example, strips all unreferenced,
> unexported functions from a build by default, and does so no matter
> where such functions are found. What would be the point of a linker
> leaving unreachable code and inaccessible data in a binary?


They just do it because the linker authors don't put sufficient priority
on dealing with the matter properly. The GNU linker for example only
garbage collects sections rather than individual functions, so if you
use one function in a large object file, the whole object will get linked.

> And why
> would programmers want to perform this tedious chore by hand themselves
> rather than let the linker do it in a few seconds?


If the codebase is full of cruft it is harder to maintain.
 
Reply With Quote
 
 
 
 
Gordon Burditt
Guest
Posts: n/a
 
      06-22-2005
>> The Metrowerks linker, as an example, strips all unreferenced,
>> unexported functions from a build by default, and does so no matter
>> where such functions are found. What would be the point of a linker
>> leaving unreachable code and inaccessible data in a binary?

>
>They just do it because the linker authors don't put sufficient priority
>on dealing with the matter properly. The GNU linker for example only
>garbage collects sections rather than individual functions, so if you
>use one function in a large object file, the whole object will get linked.


There may be insufficient information to TELL whether a particular
piece of a compilation is used or not. For example, no law says that
a particular machine instruction generated by the compiler can be
identified as being part of exactly one function. Functions might
share code. And the linker might not be able to TELL that functions
are sharing code.

int check1arg(char **argv)
{
int i;

i = validate(argv[1]);
/* common */
if (i == OK)
return 1;
else if (i == MAYBE)
return 0;
else
return -1;
}
int check2arg(char **argv)
{
int i;

i = validate(argv[2]);
/* common */
if (i == OK)
return 1;
else if (i == MAYBE)
return 0;
else
return -1;
}

For example, the same copy of the code below /* common */ may be
shared between check1arg() and check2arg(). And possibly, check2arg()
is unused. Can the code below /* common */ be omitted? No.
But how does the linker know this? Decompiling compiler output?
Possibly, but that seems to be a lot of extra effort.

Gordon L. Burditt
 
Reply With Quote
 
Geronimo W. Christ Esq
Guest
Posts: n/a
 
      06-23-2005
Gordon Burditt wrote:
>>>The Metrowerks linker, as an example, strips all unreferenced,
>>>unexported functions from a build by default, and does so no matter
>>>where such functions are found. What would be the point of a linker
>>>leaving unreachable code and inaccessible data in a binary?

>>
>>They just do it because the linker authors don't put sufficient priority
>>on dealing with the matter properly. The GNU linker for example only
>>garbage collects sections rather than individual functions, so if you
>>use one function in a large object file, the whole object will get linked.

>
>
> There may be insufficient information to TELL whether a particular
> piece of a compilation is used or not. For example, no law says that
> a particular machine instruction generated by the compiler can be
> identified as being part of exactly one function. Functions might
> share code. And the linker might not be able to TELL that functions
> are sharing code.


<snip>

The example you gave is nothing to do with linking, because a linker
never examines *within* functions to determine whether they are
redundant or not. On the other hand, the GCC compiler does (when the
optimizer is turned on) look for similar pieces of generated machine
code and "compress" them by replacing them with one copy and some pointers.

It would be very useful if the GNU linker would remove unused functions,
but at the moment it doesn't.
 
Reply With Quote
 
Gordon Burditt
Guest
Posts: n/a
 
      06-23-2005
>>>>The Metrowerks linker, as an example, strips all unreferenced,
>>>>unexported functions from a build by default, and does so no matter
>>>>where such functions are found. What would be the point of a linker
>>>>leaving unreachable code and inaccessible data in a binary?
>>>
>>>They just do it because the linker authors don't put sufficient priority
>>>on dealing with the matter properly. The GNU linker for example only
>>>garbage collects sections rather than individual functions, so if you
>>>use one function in a large object file, the whole object will get linked.

>>
>>
>> There may be insufficient information to TELL whether a particular
>> piece of a compilation is used or not. For example, no law says that
>> a particular machine instruction generated by the compiler can be
>> identified as being part of exactly one function. Functions might
>> share code. And the linker might not be able to TELL that functions
>> are sharing code.

>
><snip>
>
>The example you gave is nothing to do with linking, because a linker
>never examines *within* functions to determine whether they are
>redundant or not.


I didn't say it did. I said that if you have two functions compiled
in a (object) file, and one of them isn't needed, there's no guarantee that
the linker can determine what is part of the needed function (and possibly
the other one also) to keep, and what is NOT part of the needed function
(to delete).

You don't get to conclude that function A starts here, and function
B starts here, so everything between those two addresses is function
A, and none of what's between those two is also part of function
B or C, even if I'm only talking about the so-called code segment of
both functions.

>On the other hand, the GCC compiler does (when the
>optimizer is turned on) look for similar pieces of generated machine
>code and "compress" them by replacing them with one copy and some pointers.


So in that situation, you can have functions that share code, and
object code where there is no contiguous block of code where the
linker can determine "this is function A, and all of function A, and
none of any other function".

>It would be very useful if the GNU linker would remove unused functions,
>but at the moment it doesn't.


The point here is that it may not have the information required to
remove unused functions even if they can be determined to be unused.
The object format may not even PERMIT passing the information required
to determine what code is part of what function(s).

Gordon L. Burditt
 
Reply With Quote
 
Geronimo W. Christ Esq
Guest
Posts: n/a
 
      06-23-2005
Gordon Burditt wrote:

> You don't get to conclude that function A starts here, and function
> B starts here, so everything between those two addresses is function
> A,


I've difficulty picturing how any of the code inside a function can ever
be used in any way if the function is never invoked. I don't see how a
linker would be making an unsafe decision by removing a function that is
never invoked.

I imagine that when a compiler spots repetitive sections of code it
takes them out of the function's object code into a common area of the
object, and has the function point to them. That way redundant functions
could be safely removed.
 
Reply With Quote
 
Paul Groke
Guest
Posts: n/a
 
      06-23-2005
[]
>>On the other hand, the GCC compiler does (when the
>>optimizer is turned on) look for similar pieces of generated machine
>>code and "compress" them by replacing them with one copy and some pointers.

>
>
> So in that situation, you can have functions that share code, and
> object code where there is no contiguous block of code where the
> linker can determine "this is function A, and all of function A, and
> none of any other function".
>
>
>>It would be very useful if the GNU linker would remove unused functions,
>>but at the moment it doesn't.

>
>
> The point here is that it may not have the information required to
> remove unused functions even if they can be determined to be unused.
> The object format may not even PERMIT passing the information required
> to determine what code is part of what function(s).
>
> Gordon L. Burditt


In that case the object format should be changed
 
Reply With Quote
 
Gordon Burditt
Guest
Posts: n/a
 
      06-23-2005
>> You don't get to conclude that function A starts here, and function
>> B starts here, so everything between those two addresses is function
>> A,

>
>I've difficulty picturing how any of the code inside a function can ever
>be used in any way if the function is never invoked. I don't see how a
>linker would be making an unsafe decision by removing a function that is
>never invoked.


Given an object file containing two functions, one used and one
not, resulting from a single compilation, what makes you think that
the linker can remove anything and be sure that it has not removed
a piece of the function that *IS* used? Object file formats that
I have seen do not have labels that say this byte is part of function
a, this byte is part of function b and q, and this byte is part of
functions a, b, j, n, and z.

>I imagine that when a compiler spots repetitive sections of code it
>takes them out of the function's object code into a common area of the
>object, and has the function point to them. That way redundant functions
>could be safely removed.


And what makes you think that function1, function2, and "common area"
are labelled in a way that the linker can identify them? Sure,
the entry points are labelled. That's likely to be all the info
available.

Gordon L. Burditt
 
Reply With Quote
 
Gordon Burditt
Guest
Posts: n/a
 
      06-23-2005
>> The point here is that it may not have the information required to
>> remove unused functions even if they can be determined to be unused.
>> The object format may not even PERMIT passing the information required
>> to determine what code is part of what function(s).
>>
>> Gordon L. Burditt

>
>In that case the object format should be changed


Using that standard, can you name any object format that should
NOT be changed? One in actual use, with an actual compiler that
generates it?

Gordon L. Burditt
 
Reply With Quote
 
Dave Vandervies
Guest
Posts: n/a
 
      06-23-2005
In article <(E-Mail Removed)>,
Gordon Burditt <(E-Mail Removed)> wrote:

>I didn't say it did. I said that if you have two functions compiled
>in a (object) file, and one of them isn't needed, there's no guarantee that
>the linker can determine what is part of the needed function (and possibly
>the other one also) to keep, and what is NOT part of the needed function
>(to delete).


How hard can it be?

I mean, all you have to do is solve the halting problem...


dave

--
Dave Vandervies http://www.velocityreviews.com/forums/(E-Mail Removed)

[T]he program's running time will be reduced by ONE WHOLE MILLISECOND! WOW!
--Eric Sosman in comp.lang.c
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Removing "Unused icons ..." message? Graham Nichols Computer Support 3 09-23-2009 03:28 PM
removing unused styles julianmlp@gmail.com HTML 1 05-31-2006 04:57 AM
C++ lint (detection of unused classes and functions)? Dom Gilligan C++ 6 08-18-2005 08:45 AM
Removing dead code and unused functions Geronimo W. Christ Esq C Programming 39 07-04-2005 05:38 AM
Re: Removing dead code and unused functions Dan Henry C++ 0 06-20-2005 11:06 PM



Advertisments