Ehren's Blog

The Dead

Posted in Uncategorized by ehren on March 24, 2012

that region where dwell the vast hosts of the dead

Conservatively detecting unused functions in a large codebase requires more information than can be gleamed from a simplistic observation of compilation (using GCC or clang, for example). Functions called by ASM alone are one problem. Functions called only via dlsym are another. These are not insurmountable problems (ASM can be parsed; dlsym accepts a constant identifier).

In addition, mozilla-central contains a large amount of third party code. Removing unused functions in these libraries is at odds with merging upstream changes. There are also large numbers of functions used on one platform (or build setting) but not another. Propagating the appropriate #ifdefs is the solution here but it’s a large task.

I’d like to offer one approach with an eye towards identifying the easiest candidates for removal. This is a combination of some of my existing work, by now admittedly crusty, based on Dehydra and Callgraph, but with a new (too me) simple insight about how to group the members of the subgraph of unused functions: partition them by the “is called by or is a (dead) caller of” relation.

This has the effect that if a false positive is in the results, all functions declared unused because they’ve been transitively called by the false positive get grouped with that false positive.

The output of a tool employing the above is here (source here).

Some notes on the results

The largest partition consists of 541 nodes (warning: giant file). It is the result of a single false positive, legacy_Open, called only via PR_FindFunctionSymbol, a dlsym wrapper. I have attempted to mitigate these situations by colouring green those functions having __attribute__(visibility(“hidden”)) (visibility specified in the flags passed to GCC is also detected). The count of functions having this visibility, but not transitively called by a function that doesn’t, is listed in the ‘Transitively Hidden’ column. This info is useless here, however, because the function is exported using a linker map.

It would be interesting to determine if the visibility is always correctly applied; I seem to remember seeing warnings related to the attribute in the past. There may be technical reasons why internal C++ must be visible but, in any case, its visibility does not preclude its removal. Here’s proof. (Also, I calculate that only 17.4% of mozilla-central has hidden visibility).

Moving on, the next largest partition has 507 nodes. They are all in the pulled-in chromium sources however. Apparently, it is genuinely dead because the minimum ranked note, evrpc_register_rpc, is only used in a test case (via a macro).

xptcstubs’ PrepareAndDispatch is an example of a false positive due to ASM (graph here).

Anyhow, I will leave the reader to examine the rest which gets more interesting once you skip the mega partitions.

Potential improvements

The non-callgraph portion of the tool is really just a couple of hacky scripts. The same thing could be implemented against the DXR callgraph (it would need to determine the targets of function pointers in some regard).

On this topic of handling function pointers, note that the call graph of this tool uses the naive address-taken approach. However, it has been ‘optimized’ for the dead code problem by treating the taking of a function’s address inside the scope of a function as a normal call. This makes the call graph useless for practically anything else but I plan on adding an addressTaker/addressTakee table in the future.

In fact, such an addition would make it easier to implement a simple type-based alias analysis where functions noted to have their address taken at global or local scope are matched against pointers using their return type and the type of their parameters (they’d then be pruned from the address taken list). I’m not sure if there would be problems with this beyond unsafe casting.

(More precise attempts at function pointer may-alias analysis would first require an interprocedural control flow graph but that is the simplest step. I’m somewhat tempted to build an ICFG using a hackish framework where visiting a function body = recompiling a .ii file. Were one to go about this, doing some basic form of interprocedural constant propagation and seeing what unused blocks fall out might be more fruitful.)

In any case, I do have some numbers regarding how many more functions one could expect to declare dead by improving alias information. At one point I had made a change that affected the creation of SQL statements building the graph. By mistake I had left out the generation of SQL for all address taking, regardless of scope. This resulted in the tool flagging just over 50000 functions as dead. Given that it currently flags 11479 out of 187081 (6% — seems low), one might expect to find another 2300 (6% of 39000) or so (these numbers include declarations, definitions, gcc builtins and the like). Although come to think of it, that’s a dubious estimate because function scope address taking is already handled in an, albeit, imprecise manner and the number of functions whose address is taken at file scope is only 5949 (using the 6% figure, only 357 more would be found).

Finally, another area of unnecessary conservatism is that, as you’ll note in graphs such as this one, there is an edge going both ways from a method declared in a base class to its override in a derived class (for example, there is an edge from nsSVGAElement::GetLinkState() to Link::GetLinkState() because of a direct function call, but there are also two edges linking nsSVGAElement::GetLinkState() and nsIContent::GetLinkState() because of their inheritance relationship). The edge really only needs to go from the base to the derived though. Once this is changed, the tool will presumably flag instances where a method overrides a base class method but all calls go through the derived implementation.


9 Responses

Subscribe to comments with RSS.

  1. Taras Glek said, on March 24, 2012 at 3:06 pm

    Note we aim to add a dynamic part to this analysis. We plan to instrument firefox to do code-coverage via telemetry… Then we can flag functions that are mentioned but not ever run as “probably dead” for manual inspection to widen our catchment area.

  2. ehren said, on March 24, 2012 at 3:12 pm

    hmm… clever

  3. Taras Glek said, on March 24, 2012 at 3:18 pm

    Also, are you back for good or gonna disappear for a few more years? 🙂

  4. ehren said, on March 24, 2012 at 3:25 pm

    Well… I have a couple of things I’ve been tinkering with. Looking at bug 487075 I realize the ESP to 4.5 conversion was not done properly. Can’t really make any promises at this exact moment though.

    • Taras Glek said, on March 24, 2012 at 3:39 pm

      Lets try to base any revisions on DXR, hydras are fairly dead at this point 😦

      • ehren said, on March 24, 2012 at 3:45 pm

        For more complex static analysis, the best option would probably be to serialize the results of running a CFG plugin… or look into plugging into the analyzer.

  5. Taras Glek said, on March 24, 2012 at 3:40 pm

    On the upside, it would be cool to visually indicate dead code in DXR 🙂

    • ehren said, on March 24, 2012 at 3:48 pm

      You’d still need to partition the unused stuff at least when targeting ppl actively looking for dead code.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: