29
Nov 07

GCC Plugins under my xmas tree?

Over at LWN there is an article on GCC plugins. It touches onto how it would be useful to implement static analysis tools as GCC plugins.

It does not mention that certain optimizations are not feasible without interfacing with the compiler and that there could be a very significant decrease in errors if we the compiler were pluggable with API-specific checks. Wouldn’t it be nice if less developer time had to be spent hunting for common bugs and more implementing awesome new features?

Typically safety is accomplished by executing code in a Virtual Machine that does extra runtime checks with Just In Time compilation to make up for performance losses. This approach has many known performance and footprint disadvantages. It is used by languages like Java and Scheme.

Applications in these languages are slow and/or ship with a JIT compiler to optimize them during their runtime. C++ is compiled ahead of run time and has a reputation for running faster than these dynamic languages. However it also makes it a lot easier to make mistakes such as leak memory and buffer overflows. One can use the C++ OO system to perform extra-runtime checks to avoid some of these issues but that tends to cancel out any performance advantages of writing code in C++.

Another approach is to enforce various safety-related properties through the compiler. Awesome existing languages such as OCaml come with a strict type system that ensures that once code compiles it will run fast and have a lower bug percentages than comparable code in other languages. EcmaScript4 will feature a rocking type system similar to OCaml.

C++ does not have such an awesome typesystem. However, there are many C++ errors that occur frequently and should be detected by the compiler, however long as there is no way to specify Mozilla-specific type system restrictions the compiler has no way of getting that information. Such plugins provide a certain piece of mind that once code complies with whatever rules we set for it, it is more likely to run correctly. Furthermore, some optimizations that we have in mind for Mozilla 2 (such as incremental garbage collection) will be much easier to work with if the compiler flags memory misuse at compile time.

Currently we can use dehydra to scan the codebase, but it would be much more efficient to be able to plug such verification abilities into every developer’s GCC. I sincerely hope that whoever is in charge of the plugin decision at GCC will realize the massive advantage this would give to GCC over other compilers.

ps. Another use for plugins is to enable more aggressive optimizations. Small changes in the sourcecode can affect how conservative the generated code this. A clever plugin could warn whenever gcc cancels an optimization due to misbehaving source.


28
Nov 07

Volume of Refactoring Ahead

In the previous post, I described the simple rewriting case that I am working on at the moment. Someone was quick to point out that the approach wouldn’t work for all methods (XPIDL Arrays were the example). Indeed, anything more complicated than simple getters can’t be rewritten to “Succeeded/Failed” pattern without switching to C++ exceptions. However, in the codebase the size of Mozilla there are several megabytes worth outparam getters to be rewritten.

Currently my wimpy little outparams.js script identifies 100 methods that can be rewritten by outparamdel without any manual intervention. However doing a search for ::Get with a ** parameter yields over 2700 candidates, of which most look like they can be rewritten. Reason for the laughable detection rate is that the detection script currently refuses to flag methods that are defined in XPIDL interface or are implemented by more than one class. Soon the script will make heavier use of the class hierarchy and we will probably change XPIDL to support more efficient getters.

Complete Class Hierarchy

I finally managed to convince Dehydra to serialize the Mozilla class hierarchy into JSON files without running out of virtual memory. This will generate lots of input for refactoring and analysis tools. All kinds of interesting stats can be produced with simple scripts. Generating the index is relatively straightforward. It would be awesome if someone could figure out how to expose this data as a web app. Since there is so much being loaded incrementally, I don’t see how one can keep things simple but use an asynchronous API.

In the coming months, I am looking forward to extending this to be a complete callgraph to find dead code and other fun data.


26
Nov 07

Mozilla 2: Outparamdel

There will be a lot of under-the-hood code changes in Mozilla 2. Our goal is to end up with a simpler, safer and faster codebase.

This is my perspective on the work ahead with respect to outparamdel.

Outparamdel

In the presence of a garbage collector we will be getting rid of stack nsCOMPtr<> usage (using raw pointers instead), but the getter_Addrefs() will still be needed to pass references to heap-allocated nsCOMPtr so they can be assigned to. Eliminating as many outparams as possible will eliminate much getter_Addrefs() footprint/perf/code bloat.

Within the next week I hope to attempt to rewrite all of the auto-detectable outparamdel candidates.

Determining What To Rewrite

outparams.js is a dehydra script for flagging code that can be rewritten to use outparameters. It turned out a bit trickier than I initially expected. Here are the checks required

  1. Check that a function only ever returns 1 failure error code (NS_OK and something else). This enough if a function is not virtual.
  2. Ensure that either a) This is the only implementation of a particular virtual function or b) All other implementations of this function satisfy 1
    Currently I only do a).
  3. Also check that all overloads of this function have the same outparameter type. This is required since C++ (thankfully) doesn’t not allow function overloading by varying the return type.
  4. Checks 1-3 ensure that the function can be rewritten, however one also needs to determine if the return type should be wrapped in getter_Addrefs<>. This can not be deterministically done from looking at the getter. So one has to scan the code for usage of the function to see if the outparam is ever passed getter_Addrefs.
  5. Check that none of the callers are within macros to minimize non-automatic rewriting.

Checks 2 and 3 require the complete class hierachy of Mozilla so I finally made a few more dehydra scripts to produce that. This was on my TODO list for a while and should make a few other interesting analyses possible (my favourite one is finding interfaces which only have 1 implementation to get rid of excessive virtual functions).

Checks 4 and 5 were easiest to implement as warnings in outparamdel.

One should keep in mind transitivity. Once the first outparamdel candidates are rewritten, some of their callers should become flagged for rewriting in the same manner.

Rewriting Code

Here is an example of how code will be simplified.

given a function:

nsresult getFoo(nsIFoo **out);

And usage like:

nsCOMPtr<nsIFoo> bla;
nsresult rv = getFoo(getter_Addrefs(bla));

if ((NS_SUCCEEDED(rv) && bla) {
...
} else {
return rv;
}
nsCOMPtr<nsIFoo> bla2;
return getFoo(getter_Addrefs(bla2));

The function definition will become:

nsIFoo* getFoo();

Before this can be done, several issues come up

  1. It is not clear if the original getFoo() is allowed to always override the value passed to it. This is hard to determine automatically, so we make the assumption that in the general case it is ok.
  2. It isn’t obvious if getFoo() is returns null in the outparam to indicate some non-error condition. This is rare so the parameter shall be annotated. Currently, the plan is to annotate with a NULLABLE_OUTPARAM() macro which would be detectable by dehydra and serve as documentation for the function behavior.

nsCOMPtr<nsIFoo> bla = getFoo(); //after XPCOMGC rewrite the left side will become nsIFoo* bla
if (bla) { // could even merge the above declaration into the if condition
...
} else {
return NS_ERROR;// or NULL if this is another outparamdel candidate
}
nsCOMPtr<nsIFoo> bla2 = getFoo();
return bla2 ? NS_OK : NS_ERROR_SOMETHING; // I'm not sure if outparamdel should use an explicit ternary operator or an inline function to convert new style errors into nsresult

Currently the code is being rewritten in a much uglier way. So this cleaner version will likely be implemented as an optimization pass (probably with a new tool outparamdel-opt?). There several tricks here:

  1. Connect the declaration with initialization of bla and bla2
  2. Detect the error check and replace it with “bla”(or !bla for NS_FAILED).Then realize that bla && bla contains a redundant statement and take it out.
  3. Do something similar to return statements.

Result

This should result in prettier code that compiles quicker and to a smaller, more efficient binary. It will also be more GC-friendly.

C++ Exceptions

Right now outparamdel does rewrites that are useful even if C++ exceptions will not be introduced. There are further code reduction gains possible if above error checks were converted into C++ exceptions, but I am not clear on performance characteristics of exceptions. We would also need to change tamarin exceptions to match C++ ones before any experimentation can be done.


12
Nov 07

Cleaning up my act

I added an “ongoing work” and “tools” sections to the Mozilla 2 page.

The pork suite now has a wiki page.

#mercurial regulars kindly educated me about hg branches. Turned out hgimportsvn tries to map some subversion concepts onto hg branches which causes problems for people checking out pork using never versions of hg. For people googling for this issue: do “hg up trunk ; hg branch -f default; hg commit” to produce a magic empty revision to fix this problem.

If you have tried to compile pork before and gave up in despair, please try again using the pork wiki page for instructions.


02
Nov 07

Garburator works!

A few weeks ago I convinced myself that is possible to rewrite Mozilla to avoid COMPtrs on the stack. Since then I’ve changed my mind a few times and felt like I may not be able to get this rewrite working. However, after three or four false starts, I finally managed to work out a metal model of the stack nsCOMPtr usage. With a combination of automatic blacklisting of tricky code, manual demacroing and lots of help from Benjamin I got the generated 3.2MB patch to compile.

I am sure that there are lots of bugs to be found still, but at least we’ve discovered the pattern that the code follows. I am also sure that there are lots of unpleasant surprises to be discovered and dealt with in the near future.

The bright side is that the result of these rewrites we should get a less buggy codebase that is easier to work on, more efficient and compiles to smaller binaries. My other big wish is to significantly reduce the amount of C++ magic in the codebase.

I am happy that garburator works as it means I can go back to playing outparamdel. Hopefully, once garburator+outparamdel are applied on all possible methods we’ll end up with relatively nice looking C++ code and a healthy performance boost.