Finally making some AST progress

Posted on June 30, 2005 by Chris Lumens in , .

I’ve been stuck on mitchell (my compiler project) for several months now. In particular, I’ve been working on abstract syntax tree simplification in preparation for translation to IR but it’s been really hard and not interesting enough to get motivated to work on. But it looks like the several hours I put into it tonight might actually get me moving again.

The first thing I did was work on free value analysis. I need to do this so I can convert nested functions into closures and then lift them up to module-level scope. Free values are all the ones referenced in a function but are defined outside of its scope. Free value analysis finds all the free values and binds them in the function’s scope by appending them to the list of function parameters. I’d essentially been stuck trying to get the information I needed to determine whether or not an identifier needed to be checked for freeness. I was finally struck by the realization that I can just decorate the identifier AST nodes to tell me their purpose and got moving on that.

This led me to the problem that function arguments are in a scope outside the decl-expr making up the body of the function, so using the function arguments always results in unbound value references. Luckily I was able to think it out and remember that I’d guaranteed function bodies are always decl-exprs. I can use that fact to merge their symbol table references together in the AST nodes.

Wham, making good progress on free value analysis. I need to come up with a plan of attack for testing this stuff, though. I feel like my quality control has slipped ever since I got into AST creation because my test suite isn’t designed to handle it. Lots of work to do here. Finally, I started working on something I’d been thinking about for a while now - a generic framework for AST traversals. All my simplification passes duplicate 85% of the tree walking functions and then have their own handful of custom versions for the remainder. I spent a couple hours cranking out a generic system involving lots of function pointers and ripping out tons of old code. It’s also given me a chance to go back and correct some of my horrible ideas - like the mess that is decl-expr simplification.

Exciting times on the mitchell front again. Hopefully I can get lambda lifting done soon, be done with AST simplification, and get another test release out there. I might get a little sidetracked developing an AST test suite though to help me feel better about the state of that (rather complex) body of code.