Wednesday, February 16, 2011

LLBrowse

There hasn't been any Tart updates in a while, because I've been working on a debugging tool to help me locate problems in my compiler's output. The tool is called LLBrowse, and it's a graphical browser for LLVM module files. Here's a link to the docs and some screenshots:


LLBrowse allows you to examine all of the contents of a module - functions, global variables, type definitions, and so on. It also allows you to navigate through all of the DWARF debugging information for those items. This has already led me to discover a bug in my compiler.

Wednesday, February 2, 2011

More on garbage collection

I have to say, one requirement of implementing a garbage collector is that it really forces you to take a holistic view of your code generation process. You have to consider every possible object reference that could be generated, because if you miss one, the garbage collector will cheerfully free your object before you're done with it.

A discussion on the llvm-dev mailing list has yielded some valuable new information: LLVM metadata nodes can refer to global variables. LLVM supports the concept of arbitrary metadata associated with a module, and these metadata can contain arbitrary language-specific information which is ignored by the various LLVM optimization passes. Moreover, if a value gets eliminated during an optimization pass, the pointer in the metadata node will automatically get changed to NULL.

This is exactly what I need - I want the optimizer to be able to eliminate any garbage collection roots that are never used, and then after it's done, I want to take the roots that are left over and string them together into a table.

Monday, January 31, 2011

Finding Static Roots

I'm getting nearer to having a working garbage collector implementation. The part that I worked on this weekend was static roots - that is, pointers embedded in static data structures that are emitted by the compiler. It turns out that I had a lot of cleaning up to do in order to prepare for this.

The general plan is to have the compiler identify the data structures that are static roots, and then have the linker use that information to generate a global table of all roots. The address of this table is then passed to the garbage collector at initialization time. At the beginning of each collection, the garbage collector will trace all of the static roots, so that any object referred to will be considered live.

Each static root contains two pieces of information: A pointer to the static data structure to be traced, and a pointer to the trace table for that data structure. The reason we need the trace table is that not all data types in Tart have embedded type information, for some data types the information about pointer offsets has to be supplied externally.

Tart's code generator has a getTraceTable(Type * type) function which takes a type, and returns the trace table for that type - or NULL if that type has no traceable references embedded in it. Thus, each time the compiler emits a static data structure, it gets the trace table, and if non-NULL, adds it to the list of roots for that module.

Actually, there's an additional optimization that can be applied: If a static data structure is immutable, then there's no need to trace it, since the only thing it can point to are other static data structures, which will themselves be static roots.

The next question is how to communicate the information about static roots from the compiler to the linker. The simple solution would be to simply create an array of pointers to those roots, however this solution has a problem: By referring to global variables directly, you prevent the linker from removing dead globals. I asked about this problem on the llvm-dev mailing list, and the suggestion I got was to instead create a list containing the names of the global variables. The idea is that you would run the dead global elimination pass, and then use the list of names to see which roots remained.

Of course, for this to work, every static root has to have a name, and that name has to be globally unique after the modules have all been combined into one large module. Normally LLVM deals with name collisions either by merging or renaming the symbol, depending on what that symbol's linkage type is, but we can't allow these particular symbols to be renamed, since the name would no longer match the string. So much of the work that I did over the weekend was making sure that each static root had a proper name.

One issue that I haven't quite worked out yet: How to deal with the linker's dead global elimination pass eliminating trace tables. We only want to keep the trace tables for the globals that didn't get eliminated during the dead global elimination pass. Since the globals themselves don't point to their trace tables, we need a way to prevent the trace tables from being prematurely removed, but afterwards we only want to keep the tables for globals that didn't get eliminated.

One other thing I need to figure out is how to handle roots that are in read-only memory. In LLVM, when you create a global variable, there's a boolean parameter that you can pass in that specifies whether this global is a constant. If set to true, it puts the global in read-only memory, so that any attempt to mutate it will generate a fault. I normally set this flag to true for any static global that has no mutable fields.

However, each object has a hidden integer field called __gcstate which is intended for use by the garbage collector. The meaning of this field is unspecified, it's up to the various garbage collector implementations to decide what data they need to store on a per-object basis. A typical example might be a "marked" bit to indicate that the object has been traced. However, garbage collectors will need some way to detect objects in read-only memory and refrain from writing to the __gcstate field of those objects. Probably the simplest solution is to assume that all objects whose address is outside of the collector's memory pool should not be modified. That means that we'll need to keep a record of which objects have been traced in some sort of auxiliary data structure.

(This makes me wonder if it's even worth having a __gcstate field, since the collector can easily create any auxiliary data fields it wants by prefix them to the beginning of the object -- although there are some alignment benefits to having the field be within the object, especially on 32-bit architectures.)

Another possibility is to have the __gcstate of all readonly objects always be zero, and the __gcstate of any objects allocated by the garbage collector be non-zero.

Tuesday, January 25, 2011

Executable size measurements

I've been working on improving my Python script that takes the output of 'nm' and parses it to get a sense of how much space in the executable is being taken up by various data structures output by the compiler. Here's what the output looks like:

Total size:  155824

Category                          Count   Size Average Percent
================================ ====== ====== ======= =======
Reflection                           --  39088      --    25.1
  Composite types                   128  22528     176    14.5
  Enum types                          1     64      64     0.0
  Other types                         9    576      64     0.4
  Type references                     2     80      40     0.1
  Type lists                         45   1616      35     1.0
  Invokers                            8   6240     780     4.0
  Name tables (head)                 42   2880      68     1.8
  Name tables (simple)               41   3591      87     2.3
  Name tables (compound)             29    793      27     0.5
  Field offsets                      39    720      18     0.5

TIB                                  --  12384      --     7.9
  TypeInfoBlocks                    128   7040      55     4.5
  Base class lists                   56   1856      33     1.2
  IDispatch functions                91   3488      38     2.2

Standard Library                     --  94492      --    60.6
  tart.core                         209  15944      76    10.2
  tart.collections                  214  40016     186    25.7
  tart.gc                            16   1012      63     0.6
  tart.io                             0      0       0     0.0
  tart.reflect                      165  30096     182    19.3
  tart.testing                       10   2896     289     1.9
  tart.text                          22   4528     205     2.9

Classes                              --  57976      --    37.2
  tart.core.Array                   177  13928      78     8.9
  tart.core.String                   21   5152     245     3.3
  tart.collections.ArrayList         86  22944     266    14.7
  tart.collections.ImmutableList     69  14672     212     9.4
  tart.collections.List              21   1280      60     0.8

Static strings                      151  10728      71     6.9
Trace tables                         39    736      18     0.5

You'll note that in some cases the percentages add up to more than 100%. That's because not all of the categories are exclusive - for example, a given symbol can be in both the "Reflection" and "Standard Library" subheadings.

Also note that the actual size of the binary file being analyzed was 332049 bytes, not 155824 as is claimed above. The 155824 number only includes symbols that were generated by the Tart compiler.

A few surprising things:
  • CompositeType structures, which serve the function of metaclasses, take up 14% of the space. I have an idea how to make that smaller, however.
  • Invoker functions, which are responsible for boxing and unboxing of parameters when calling a method via reflection, take up 4% of the space. I'm not sure these can be shrunk significantly.
  • ArrayList is much bigger than Array. Note that for templated classes such as Array and ArrayList, the size includes all template expansions for different type parameters.

Type inference and type constraints

Some notes about the way Tart's type inference solver works.

The type solver takes as its input an expression tree, and returns an updated expression tree. The input tree has ambiguous or unspecified types for the expression nodes in the tree, while the output tree has fully-specified types for every expression node. If the input tree is already fully specified, or the solver fails to find a solution, then the original tree is returned unchanged.

The first phase is the "gather constraints" pass. The solver walks the entire tree looking for "constraint sites", that is, nodes in the tree that implicitly constrain the types of their child or parent nodes. The simplest example is a call to a non-overloaded function: Each sub-tree representing an argument is constrained to be the same type as the corresponding function parameter.

In more complex cases, a function may have multiple overloads, or may be a template where the type of the argument is a template parameter. For cases like this, we create a "type constraint object", which is an subclass of Type. A type constraint represents all of the possible types that could exist at that location.

For example, suppose we call "foo(a, b)", and there are two overloads of foo: "foo(int, int)" and "foo(float, float)". Since we don't know yet whether parameter 'a' is an int or a float, we instead assign to 'a' a type constraint representing the set {int, float}.

However, a type constraint is not just a passive collection of types. The constraint remains connected to the original site - so for example, if we decide later to discard one of the two overloads of 'foo', the constraint will automatically update itself to reflect the new set of types that could exist at that point.

Type constraints have many of the same methods that types do. For example, types have a method called canConvert(), which attempts to convert an expression to that type, and returns an integer indicating the compatibility level for that conversion - whether it is possible, whether it would cause a compiler warning, etc. For type constraints, calling canConvert() simply calls canConvert() to each of the types in the set, and returns the worst compatibility level found. Similarly, type constraints have isSubclass(), includes(), isEqual() and other type comparison methods.

There are several different kinds of type constraints. The three most important are:
  • "parameter-of": Given a call site, return all of the possible types for the Nth parameter of the function being called.
  • "result-of": Given a call site, return all of the possible types for the return value of the function being called.
  • "type-parameter-of": Given a set of types, some of which may be parameterized types, return the set of their type parameters. So for the input set {Address[int], Address[float]}, it returns the set {int, float}.
Once the type constraints are in place, the solver starts the next phase, which is unification. This looks for any unbound template parameters in the expression, and binds them to the type of the corresponding sub-node. So if the template function foo(%T) is called with 'int', it binds %T=int. In many cases, the template parameter will be bound to a type constraint.

After unification comes pruning. This is essentially an optimization problem: For each call site, we want to reduce the number of choices available, but only in a way that increases the total compatibility ranking for the entire expression.

There are three pruning stages. Each stage makes use of a backtracking "cull" function. The "cull" function eliminates from a call site one or more choices (i.e. overloaded methods) for that site, but does it in a way that can be backtracked. (It basically just saves an integer backtracking level with each choice.)
  • Cull by ranking: We cull all methods that have a conversion compatibility level less than some threshold. So for example, we remove from consideration all choices that would produce a compiler warning.
  • Cull by specificity: For any given site, we compare the choices, and if one choice is strictly more general than another, we eliminate the more general one. So given foo(String) and foo(Object), both of which have the same compatibility ranking, we eliminate foo(Object) from consideration.
  • Cull by elimination. If neither of the two culling phases produces a solution, we do a brute force search over all possible permutations.
In each culling phase, we keep track of whether the particular combination of cullings is overconstrained or underconstrained. If it's overconstrained (meaning that there are one or more sites with no choices left), then we backtrack. If the solution is underconstrained, meaning that there are some sites with more than one choice remaining, then we proceed to the next phase and tighten the constraints even further.

The solver finishes when there is only one choice remaning at each constraint site.

Monday, January 24, 2011

Tart status update

I got a lot of Tart-related work done over the weekend, and am very close to having a simple garbage collector working.

One new feature is the ability to create objects using a custom allocator. The garbage collector needs this, because it requires some objects to be created before it has finished initializing. These objects are allocated in "permanent memory" outside of the region of memory that the collector manages.

Since Tart doesn't have a 'new' keyword, we can't use the C++ syntax "new(allocator) Type(args...)". Instead, the type's Type object has a method, 'create', which takes an allocator as an optional argument. There are currently two allocators, the "default" allocator, which just calls GC_alloc(), and the "malloc" allocator which calls malloc(). Allocating an object via malloc() looks like this:

let obj = typecast[MyClass](CompositeType.of(MyClass).create(MallocAllocator.INSTANCE));

A bit wordy, but that's fine, because this should only be used rarely. It's also slower than the normal object creation pattern, but again that should be fine.

One question that I've been mulling over is Tart's support of pointers. In the ideal case, a user of Tart should never have to deal with pointers directly, everything should be done in terms of object references (which are essentially pointers underneath, but have a lot of special semantics known to the compiler.) However, because a lot of Tart's runtime is written in Tart, there is a large body of Tart code that does in fact use pointers directly.

Because I don't want to encourage people to use pointers, the syntax for declaring and using a pointer is deliberately somewhat verbose:

import tart.core.Memory.Address;

var p:Address[ubyte];

Similarly, there's no special syntax for dereferencing a pointer - instead you say something like "Memory.deref(ptr) = value" or "ptr[0] = value".

However, because I've been working with pointers so much recently, I've slowly been giving way and adding operator support for pointers - so now you can say "ptr += 3" instead of "p = Memory.addressOf(p[3])".

Yesterday I added comparison operators for pointers - <, <=, >, >=, and so forth. Unfortunately, this confused the type solver, and I'm still tracking that one down. Aside from that, adding operator support for pointers is fairly trivial. It would take me all of 10 minutes to add "type^" or "type*" as a synonym for "Address[type]". The question is, should I do it?

Sunday, January 16, 2011

Anonymous classes

In my day-to-day work using Java, one of the most frequently used and useful features is anonymous inner classes. Here's a code snippet showing a typical use case, in this case an asynchronous load of a resource:

final FormattingLogger logger = getLogger();
resources.loadImageAsync("texture.png", new AsyncCallback<Image>() {
  @Override
  void onSuccess(ImageResource img) {
    // do something with img
  }

  @Override
  void onFailure(Throwable error) {
    logger.logError("Resource load failed: " + error);
  }
}

What this does is create an unnamed subclass of AsyncCallback<Image>. AsyncCallback in this case is a generic interface that has two methods: onSuccess and onFailure.

Since Java doesn't support closure functions (although apparently the next version of Java will), anonymous inner classes are used instead. They also have one obvious advantage over a function pointer, which is the ability to support multiple methods, such as the onSuccess & onFailure case in the example above.

Like a closure, the anonymous inner class has access to the environment in which it is defined, as seen in the use of 'logger' above. Note that Java doesn't support true capturing of variables, however - any variable referenced by the inner class must be declared 'final'. (The reason is that Java makes a copy of the variable, rather than giving shared access - so making it immutable reduces the confusion that would result if you tried to modify the variable.)

Although the example doesn't show it, you can also pass constructor parameters to the anonymous class in the parentheses following the class name. Of course, you would also need to declare a constructor with the appropriate type signature.

Now, there's no reason why you couldn't create a named subclass of AsyncCallback to do exactly the same thing. It's just more typing, and it also requires the subclass to be defined elsewhere, outside of the place where it is used.

It seems logical that we would want a similar feature in Tart. However, the above syntax won't work, because Tart doesn't have the "new" keyword. Simply typing "classname() { ... }" won't work either, because the syntax is ambiguous - as in the case "if classname() { ... }". So we'll need to come up with some other syntax.

Also, I suspect that anonymous classes, while still useful, will be used somewhat less frequently in Tart than in Java, due to the existence of closures. Assuming that both closures and anonymous classes are available, a programmer who is designing a callback API would need to consider the following factors in deciding which to use:
  • If there are multiple methods in the callback, then then an anonymous class would seem a better fit. That being said, it is possible to either use multiple closures (one for each callback method), or to define a single closure whose parameters allow the passing of different meanings (such as an status code + result.) However, this rapidly becomes unwieldy as the number of methods increases.
  • Some would argue that both the class name and the method name of the callback are an important part of the self-documentation of the callback code. If I define an interface that is named "AsyncCallback" with a method "onSuccess", that tells me more than if I use a generic "Function" type.
Still, even with the above caveats, programmers are going to choose closures a large part of the time because of their convenience, especially for interfaces where there's only a single method. So the need to provide anonymous classes isn't quite as crucial as it would be in Java.