Thursday, January 14, 2010

Semantic analysis woes

There's one part of my compiler that I am not particularly happy with, which is the analysis queue. Tart, like many languages, allows definitions to be in any order in the source file. Moreover, because it supports (limited) type inference, it means that some declarations need to be evaluated before others can be.

The analysis of a data type consists of many different passes over the structure. The most complex of these is ClassAnalyzer, which performs the following tasks:
  • Populate the symbol table for class members.
  • Resolve base classes.
  • Analyze and apply annotations.
  • Analyze template parameters.
  • Analyze constructors.
  • Analyze conversion methods.
  • Analyze member fields and properties.
  • Analyze member types.
  • Analyze methods.
  • Check for name conflicts.
  • Figure out which methods are overloads of base class methods and build overloading tables.
  • Add any externally visible definitions to the module's symbol table.
Some of these tasks have to be completed before certain operations can occur. For example, a call to create a new instance cannot be analyzed until the constructors for that class have been analyzed, since we need to be able to examine the types of the constructors to do overload resolution.

Worse, some types of analysis are cyclical - you can't finish A until you've analyzed B, and you can't finish B until you've analyzed A. My solution is to allow symbols to be in a partially analyzed state - while analyzing A, you can suspend what you are doing and go work on B, then return and finish A.

Now, all of this takes place during the compiler's second phase (analysis). The compiler has 3 phases: Parsing, Analysis and Code Generation. Phase 2 must be complete before Phase 3 starts - in fact, there's a check to make sure that no code attempts to add additional analysis work once phase 3 has started.

In phase 2, we keep track of the work we need to do via a queue. When we wish to analyze a class, we place it on the queue. If during analysis of that class, we discover other symbols that need to be analyzed, we have two options: If we need to know the result of the analysis right away, we can dive in and do it right there (we can pass in a set of flags that says what information we're looking for, so that it doesn't analyze more than is needed.) If, on the other hand, we don't need the answer right away, but we do know that we'll need the answer in phase 3, we can enqueue the symbol so that it will be processed eventually. Phase 2 ends when the queue is empty.

There's another queue which is used in Phase 3, but this queue is actually built in phase 2 and never modified in phase 3. This queue is the queue of all externally visible symbols which were generated in phase 2. Phase 3 walks the entire graph of all of the symbols on the queue and generates code for them. However, the entries are not always processed strictly in queue order.

Take for example a class on the queue. We need to build a vtable for the class, so we need to generate an exportable symbol for every instance method in the class. Even though the methods may be on the queue, we actually need them right now so we can get the pointer to stick into the vtable. Later, when the queue gets around to generating that function, it will notice that it has already been generated, and therefore skip it.

The relationship between symbols is very complicated, and there are about a dozen ways that one declaration can refer to another. For example, say I have a method A, which has a parameter of type B. The reflection data for parameter B consists of an object of type C, which contains an array of type D holding objects of type E, which have a superclass of type F. This superclass has a field whose type is G, which in turn has a class annotation of type H. The system is complex enough that reasoning about it is hard.

In order to prevent the compiler from compiling the entire world when you give it a single module to compile, phase 2 tries to do as little work as possible. Obviously, any type which is declared in the module being compiled must be fully analyzed, but what about imported symbols? In many cases we don't need to know everything about the imported symbol - thus, to return A as a return value of a function, you don't need information about how to call A's methods or how to convert A into B.

Template instantiations make this somewhat more complex, because even though the original template definition maybe external, the instantiated copy belongs to the module that invoked it. There's a special "Synthetic" bit which is set on any type or definition which was generated by the compiler, which tells the analyzer that this type must be fully analyzed.

So what exactly is the problem with this? Because reasoning about the system is so hard, I often make mistakes. The most common mistake is over-analyzing or under-analyzing a definition. If I over-analyze, it means that the compiler has to do more work than it needs to, and is therefore slower. If I under-analyze in phase 2, it means that some definitions will leak through to phase 3 without being sufficiently analyzed. This causes phase 3 to throw an assertion because the data it is looking for is not there.

A typical example: Inside class A there is a method B that has a parameter whose type is an enumeration class C. Because this information is reflected, we need to import the class tart.reflect.EnumType to generate a description of the enumeration. This involves the code generator creating a static instance of EnumType, so we need to analyze the member fields of EnumType. So we get to Phase 3, and the code generator complains that tart.reflect.EnumType has not had the "MemberFields" pass run on it (each type has a bitfield of what passes have been run.) So I have to track down where the missing link is.

I have run into so many bugs in this system that I feel like I am playing dependency whack-a-mole. But I can't think of any algorithm that is easier to reason about that will satisfy all of my requirements.

--
-- Talin

No comments:

Post a Comment