Main menu:

Site search



Making Treehydra do useful tricks

Taras’ last blog post ended with a comment about “making [Treehydra] do useful tricks”, which oddly enough, is exactly what I’ve been working on, and I’ve finally made enough progress to blog about it. I’ve been alternating between implementing a Treehydra Javascript analysis library and adding needed features to Treehydra.

Just today, I managed to do an intraprocedural live variable analysis, which is one of the simplest program analyses, on every file in mozilla-central. (Live variable analysis determines the set of variables that may be read in the future at every point in a function. It’s commonly used in optimization to save storage for unused variables, but I use it to make checkers “forget” information about unused variables.) Here’s a visualization of the results for Firefox’s main() function in a Linux build: the set of live variables is listed at the bottom of each basic block.

It took 25-30 minutes to run on all of Mozilla (as preprocessed C++), but I know a lot of that is simply GCC compile time, and I think a fair fraction of the rest was spent generating the visualizations, which most analyses won’t do. I guess I need to investigate how to time JS execution internally.

My Javascript analysis library is about 900 lines of code, with modules for Treehydra utilities, GCC data access, GCC value printing, data structures needed for analysis, backward data-flow analysis. I hope these will be reused for other analyses–there are fewer than 100 lines of code specific to liveness analysis. The code is available here.

The next step will be to finish the outparam analysis. Hopefully, it won’t be too hard. The big pieces are:

  • An analysis to determine which variables may reach the return statement of the function (the technique is similar to the liveness analysis).
  • Port over my ESP analysis framework from Python.
  • Implement the outparam checker in the ESP framework.

I prototyped all of it in Python, so I know the algorithms work, and I’ve ported much of it over to Treehydra/JS for the liveness demo, so I know it codes up nicely there as well. I’m sure there will be glitches to fix, and I’m sure I made some mistakes in designing my Javascript framework, but I’ll just have to see how it goes.

Finally, I have to mention that I’ve upgraded my Javascript skills quite a bit in the process of doing this (it’s the most complex JS program I’ve written, and I’ve also been using JSAPI), and it’s all thanks to the MDC Javascript Guide, which has been an excellent resource.