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 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:
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: 155824Category Count Size Average Percent================================ ====== ====== ======= =======Reflection -- 39088 -- 25.1Composite types 128 22528 176 14.5Enum types 1 64 64 0.0Other types 9 576 64 0.4Type references 2 80 40 0.1Type lists 45 1616 35 1.0Invokers 8 6240 780 4.0Name tables (head) 42 2880 68 1.8Name tables (simple) 41 3591 87 2.3Name tables (compound) 29 793 27 0.5Field offsets 39 720 18 0.5TIB -- 12384 -- 7.9TypeInfoBlocks 128 7040 55 4.5Base class lists 56 1856 33 1.2IDispatch functions 91 3488 38 2.2
Standard Library -- 94492 -- 60.6tart.core 209 15944 76 10.2tart.collections 214 40016 186 25.7tart.gc 16 1012 63 0.6tart.io 0 0 0 0.0tart.reflect 165 30096 182 19.3tart.testing 10 2896 289 1.9tart.text 22 4528 205 2.9Classes -- 57976 -- 37.2tart.core.Array 177 13928 78 8.9tart.core.String 21 5152 245 3.3tart.collections.ArrayList 86 22944 266 14.7tart.collections.ImmutableList 69 14672 212 9.4tart.collections.List 21 1280 60 0.8
Static strings 151 10728 71 6.9Trace 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>() {@Overridevoid onSuccess(ImageResource img) {// do something with img}@Overridevoid 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.
Subscribe to:
Posts (Atom)