I spent much of the weekend working on my automatic stack-ripping program. My eventual goal is to make it possible for people to write server code as plain old C functions, complete with local variables and loops and blocking behavior, but then produce code that’s suitable for a staged event-handling infrastructure instead of relying on a less efficient massively-multithreaded infrastructure. The tool’s job, therefore, is to take the source for a function with annotations to indicate where it blocks, and then generate source for several functions connected by a context structure to do the same job. I’ve figured out how to do this in the abstract, and now I’ve moved on to actual implementation.

The key to the implementation is the -fdump-translation-unit argument to gcc. With this argument, the compiler does all of the lexical and syntactic analysis and then dumps the resulting parse tree into a file with a .tu suffix. This frees me of the need to write a complete gcc-compatible parser and lexer just so I could get started. Yay! The format of the .tu file is not quite ideal for my purposes, but it’s usable. One thing I find slightly amusing and slightly disgusting is that the file’s grammar is ambiguous with respect to attribute names and values that contain spaces, which gcc will generate internally in several cases. So far the ambiguity hasn’t posed any insurmountable problems in extracting the information I want, but I had sort of thought that compiler guys might be able to come up with a clearer output format. I guess not. So far the tool can:

  1. Find a function in the .tu file, given its name.
  2. Generate an internal statement-level parse tree with most of the extraneous cruft removed (the gcc tree often uses several more layers of indirection than I need). It handles all statement types except goto.
  3. Recognize variable declarations, including types. It can understand anything with a typedef plus all kinds of integers, pointers/arrays, and structs/unions. It does not handle function types without a typedef.
  4. Generate something akin to the original function in a consistent format as output.

The next few steps are:

  1. “Flatten” the variable scope down to one level for the entire function. This is mostly a matter of detecting variables declared with the same name in nested scopes, and renaming as necessary to resolve the conflict when they’re all moved into one scope.
  2. Generate a context-structure declaration to hold all of the local variables in the original function.
  3. Convert the parse tree into a more general kind of control-flow graph, with separate nodes e.g. for the pieces of a for-loop and more explicit successor-node information.
  4. Find the points where the original function blocks. In the simplest case this will be indicated by calls to a block() pseudo-function, but I might provide other constructs as well. Whatever I do in this area will have to be implementable as pseudo-functions, though, because otherwise I wouldn’t be able to rely on gcc to do all of the parsing for me.
  5. Split the graph into multiple pieces around the blocking points.
  6. Generate a new function from each subgraph, replacing local-variable references with context-structure member references.

One optimization that I’d like to add in a future version would be to “promote” local variables into the context structure only if they’re used by more than one sub-function. Otherwise I could just leave them local, which would both reduce memory usage and enable better optimization of the output code. I have plenty to do before I start to worry about that, though. As I said, I’ve figured out how to do all of this in the abstract, but the graph-splitting code is still going to be complex and tedious. Let’s see how much energy I have left when I’m done with that.