Ehren's Blog

A Treehydra + GCC plugin combo for alwayszero functions

Posted in Seneca by ehren on December 4, 2009

Yesterday (err technically two days ago), I was able to cleanly add my user(("alwayszero")) attribute to about 1780 of the ~6300 functions I have identified as alwayszero within mozilla-central. I was even able to get through a build using my pluginified GCC 4.5. Further, by adding a bit of debug info right into the plugin I was able to count the number of times the optimization was executed ie every time the return value of a call to an alwayszero function is stored. Unfortunately, the results were somewhat disappointing in that the optimization was only executed 1300 times. This doesn’t take into account any additional constant propagation that resulted from these optimizations but, by comparing the sizes of the .so files in the object directory to the .so files of an equivalent non-plugin enabled GCC 4.5 build, there was no code size advantage to be had. In fact a handful of the files increased by 5 or so bytes!

I suppose it’s premature to derive any conclusions at this point, though, with less that a third of the functions patched with my attribute.

Anyway, the next step in completing the patching process was to clean up my analysis to:
1) remove all of the outparams.js code that’s unnecessary for determining the final return value
2) ensure that the attribute has not been misapplied (this will result in very bad/interesting things happening at runtime)

During this step, I somehow introduced some very bizarre errors into my Treehydra script that I’ve only now been able to resolve. At some point I’d like to examine the source of these errors but at the moment there are bigger issues.

Perhaps foolishly, I’ve now placed all of my code into bugzilla. The treehydra analysis certainly has a few issues, since, for one thing, if it’s placed into trunk as is (with FIND_NEW_FUNCTIONS = true) static-checking builds will contain an overwhelming amount of alwayszero identifying output. However, at this point, I think that if there are any major issues left (other than writing a Pork patch) they can probably best be discovered in the bug.

One thing I didn’t put in bugzilla was the insane technique I’ve used to identify and patch as many alwayszero functions as possible. For the non-squeamish, I’ll describe the process now.

I first create a typescript of a build running my analysis script. It spits out output like this:

alwayszero function found! location: /home/ehren/mozilla-central/xpcom/glue/nsCategoryCache.cpp:126:51 name: Observe class: /home/ehren/mozilla-central/xpcom/glue/nsCategoryCache.h:65:59 overloadCount: 0 args: nsCategoryObserver*, nsISupports*, const char*, const PRUnichar*

Next I grep for all of these lines removing any duplicates:
grep 'alwayszero function found!' typescript | sort | uniq > uniq.txt

Rather than patch my main mozilla-central repository, I typically create a copy and then rename all the directories in this file. For example with vim:

Overloaded methods are a big headache for the techniques I’m using because, as you’ll see, the matches I’m making are only by function name. So, after identifying them in my treehydra script, I simply remove them (there are only about 130 anyway):

grep 'overrideCount: 0' uniq.txt > no-overrides.txt

Now it’s time for the first shell script. I use the following to print out the (possible) location of the declaration of the function within its class:

while read line ; do
  name=$(echo $line | cut -d' ' -f 7)
  path=$(echo $line | cut -d' ' -f 5)
  classpath=$(echo $line | cut -d' ' -f 9)
  lineno=$(echo $classpath | cut -d':' -f 2)
  classpath=$(echo $classpath | cut -d':' -f 1) # strip off line info
  # start at the beginning of the class and returns the first line containing the 
  # function's name. (actually it starts at line 1 but the d actions skips these lines)
  nameinfo=$(sed -n "1,$lineno d; /$name/{p;=;q;}" $classpath)
  echo $name path: $path classpath: $classpath nameinfo: $nameinfo
done < $1

I then run it like so:

./ no-overrides.txt > found-decls.txt

This output will contain a tonne of blank nameinfo entries because most of the functions I’ve found are behind macros. There are also just lots of phony results, mainly because my search is extremely imprecise. To cut down on the junk, therefore, I do this:

grep '\(virtual\)\|\(NS_IMETHOD \)' found-decls.txt > found-decls-trimmed.txt

All of this will result in output like so:

GetRoleInternal path: /home/ehren/mozilla-central-Copy/accessible/src/html/nsHTMLSelectAccessible.cpp:963:58 classpath: /home/ehren/mozilla-central-Copy/accessible/src/html/nsHTMLSelectAccessible.h nameinfo: virtual nsresult GetRoleInternal(PRUint32 *aRole); 235

Now we’re ready for the second shell script:

while read line ; do
  fnname=$(echo $line | cut -d' ' -f 1)
  classpath=$(echo $line | cut -d' ' -f 5)
  lineno=$(echo $line | sed -n "s/.*[^0-9]\([0-9]\+\)$/\1/p") # thanks chris!
  # make sure we haven't already applied the attribute
  match=$(sed -n "$lineno s/NS_ALWAYSZERO/&/p" $classpath)
  if [ "$match" == "" ]
    # in-place replace
    sed -in "$lineno s/ $fnname/ NS_ALWAYSZERO&/" $classpath
done < $1

Running it will result in a patched mozilla-central-Copy:

./ found-decls-trimmed.txt

(All of this could be done with one script but there are certain advantages to breaking it up)

Earlier, as I mentioned, I did run such a patched build with GCC 4.5 using my optimization plugin. However, after finalizing my treehydra analysis, I know that a number of the functions patched should not have been. The fact that I encountered no compile time errors (naturally I wouldn’t) is a reminder of the danger of this plugin without a complementary static analysis. I still have my crazy unsafe build which I am tempted to try in the CDOT tomorrow. Could be a new FOX special: “when functions return zero”.

Now that I recently enabled a ‘safety checking’ feature in the analysis, where an error raised if a function is inappropriately tagged as alwayszero, the above is not an issue though. In fact, I am more confident in my analysis now that it has identified a number of misapplied attributes than when it simply was only identifying zero-return functions. For those interested, here’s a ramshackle list of functions which my shellscript’s inappropriately patched. Notice that there’s only one syntax error. Note that even though there are only 22 of them, I had a miserable time manually fix them all/waiting for the compiler to identify them!

To wrap this up, I should mention the results of running a final static-checking build after all the patching had been finalized. As you can see here, there are only 4514 left to go. Woohoo!


One Response

Subscribe to comments with RSS.

  1. My First FUDCon said, on December 6, 2009 at 12:10 pm

    […] I was also able to demonstrate some ways in which Mozilla has done automatic rewrites, including Ehren’s work to optimize away functions that always return zero.¬† Chris also joined me in the presentation, and […]

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: