Vidar Hokstad

Docker Postfix container w/Virtual Hosts support

Wed, 13 Apr 2016 05:50:00 +0000

Just wanted to point you to a short post I just published on my consulting site:

It provides a very basic Postfix setup that's ready for handling multiple domains and forwarding.

Writing a (Ruby) compiler in Ruby bottom up - step 45

Sun, 26 Jul 2015 05:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Send

One of the great "joys" of trying to compile Ruby is of course the level of dynamism. Especially when trying, as I am, to make the compiler as static as possible.

One of the culprits is the ability to send messages to objects that may be composed dynamically (e.g. formatting strings), and that may or may not even exist at compile time.

So far we've avoided this. There are two issues here:

We need to be able to handle methods with names that are not present in the application at compile time. Currently we put everything into vtables, and to know how to allocate slots we need to know the names at compile time.
We need to be able to look up methods by name, and do something with the information.

Matz' Ruby implementation does this with a hash table of methods. And we will too. This does, however, not mean we'll ditch the vtables. The vtables are essential to get fast method calls for methods we call by names statically known, which for most applications will likely be the vast majority.

Even for method calls where the target method was not defined at compile time this works, by pre-allocating a vtable slot.

Instead what we will do is add redundant information for the methods known at compile time, and augment this with the ability to add new methods down the line.

The initial motivation for this is the work towards self-hosting, and the compiler itself, foolishly or not, uses #send to call the #parse_XXX methods in Parser for example.

CS101 - Hash tables

The last time I wrote a hash table implementation from scratch was more than 20 years ago, in my introductory data structures and algorithms course. I read the book on a long train journey and mostly ignored the lessons. Apart from frustrating everyone by insisting on doing a N-Queens exercise in Amiga-E (a wonderful language by the amazing Wouter van Oortmerssen, though unfortunately rather esoteric even back in '94)

Thankfully, making a simple hash table is, well, simple.

We'll do a very basic linear scan hash table. If you've forgotten your CS courses and is too lazy to click the wikipedia link, that means that once we've calculated which slot an entry should ideally go in, if it is occupied, we linearly probe the other slots until we find an empty one.

There are all kinds of upsides and downsides from various methods for scanning/probing, and from using scans instad of alternative structures, but the point as usual is simplicity first. Especially in this case as we won't even know the access patterns until things are complete enough to do proper benchmarks.

A hash function, and comparisons

Firstly, let us implement #hash. The documentation for Object#hash says this:

Generates a Fixnum hash value for this object. This function must have the property that a.eql?(b) implies a.hash == b.hash.

The hash value is used along with eql? by the Hash class to determine if two objects reference the same hash key. Any hash value that exceeds the capacity of a Fixnum will be truncated before being used.

The hash value for an object may not be identical across invocations or implementations of Ruby. If you need a stable identifier across Ruby invocations and implementations you will need to generate one with a custom method.

This is thankfully easy to match, and we'll do it with the DJB hash function used in amongst others CDB. It's simple, and reasonably efficient:


    +  # DJB hash
    +  def hash
    +    h = 5381
    +    each_byte do |c|
    +      h = h * 33 + c
    +    end
    +    h
    +  end

You'll note we use a multiply by 33 instead of the ((h << 5) + h) in the description. The real reason for this is that I haven't implemented << yet. But in our case, given Ruby's pathological amount of method calls, h * 33 is actually even likely to be faster than ((h << 5) + h) until we actually add some fairly advanced optimization (so ca. 2030 at my current pace).

Note that our function is not entirely equivalent to the original djb hash function, as the original assumes truncation to a 32 bit value. It has little practical implication here given that we will be using a modulo of it in the actual code.

We'll also add String#eql?, which in this case is just an alias for #==:


    +  def eql? other
    +    self.== other
    +  end

(In 6b01ee3)

Handle modulus

Since I happen to know we'll want a working modulus operator (because we'll want to take the hash value of a string, and take the modulus of the hash value and the capacity of the Array we'll store the hash table in to find out where to start probing), that's what we'll fix next.

We start out gently in 3f24489 by adding it to the operator table in operators.rb, and in e6bb8c7 we add the mod keyword to the s-expression syntax to give us something to implement it with.

In 88066af we implement the mod keyword:


    --- a/compile_arithmetic.rb
    +++ b/compile_arithmetic.rb
    @@ -46,8 +46,16 @@ class Compiler
             @e.movl(@e.result, dividend)
             @e.sarl(31, dividend)
             @e.idivl(divisor)
    +
    +        yield if block_given?
           end
         end
         Value.new([:subexpr])
       end
    +
    +  def compile_mod(scope, left, right)
    +    compile_div(scope,left,right) do
    +      @e.movl(:edx, @e.result)
    +    end
    +  end
     end

Piece of cake as div already does the calculation, we just need to actually save the modulus that's already calculated.

Then starts the pain - or "% is the devil"

% is one of the most heinous abominations of Ruby syntax. I'm not talking about the modulus operator. I'm talking about the other %. The evil twin.

You have met it. It's the % that starts quoted strings og all kinds. We've "stolen" one of the codes for the s-expression syntax.

Only % is really horrendously ambiguous. For example, consider what this expression should parse as:

% x

In a sane, just world, this would be a syntax error.

Nah. Too obvious, isn't it? Can't be anything but "x". Uh? What?!?

As it happens, in contexts where it can't validly be the infix modulus opeator, % starts a quoted string even when the following character is a space.

For characters outside of a specific set of exceptions with special meaning, % will treat the character immediately following as the "quote" character that will start and terminate the given string. So above, we're basically using space as the equivalent of a quote.

(If you have ever seen that used other than as a way of terrorising language implementors or other unsuspecting ~~developers~~ victims, I want to know)

Of course this broke the parser, as we've consistently gone for simplicity first...

First of all, let's get some test cases in place (in 8473eaecb):


    
        @mod
            Scenario Outline: Simple expressions
                    Given the expression <expr>
                    When I parse it with the full parser
                    Then the parse tree should become <tree>
    
            Examples:
          | expr       | tree                 | notes  |
          | "% x "     | [:do,"x"]            |        |
          | "a + % x " | [:do,[:+,:a,"x"]]    |        |
          | "1 % 2 "   | [:do,[:%,1,2]]       |        |
          | "1 % 2"    | [:do,[:%,1,2]]       |        |

Then we fix it. As it happens the fix is simple. As horrendous as this syntax looks, at least the cases we're concerned with now are just a matter of distinguishing between a prefix and infix operator, and the shunting yard parser has a mechanism for that. First we change the operator table (in c276794):


    --- a/operators.rb
    +++ b/operators.rb
    @@ -97,7 +97,10 @@ Operators = {
         :prefix => Oper.new( 20, :-,      :prefix)
    },
       "!"         => Oper.new( 10, :"!",      :prefix),
    -  "%"         => Oper.new( 20, :"%",      :infix),
    +  "%"         => {
    +    :infix_or_postfix => Oper.new( 20, :"%",      :infix),
    +    :prefix => Oper.new( 20, :quoted_exp, :prefix)
    +  },
       "/"         => Oper.new( 20, :/,      :infix),
    "*"         => {
         :infix_or_postfix => Oper.new( 20, :"*",   :infix),

This basically makes the parser accept both versions in their respective contexts.

Then we need to handle it. As it happens we can use the opportunity for some minor cleanup. We already added code to special case the operator case of '%', and that's actually what broke the modulo operator case. So now we rip that out, and add a helper #get_quoted_exp to let the parser choose whether to call back in and parse a quoted expression (and make use of that helper one other place as well) (in 3815fb2):


    --- a/tokens.rb
    +++ b/tokens.rb
    @@ -143,10 +143,15 @@ module Tokens
           @s.unget(s)
         end
    
    +    def get_quoted_exp(unget = false)
    +      @s.unget("%") if unget
    +      @s.expect(Quoted) { @parser.parse_defexp } #, nil]
    +    end
    +
         def get_raw
           case @s.peek
           when ?",?'
    -        return [@s.expect(Quoted) { @parser.parse_defexp }, nil]
    +        return [get_quoted_exp, nil]
           when DIGITS
             return [@s.expect(Number), nil]
           when ALPHA, ?@, ?$, ?:, ?_
    @@ -182,11 +187,6 @@ module Tokens
           else
             # Special cases - two/three character operators, and character constants
    
    -        if @s.peek == ?%
    -          r = @s.expect(Quoted) { @parser.parse_defexp }
    -          return [r,nil] if r
    -        end
    -

Note that in the operator case, the rest of that code have already 'eaten' the '%' so we need an option to unget it.

We also expose the #get_quoted_exp helper in tokenizeradapter.rb.

And finally in shunting.rb we trigger on quoted_exp and call back into the tokenizer via the adapter (in 3815fb2):


    +    def parse_quoted_exp
    +      @tokenizer.get_quoted_exp
    +    end
    +
         def shunt(src, ostack = [], inhibit = [])
           possible_func = false     # was the last token a possible function name?
           opstate = :prefix         # IF we get a single arity operator right now, it is a prefix operator
    @@ -90,6 +94,8 @@ module OpPrec
                 else
                   raise "Block not allowed here"
                 end
    +          elsif op.sym == :quoted_exp
    +            @out.value(parse_quoted_exp)
               else
                 if op.type == :rp
                   @out.value(nil) if lastlp

Finally we can implement the '%' operator in Fixnum (in 9f6f151):


    --- a/lib/core/fixnum.rb
    +++ b/lib/core/fixnum.rb
    @@ -5,6 +5,16 @@ class Fixnum < Integer
         %s(assign @value 0)
       end
    
    +  def % other
    +#    %s(printf "%i\n" (callm other __get_raw))
    +    %s(assign r (callm other __get_raw))
    +    %s(assign m (mod @value r))
    +
    +    %s(if (eq (gt m 0) (lt r 0))
    +         (assign m (add m r)))
    +    %s(__get_fixnum m)
    +  end
    +

Note the last if expression, which is used because the x86 instruction set and Ruby disagrees on how to handle modulo operations with negative numbers, and I opted to stick with code similar to what gcc outputs for C rather than encode the Ruby behaviour in the s-exp syntax. I may yet change my opinion on that - we'll see, but for now this works.

Minor Array fixes

In addition to the above, in 928fe97 I add support for Array.new(capacity) and Array#capacity, as well as make Array#[]= work for the basic cases, as this will be needed for the Hash implementation below.

Creating the class hash table

In 913a3de you will find an initial implementation of Hash. Notably, this implementation is pure Ruby, and (basic, simple) programs will not even necessarily break if you load this implementation in MRI and proceed to use it. It also maintains insertion order, like MRI 1.9+, which aids in testing vs. MRI.

It does, however, lack most methods, but it should be sufficient for us for the next steps. It is worth noting, though, that it is certainly still inefficient in eg. the interaction with Array, and there's plenty of scope for improvement in the future.

I'll leave figuring the hash implementation out as an exercise for the reader (or ask in the comments), as there's nothing specific to the compiler in that one and it should be quite simple: Basically I maintan an array of slots consisting of pointers - one to the key, one to the value, and a linked list to maintain insertion order. Then on setting and reading the hash table, we calculate the hash of the key, look up the first applicable slot, then we loop over the hash table until we've found a matching key, possibly wrapping around, or we find an empty slot.

If the table is too small, we re-allocate the array and re-insert all the key/value pairs.

We could do this more efficiently for special cases like the vtable where we don't need the insertion order, for example, but as usual, efficiency for later.

Creating a hash table of String => Symbol

But in the interest of (some) efficiency as in this case it also brings us closer to feature-completeness, I will first make one further improvement to Symbol handling.

Since we now have a Hash table, we can store a hash mapping Symbol names to Symbol instances, and thus gain the two main advantages Symbol is meant to have: Ability to treat object identity as equality (in other words: compare pointers rather than string values in our case), and secondly reusing the same object instance each time the symbol is mentioned.

We'll use this to make the cost of the class method tables less excessive.

Firstly, to make Symbol work with these changes, it was necessary to move it later in the bootstrap of the runtime (in fc674f3). This is one of the things I find most interesting with working on this compiler: Slowly teasing out a minimal core of Ruby and figuring out how to bootstrap just the lower level facilities and bootstrap. That's going to be an interesting subject in its own right at some point.

Secondly we implement Object#object_id as simply returning %s(__get_fixnum self). So (and this should not be relied on), #object_id in our case is actually the fixnum version of the pointer to the object.

We strictly don't need this, but it's used by my test case, and also lets me isolate the s-expression parts further, implementing Object identity comparisons (note: these actually belongs in Comparable, but we don't do include and friends yet). (In 38ca5270e3)

These leave us with a very small manageable set of changes to Symbol. Small enough to just include the whole rudimentary Symbol class here (changes can be seen in 9abb565, and followup in 077dcf3):


    class Symbol
       @symbols = {}

The above is our symbol-name to Symbol hash table.

Cleaned it up to use proper String objects for the name (though #to_s should probably use #dup, which I don't think we've implemented yet)


      # FIXME: Should be private, but we don't support that yet
      def initialize(name)
        @name = name
      end
    
      def to_s
        @name
      end
    
      def hash
        to_s.hash
      end
    
      # FIXME
      # The compiler should turn ":foo" into Symbol.__get_symbol("foo").
      # Alternatively, the compiler can do this _once_ at the start for
      # any symbol encountered in the source text, and store the result.
      def self.__get_symbol(name)
        sym = @symbols[name]
        if sym.nil? ## FIXME: Doing !sym instead fails w/method missing
          sym = Symbol.new(name)
          @symbols[name] = sym
        end
        sym
      end
    end
    
    %s(defun __get_symbol (name) (callm Symbol __get_symbol ((__get_string name))))

Here is the fun: Look up the symbol; if not present in the hash table, create a new one, and return it.

One notable thing: MRI recently added garbage collection of symbols. The above actively works counter to garbage collection of symbols - once we get to add a GC we'll want to deal with that by letting the GC handle certain structures, such as this hash, as "weak" references that can be broken. It's an extra complexity, but far away.

Bootstrapping the values

Eventually we are going to use two separate types of hash tables: Symbol => offset in vtable for statically allocated methods, and Symbol => address of method for runtime defined methods. This will keep the class specific hash tables small at the cost of one extra hash table lookup in #send, but #send will always be slow compared to the direct vtable lookup anyway.

This time we will only actually implement the former, and only handle cases of "#send" called with method names we've statically seen. This actually covers a substantial proportion of the use of #send. The big exception is cases where a method is both dynamically defined and dynamically used by string composition or by requiring files at load time (which we don't support yet). Most importantly at this stage it handles the specific case of bootstrapping the compiler itself.

We'll declare it out of bounds for the compiler itself to use #send before a suitable point in the bootstrap process, where we call a compiler generated function to bootstrap this hash table.

Calling #send before that will trigger a runtime error.

In 5a269ec I add a new file lib/core/class_ext.rb that implements the send "send" logic, and the code to bootstrap these values. This goes in a separate file for the simple reason that it needs to be loaded after Symbol and various other things have gotten bootstrapped, but the basics of Class are needed much earlier.

First of all, this is how the send happens:


      # This is called by __send__
      def __send_for_obj__ obj,sym,*args
        voff = Class.method_to_voff[sym]
        if !voff
          %s(printf "WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.\n")
          %s(if sym (printf "WARNING:    Method: '%s'\n" (callm (callm sym to_s) __get_raw)))
          %s(printf "WARNING:    symbol address = %p\n" sym)
          %s(printf "WARNING:    object = %p\n" obj)
          %s(printf "WARNING:    class '%s'\n" (callm (callm self name) __get_raw))
          nil
        else
          # We can't inline this in the call, as our updated callm
          # doesn't allow method/function calls in the method slot
          # for simplicity, for now anyway.
          %s(assign raw (callm voff __get_raw))
          %s(callm obj (index self raw) ((splat args)))
        end
      end

There's not that much new or different here. Mainly we look up the method name in the new hash table (which should not be public, but we'll worry about that later). Secondly, if the vtable offset is known - which will be the case for all methods we've seen statically mentioned - we attempt to convert the stored Fixnum to a raw integer, retrieve the address from the vtable, and do a callm with the address instead of a method name.

This latter part is new, and we'll have a look at how to handle that shortly, but first the last part of lib/core/class_ext.rb:


    #
    # Populate the Class.method_to_voff hash based on the __vtable_names
    # table that gets generated by the compiler.
    #
    %s(let (i max)
       (assign i 0)
       (assign max __vtable_size)
       (assign h (callm Class method_to_voff))
       (while (lt i max)
          (do
             (if (ne (index __vtable_names i) 0)
                (callm h []= ((__get_symbol (index __vtable_names i)) (__get_fixnum i)))
                )
              (assign i (add i 1))
          )
       )
    )

This is fairly straight forward: We iterate over a table name __vtable_names that the compiler will henceforth output, and for __vtable_size entries we obtain a Symbol object, and then add a mapping from the ymbol to the according offset to the Class.method_to_voff hash table.

This table was actually added in e6bb8c75 - I think that method in Compiler should be reasonable self-explanatory - basically outputs an array of pointers to constant strings.

Handling callm with computed addresses

Previously %s(callm ...) have only supported names. Now it needs to supports %s(callm object <some expression resulting in method address> ...) too.

We handle this as follows. Firstly, we (in 46bb9d0) we check if the method is provided by name (as a Symbol), and only use the old logic if it is:


    +      if method.is_a?(Symbol)
    +        off = @vtableoffsets.get_offset(method)
    +        if !off

Then further down, we conditionally compile the actual call differently:


    -        @e.callm(m)
    +        if off
    +          @e.callm(m)
    +        else
    +          # NOTE: The expression in "method" can not
    +          # include a function call, as it'll clobber
    +          # %ebx
    +          @e.call(compile_eval_arg(scope,method))
    +        end

I'm not quite pleased with the complexity of compile_call.rb, but it'll do for now.

Parting words

And that's in. Doing #send now works. And we have a somewhat working Hash.

Not bad.

And with this I will start doing what I've mentioned for a while now and switch to writing shorter, more focused entries on specific features rather than these huge parts. And feature branches instead of branches focused on a specific part....

Hopefully it will get things moving a bit quicker.

(This also signals that I'll be more open to outside contributions and suggestions, though I recognise this probably isn't the easiest codebase to jump into, despite the copious amount of writing I've done about it's internals)

Writing a (Ruby) compiler in Ruby bottom up - step 44

Tue, 17 Mar 2015 00:35:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Further misadventures on the way to self-hosting

In which we continue the circuitous approach towards parsing s-expressions

As you may or may not remember (it's taking a while, after all), the immediate purpose is to use the limited s-expression part of the parser to ferret out the first batch of problems standing beween us and fully self-hosting the compiler.

For that purpose, I've now put together a tiny test driver and the minimal dependencies of the s-expression parser, and this part we will look at 1) changes to reduce coupling (which means we're cheating by delaying certain types of fixes by moving the troublesome code out of the immediate dependencies of the s-expression parser) and 2) changes to make that code compile, and hopefully even run.

I'll give you a spoiler right now, and tell you that at the end of this there will be at least one more roadblock: Implementing dynamic method dispatch (looking up a method by name for #send).

At the time of writing I don't know if that will be the only outstanding issue (probably not), but it's most likely the biggest of the remaining issues to get the s-expression parser to work by itself, since call parser methods by name.

(Whether or not it's a good idea to do that is another matter, but for now it'll stay since we need to cover that bit anyway).

Improving 'require' and the driver

An immediate problem presented itself when trying to compile code that require'd other code expecting a different load path. I'm not quite reading to start dealing with the pain (in terms of ahead-of-time, semi-statically) compiling code that dynamically messes with $:, but adding options to set the load path, and improving/fixing some of the path issues with the current implementation of require, as well as improving the option passing in the driver code seems like a good idea.

Time to start cleaning up the driver for the compiler ever so slightly. In 91aa84d I started by making the driver bail out without trying to assemble if the compilation fails, as that's been driving me crazy for a while.

In 4b62af4 I added slightly better load/include path handling. In driver.rb, I added support for "-I" to indicate the initial include path (we do not support $: etc. yet). That is supported in parser.rb by quite straight forward code to mangle the paths and identify the actual files as needed, and to ensure the core library still loads.

Improving nested symbol resolution

What was revealed once I added the above, was that I took too many shortcuts for resolving Foo::Bar back in part 41:


    ./compiler.rb:199:in `compile_deref': Unable to resolve: Scanner::ScannerString statically (FIXME) (RuntimeError)
    from ./compiler.rb:540:in `compile_exp'
    from ./compiler.rb:114:in `get_arg'
    from ./compiler.rb:370:in `compile_eval_arg'

We're going to attack this first by improving the debugging of symbol table content.

In a8b23a9 I added the --dumpsymtab option, which makes use of new #dump methods added to Scope with specializations for GlobalScope and ClassScope in debugscope.rb, which recursively processes the symbol table.

What that that revealed was the result of the ugly shortcut of conflating the low level output of assembler level symbols with Ruby-level constant nesting, as a result of hacking our way through this without a detailed up front design.

Thankfully that's not all that hard to fix at this stage - we already did the most important work with the introduction of build_class_scopes in part 41, which ensures that the right information is available - that's what made the --dumpsymtabs option easy to provide.

All we need to do is to actually look up what we should be looking up: the name of the inner constant, instead of the synthetic assembly level name, so that it is found in the scope chain instead of ending up being forwarded all the way up to GlobalScope (which still has the ugly synthetic variable name - that needs to go eventually, and not be exposed to Ruby).

In ClassScope (in e4eafcc) :


       def find_constant(c)
         const = @constants[c]
         return const if const
    -    return @next.find_constant(@name+"__"+c.to_s) if @next
    +    return @next.find_constant(c) if @next
         return nil
       end

While doing a global looking in compiler.rb we'll actually look up these ugly compound names for now, and then add them to the list (e4eafcc) :


    +      prefix = scope.name
    +      aparam = prefix + "__" + aparam.to_s if !prefix.empty?
           @global_constants << aparam

Handling "include"

For now we're just stubbing it out, together with protected. See f0dfb45 which basically just adds them without doing anything of substance...

Handling splat => array conversion

Now to the big one for this round. The remaining other issues I dealt with for this part all fell out of addressing the splat handling.

This is one of the long-standing tensions between efficiency and getting required Ruby functionality.

This does what you'd expect with MRI, of course:


    def foo *args
      puts "Length:"
      puts args.length
      puts "Members:"
      puts args[0]
      puts args[1]
      puts args[2]
    end
    
    foo(1,2,3)

But on entering foo at the moment, args is a c-style array. It works if we dip into the s-expression syntax:


    def foo *args
      puts "Length:"
      %s(callm self puts ((__get_fixnum numargs)))
      puts "Members:"
      %s(callm self puts ((index args 0)))
      %s(callm self puts ((index args 1)))
      %s(callm self puts ((index args 2)))
    end
    
    foo(1,2,3)

(never mind that it outputs a length of 5 - that reflects self and space for a pointer to a block).

To handle this, we need to add support for turning args into an actual Ruby array.

There's a wrinkle: So far we've used this as a shortcut for quickly pushing members onto the call stack if we subsequently turn around and call another method with it. Either we need to continue supporting that (it will be sufficient if the second example above still works, but there are other alternatives)

One solution is to allocate arguments in a Ruby array, but that has terrible overhead, and complicates interoperability with C. Another is to allocate a Ruby Array in the method, optionally using some method to determine if the array is likely to be used.

For now, I have chosen to add code in the method to convert splat arguments to a real Ruby array, and to take the pain of rewriting code that used index/numargs on splat arguments.

A problem which instantly materialize is that calling Class#new can not directly or indirectly require calls to Class#new in order to complete. If it does, we get infinite recursion, obviously (or rather, recursion until we run out of stack).

Unfortunately this is tricky: Class#new currently uses a splat argument, which in the most obvious naive implementation of turning splat arguments into a real Ruby Array itself triggers a Class#new call (in the form of Array.new).

Array#initialize further assigns Fixnum'a to instance variables, and this too triggers Class#new to instantiate said Fixnum's.

We either needs to shortcircuit this in the case of an empty splat array, and add a way of constructing an empty Array, or find some other way of short-circuiting this recursion.

(We're going to deal with the fallout of figuring out a more reasonable ordering of the bootstrapping of the core classes for some time to come).

Let's look at the code

You'll find this entire change in d9ac43d75

I'm not going to go over every tiny little bit, but let's examine the most important pieces.

First of all, this is a bit on the sidelines, but a major reason to complete the splat support was to handle literal arrays. There's now a new method Compiler#compile_array to handle that simply by turning them into Array[] calls:


    +  # Compile a literal Array initalization
    +  #
    +  # FIXME: An alternative is another "transform" step
    +  #
    +  def compile_array(scope, *initializers)
    +    compile_eval_arg(scope,
    +                     [:sexp,
    +                      [:callm, :Array, :[], initializers]
    +                      ])
    +    return Value.new([:subexpr], :object)
    +  end

Next, in transform.rb the work starts by modifying methods with splat arguments. First we rename the argument to __splat (at some point I'll probably change this to hide them from the Ruby code entirely):


        +      rest = e[2][-1] rescue nil
        +      rest = (rest[-1] == :rest ? rest[0] : nil) rescue nil
        +      if rest
        +        e[2][-1][0] = :__splat
        +      end
        +

Then we introduce a new local variable (hence the location of this transformation rule in rewrite_let_env) with the original name of the argument, and assign the result of a call to __splay_to_Array_ to it:


    -      e[3] = E[e.position,:let, vars,*e[3]]
    +      if rest
    +        vars << rest.to_sym
    +        rest_func =
    +          [:sexp,
    +           [:assign, rest.to_sym, [:__splat_to_Array, :__splat, :numargs]]
    +          ]
    +      else
    +        rest_func = []
    +      end
    +
    +      e[3] = E[e.position,:let, vars, rest_func,*e[3]]

One immediate thing is worth observing: We could certainly defer this call as long as possible, to hope to avoid the conversion in e.g. cases of early return.

At some point that will be worth exploring, but note also that this could/should fall out automatically if we later add suitable optimization passes. For now it's by far easiest to just put it at the beginning of the method.

This of course means we need to implement __splat_to_Array:


    +%s(defun __splat_to_Array (r na)
    +   (let (splat pos data max)
    +    (assign splat (callm Array __new))
    +    (assign pos 0)
    +    (assign max (sub na 2))
    +    (callm splat __grow (max))
    +    (while (lt pos max)
    +       (do
    +          (callm splat __set (pos (index r pos)))
    +          (assign pos (add pos 1))
    +          )
    +        )
    +  splat
    +  ))
    +

This is roughly equivalent to (pseudo-Ruby):


    def __splat_to_Array(r na) # na is "numargs"; r is the c-style splat array.
      splat = Array.__new
      pos = 0
      max = numargs - 2 # Subtract two for "self" and a &block argument we always allocate space for
      splat.__grow(max)
      while pos < max
        splat.__set(pos, r[pos])
        pos += 1
      end
    end

There are a few odd things here. For starters, we do this using the s-expression syntax because nearly "everything" otherwise would potentially trigger attempts to allocate objects, and Class#new uses splats. This also means we can't use Class#new, as discussed above.

So I've introduced Class#__new as a lower level method that you should never-ever use in Ruby code (and which we'll find some way of hiding later). I also had to modify Array extensively to avoid even using Fixnum's, since we're for the time being at least using objects rather than type-tagged integers.

The rest pretty much falls out of that. Class#__new and Class#__alloc (used by Class#__new) looks like this:


    +  # Clients that need to be able to allocate a completely clean-slate empty
    +  # object, should call <tt>__alloc</tt>.
    +  #
    +  def __alloc
    +    %s(assign ob (__array @instance_size))
    +    %s(assign (index ob 0) self)
    +    ob
    +  end
     
     +  # Clients that want to be able to create and initialize a basic version of
     +  # an object without normal initializtion should call <tt>__new</tt>. See
     +  # <tt>__splat_to_array</tt>
     +  #
     +  def __new
     +    ob = __alloc
     +    ob.__initialize
     +    ob
     +  end

These should be pretty self-explanatory. Note that the new Class#new calls __alloc, but not __initialize.

A very basic initial version of Array is now first introduced in lib/core/core.rb. It needs to be introduced that early for bootstrapping reasons, since it needs to exist when Class#new is first called. This showcases __initialize:


    +class Array
    +  # __get_fixum should technically be safe to call, but lets not tempt fate
    +  # NOTE: The order of these is important, as it is relied on elsewhere
    +  def __initialize
    +    %s(assign @len 0)
    +    %s(assign @ptr 0)
    +    %s(assign @capacity 0)
    +  end
    +
    +  #FIXME: Private; Used by splat handling
    +  def __len
    +    @len
    +  end
    +
    +  def __ptr
    +    @ptr
    +  end

And here's __grow that's used internally to ensure the Array is big enough. Normally it should not be called directly, but we make an exception for the splat code:


    +  def __grow newlen
    +    # FIXME: This is just a guestimate of a reasonable rule for
    +    # growing. Too rapid growth and it wastes memory; to slow and
    +    # it is, well, slow to append to.
    +
    +    # FIXME: This called __get_fixnum, which means it fails when called
    +    # from __new_empty. May want to create new method to handle the whol
    +    # basic nasty splat allocation
    +    # @capacity = (newlen * 4 / 3) + 4
    +    %s(assign @capacity (add (div (mul newlen 4) 3) 4))
    +
    +    %s(if (ne @ptr 0)
    +         (assign @ptr (realloc @ptr (mul @capacity 4)))
    +         (assign @ptr (malloc (mul @capacity 4)))
    +         )
    +  end

And __set is a low level method to assign to the array and extend, that makes assumptions we can't safely make in general (that is, it expects an expansion by at most one element at a time. Frankly rewriting __splat_to_Array to set length once and omit it here would probably be worth it, but some other time:


    +  #FIXME: Private. Assumes idx < @len && idx >= 0
    +  def __set(idx, obj)
    +    %s(if (ge idx @len) (assign @len (add idx 1)))
    +    %s(assign (index @ptr idx) obj)
    +  end
    +
    +end
    +

Most of the rest of the changes, apart from compile_calls.rb, are changes to the library code (particularly Array to accommodate the splat handling changes and/or take advantage of them). compile_calls.rb, though has seen a huge rewrite. Rather than go through the diff, it's easier to walk through the new version.

Both method and our "c-level" function calls now use the same method-chanin to push arguments onto the stack. It starts with this:


      def compile_args(scope, ob, args, &block)
        @e.caller_save do
          splat = args.detect {|a| a.is_a?(Array) && a.first == :splat }
    
          if !splat
            compile_args_nosplat(scope,ob,args, &block)
          else
            compile_args_splat(scope,ob,args, &block)
          end
        end
      end

The "nosplat" case is simple, and pretty much what we used to do:


      def compile_args_nosplat(scope, ob, args)
        @e.with_stack(args.length, true) do
          @e.pushl(@e.scratch)
          args.each_with_index do |a, i|
            param = compile_eval_arg(scope, a)
            @e.save_to_stack(param, i + 1)
          end
          @e.popl(@e.scratch)
          yield
        end
      end

The tricky bit is the splat handling, which I'm by no means happy with, and it will probably need significant simplification:


     def compile_args_splat(scope, ob, args)
        # Because Ruby evaluation order is left to right,
        # we need to first figure out how much space we need on
        # the stack.
        #
        # We do that by first building up an expression that
        # adds up the static elements of the parameter list
        # and the result of retrieving 'Array#length' from
        # each splatted array.
        #
        # (FIXME: Note that we're not actually type-checking
        # what is *actually* passed)
        #
        num_fixed = 0
        exprlist = []
        args.each_with_index do |a, i|
          if a.is_a?(Array) && a[0] == :splat
            # We do this, rather than Array#length, because the class may not
            # have been created yet. This *requires* Array's @len ivar to be
            # in the first ivar;
            # FIXME: should enforce this.
            exprlist << [:index, a[1], 1]
          else
            num_fixed += 1
          end
        end
        expr = num_fixed
        while e = exprlist.pop
          expr = [:add, e, expr]
        end
    
        @e.comment("BEGIN Calculating argument count for splat")
        ret = compile_eval_arg(scope, expr)
        @e.movl(@e.result, @e.scratch)
       @e.comment("END Calculating argument count for splat; numargs is now in #{@e.scratch.to_s}")

The comments in the part above hopefully speaks for itself. For e.g. foo(*a, b, *c) it basically does the equivalent of a.length + c.length + n where n is the number of non-splat arguments.

Next we save the count we found, and then allocate space on the stack:


        @e.comment("Moving stack pointer to start of argument array:")
        @e.pushl(@e.scratch) # We assume this may get borked during argument evaluation
        @e.imull(4,@e.result)
    
        # esp now points to the start of the arguments; ebx holds numargs,
        # and end_of_arguments(%esp) also holds numargs
        @e.subl(@e.result, :esp)

Then we start at the bottom of the allocated stack segment, and evaluate arguments and save the result, working our ways up the stack, except if we find a splat argument, we call compile_args_copysplat to take care of that:


        @e.comment("BEGIN Pushing arguments:")
        @e.with_register do |indir|
          # We'll use indir to put arguments onto the stack without clobbering esp:
          @e.movl(:esp, indir)
          @e.pushl(@e.scratch)
          @e.comment("BEGIN args.each do |a|")
          args.each do |a|
            @e.comment(a.inspect)
            if a.is_a?(Array) && a[0] == :splat
              compile_args_copysplat(scope, a, indir)
            else
              param = compile_eval_arg(scope, a)
              @e.save_indirect(param, indir)
              @e.addl(4,indir)
            end
          end
          @e.comment("END args.each")
          @e.popl(@e.scratch)
        end
        @e.comment("END Pushing arguments")

Then we yield to handle the actual call for various types of calls, and then adjust the stack:


        yield
        @e.comment("Re-adjusting stack post-call:")
        @e.imull(4,@e.scratch)
        @e.addl(@e.scratch, :esp)
      end

That leaves compile_args_copysplat:


      # For a splat argument, push it onto the stack,
      # forwards relative to register "indir".
      #
      # FIXME: This method is almost certainly much
      # less efficient than it could be.
      #
      def compile_args_copysplat(scope, a, indir)
        @e.comment("SPLAT")
        @e.with_register do |splatcnt|
          param = compile_eval_arg(scope, a[1])
          @e.addl(4,param)
          @e.load_indirect(param, splatcnt)
          @e.addl(4,param)
          @e.load_indirect(param, :eax)
          @e.testl(:eax,:eax)
          l = @e.get_local

Notice the ugliness that comes next: We need to sort-of the case where the Array class itself simply hasn't been created yet at all (which will only "work" if the splat arguments in question are not actually used):


          # If Array class ptr has not been allocated yet:
          @e.je(l)

I really hope there's a nicer/cleaner/faster way of doing this, but what's driving me crazy below is the addressing modes for x86. For m68k, you can get away with some indirect gymnastics which makes stuff like this far simpler:


          @e.loop do |br|
            @e.testl(splatcnt, splatcnt)
            @e.je(br)
            # x86 will be the death of me.
            @e.pushl("(%eax)")
            @e.popl("(%#{indir.to_s})")
            @e.addl(4,:eax)
            @e.addl(4,indir)
            @e.subl(1,splatcnt)
          end
    
          @e.local(l)
        end
      end

I'm sure there are better ways of doing it for x86 too (and certainly for x64; one day we'll get around to doing a 64-bit backend).

Parting words

And that's it. This brings me to the point where the main obvious hindrance (I'm sure others will pop up) is the lack of proper support for send, and so that is what I'll cover in part 45.

Writing a (Ruby) compiler in Ruby bottom up - step 43

Mon, 02 Feb 2015 02:05:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Eigenclasses

Eigenclasses, or meta-classes in Ruby are effectively regular classes that gets "injected" in the inheritance chain, but hidden when calling #super and #class (Ruby is sneaky like that; I'm not convinced I like that part). For more on eigenclasses there's _why's excellent old article

Fixing this is deceptively easy, at least for the basic case. Lets get this example working first:


    class Foo
    
      def self.bar baz
        puts baz
      end
    
    end
    
    Foo.bar("Hello world")

def self.bar basically means (using the convention that "#klass" refers to the real class of the object, rather than whatever #class returns):

"if self.klass is not an eigenclass, then make it one (create a new subclass of self.klass that is marked as an eigenclass). Define #bar as a method on self.klass". Note that "self" in this case is the Class object Foo, so Foo.klass will be Class, and the new eigenclass that we define a method on will be a subclass of Class, not a subclass of Foo.

Similarly, the alternative syntax (which we'll get back to later) of "class <

(where green represents Class objects)

This represents this:


    class Foo
    end
    
    Foo.new

Now we want to do the def self.bar from above. The resulting objects should look like this:

For illustration: The non-class case

Consider if we instead did:


        class Foo
        end
        
        ob = Foo.new
        
        def ob.bar
        end

In that case, we'd expect #bar to get defined on an Eigenclass that pops into the hierarchy like this:

Notice how the Eigenclass for the non-class case gets introduced as the new class of the instance. The object isn't "really" an instance of Foo any more, but an instance of the eigenclass, which again is inherited from Foo.

Conceptually it's exactly the same. It's just a matter of which object we introduced a new method on, and therefore which object we attached an eigenclass to.

We'll not deal with this case any further in this part. We'll wrap that up later. Especially as instance specific eigenclasses is rare (because they should be used sparingly: they are expensive, causing a Class object per object you attach methods to).

Implementation

First we get 51c003f out of the way, which simply expands the Scope class slightly to forward and provide defaults for more cases. Most of these will be made use of later.

Then let's start to hook in the actual eigenclass treatment. We're now aiming for handle the def self.foo case, which the parser will deliver as [:defm, [:self, :foo], ...].

All of the following is in 8ad4e6f


       def compile_defm(scope, name, args, body)
         scope = scope.class_scope
     
    +    if name.is_a?(Array)
    +      compile_eigenclass(scope, name[0], [[:defm, name[1], args, body]])
    +      return Value.new([:subexpr])
    +    end

compile_eigenclass looks like this:


    +  def compile_eigenclass(scope, expr, exps)
    +    @e.comment("=== Eigenclass start")
    +
    +    ob = [:index, expr, 0]
    +    ret = compile_eval_arg(scope, [:assign, ob,
    +                                   [:sexp, [:call, :__new_class_object, [scope.klass_size, ob, scope.klass_size]]]
    +                                  ])
    +    @e.save_result(ret)
    +
    +    let(scope,:self) do |lscope|
    +      @e.save_to_local_var(:eax, 1)
    +
    +      # FIXME: This uses lexical scoping, which will be wrong in some contexts.
    +      compile_exp(lscope, [:sexp, [:assign, [:index, :self ,2], "<#{scope.local_name.to_s} eigenclass>"]])
    +
    +      exps.each do |e|
    +        compile_do(lscope, e)
    +      end
    +      @e.load_local_var(1)
    +    end
    +    @e.comment("=== Eigenclass end")
    +
    +    return Value.new([:subexpr], :object)
    +  end
    +

Basically, we create a new class object, save the pointer to it as a local variable temporarily, and alias self. We then assign a name to the class, and compile methods in that new context.

This is all fairly similar to compile_class, and there might be opportunities to combine the two more later (and there's almost certainly holes/bugs in compile_eigenclass as it stands.

There's also one big inefficiency: If you define multiple methods, you get multiple eigenclasses chained. That's ok. It's just wasteful, and potentially slow. It's easier to fix that once I get around to adding an easier way of identifying an eigenclass.

But what is the let method above?

A convenience method for local variables

Basically, I needed a simple way of defining a local scope, and allocating stack space for it. compile_let did that, but only for code in tree form. So the new let is a rewrite that extracts out that part of the code, and leaves compile_let a tiny little stub:


      def let(scope,*varlist)
        vars = Hash[*(varlist.zip(1..varlist.size)).flatten]
        lscope =LocalVarScope.new(vars, scope)
        if varlist.size > 0
          @e.evict_regs_for(varlist)
          @e.with_local(vars.size) do
            yield(lscope)
          end
          @e.evict_regs_for(varlist)
        else
          yield(lscope)
        end
      end
    
      
      # Compiles a let expression.
      # Takes the current scope, a list of variablenames as well as a list of arguments. 
      def compile_let(scope, varlist, *args)
        let(scope, *varlist) do |ls|
          compile_do(ls, *args)
        end
        return Value.new([:subexpr])
      end

Before we move on to some minor supporting changes in the runtime library, there was one bug that slowed me down substantially I want to briefly mention:

compile_assign was the only user of what at some point became a severely broken mechanism for saving register content. With the proper register allocation there's no excuse for it any more, and so Emitter#save_register has to go. The problem was that if you indicated a register should be saved, it didn't properly mark it as freed up again, and so we got spurious pushl's onto the stack in positions which meant you could push and pop values in the wrong order The replacement in `compile_assign is sometimes less efficient, but also less broken.

It also cuts some lines out of emitter.rb

Runtime library changes

The bootstrapping of the object model is still a bit messy. One aspect that has been there "forever" but which became more obvious when working on this part, is the chicken and egg problem with Class and Object. With the support for re-opening classes, we have the mechanism for making the situation better.

This change in 1e1ce21 improved by explicitly "manually" link Class into the list of subclasses of Object. This means Class will properly inherit methods of Object after all, and let us clean up Class next.


     class Object
    +  # At this point we have a "fixup to make as part of bootstrapping:
    +  #
    +  #  Class was created *before* Object existed, which means it is not linked into the
    +  #  subclasses array. As a result, unless we do this, Class will not inherit methods
    +  #  that are subsquently added to Object below. This *must* be the first thing to happen
    +  #  in Object, before defining any methods etc:
    +  #
    +  %s(assign (index self 4) Class)
    +

The above let us strip out the suprfluous Class#== and depend on Object#== in 4c0c349. At the same time (and same commit) we fix Class#to_s and Class#inspect to use the ugly Class#name. We also "manually" set the class of Class to Class, and it's name to the raw string "Class"

Conclusion

These changes leave us with what's needed to compile almost all of the tokenizer code pretty much unmodified, and so we're no rapidly closing on the initial goal of compiling the s-exp subset of the parser. We'll look at the next batch of changes for that next.

However I will make a change going forwards. After part 44 or 45, rather than batching up changes and trying to cover specific subjects, I'll be pushing out changes as soon as I have something ready to commit, and will mention the commits I think are worth while discussing in much shorter posts. I'll then follow it up with longer articles covering specific areas of the compiler or larger changes more rarely as I think I have something more worthwhile about a specific component.

The main reason is that it takes a lot of effort to write these larger posts - 2-3 times as long as actually making the changes (including time to restructure some of the commits to make more sense for the articles), and frankly I want to make faster progress on actually being able to use the compiler.

This will also simplify my git handling substantially - currently I manage two repos in addition to my local working copies - one for my drafts, and the public one on Github. Going forwards I'll push changes to the Github repo right away. Branches will also no longer reflect a specific article.

I hope this will lead to more interesting development rather than fewer, though recent parts of this series have been very much a mixed bag of commits that are only related by the what goal I've been working towards rather than what code they've touched anyway.

Writing a (Ruby) compiler in Ruby bottom up - step 42

Sun, 07 Dec 2014 02:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Re-opening class definitions

The main reason for handling re-opening of class-definitions at this stage, is for a simple reason:

We're going to attack eigenclasses soon, and being able to handle class re-opening makes that a lot simpler in addition to being needed in and of itself too.

Part of the reason is that I made the choice way back in part 19 to use vtables as the basic method for dispatch, and while vtables make for fast method calls, there's extra book-keeping required if we allow re-defining a method, which Ruby of course does.

But how does that affect eigenclasses?

A quick refresher on vtables, and how this fits with Ruby

As you may or may not remember, this involves an array in the class object with a pointer to each method. This is what an instance, and its class (which is itself an instance of Class) looks like today:

(the left column represents the "slot" in the object structure. With our current 32-bit backend, this is a multiple of 4 bytes offset from the start of the structure)

This is the standard approach for virtual method dispatch in languages like C++. There it is easier than in Ruby for a few reasons:

The class hierarchies are rarely as deep, since they're not all rooted in a single class (Object previously, these days BasicObject). Furthermore, not all methods are virtual, and member functions that are not virtual do not typically get vtable slots. This substantially reduces the likely maximum size of the vtables.
You're not expected to be able to safely call any method on any object. If you do stupid stuff like statically casting objects to incompatible types, your application will crash when you call the wrong methods on it. But in Ruby, that's expected to be "safe" (as in, the worst case is a method_missing. This means a vtable in C++ only needs to contain space for virtual member functions up to and including the current class. New ones added in sub-classes does not impact the size.
You're not expected to be able to re-open classes and make further definitions, and certainly not allowed to define the same method multiple times for the same class (with the result of overwriting past versions)

It's this last one that makes re-opening classes and Eigenclasses tangled up for us. Consider these two variants:


    class Foo
      # Here self == Foo
      class << self
         # Here self == Foo's eigenclass
         def foo
         end
      end
      # Here self == Foo again
    end
    
    class Foo
       
       def self.foo
       end
       
    end

While in the latter case it's not as explicit, in both cases we're handling first class Foo, then opening Foo's eigenclass, then handling class Foo again. While we can optimize away some cruft here later, to merge processing of adjacent definitions (so that e.g. defining self.foo and self.bar right after each other maintains the same scope), that's extra complexity that does not solve the wider issue.

Re-opening classes with vtables

There is one obvious issue with trying to re-open a class with vtables: What about sub-classes?

Consider our earlier example fleshed out a bit more:

What do we now have to do if we want to override, say, vtable slot 2 in Foo? Well, that depends on Bar:

If Bar has overridden vtable slot 2, then we just update Foo
If Bar has not overridden vtable slot 2, then we need to update Foo and Bar.

So we need to expand the Class instance variables to let us find the sub-classes of any given class. As an example, I've added in a Baz class which is a second subclass of Foo. So this:


    
        class Foo
        end
        
        class Bar < Foo
        end
        
        class Baz < Foo
        end
        
        ob = Bar.new

turns into this:

This leaves us with these steps to set a vtable slot:

Does this class have sub-classes?
If yes
- Find the current vtable entry for the current class, lets call it "cur", and the new entry "new", and the vtable slot entry "slot"
- For each subclass "c":
  - if c[slot] == cur (the slot has not been overridden)
    - Recurse and check all subclasses of "c".
    - Set c[slot] = new
  - if c[slot] != cur
    - the slot has been overridden, so we don't do anything else for this class
- Override the current slot for this class

(Instead of using a pointer to the first subclass, and a chained linked list like this, we could use a hash table or array, and we might very well do that at some point, but not now).

Test case

I've added a test case in 02021ad which simply exercises the basic scenarios by creating a class and two sub-classes - one for which a method is overridden - and then re-opens the base class and overrides one of the original methods.

Globals

One of the first things to overhaul is the method I introduced way back at the start of this series to keep track of functions we want to output.

While Ruby does not have functions, we turn every method we find statically into something that looks much more like a function, and name it in a reasonably human-friendly way in part to make it easier to debug the assembler output.

You can check out most of this (all of the handful of lines) yourself, apart from the new globals.rb which contains the meat in this method (in b88a31b):


      # Returns the actual name
      def set(fname, function)
        suffix = ""
        i = 0
        while @global_functions[fname + suffix]
          i += 1
          suffix = "__#{i}"
        end
        fname = fname + suffix
    
        # add the method to the global list of functions defined so far
        # with its "munged" name.
        @global_functions[fname] = function
        fname
      end

All this does is append __ to a desired global function name and return the (possibly munged) name.

The reason we need to do this is that we now of course can have multiple Foo#bar methods at various stages of the execution.

New class object vs. re-opening

I also snuck in another minor change in the preceding commit (b88a31b)

To allow re-opening classes, we need to not blindly create new class objects as we did before (though we're still assuming the class and its name is/was possible to determine statically. This is the change, which basically wraps an if check around the old version:


    -    compile_exp(scope, [:assign, name.to_sym, [:sexp,[:call, :__new_class_object, [cscope.klass_size,superclass,ssize]]]])
    +    compile_eval_arg(scope, [:if,
    +                             [:sexp,[:eq, name, 0]],
    +                             # then
    +                             [:assign, name.to_sym,
    +                              [:sexp,[:call, :__new_class_object, [cscope.klass_size,superclass,ssize]]]
    +                             ]
    +                            ])

Updating the class objects / vtable

Next up we assign two extra instance variable slots in the class objects:


      # slot 4 is reserved for subclasses
      # slot 5 is reserved for next_sibling
      CLASS_IVAR_NUM = 6

You'll find the remaining bits in 4733be0, and we'll look at lib/core/class.rb in more detail.

Firstly, this part of __new_class_object is new:


    # Sub-classes
      (assign (index ob 4) 0) 
      (if (eq superclass 0)
         (assign (index ob 5) 0)
         (do
            # Link in as subclass:
            (assign (index ob 5) (index superclass 4))
            (assign (index superclass 4) ob)
            )
    )

Basically it simply links this class into the list of sub-classes for it's superclass, by prepending it to the head.

The more interesting bit is __set_vtable. This was previously the over-simplistic:


    %s(defun __set_vtable (vtable off ptr)
      (assign (index vtable off) ptr)
      )

Now it looks like this:


    %s(defun __set_vtable (vtable off ptr)
       (let (p)
        (assign p (index vtable 4))
        (while (sexp p)
           (do
              (if (eq (index p off) (index vtable off)) (__set_vtable p off ptr))
              (assign p (index p 5))
           )
        )
      (assign (index vtable off) ptr)
    ))

This boils down to this "pseudo-Ruby" which follows the algorithm sketched out earlier:


       p = vtable.subclasses
       while p
          if p[off] == vtable[off]; __set_vtable(p,off,ptr); end
          p = p.next_sibling
       end
       vtable[off] = ptr

And that's it!

Next up: Eigenclasses.

Writing a (Ruby) compiler in Ruby bottom up - step 41

Wed, 12 Nov 2014 01:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Messy further steps towards self-hosting

This part is going to be a hodge-podge of changes, as I walk through a good chunk of changes needed to prepare to compile the tokenization code in tokenizer.rb, and improves what we can handle from scanner.rb.

I'm going to start by briefly talking about this commit:

[part-41 d0ee180] Refactoring of tokenizer

This commit breaks tokenizer.rb into several separate files. And that was the starting point for this part. To identify what I had to do, I broke apart the Tokenizer module, and wrote a few small scripts to see what compiled, and what crashed. E.g:


    require 'selfhost/atom'
    require 'selfhost/scanner'
    
    s = Scanner.new(STDIN)
    
    i = Tokens::Atom.new
    
    puts i.expect(s)

(I haven't checked in the "selfhost" directory - the files there are mostly like the broken up tokenizer.rb)

The purpose was to tweak the classes however much I needed to compile them, then fix or tweak until I got them mostly working, based on whatever errors I run into.

The purpose of this is of course to get one step closer to the first big "selfhosting" goal of being able to run the s-expression parser.

Rather than following the entire process, which was simple yet tedious, I'll walk through the most important commits, and simply list the others.

A number of minor tweaks

I'm going to skip over these, other than mentioning the commits. They are all important, but trivial. If you have any questions about them, I'm happy to answer comments:

[part-41 8fe7103] Add FalseClass#to_s
[part-41 79d39f4] Add TrueClass#to_s
[part-41 e31a44e] Added first stab at NilClass#==
[part-41 814b520] Naive / incomplete (base 10 only) version of String#to_i
[part-41 2f8ecb7] Absent #is_a? etc., adding explicit nil check in Fixnum#== as a temporary hack to get the parser closer to self-hosted
[part-41 7ae9623] Replace += with << in tokenizer and scanner; partly because it may be more efficient, partly because it removes an obstacle to self-hosting
[part-41 6f1c5a1] Let get_arg transparently convert true/false to :true, :false
[part-41 7429885] Fixed handling of quoted strings in asm output
[part-41 72d255e] Prevent 'require' loops by 'registering' the required file as empty at the outset
[part-41 ffda923] Added String#+
[part-41 a1af1fb] Assume :assign outside %s() returns an object

Valid return addresses for empty methods

[part-41 7b4cf91] Ensure a valid return value for empty method (caused String#to_i to seg fault)

Until now, if a method did not specify a return value, we'd leave garbage in %eax. Ruby does in fact require nil to be returned in most instances where there's not a sane last expression value to depend on.

The case of the argumentative not operator

For a while I was baffled at why the not-operator methods required an extra argument, and used workarounds:

[part-41 e2f6b37] Another workaround for not operator requiring arguments
[part-41 d734bb4] Added dummy/trivial not operator for String

Here I fixed it:

[part-41 1d54cec] Fix situation where not operator methods needed an argument

The specific line that fixes it was this from transform.rb:


         e[3] = E[e[2]] if e[2]

Previously this was done unconditionally, which meant that if e[2] was already an empty array, we wrapped it in another array and unintentionally gave a method call an extra, though invalid, argument.

Range class

[part-41 a18cdef] Add first trivial version of Range class + rewrite :range nodes in AST to Range.new(...)

The tokenizer classes relies on ranges in a number of locations. This commit takes a first tiny stab at a basic version of the Range class, and also adds support for literal ranges (1..5), through this bit added to transform.rb:


    +  def rewrite_range(exp)
    +    exp.depth_first do |e|
    +      if e[0] == :range
    +        STDERR.puts e.inspect
    +        e.replace(E[:callm, :Range, :new, e[1..-1]])
    +      end
    +      :next
    +    end
    +  end
    +

Quirks of parsing Ruby

[part-41 dbfe020] Function/method calls with arguments inside () or without parentheses have different needs for the priority of the call operator; we need to push a variation with a different priority onto the operator stack if we detect a method call without an opening parenthesis (caveat: Ruby has rules regarding whitespace here too, that I believe we're currently not taking into account)

What this is talking about (unfortunately the commit is really messy and includes unrelated whitespace and documentation changes etc - I was sloppy; sorry about that), is for example the difference between these expressions:


        foo(45 + 5)
        foo 45 + 5

Prior to this change, these were handled differently. The synthetic "call" operator used by the shunting yard parser needs a high priority to bind tightly to the function arguments. But in the absence of parentheses, this means it bound too tightly to the tokens immediately following, so that the latter example above would be treated as foo(45) + 5 because the call operator was given higher precedence than +.

This was resolved by introducing a second call operator, and in the instance where we are handling functions without a leading parenthesis, that operator (with much lower priority) is pushed onto the operator stack instead:


        if possible_func
          reduce(ostack)
    -     ostack << opcall
    +     ostack << @opcall2
        end

Correctly compiling "||"

[part-41 456a989] Improved comments / label names for #compile_if and fixed rather broken 'or' logic
[part-41 c288585] Rewrite compile_or to deal properly with shortcut logic, and in process do slight refactor to split out common functionality also used by compile_if and compile_while

As it turned out, my previous attempt at implementing || was completely broken. I don't know what I was thinking. All evidence is that I was not.

The original "||" implementation basically turned <left> || <right> into if <left>; false; else <right>; end. Which sort-of works, except it discards the result from <left>, which obviously isn't acceptable.

The first commit above improves that every so slightly by changing the implementation into the equivalent of this pseudo code:


      __left = <left>
      if __left
         __left
      else
         <right>
      end

But that really was not a very satisfying solution. So the next commit changes it drastically, and also refactors #compile_if and #compile_while, and at the same time takes a stab at handling our minimal static typing in a reasonable way. Here's how #compile_or changed:


       def compile_or scope, left, right
         @e.comment("compile_or: #{left.inspect} || #{right.inspect}")
    -    # FIXME: Eek. need to make sure variables are assigned for these. Turn it into a rewrite?
    -    compile_eval_arg(scope,[:assign, :__left, left])
    -    compile_if(scope, :__left, :__left, right)
    +
    +    ret = compile_eval_arg(scope,left)
    +    l_or = @e.get_local + "_or"
    +    compile_jmp_on_false(scope, ret, l_or)
    +
    +    l_end_or = @e.get_local + "_end_or"
    +    @e.jmp(l_end_or)
    +
    +    @e.comment(".. or:")
    +    @e.local(l_or)
    +    or_ret = compile_eval_arg(scope,right)
    +    @e.local(l_end_or)
    +
    +    @e.evict_all
    +
    +    combine_types(ret,or_ret)
       end

Which does roughly this, as pseudo-code:


        ret = <left>
        if !ret goto <label>_or
        goto <label>_end_or
    <label>_or:
        <right>
    <label>_end_or:

You'll note this is not optimal, we can improve on it by adding code to avoid one of the branches, but this was a decent shortcut to let it still share code with #compile_if and #compile_while.

#compile_jmp_on_false and #combine_types are worth a quick look. #compile_jmp_on_false extracts part of #compile_if as follows:


    +  def compile_jmp_on_false(scope, r, target)
    +    if r && r.type == :object
    +      @e.save_result(r)
    +      @e.cmpl(@e.result_value, "nil")
    +      @e.je(target)
    +      @e.cmpl(@e.result_value, "false")
    +      @e.je(target)
    +    else
    +      @e.jmp_on_false(target, r)
    +    end
    +  end

As you can see, the main reason it has been given its own method is to handle the case where we check the truthyness of an object.

#combine_types looks like this:


        +  def combine_types(left, right)
        +    type = nil
        +    if left && (!right || left.type == right.type)
        +      type = left.type
        +    end
        +    return Value.new([:subexpr],type)
        +  end

This was also extracted from #compile_if, and is responsible for ensuring the weaken the type information. Which is the fancy way of saying that if the type of the left hand expression matches that of the right hand expression, we return that type. Otherwise, we return "nil" in the type field, which in our current incarnation means "we have no clue, this could be anything" which means we won't take any object-specific action elsewhere.

Resolving Foo::Bar

[part-41 3a7e275] Add default implementations for new Scope#add_constant and Scope#find_constant
[part-41 6ceb215] Turn '::' into internal operator :deref, and add machinery to pre-build scope chain and traverse it to resolve class constant names at compile time where possible
[part-41 960f1b0] Make use of new inner classes support to bring test case closer to real Scanner implementation

Next up we need to handle inner classes. The first step is to actually capture Foo::Bar as different to Foo.bar, as it was previously. We do this by introducing the internal :deref operator in the parse tree in 6ceb215 in operators.rb:


    -  "::"        => Oper.new(100, :callm,    :infix, 2,2,:left),
    +  "::"        => Oper.new(100, :deref,    :infix, 2,2,:left),

The next step is a major change to build a sequence of class scope objects. Consider the case where I open a class, define a method that refers to an as yet undefined class. Then later I re-open the class and define the earlier class as an inner class:


    class Foo
       def hello
         Bar.new
       end
    end
    
    class Foo
       class Foo
         class Bar
         end
       end
    end

To handle this case, ClassScope objects must persist across open/close of a class, and they do. However, to compile this to static references, I also must identify any references and resolve them, to be able to distinguish a possible ::Bar from ::Foo::Bar without being forced to do runtime lookups (we still need to be able to fall back to dynamic constant lookup at some point in the future).

So lets take a look at the code, in transform.rb:


    +  def build_class_scopes(exps, scope = nil)
    +    scope = @global_scope if !scope
    +
    +    return if !exps.is_a?(Array)
    +
    +    exps.each do |e|
    +      if e.is_a?(Array)
    +        if e[0] == :defm && scope.is_a?(ClassScope)
    +          scope.add_vtable_entry(e[1]) # add method into vtable of class-scope to associate with class
    +
    +          e[3].depth_first do |exp|
    +            exp.each do |n|
    +              scope.add_ivar(n) if n.is_a?(Symbol) and n.to_s[0] == ?@ && n.to_s[1] != ?@
    +            end
    +          end

Firstly, above, we deal with method definitions, by identifying instance variables that are plainly mentioned (we still don't support dynamically generated ivars).

Then this bit was extracted from compile_class as we may as well allocate these earlier:


    +        elsif e[0] == :call && e[1] == :attr_accessor
    +          # This is a bit presumptious, assuming noone are stupid enough to overload
    +          # attr_accessor, attr_reader without making them do more or less the same thing.
    +          # but the right thing to do is actually to call the method.
    +          #
    +          # In any case there is no actual harm in allocating the vtable
    +          # entry.`
    +          #
    +          # We may do a quick temporary hack to synthesize the methods,
    +          # though, as otherwise we need to implement the full define_method
    +          # etc.
    +          arr = e[1].is_a?(Array) ? e[2] : [e[2]]
    +          arr.each {|entry|
    +            scope.add_vtable_entry(entry.to_s[1..-1].to_sym) 
    +          }

And then we handle the case of the class or module blocks themselves, by creating the ClassScope objects that will hold the scope information, and recursing, as well as finally recursing for all other AST node types:


    +        elsif e[0] == :class || e[0] == :module
    +          superclass = e[2]
    +          superc = @classes[superclass.to_sym]
    +          cscope = @classes[e[1].to_sym]
    +          cscope = ClassScope.new(scope, e[1], @vtableoffsets, superc) if !cscope
    +          @classes[cscope.name.to_sym] =  cscope
    +          @global_scope.add_constant(cscope.name.to_sym,cscope)
    +          scope.add_constant(e[1].to_sym,cscope)
    +          build_class_scopes(e[3], cscope)
    +        elsif e[0] == :sexp
    +        else
    +          e[1..-1].each do |x|
    +            build_class_scopes(x,scope)
    +          end
    +        end
    +      end
    +    end
    +  end

And at the top level in transform.rb we hook this step in early, starting by initializing the GlobalScope object, so we have something to hook the class scopes into:


       def preprocess exp
    +    # The global scope is needed for some rewrites
    +    @global_scope = GlobalScope.new(@vtableoffsets)
    +    build_class_scopes(exp)
    +

There are a number of smaller supporting changes, but lets just look at compile_deref that handles the new internal :deref node as a starting point:


    +  def compile_deref(scope, left, right)
    +    cscope = scope.find_constant(left)
    +    raise "Unable to resolve: #{left}::#{right} statically (FIXME)" if !cscope || !cscope.is_a?(ClassScope)
    +    get_arg(cscope,right)
    +  end

This simply delegates to the new find_constant methods in the scope classes, which for ClassScope recurses and builds a multi-level class name (e.g. Foo__Bar) - in classcope.rb:


    +  def find_constant(c)
    +    const = @constants[c]
    +    return const if const
    +    return @next.find_constant(@name+"__"+c.to_s) if @next
    +    return nil
    +  end

Rewriting :incr

[part-41 b3edea5] Rewrite :incr internal operator into += method call

There's not much to say about this. The whole change simply adds a small bit to treeoutput.rb that on coming across [:incr, :foo] insteads translates it into [:callm, :foo, :"+", right hand expression.

is_a?

[part-41 e19a85d] Support for #is_a?; also needed to add default Object#==, since comparison of object references is used in the #is_a? implementation

This implements a very basic #is_a? implementation that simply loops up the superclass chain.

It required the implementation itself, but also adding a basic Object#== that does pointer based comparison, and Class#superclass itself.

attr_reader / accessor / writer

[part-41 af00ab3] Filter out leading nil's where E[node.position, ....] is called and node does not have a position set

The above is a one-liner that helps debugging by ensuring the position doesn't get accidentally set to nil.

[part-41 ee85225] Quick and dirty attr_accessor / attr_reader / attr_writer implementation and minor bug fix (array index e[1] => e[2])
[part-41 83f0333] Made use of attr_reader / writer / accessor, and fixed += operator to bring test Scanner version closer in line with the real Scanner

A while back I was holding back on this awaiting a full define_method implementation, so I could do this in pure Ruby, but since I pulled back on that, it's time for a simple implementation since it helps actually get closer to compile the unmodified scanner. The bulk of is this in transform.rb, which simply injects one or two method definitions:


    +
    +          # Then let's do the quick hack:
    +          #
    +
    +          type = e[1]
    +          syms = e[2]
    +
    +          e[0] = :do
    +          e.slice!(1..-1)
    +          syms.each do |mname|
    +            mname = mname.to_s[1..-1].to_sym
    +            if (type == :attr_reader || type == :attr_accessor)
    +              e << E[:defm, mname, [], ["@#{mname}".to_sym]]
    +            end
    +            if (type == :attr_writer || type == :attr_accessor)
    +              e << E[:defm, "#{mname}=".to_sym, [:value], [[:assign, "@#{mname}".to_sym, :value]]]
    +            end
    +          end

Refactoring

I won't comment further on these:

[part-41 0084643] Refactored *Scope classes into separate files
[part-41 d9d9d2b] Refactoring: Split compiler driver out into separate file
[part-41 7fe231b] Refactored out code related to compiling function and method calls
[part-41 2da30b5] Refactoring
[part-41 083d0b5] Additional refactoring

Next steps

My current plans (subject to changes):

Part 42 will cover re-opening classes
Part 43 will cover Eigenclasses.
Part 44 will wrap up a few niggling issues with compiling the tokenization code, such as named block arguments (&block), possibly Struct, and any other small issues required for self-hosting
Part 45 will start to attack ParserBase. The most likely subject is #send and according method lookup machinery (this also affects the main Compiler class). There's also the issue of exceptions, though I'm unsure if I want to deal with that yet, as well as #include'ing modules.
Part 46-50 - by this point I expect to wrap up self-hosting of the s-expression parser, and start attacking the operator precedence parser. At this point we should have gotten rid of the worst hindrances for full self-hosting, ad I hope to get there by part 50.

These may be hopelessly optimistic:

Parts 51-60 or so:

Parse (possibly not correctly) all of Rubyspec.
Run mspec (for Rubyspec)
Case studies of compiling (and fixing issues with) specific applications.
Yanking out "gas" and generate asm opcodes directly. JIT to support eval().
Refactoring towards better support for retargeting to another backend
Start on an x86-64 backend

Part 61-70 or so:

Optimization and re-targeting
Rubyspec compliance
A "review"/revisit of the major components

Writing a (Ruby) compiler in Ruby bottom up - step 40

Wed, 05 Nov 2014 01:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Untangling Expect

Next up in my attempt to self-host parts of the parser, is Scanner#expect. This was no fun, and this part again recounts a long string of attempts at addressing relatively small annoying issues that will seem disjoint and probably confusing, but possibly useful in showing some of the debugging approaches.

Diving in

The immediate problem with Scanner#expect is this curious line:


        return Tokens::Keyword.expect(self, str) if str.is_a?(Symbol)

It calls into Tokens::Keyword for no obvious reason. Because when we dig into Tokens::Keyword, we find that Tokens::Keyword.expect simply calls Atom.expect and compares the result with what it got passed in.

So in our case, the only result of going that route, instead of falling through to the rest of Scanner#expect is basically to turn the expected string into a Symbol on returning it.

Now, first of all, we don't need to call Tokens::Keyword.expect for that. I'm not quite sure why I did that. Secondly, the "proper" thing to do here is to just return a String anyway, or specifically a ScannerString, as that includes the position, allowing for better error reporting.

The only place I find that depend on a specific value returned from expect is a line that uses ParserBase#expect with three symbols, which again call Scanner#expect with each in turn (I'm itching to optimize, but it's not for now), and uses that to determine what expression to return (:if, :while, or :rescue nodes). But that piece of code actually calls #to_sym on the result...

So, we're going to clean up Scanner#expect to simply call #to_s on objects that don't respond to #expect, and treat it as we do strings in f190425 :


    
       def expect(str,&block)
         return buf if str == ""
         return str.expect(self,&block) if str.respond_to?(:expect)
    -    return Tokens::Keyword.expect(self, str) if str.is_a?(Symbol)
    +
    +    str = str.to_s
         buf = ScannerString.new
         buf.position = self.position
         str.each_byte do |s|
    @@ -102,6 +103,7 @@ class Scanner
           end
           buf << get
         end
    +
         return buf
       end

And the problems pile up...

Firstly, our number of arguments check does not handle an explicit block argument as optional.

Comment out that for now, and I get "Method missing: Symbol#==" when testing Scanner#expect by calling expect(:rescue).

I've added one in 4292c34 - it's trivial, just comparing the string values This version is inefficient; part of the value of Symbol in Ruby is that it does not need to have the cost of String for comparisions, but it's functionally sufficient for now. A better way of handling it is to ensure Symbol objects are unique per symbol (so we can depend on just a pointer comparison), or at least obtain a unique id for any given string and compare that (which would be closer to how MRI is doing it); we'll revisit that again some day (not soon).

Next up, I stub out String#is_a?, since Scanner#expect depends on it. I just make it return true, which will obviously cause problems later. We don't yet have exactly what we need to implement it properly. See 284d493

Then I ran into a segmentation fault. Some poking reveals several possible causes.

One clear candidate is that String#initialize by default uses a null pointer, but that'd force us to check for null all over the place. And indeed, String#length doesn't. Rather than adding null checks all over, we fix String#initialize in 7b5805b.

Default nil from blocks

We also need to add something to String#reverse so what's returned is at a bare minimum a viable object. The obvious answer here would be to implement it, and we will, but first we should solve the reason this crashes:

As it turns out, when we compile an empty array of expressions, we return junk: Whatever is in %eax. Thankfully this is trivial to fix the most obvious cases of. In Compiler#compile_do we do this (in c359ea7ca) :


    diff --git a/compiler.rb b/compiler.rb
    index 751c34b..dfcd253 100644
    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -649,6 +649,10 @@ class Compiler
     
       # Compiles a do-end block expression.
       def compile_do(scope, *exp)
    +    if exp.length == 0
    +      exp = [:nil]
    +    end
    +
           exp.each { |e| source=compile_eval_arg(scope, e); @e.save_result(source); }
         return Value.new([:subexpr])
       end

String#reverse

Great! Now we fail on NilClass#length due to the empty String#reverse. So lets add a basic version. Not the most inspired, nor most Ruby-ish implementation, but it has the benefit that it works with the current state of the compiler (in 9a363ee):


    diff --git a/lib/core/string.rb b/lib/core/string.rb
    index 0cbba12..d118d91 100644
    --- a/lib/core/string.rb
    +++ b/lib/core/string.rb
    @@ -130,6 +130,16 @@ class String
     
     
       def reverse
    +    buf = ""
    +    l = length
    +    if l == 0
    +      return
    +    end
    +    while (l > 0)
    +      l = l - 1
    +      buf << self[l].chr
    +    end
    +    buf
       end

String#<<

The next error I ran into was this:

WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.
WARNING:    Method: '&lt;6a5ffde) since we don't have support for method aliases (method aliases are actually quite

straight forward to implement in this case: We 'just' need to update the vtable pointers; the only complication is that since this effectively means re-opening the class, it may have been sub-classed, in which case we need to update the sub-classes vtables as well; we'll deal with this properly once we "have to" deal with class re-opening).

String#count

The scanner uses String.count(character) to count the number of instances of LF (ASCII 10) to determine how to adjust the line number. We don't care about this for now, so I just give it an argument that defaults to nil, and make it return 1 (in f41af6b)

Now my test program runs all the way through, but it doesn't do much.

Adding String#each_byte, and the fallout

The big deal is the missing String#each_byte which the Scanner class uses to check the stream against each byte in the expected string. We fill in a basic version like this (in b7879ee):


    diff --git a/lib/core/string.rb b/lib/core/string.rb
    index b89ae2c..51dba30 100644
    --- a/lib/core/string.rb
    +++ b/lib/core/string.rb
    @@ -82,6 +82,13 @@ class String
       end
    
       def each_byte
    +    i = 0
    +    len = length
    +    while i <  len
    +      yield(self[i])
    +      i = i + 1
    +    end
    +    self
       end

Boom. Back to segmentation faults. The most obvious culprit is yield.

Replacing the yield with __closure__.call(self[i]), using what should eventually be a "hidden" internal variable name for the block argument, we quickly run into a different error, but one that makes it clear that yield doesn't work. This is another unfortunate regression. As it turns out we can now reduce yield to this, though:


      # Yield to the supplied block
      def compile_yield(scope, args, block)
        @e.comment("yield")
        args ||= []
        compile_callm(scope, :__closure__, :call, args, block)
      end

But while this makes yield and __closure__.call() equivalent, it does not make it work with an argument.

Splat handling, again ##

This is one of those little overcomplicated bits that badly needs to be re-thought. Basically, whenever we come across *rest in a method, we do a raw copy of it onto the stack for the call we expect to currently be preparing for.

Except *rest can occur anywhere. And it can be used for things that does not refer to the argument list from the calling function. Except that will fail horribly.

Basically this is a hack that is quickly overstaying its welcome. Particularly because the current solution is error prone. We'll give it this one last chance, before getting rid of it.

There are two glaring problems with the current code: Firstly, it doesn't handle the case where there are no arguments properly. Secondly, I actually confused the parameters provided to the method/function being called, with the arguments provided to the method we're currently in.

This has worked, sort of, as long as the methods have sufficiently similar signatures, which is why I haven't spotted it previously.

I've fixed it like this (in 58c4373):


    diff --git a/splat.rb b/splat.rb
    index 65cf0f9..a7c1b46 100644
    --- a/splat.rb
    +++ b/splat.rb
    @@ -20,7 +20,10 @@ class Compiler
         # (needs proper register allocation)
                         @e.comment("*#{args.last.last.to_s}")
         reg = compile_eval_arg(scope,:numargs)
    -    @e.subl(args.size-1,reg)
    +
    +    # "reg" is set to numargs - (number of non-splat arguments to the *method we're in*)
    +    m = scope.method
    +    @e.subl(m.args.size-1,reg)
         @e.sall(2,reg)
         @e.subl(reg,@e.sp)

The above is the critical bit that takes the correct argument length.

And this changes the loop that copies, so that we jump to the end and do the check against the end condition first to handle the case of zero arguments to copy:


    @@ -32,16 +35,25 @@ class Compiler
           
           @e.with_register do |dest|
             @e.movl(@e.sp,dest)
    -        l = @e.local
    +        lc = @e.get_local
    +        @e.jmp(lc) # So we can handle the zero argument case
    +
    +        ls = @e.local
             @e.load_indirect(reg,@e.scratch)
             @e.save_indirect(@e.scratch,dest)
             @e.addl(4,@e.result)
             @e.addl(4,dest)
    +
    +        @e.local(lc)  # So we can jump straight to condition
             @e.cmpl(reg,argend)
    -        @e.jne(l)
    +        @e.jne(ls)
    +
    +        # At this point, dest points to the position *after* the
    +        # splat arguments. Subtracting the stack pointer, and shifting
    +        # right twice gives us the number of splat arguments
    +
             @e.subl(@e.sp,dest)
             @e.sarl(2,dest)
    -        @e.subl(1,dest)
             @e.movl(dest,@e.scratch)
            @e.comment("*#{args.last.last.to_s} end")

The above also depends on some minor changes to the classes in scope.rb, which now have finally gotten a shared superclass. FuncScope have had a #method method that returns the Function object. The change introduced #method methods in all the scope classes, so that we can get at the method in question to figure out the argument length (in 58c4373 too)

We also need to "fix" compile_call, as we're "abusing it" to implement yield, and it also needs to handle splats (we are long overdue a refactoring of compile_call and compile_callm, so we'll give that a gentle nudge by factoring out a tiny bit of code from it as well).

Here is the change that includes invoking handle_splat (in 8b013ef15a):


    diff --git a/compiler.rb b/compiler.rb
    index d77bf08..f09da08 100644
    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -489,6 +489,15 @@ class Compiler
       end
    
    
    +  # Push arguments onto the stack
    +  def push_args(scope,args, offset = 0)
    +    args.each_with_index do |a, i|
    +      param = compile_eval_arg(scope, a)
    +      @e.save_to_stack(param, i + offset)
    +    end
    +  end
    +
    +
       # Compiles a function call.
       # Takes the current scope, the function to call as well as the arguments
       # to call the function with.
    @@ -504,15 +513,17 @@ class Compiler
    
         args = [args] if !args.is_a?(Array)
         @e.caller_save do
    -      @e.with_stack(args.length, true) do
    -        args.each_with_index do |a, i|
    -          param = compile_eval_arg(scope, a)
    -          @e.save_to_stack(param, i)
    +      handle_splat(scope, args) do |args,splat|
    +        @e.comment("ARGS: #{args.inspect}; #{splat}")
    +        @e.with_stack(args.length, !splat) do
    +          @e.pushl(@e.scratch)
    +          push_args(scope, args,1)
    +          @e.popl(@e.scratch)
    +          @e.call(compile_eval_arg(scope, func))
             end
    -        @e.movl(args.length, :ebx)
    -        @e.call(compile_eval_arg(scope, func))
           end
         end

Yet more is needed to make this work properly, as we did not handle arguments to Proc#call previously.

Fixing Proc

I will repeat the entirety of the "new" Proc here, as it's not very large. The main change is that instead of continuing to expand the __new_proc function, I've followed the approach taken in many of the other classes and added a #__set_raw method, with the intent of eventually preventing access to this method from regular Ruby.

Other than that, the main difference, and the point of changing the class, is to make use of the fixed splat support to allow arguments, and at the same time attack another problem we'd run into shortly: self.

The "old Proc executed the block with self bound to the instance of Proc itself, which does not work very well if the block tries to run methods on the object it was defind in. So now we pass in the value that should be bound to self as well.

Also note the warning at the end of #call. This has a very good reason, which will be addressed in the next section.

You can find this in 226e24f


    class Proc
      def initialize
        @addr = nil
        @env  = nil
        @s    = nil  # self in block
      end
    
      # We do this here rather than allow it to be
      # set in initialize because we want to
      # eventually "seal" access to this method
      # away from regular Ruby code
    
      def __set_raw addr, env, s
        @addr = addr
        @env = env
        @s = s
      end
    
    
      def call *arg
        %s(call @addr (@s 0 @env (splat arg)))
    
        # WARNING: Do not do extra stuff here. If this is a 'proc'/bare block
        # code after the %s(call ...) above will not get executed.
      end
    end
    
    %s(defun __new_proc (addr env self)
    (let (p)
       (assign p (callm Proc new))
       (callm p __set_raw (addr env self))
       p
    ))

There's also a minor change to transform.rb to ensure __new_proc is called with a self value to assign to the Proc object:


    diff --git a/transform.rb b/transform.rb
    index 22f3efb..406ca30 100644
    --- a/transform.rb
    +++ b/transform.rb
    @@ -25,7 +25,7 @@ class Compiler
                 E[:self,:__closure__,:__env__]+args,
                 body]
             ]
    -        e[2] = E[exp.position,:sexp, E[:call, :__new_proc, E[:__tmp_proc, :__env__]]]
    +        e[2] = E[exp.position,:sexp, E[:call, :__new_proc, E[:__tmp_proc, :__env__, :self]]]
           end
         end
       end

We have two minor little bits to add after this: Fixnum#! and String#ord which I've added in a93f95e.

And then it's on to one more larger change before we're done:

Return from blocks

Ruby semantics is that a "return" from a block exits the method that calls the block. That doesn't currently work for us, because a block gets compiled into a C-style function that takes some extra arguments.

A solution is to put the return address into the environment, and treat a return as a goto __env__.__return_address__ of sorts.

Another complication is that when you use lambda to create Proc object, a return inside the block does seemingly not exit the defining method. But another way of seeing it, it that the return does exit Proc#call. This is a useful realisation, since for the time being at least, we've been creating Proc objects for simplicity.

There are a few ways around this difference:

Create a different class for "plain" blocks that can handle the call accordingly.
Don't create a class for "plain" blocks, at all, but pass around a "raw" tuple of the address and environment of some sort.
Change how we create he Proc objects, so that the return address for "proper" Proc objects explicitly instantiated, or created via lambda, gets the following instruction in Proc#call set as its address for explicit returns.

I'm sure there are other options too.

One additional complication: If you return a block as a Proc, and it has a return inside, it will raise a LocalJumpError exception, so ideally we should be able to recognize this case, though we will defer that for later.

We'll opt for storing what we need to return out of the defining scope on creation of the object. We'll also make a block act as the proc keyword (which we don't currently support). Note that there are additional complications: We're meant to nil out missing arguments, and ignore excess arguments rather than do strict argument checking as well. Those will have to wait.

The approach chosen will absent additional work make things go badly haywire if we commit the sin of returning a Proc by returning a bare block / or Proc.new/proc result (which we also doesn't support yet), since we can't yet detect it.

First of all, we will add a new low level operation: :stackframe, which will return the contents of %ebp. By restoring %ebp to that of the defining method, we can do a normal leave then ret sequence, and the stack pointer will be correctly adjusted, and the return address of the next instruction in the containing method will be used. Conversely, for non-proc blocks, a normal return will still be done, resulting in a return to Proc#call, which will again just return out in the calling scope.

Apart from adding it to @@keywords in Compiler, #compile_stackframe consists of just this (in e39ae721f48ed) :


      def compile_stackframe(scope)
        @e.comment("Stack frame")
        Value.new([:reg,:ebp])
      end

Above I've eluded to special handling of :return for :proc's. We do this in a new low level operation called :preturn that you can se below. In a little bit we'll then go through changes to transformations in transform.rb that rewrites :return nodes to :preturn as needed. But first #compile_preturn (still in e39ae721f48ed) :


      # "Special" return for `proc` and bare blocks
      # to exit past Proc#call.
      def compile_preturn(scope, arg = nil)
        @e.comment("preturn")
    
        @e.save_result(compile_eval_arg(scope, arg)) if arg
        @e.pushl(:eax)
    
        # We load the return address pre-saved in __stackframe__ on creation of the proc.
        # __stackframe__ is automatically added to __env__ in `rewrite_let_env`
    
        ret = compile_eval_arg(scope,[:index,:__env__,0])
    
        @e.movl(ret,:ebp)
        @e.popl(:eax)
        @e.leave
        @e.ret
        @e.evict_all
        return Value.new([:subexpr])
      end

__stackframe__ here is hardcoded to offset 0 of __env__ which isn't particularly clean, but it works. So first we reload %ebp from what is effectively __env__[0], then we pop the return value off the stack, and do a normal return. Simple and fast.

Here's our new #compile_proc... At the moment it's a pointless waste as it is pretty much identical to #compile_lambda. It will make more sense later, given the differences in how proc and lambda affect treatment of checking argument count etc. (e39ae721f48ed)


      # To compile `proc`, and anonymous blocks
      # See also #compile_lambda
      def compile_proc(scope, args=nil, body=nil)
        e = @e.get_local
        body ||= []
        args ||= []
    
        r = compile_defun(scope, e, [:self,:__closure__]+args,[:let,[]]+body)
        r
      end

Some minor additional static typing

To make accessing captured variables (variables defined outside of the block, but used inside it) work with our recent typing, we need to define the contents of __env__ apart from the stack frame to be of type :object. To do this reasonably cleanly, we add a tiny #lookup_type method which for now is a bit of a hack, but that allow us to expand the type lookups later (e39ae721f48ed) :


      # For our limited typing we will in some cases need to do proper lookup.
      # For now, we just want to make %s(index __env__ xxx) mostly treated as
      # objects, in order to ensure that variables accesses that gets rewritten
      # to indirect via __env__ gets treated as object. The exception is
      # for now __env__[0] which contains a stackframe pointer used by
      # :preturn.
      def lookup_type(var, index = nil)
        (var == :__env__ && index != 0) ? :object : nil
      end

For now this is only used in #compile_index:


       return Value.new([:indirect, r], lookup_type(arr,index))

Transformations

The above is still not enough to use :preturn and :proc. For starters, in a number of places we now check for both :lambda an :proc nodes.

Additionally, in the event we get a :proc, we call a new method to rewrite the body of the :proc to replace and :return nodes with :preturn:

(e39ae721f48ed)


    +        if e[0] == :proc && body
    +          body = rewrite_proc_return(body)
    +        end

#rewrite_proc_return looks like this:


      def rewrite_proc_return(exp)
        exp.depth_first do |e|
          next :skip if e[0] == :sexp
          if e[0] == :return
            e[0] = :preturn
          end
        end
        exp
      end

And in #rewrite_let_env we add __stackframe__ to the __env__:


          # For "preturn". see Compiler#compile_preturn
          aenv = [:__stackframe__] + env.to_a
          env << :__stackframe__

In addition there are a few minor changes to correctly pick up variable references that were left out.

Finally, in 927f173 I make a minor change to actually generate :proc nodes from bare blocks. I've not yet added support for the proc keyword itself, though that should be trivial.

Some final changes

e535b77 contains a number of test case updates to cover some of the above changes, as well as a bug fix that caused a number of vasted lines special casing on single-argument function/method calls. It also contains some minor refactoring to start reducing the coupling of the shunting yard parser to the higher level Ruby parser (eventually I'd like to extract a useful generic component from it, but the separation is also intended to make the next step of self-hosting easier).

The current state of the test scanner

You can find features/inputs/scanner6.rb in 36e3da5. This is the exact bastardized / cut down version of the scanner that compiles after the above changes. When run it tests #peek, #get, #unget and #expect (for some limited values of "tests" - many things will still not work). Compile and echo a suitable string in:

$ ./compile features/inputs/scanner6.rb
[...]
$ echo "forescue" | /tmp/scanner6
Got: 102 (PEEK)
Got: f (GET)
Got: o (GET2)
rescue
f
o
o
DONE

Parting words

The output from the scanner test code is hardly impressive for the amount of work put in so far, but more and more of the foundation is in place now, and as you can see from this part, apart from some hairy moments dealing with things like proc and yield, an increasing number of the fixes are a matter of small additions to our highly under-developed version of the Ruby standard library rather than gnarly low level compiler code.

As a result I expect progress towards self-hosting to be faster for each coming part.

There's certainly still plenty of gnarly low level compiler code left to do, such as re-opening of classes, proper handling of method-missing and send, as well as attr_accessor/reader/writer, define_method (again...), module, class methods and include. (I'm sure there are many more that I'm repressing too...), but even much of that should be simpler than what we've gone through over the last couple of parts.

The next part too will be fairly messy, but then we'll have soother sailing for a few rounds as I'll be covering more focused features again.

Eight Docker Development Patterns

Wed, 22 Oct 2014 02:00:00 +0000

In the past I've written about my "home cloud" that used to be OpenVz containers, and how I've come to advocate rebuilding the "build server" for every build

Docker has quickly become one of my favorite enabling tools for this overall philosophy of creating repeatable builds that results in as-static-as-possible server environments.

Here I will outline some patterns that have started to show up repeatedly in my use of Docker. I don't expect any of them to be particularly novel or any big surprises, but I hope some can be useful, and I would very much like to hear from others about patterns you come across while working with Docker.

A foundation for all of my Docker experiments, is keeping state that should persist in volumes, so that the Docker containers themselves can be re-created at will without data loss (unless I've been naughty and modified container state without updating the Dockerfile's - and regularly rebuilding the containers helps stop that bad habit).

The examples Dockerfiles below are all focused on that: Creating containers where the containers themselves can be replaced at any time without having to think about it.

The more regularly the containers are recreated; the more habitual this becomes, the more it reinforces a habit of avoiding state outside of clearly defined locations that are explicitly persisted.

1. The Shared Base Container(s)

Docker encourages "inheritance" so this should not come as a surprise - it is a fundamental aspect of effectively using Docker, not least because it contributes to reducing the time it takes to build new containers by not having to re-execute steps as often. Docker does a good job - sometimes too good - of trying to cache intermediate steps, but it is easy to lose out on opportunities for sharing when not being explicit about it.

One of the first things that became apparent on migrating my various containers to Docker was the amount of redundant setup.

I run separate containers for most projects that I expect to ever deploy anywhere, at least the moment it needs any long running processes, or needs any specific packages beyond my "standard" set, so I have many containers, and the set is rapidly growing.

To the point where I'm considering moving towards trying to run "everything" (including the few desktop apps I depend on) in Docker in order to make mybase environment entirely disposable.

So I quickly started extracting my basic setups into base containers for various purposes. Here's my current "devbase" Dockerfile:


    FROM debian:wheezy
    RUN apt-get update
    RUN apt-get -y install ruby ruby-dev build-essential git
    RUN apt-get install -y libopenssl-ruby libxslt-dev libxml2-dev
    
    # For debugging
    RUN apt-get install -y gdb strace
    
    # Set up my user
    RUN useradd vidarh -u 1000 -s /bin/bash --no-create-home
    
    RUN gem install -n /usr/bin bundler
    RUN gem install -n /usr/bin rake
    
    WORKDIR /home/vidarh/
    ENV HOME /home/vidarh
    
    VOLUME ["/home"]
    USER vidarh
    EXPOSE 8080

There's nothing much special to note about it - it installs some specific tools I tend to like to always have available. These will presumably be different for most people. The distribution choice is pretty arbitrary. The one thing about it worth considering is to specify a specific tag to avoid surprises if/when you rebuild a container (and I need to get better at that too - I do it for the distributions, but I too rarely tag my own containers).

It exposes port 8080 by default, since that's where I usually expose my web apps, which is what I usually use these containers for.

It adds a user for me, and forces the userid to the user id I have on my server, and doesn't create a /home directory. This latter is because I bind mount a shared /home from the host. Which brings us to the next pattern:

2. The Shared Volume Dev Container

All of my dev containers share at least one volume with the host: /home. This is for ease of development. For many apps it lets me leave the apps running with a suitable file-system-change based code-reloader in dev mode, so that the containers encapsulate the OS/distro-level dependencies, and help verify that the app-as-bundled works in a pristine environment, without making me restart/rebuild the VM fully on every code change. Meanwhile I can, and do restart them fairly frequently to ensure that nothing slips past.

For the rest, it lets me just restart (rather than rebuild) the container to pick up code changes.

For test/staging and production containers I would in most cases avoid sharing code via volumes, and instead use "ADD" to add the code in question to the Docker container itself.

Here is the Dockerfile for my "homepage" dev container, for example, which contains my homegrown personal wiki, that draws on the already shared /home volume from my "devbase" container, and so showcases the shared base and how I use the shared /home volume:


    FROM vidarh/devbase
    WORKDIR /home/vidarh/src/repos/homepage
    ENTRYPOINT bin/homepage web

(note, I really should version tag my devbase container)

And for my dev-version of my blog:


    FROM vidarh/devbase
    
    WORKDIR /
    USER root
    
    # For Graphivz integration
    RUN apt-get update
    RUN apt-get -y install graphviz xsltproc imagemagick
    
    USER vidarh
    WORKDIR /home/vidarh/src/repos/hokstad-com
    ENTRYPOINT bundle exec rackup -p 8080

Because they pull in the code from a shared repository, and are based on a shared base container, these containers are in general extremely fast to rebuild when I add/modify/remove dependencies, which I find important in order to ensure I don't get tempted to resort to workarounds that leave undocumented dependencies.

Even so, there are certainly things I'd like to improve on. Even though the base for the above are lightweight, they could certainly be much more so: Most of what are in these containers remain unused. Since Docker uses copy-on-write overlays, this does not result in a huge overhead, but it does still mean I am not truly capturing the bare minimal requirements, nor minimizing the attack- or error-surface as much as possible. (I'm not so concerned about attack surface for these specific cases, as e.g. my blog does not maintain any important state in the "live" version that's not sitting in two git repositories in two other locations, and it gets overwritten on every push I do; but it's the principle)

3. The Dev Tools Container

This may be most attractive for those of us who like to rely on ssh to a screen session to work on code, and less for the IDE crowd, but for me, one of the nice things about the above setup is that it lets me separate out editing and test-executing parts of code from running the in-development application.

One of the annoying thing in the past for me with dev-systems have been that dev and production dependencies and development tool dependencies easily get co-mingled. You can try to keep them apart, but unless these setups are genuinely kept separated, it is all too easy to create undocumented dependencies by e.g. in a bind during debugging apt-get'ing strace or tcpdump - or even emacs - in an environment that does not really need it, and pull in a boatload of dependencies for the various tools at the same time.

In the past I had this driven home after spending weeks "reverse engineering" the dependencies of an application that had accreted all kinds of undocumented dependencies due to co-mingling of dev-environment, testing and initial prototype deployment environment.

While there are many ways of solving this by ensuring you do regular test-deployments, combined with the patterns above I have a solution I quite like because it prevents the problem from arising in the first place:

I have a separate container that contains my Emacs installation, and various other tools that I like to have available. I still try to keep it sparse, but the point is, my screen session can live in this container, and coupled with "autossh" set up on my laptop, there's pretty much always a running connection to it, where I can edit code that is shared "live" with my other dev containers.

This container is also one where I allow the occasional transgression of installing packages directly (with the caveat that if I want to keep them around, I need to put them in my Dockerfile, or they'll get blown away next time I rebuild) because it only affects debugging and development.

Currently it looks like this:

FROM vidarh/devbase
RUN apt-get update
RUN apt-get -y install openssh-server emacs23-nox htop screen

# For debugging
RUN apt-get -y install sudo wget curl telnet tcpdump

# For 32-bit experiments
RUN apt-get -y install gcc-multilib 

# Man pages and "most" viewer:
RUN apt-get install -y man most

RUN mkdir /var/run/sshd
ENTRYPOINT /usr/sbin/sshd -D

VOLUME ["/home"]
EXPOSE 22
EXPOSE 8080

Combined with the shared "/home", this gets me a sufficiently functional little place to ssh into. I'm sure I'll augment it as I use it more, but for now it has proven quite sufficient for my needs.

4. The Test In A Different Environment containers

One aspect of Docker I particularly love is the ease with which I can test my code in different environments. For example, when I upgraded my Ruby compiler project to handle Ruby 1.9 (much overdue), I created this trivial little Dockerfile to let me spawn a shell in a Ruby 1.8 environment after I'd transitioned my main dev environment to 1.9:

FROM vidarh/devbase
RUN apt-get update
RUN apt-get -y install ruby1.8 git ruby1.8-dev

Of course you can achieve a similar effect with rbenv etc.. But I've always found those tools annoying as I prefer to deploy as much as possible with distro-packages (as painful as that has been with Ruby in the past), not least because it makes it easier for others to use my code if I ensure that works smoothy.

Having a docker container that I can just "docker run" when I need a different environment for a few minutes solves the problem neatly, and also has the benefit that it is not constrained to things like Ruby that have pre-packaged custom tools to deal with versioning.

I could also achieve it with full VM's, as is the case for many of the things I describe, but I can start the above docker containers in far less time.

5. The Build Container

Most of what I write are in interpreted languages these days, but even then there are often useful "build" steps that are expensive enough that I'd prefer not to execute them all the time.

An example is running "bundler" for Ruby applications. Bundler updates cached dependencies for Rubygems (and optionally full gem files, or even unpacked contents) and it can take some time to run for a larger app.

It also often requires dependencies that are not needed at runtime for the application. E.g. installing gems that rely on native extensions can often depend on so many packages - often without documenting exactly which - that it's easier to just start by pulling in all of build-essential and it's dependencies. At the same time, while you can make bundler do all the work up-front, I really don't want to run it in the host environment that may or may not be compatible with the containers I want to deploy in.

A solution for this is to create a build container. You can create a separate Dockerfile if the dependencies are different, or you can reuse the main app Dockerfile and just override the command to run your desired build commands. E.g. the Dockerfile may look like this:

FROM myapp
RUN apt-get update
RUN apt-get install -y build-essential [assorted dev packages for libraries]
VOLUME ["/build"]
WORKDIR /build
CMD ["bundler", "install","--path","vendor","--standalone"]

Then run this while mounting your build/source directory in the containers "/build" directory whenever you have updated your dependencies. Replace as suitable.

The point is that you can decouple build of your applications, or parts of it from the final packaging, while still encapsulating both processes and their dependencies in Docker containers by breaking the process into two or more containers.

(I often check in the build artefacts, to be 100% certain I can reproduce the final packaging steps; an alternative is to do a full end-to-end build and test on a regular basis as well, to make sure the split accurately reflects th full process)

6. The Installation Container

This is not my own, but really deserves a mention. The excellent nsenter and docker-enter tools comes with an installation option that is a nice step forward from the popular but terrifying "curl [some url you have no control over] | bash" pattern. It does this by providing a Docker container that implements the "Build Container" pattern from above, but goes one step further. It deserves a look.

This is the last portion of the Dockerfile, from after it has downloaded and built a suitable version of nsenter (my one caveat is no integrity check of the downloaded archive):

ADD installer /installer
CMD /installer

"installer" looks like this:

#!/bin/sh
if mountpoint -q /target; then
       echo "Installing nsenter to /target"
       cp /nsenter /target
       echo "Installing docker-enter to /target"
       cp /docker-enter /target
else
       echo "/target is not a mountpoint."
       echo "You can either:"
       echo "- re-run this container with -v /usr/local/bin:/target"
       echo "- extract the nsenter binary (located at /nsenter)"
fi

While the potential is still there for a malicious attacker to try to exploit potential privilege escalation problems with containers, the attack surface is at least substantially smaller.

But the most likely immediate win for most of us with this pattern is to avoid the risk of wellmeaning developers who occasionally make very dangerous mistakes in installation scripts.

I really love this approach. And hopefully it will help curtail the abomination that is "curl [something] | bash", (but even if it doesn't, at least we can easily contain that within containers too...)

7. The Default-Service-In-A-Box Containers

While I relatively quickly if I get "serious" with an app will prep suitable containers to handle the database etc. for the project, I find it invaluable to have a series of "basic" infrastructure containers sitting there, with suitable tweaks for me to be able to spin up e.g. the database of my choice, or queueuing system of choice with suitable default settings.

Of course you can get "mostly there" by just trying "docker run [some-app-name]" and cross your fingers that there's a great alternative in the Docker index, and often there is. But I like to vet them first, and figure out e.g. how they handle data, and then I will be more likely to add my own tweaked version to my own "library".

E.g. I have one sitting around for Beanstalkd:

FROM debian:wheezy
ENV DEBIAN_FRONTEND noninteractive
RUN apt-get -q update
RUN apt-get -y install build-essential
ADD http://github.com/kr/beanstalkd/archive/v1.9.tar.gz /tmp/
RUN cd /tmp &amp;&amp; tar zxvf v1.9.tar.gz
RUN cd /tmp/beanstalkd-1.9/ &amp;&amp; make
RUN cp /tmp/beanstalkd-1.9/beanstalkd /usr/local/bin/
EXPOSE 11300
CMD ["/usr/local/bin/beanstalkd","-n"]

(For e.g. Postgres I have a vastly more complicated one that amongst others also set up persistent volumes for data, configuration etc.)

My goal is to be able to go "ok, I'm going to need memcached, postgres and beanstalk" and three quick "docker run"'s later have three containers up and running that are tweaked to my environment and personal preferences for a default environment, and ready to go. Setting up "standard" infrastructure components should be a 1 minute job rather than take away from the development itself.

8. The Infrastructure / Glue Containers

Many of these patterns focus on the development environment (and this means there's many more to discuss some other time for production environments), but there is one big category missing:

Containers whose purpose is to glue your environment together into a cohesive whole. This is an under-explored area for my part so far, but I will mention one particular example:

To enable easy access to my containers, I have a small little haproxy container. I have a wildcard DNS entry pointing at my home server, and an iptable entry opening up access to my haproxy container. The Dockerfile is nothing special:

FROM debian:wheezy
ADD wheezy-backports.list /etc/apt/sources.list.d/
RUN apt-get update
RUN apt-get -y install haproxy
ADD haproxy.cfg /etc/haproxy/haproxy.cfg
CMD ["haproxy", "-db", "-f", "/etc/haproxy/haproxy.cfg"]
EXPOSE 80
EXPOSE 443

The fun part here is the haproxy.cfg, which is generated by a script that generates backend sections like this from the output of "docker ps"

backend test
    acl authok http_auth(adminusers)
    http-request auth realm Hokstad if !authok
    server s1 192.168.0.44:8084

and a bunch of acls and use_backend statements in the frontend definition that dispatches [hostname].mydomain to the right backend.backend test.

If I wanted to be fancy, I'd deploy something like AirBnB's Synapse, but it has far more options than I need for my dev use.

For my home environment, this makes up most of my infrastructure needs. While at work I'm rolling out an increasing array of infrastructure containers whose purpose is to make deployment of the actual applications a breeze as I'm transitioning a full private cloud system towards Docker.

Writing a (Ruby) compiler in Ruby bottom up - step 39

Tue, 30 Sep 2014 04:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

To be or not to be nil

One of the big elephants sauntering around the room for a long time has been the issue of how to handle the specifics of how Ruby handles nil, true and false. To a lesser extent this issue also affects numbers, but it is those three values that are most critical right now.

The reason is control flow. So far, we've treated these values the way C does: nil is simply the null pointer; true is any non-zero value, and false is zero (and thus for most practical intents the same as nil.

The problem, of course, is that this is not the way it is in Ruby. true, false and nil are values distinct from the numbers, and they compare with each others and with other values in different ways than in C.

They are also objects. Which means we lose out on some of the simplest ways of doing comparisons and turning the comparison results into a value. We may find people doing things like if <some expression>.nil?.

nil and false both evaluate to false in a conditional, but nil != false.

So far "faking it" have worked, because with a few exceptions like the ones above, the C and Ruby variations are relatively compatible. But it's not a lasting solution.

There is another problem: If we change basic contructs like the s-expression if to work on Ruby objects, we'll find it hard to implement the "plumbing" under Ruby.

Introducing some static typing

Don't bring out the pickaxe just yet (groan). As it happens, our compiler compiles two very different languages: The s-expression inspired low level language used both as the compilation target for Ruby and implementation language for low level features, and Ruby itself.

The former language is de facto typeless, like BCPL: We pass values around with wild abandon, and we even clobber Ruby local variables and instance variables with it, but what meaning these values have depends entirely on usage rather than the type of the variable (as in C) or a type attached to the value itself, like in Ruby.

And as it happens, here lies both the problem and solution to our conundrum from above:

If only the compiler can know when it is dealing with real Ruby values, and when it is dealing with something else, then, e.g. compile_if can generate different code in these situations.

Not only that: We will need this information when we eventually get tired of leaking memory and start adding a garbage collector - otherwise we're stuck with a conservative collector, so we get twice the benefit.

It will also help us contain the "leakage" of untyped values into Ruby, by letting us define and narrow the rules for when and where and how we're allowed to work with them.

As it happens, we don't need a very complicated type-system: For now we can get away with knowing if a reasonable subset of constructs returns either an object or may contain anything.

That's it. That's the grand total of the static typing we'll introduce this time.

However the changes start laying the groundwork for more static typing that we can use for optimizations and sanity checks. Ultimately I wish to relegate the "s-expression plumbing" to a very restricted space.

Apart from just categorizing stuff into two types, there's another limitation too for now: Where we act on type information, we will treat all variables as typed to objects, and all return variables from method calls to be typed as objects. We will implicitly assume that the s-expression syntax will be contained, though we are not yet verifying that. In some cases this will be outright wrong. E.g. this explicitly prevents if foo; bar; end from working correctly if foo is not an object, and happens to contain 0, and in any number of similar instances, so it is likely introducing some regressions (I caught one while writing this - there are probably more).

Introducing Value

First, let's put some basic test cases in place. You'll find them in d22b95f

Then lets start putting our new typing into place. Let's start with a Value class to hold a possibly typed value (in 3ec81cb):


    require 'delegate'
    
    # Used to hold a possiby-typed value
    # Currently, valid values for "type"
    # are :object or nil.
    class Value < SimpleDelegator
      attr_reader :type
    
      def initialize ob, type = nil
        super(ob)
        @type = type
      end
    
      # Evil. Since we explicitly check for Symbol some places
      def is_a?(ob)
        __getobj__.is_a?(ob)
      end
    end

To simplify refactoring, we have it be a delegator, so we only selectively add/change behaviour as needed. For now, the only new thing is that #type will return the associated type tag, or nil. We only support :object for now, to indicate we know the value to be a pointer to a Ruby object.

I'm not going to go through ever detail of the changes in compiler.rb. You can find the full set in 0ded9c1

Apart from a number of changes to return objects of the new Value class, the main things to notice are as follows:

We add :false, :true, and :nil to @global_constants to prevent them from being treated as method calls:


    +    @global_constants << :false
    +    @global_constants << :true
    +    @global_constants << :nil

Next up is this change in compile_if:


    -    @e.jmp_on_false(l_else_arm, res)
    +
    +    if res && res.type == :object
    +      @e.save_result(res)
    +      @e.cmpl(@e.result_value, "nil")
    +      @e.je(l_else_arm)
    +      @e.cmpl(@e.result_value, "false")
    +      @e.je(l_else_arm)
    +    else
    +      @e.jmp_on_false(l_else_arm, res)
    +    end
    +

What's happening here is that instead of assuming an untyped value, we check to see if we know we have an object. If we do, and we come across "if result; ...; else ...; end", we change the code to effectively do the equivalent of:


       if result != nil && result != false
          # if block
       else
          # else block
       end

There's an equivalent change for compile_while.

Furthermore there's a few minor additional changes to scope.rb to prevent true/false/nil from being treated as method calls in 52f31ad3

We also need to check in transform.rb that we're not trying to treat true, false and nil as local variables. See f2af5fc

Changes to the runtime

In order to make these changes work, we also need to modify the runtime in various ways. Most obviously, we need to actually make true, false and nil real objects. We do that in lib/core/core.rb:


    +require 'core/true'
    +true = TrueClass.new # FIXME: MRI does not allow creating an object of TrueClass
    +require 'core/false'
    +false = FalseClass.new # FIXME: MRI does not allow creating an object of FalseClass
    +require 'core/nil'
    +nil  = NilClass.new # FIXME: MRI does not allow creating an object of NilClass.
    +
     # OK, so perhaps this is a bit ugly...
     self = Object.new
     
    @@ -59,9 +66,6 @@ STDERR = 1
     STDOUT = IO.new
     ARGV=7
     Enumerable=8 #Here because modules doesn't work yet
    -nil = 0      # FIXME: Should be an object of NilClass
    -true = 1     # FIXME: Should be an object of TrueClass
    -false = 0    # FIXME: Should be an object of FalseClass

These depends on very basic initial implementations of TrueClass, FalseClass and NilClass - see c356591

Another change is in lib/core/fixnum.rb, where all the comparison operators needs to change:


       def == other
    -    %s(eq @value (callm other __get_raw))
    +    %s(if (eq @value (callm other __get_raw)) true false)
       end

This is because %s(eq ..) etc. does not handle typing yet (and they may not necessarily ever need it), so we use our newly typed %s(if ..) coupled with explicitly returning the right objects instead of the numeric values we'd previously get.

It is important to do this in particular as one of the changes I snuck past in compiler.rb assumes that method calls returns Ruby objects.

Almost done now, but there's also a minor change to lib/core/object.rb to remove the horribly hacky true and false methods we used previously.

To be or not to be and more?

As it happens, we have a few more things to do: %s(and ..) and %s(or ...) needs to take type information into account to be able to generate proper code for e.g.:


        if a and b
            ...
        elsif a or c
            ...
        end

In our new world, a and b (or a && b) will always be true, because both true and false have integer values that are non-null. Similarly a or c / a || c will always be true as well, since both values will be seen to evaluate to true.

First of all, I've added a test case to catch this, in 1dfe043. But one of our other test cases shows a regression as well. features/inputs/strcmp.rb now gives wrong results, because we previously relied on being able to use "plain Ruby" if to check the result of a call to strcmp that we stored in a local variable. But for now at least, we're assuming variables contain objects. We'll likely want to refine that, but for now we'll apply a workaround that will work (in 32ddcde):


        %s(assign res (if (strcmp @buffer (callm other __get_raw)) false true))

By explicitly assigning with the values false or true, from the result of a value that will get an indeterminate type, it will work again.

But lets fix "&&"/"and". Firstly we need to actually store the return value from compile_eval_arg for if_arm and else_arm (in 2ae727d):


    -    compile_eval_arg(scope, if_arm)
    +    ifret = compile_eval_arg(scope, if_arm)
         @e.jmp(l_end_if_arm) if else_arm
         @e.local(l_else_arm)
    -    compile_eval_arg(scope, else_arm) if else_arm
    +    elseret = compile_eval_arg(scope, else_arm) if else_arm

Secondly, we need to determine type based on them. Most importantly, we can only safely return a type that is shared by both of them if both if and else are present (also in 2ae727d):


    -    return Value.new([:subexpr])
    +    # We only return a specific type if there's either only an "if"
    +    # expression, or both the "if" and "else" expressions have the
    +    # same type.
    +    #
    +    type = nil
    +    if ifret && (!elseret || ifret.type == elseret.type)
    +      type = ifret.type
    +    end
    +
    +    return Value.new([:subexpr], type)
       end

Other than that, we're simply just adding our missing compile_or:

(EDIT: This implementation is broken; a correct version will be in part 41)


    +  def compile_or scope, left, right
    +    compile_if(scope, left, false, right)
    +  end

And that's it for this time.

Writing a (Ruby) compiler in Ruby bottom up - step 38

Sun, 28 Sep 2014 13:50:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

I've been lazy again. Just today I realized that not only has it been two months since last post, but I still have one more post queued than I thought. I hope to clean up the next post in 2-3 weeks time, and another one in the following 2-3 weeks. I've actually just started preparing part 42..

Super

This time, I'm going to cover a small, simple change again for a change. Make this compile:


      class ScannerString < String
        def initialize str
          super(str)
          @position = 0
        end
      end

Which means implementing super. Conceptually this is easy. Consider that "under the hood", a method call effectively compiles to roughly the following pseudo code (imagine we're compiling to C instead of assembler). "self.bar(baz)" becomes:


        self->__class_pointer[offset_of_bar](baz)

(this assumes the method has a vtable slot, but we don't handle ones that don't yet, anyway)

We want to translate this into something like this:


        self->__class_pointer->__super_class_pointer[offset_of_bar](baz)

In other words: We find the pointer to the Class object, and then we need to look up the super-class of that class.

A quick aside about eigenclasses

If you're experienced with Ruby, you've probably at least heard of eigenclasses or metaclasses.

An eigenclass in Ruby is a class that is private to the instance. This may look like a complicating factor, especially since if you call #class on an object after defining a method on the eigenclass, you still get the same class as before. But what actually happens is that the eigenclass is added into the inheritance chain, but "hidden" from certain types of lookup.

For method calls, everything is as before, so we continue to ignore eigenclasses (at this point it looks like I'll cover that in part 42 or 43)

Getting the superclass

First things first: We currently don't actually store a pointer to the super-class anywhere.

In lib/core/class.rb, we handle the storage (in b05160c):


      (assign (index ob 3) superclass)

We then increase ClassScope::CLASS_IVAR_NUM in scope.rb. At the same time, we add a #method method that will be needed to get the name of the method we're currently compiling, in order to compile a call to the super-class version of the method correctly.

compile_super and friends

Next, we add the function/method name Function, which includes a few changes to actually pass it when it is known. But the real work gets done by Compiler#compile_super which we'll look at shortly, and this new line in #compile_call (in cd29057):


     +    return compile_super(scope, args,block) if func == :super

This is because super-calls will look like receiver-less method-calls, which are handled by compile_call.

And here's #compile_super:


      # Compiles a super method call
      #
      def compile_super(scope, args, block = nil)
        method = scope.method.name
        @e.comment("super #{method.inspect}")
        trace(nil,"=> super #{method.inspect}\n")
        ret = compile_callm(scope, :self, method, args, block, true)
        trace(nil,"<= super #{method.inspect}\n")
        ret
      end

It pulls the name of the surrounding method, and then calls #compile_callm, with an added new flag. Other than that it's debugging/tracing only. The new flag to #compile_callm is do_load_super. #compile_callm changes like this:


    -  def compile_callm(scope, ob, method, args, block = nil)
    +  def compile_callm(scope, ob, method, args, block = nil, do_load_super = false)

and this:


      load_class(scope) # Load self.class into %eax
    + load_super(scope) if do_load_super

and finally, #load_super looks like this:


    +  # Load the super-class pointer
    +  def load_super(scope)
    +    @e.load_instance_var(:eax, 3)
    +  end

Basically #load_super depends on the hardcoded slot for the super class pointer as an instance variable. Note: We could alternatively expose this pointer as a instance variable of some sort, but this keeps it anonymous and inaccessible (keep in mind that asking for the super-class is different to following this field, as following the inheritance chain from Ruby excludes eigenclasses, and also modules.

Are we there yet?

Not quite. We're going to make string take an optional argument to #initialize too, in order to be able to handle the example I started with.

Here is the change we make (in 55d076e). See the comments inline.


     class String
    -  def initialize
    +  # NOTE
    +  # Changing this to '= ""' is likely to fail, as it
    +  # gets translated into '__get_string("")', which
    +  # will do (callm String new), leading to a loop that
    +  # will only terminate when the stack blows up.
    +  #
    +  # Setting it "= <some other default>" may work, but
    +  # will be prone to order of bootstrapping the core
    +  # classes.
    +  #
    +  def initialize *str
         # @buffer contains the pointer to raw memory
         # used to contain the string.
         # 
    @@ -13,7 +23,13 @@ class String
         # 0 outside of the s-expression eventually will
         # be an FixNum instance instead of the actual
         # value 0.
    -    %s(assign @buffer 0)
    +
    +    %s(if (lt numargs 3)
    +         (assign @buffer 0)
    +         (do 
    +            (assign len (callm (index str 0) length))
    +            (callm self __copy_raw ((callm (index str 0) __get_raw) len)))
    +        )
       end

Next time

Next time it will be time to fix "nil". And since we're going there, maybe "true" and "false" too.

Writing a (Ruby) compiler in Ruby bottom up - step 37

Sat, 19 Jul 2014 19:27:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

(I will be at the Brighton Ruby Conference on Monday July 20th if you're attending and follow my series or just want to talk about Ruby in general, I'm happy to have a chat)

Default arguments

First order of business today is to get rid of this abomination from last time:


    # FIXME: ScannerString is broken -- need to handle String.new with an argument
    #  - this again depends on handling default arguments
    
        s = ScannerString.new
        r = ch.__get_raw
        s.__set_raw(r)

Essentially we want to be able to do both String.new and String.new "foo", and then inherit String with ScannerString, and use super to pass a String argument straight through to the super class constructory, so we can change the code above to:


        s = ScannerString.new(ch)

This shouldn't be too hard: We pass the argument count to methods, and


        def foo arg1, arg2 = "something"
        end

.. is equivalent to (pseudo code):


       def foo args
          arg1 = args[0]
          if <number of args> == 2
             arg2 = args[1]
          else
            if <number of args> == 1
               arg2 = "something"
            else
              [here we really should raise an exception]
            end
          end
       end

The overheads Ruby imposes for all the nice high level stuff should start to become apparent now...

We don't have support for raise yet, but we can at least output a message for the else case too while we're at it. Of course, the more arguments, the more convoluted the above will get, but it's not hard - we have %s(numargs) to get at the argument count, and we should be able to do this pretty much just with high level constructs.

A first naive approach

My first attempt was something like this:


    def foo arg1, arg2 = "default"
      %s(if (gt numargs 4) (printf "ERROR: wrong number of arguments (%d for 1)\n" (sub numargs 2))
           (if (lt numargs 3) (printf "ERROR: wrong number of arguments (%d for 1)\n" (sub numargs 2))
            (if (le numargs 3) (assign arg2 (__get_string "default"))))
             )
    
      puts arg1
      puts arg2
    end

Spot the mistake? It is slightly tricky. The problem is not in this function itself, but in how the arguments get allocated: Since the caller allocates space on the stack for the arguments, if arg2 is not being passed, then there's no slot for it, so we can't assign anything to it.

One way out of this is to allocate a local variable, and copy either the default value or or the passed in argument to the local variable, and then rewrite all references to arg2 to local_arg2 in the rest of the function.

Another variation is to instead of doing the rewrite, change the Function#get_arg method to allow us to "redirect" requests for the argument afterwards. We can do this similarly to how we reference numargs, by treating them as negative offsets

Parsing

We were getting ahead of ourselves. First lets update the parser. In 7bca9f3 I've added this to parse_arglist. Previously we just ignored the result of the call to the shunting yard parser. Now we keep it, and treat the argument differently if we have a default value:


        default = nil
        if expect("=")
          nolfws
          default = @shunting.parse([","])
        end
    
        if prefix then args = [[name.to_sym, prefix == "*" ? :rest : :block]]
        elsif default
          args = [[name.to_sym, :default, default]]
        else
          args = [name.to_sym]
        end

This change breaks a number of test cases, so there's also a series of updates to features/parser.feature

To make this work, we also need to slightly change transform.rb to actually handle these arrays in the argument list (which brings up the question of whether or not it might not be cleaner to modify the parser to store them uniformly, but lets leave that for later).


       def rewrite_let_env(exp)
         exp.depth_first(:defm) do |e|
    -      args   = Set[*e[2]]
    +      args   = Set[*e[2].collect{|a| a.kind_of?(Array) ? a[0] : a}]

Creating our own local variables

Note that I'm not particularly happy with the approach I'm about to describe. It feels a bit dirty. Not so much the concept, but the implementation. I'd love suggestions for cleanups.

But first, there's a test case in f25101b

Next, we turn our attention to function.rb. Function and Arg objects are instantiated from the data in the parse tree, and we now need to handle the arguments with :default in them.

We start by simply adding a @default in Arg (In 1a09e19 ). You'll note I've also added a @lvar that is not being set immediately, as this value will depend on the function object. But as the comment says, this will be used to let us "switch" this Arg object from referring to refer to a local variable that will effectively (and intentionally) alias the original in the case of defaults.


     class Arg
    -  attr_reader :name, :rest
    +  attr_reader :name, :rest, :default
    +
    +  # The local variable offset for this argument, if it 
    +  # has a default
    +  attr_accessor :lvar
    
       def initialize(name, *modifiers)
         @name = name
         # @rest indicates if we have
         # a variable amount of parameters
         @rest = modifiers.include?(:rest)
    +    @default = modifiers[0] == :default ? modifiers[1] : nil
       end

In Function, we add a @defaultvars that keeps track of how many extra local variable slots we need to allocate. In Function#initialize we change the initalization of the Arg objects, and once we've created it, we assign a local variable slot for this argument.


    +    @defaultvars = 0
         @args = args.collect do |a|
    -      arg = Arg.new(*[a].flatten)
    +      arg = Arg.new(*[a].flatten(1))
    +      if arg.default
    +        arg.lvar = @defaultvars
    +        @defaultvars += 1
    +      end

We then initialize @defaults_assigned to false. This is a new instance variable that will act as a "switch". When it is false, compiling request for an argument with a default will refer to the argument itself. So we're not yet aliasing. At this stage, we need to be careful - if we read the argument without checking numargs, we may be reading random junk from the stack.

Once we switch it to true, we're telling the Function object that we wish to redirect requests for arguments that have defaults to their freshly created local variables. We'll see how this is done when changing Compiler shortly.

Let's now look at get_arg and some new methods, in reverse order of the source, Function#get_arg first:


      def get_arg(a)
        # Previously, we made this a constant for non-variadic
        # functions. The problem is that we need to be able
        # to trigger exceptions for calls with the wrong number
        # of arguments, so we need this always.
        return [:lvar, -1] if a == :numargs

The above is basically a bug fix. It was a short-sighted optimization (I knew there was a reason why I don't like premature optimizations, but every now and again they are just too tempting) which worked great until actually getting the semantics right.

And this is the start of the part I'm not particularly happy with:


        r = get_lvar_arg(a) if @defaults_assigned || a[0] == ?#
        return r if r
        raise "Expected lvar - #{a} / #{args.inspect}" if a[0] == ?#
    
        args.each_with_index do |arg,i|
          return [arg.type, i] if arg.name == a
        end
    
        return @scope.get_arg(a)
      end

Basically, if the @defaults_assigned "switch" has been flipped, or we explicitly request a "fake argument", we call get_lvar_arg to try to look it up. If we find it, great. If not, we check for a normal variable. We feel free to throw an exception for debugging purposes if we're requesting a "fake argument", as they should only ever be created by the compiler itself, and should always exist if they've been created. The "fake argument" here is "#argname" if the arguments name is "argname". I chose to use the "#" prefix as it can't legally occur in an argument name, and so it's safe. It's still ugly, though.

Next a helper to process the argument list and yield the ones with defaults, and "flip the switch" when done:


      def process_defaults
        self.args.each_with_index do |arg,index|
          # FIXME: Should check that there are no "gaps" without defaults?
          if (arg.default)
            yield(arg,index)
          end
        end
        @defaults_assigned = true
      end

Last but not least, we do the lookup of our "fake argument":


      # For arguments with defaults only, return the [:lvar, arg.lvar] value
      def get_lvar_arg(a)
        a = a.to_s[1..-1].to_sym if a[0] == ?#
        args.each_with_index do |arg,i|
          if arg.default && (arg.name == a)
            raise "Expected to have a lvar assigned for #{arg.name}" if !arg.lvar
            return [:lvar, arg.lvar]
          end
        end
        nil
      end

Using our own local variables

in Compiler#output_functions (still in 1a09e19), we add a bit to actually handle the default argument:


    -        @e.func(name, func.rest?, pos, varfreq) do
    +        @e.func(name, pos, varfreq) do
    +
    +          if func.defaultvars > 0
    +            @e.with_stack(func.defaultvars) do 
    +              func.process_defaults do |arg, index|
    +                @e.comment("Default argument for #{arg.name.to_s} at position #{2 + index}")
    +                @e.comment(arg.default.inspect)
    +                compile_if(fscope, [:lt, :numargs, 1 + index],
    +                           [:assign, ("#"+arg.name.to_s).to_sym, arg.default],
    +                           [:assign, ("#"+arg.name.to_s).to_sym, arg.name])
    +              end
    +            end
    +          end
    +
    +          # FIXME: Also check *minium* and *maximum* number of arguments too.
    +

This piece basically allocates a new stack frame for local variables, and then iterates through the arguments with defaults; we then compile code equivalent to if numargs < [offset]; #arg = [default value]; else #arg = arg; end where "arg" is the name of the current argument.

Adding checks for minimum and maximum number of arguments

What should have been utterly trivial, given the above, turned into a couple of annoying debugging sessions, due to bugs that were in fact exposed once I started checking the argument numbers...

But let us start with the actual checks:


    +          minargs = func.minargs
    +
    +          compile_if(fscope, [:lt, :numargs, minargs],
    +                     [:sexp,[:call, :printf, 
    +                             ["ArgumentError: In %s - expected a minimum of %d arguments, got %d\n",
    +                              name, minargs - 2, [:sub, :numargs,2]]], [:div,1,0] ])
    +
    +          if !func.rest?
    +            maxargs = func.maxargs
    +            compile_if(fscope, [:gt, :numargs, maxargs],
    +                       [:sexp,[:call, :printf, 
    +                               ["ArgumentError: In %s - expected a maximum of %d arguments, got %d\n",
    +                                name, maxargs - 2, [:sub, :numargs,2]]],  [:div,1,0] ])
    +          end

These should be reasonably straightforward:

If the number of passed arguments is below a calculated minimum (we'll look at Function#minargs shortly), we printf an error.
If the number of passed arguments is below a calculated maximum, we'll printf another error - unless there's a "splat" (*arg) in the argument list, in which case the number of arguments is unbounded.
For now, I've just used 1/0 to trigger an floating point exception as a convenient way of exiting. I could have used int 1 or int 3, which are intended for debugging, but this is temporary until implementing proper exceptions, and I've not surfaced access to the int instruction to the mid-layer of the compiler, so this is a lazy temporary alternative.

In Function (function.rb), this is #minargs and #maxargs:


    +  def minargs
    +    @args.length - (rest? ? 1 : 0) - @defaultvars
    +  end
    +
    +  def maxargs
    +    rest? ? 99999 : @args.length
    +  end

(We could leave #maxargs undefined for cases where #rest? returns true, but really, we could just as well try to set a reasonable maximum - if it gets ridiculously high, it likely indicates a messed up stack again)

Fixing saving of caller saved registers

One thing that I wasted quite a bit of time with when adding the min/max argument checks was that this triggered a few lingering bugs/limitations of the current register handling.

The main culprit was the [:div, 1, 0] part. As it happens, because this forces use of %edx (if you remember, this is because on i386, idivl explicitly depends on %edx), which is a caller saved register, our lack of proper handling of caller saved registers caused spurious errors.

The problem is that Emitter#with_register is only safe as long as nothing triggers forced evictions of registers within the code it uses. This code is going to need further refactoring to make it safer. For now I've added a few changes to make the current solution more resilient (at the cost of sometimes making it generate even less efficient code, but it should long since have been clear that efficiency is secondary until everything is working).

The most important parts of this change is in Emitter and RegAlloc (in 3997a31)

Firstly, we add a Emitter#caller_save, like this:


      def caller_save
        to_push = @allocator.evict_caller_saved(:will_push)
        to_push.each do |r|
          self.pushl(r)
          @allocator.free!(r)
        end
        yield
        to_push.reverse.each do |r|
          self.popl(r)
          @allocator.alloc!(r)
        end
      end

This depends on an improvement of #evict_caller_saved that returns the registers that needs to be saved on the stack, because they've been allocated "outside" of the variable caching (for cached variables, we can "just" spill them back into their own storage locations, and reload them later, if they are referenced again). We then push them onto the stack, and explicitly free them, yield to let the upper layers do what it wants (such as generate a method call), and pop them back off the stack.

There's likely lots to be gained from cleaning up the entire method call handling once the dust settles and things are a bit closer to semantically complete - we'll get back to that eventually, I promise.

The new version of evict_caller_saved looks like this:


      def evict_caller_saved(will_push = false)
        to_push = will_push ? [] : nil
        @caller_saved.each do |r|
          evict_by_cache(@by_reg[r])
          yield r if block_given?
    
          if @allocated_registers.member?(r)
            if !will_push
              raise "Allocated via with_register when crossing call boundary: #{r.inspect}"
            else
              to_push << r
            end
          end
        end
        return to_push
      end

Basically, we iterate through the list of caller-save reigsters, and if we've indicated we intend to push the values on the stack, we return a list of what needs to be pushed. Otherwise we raise an error, as we risk losing/overwriting an allocated register.

You will see Emitter#caller_save in use in compiler.rb in #compile_call and #compile_callm, where it simply wraps the code that evaluates the argument list and calls themselves.

Other than that, I've made some minor hacky changes to make #compile_assign, #compile_index and #compile_bindex more resilient against these problems.

Splats and numarg revisited

The last, missing little piece is that it surfaced a bug in the handling of numargs with splats. In particular, once I added the min/max checks, the call to a class's #initialize triggered the errors, because this is done with ob.initialize(*args) in lib/core/class.rb, and it didn't set numargs correctly.

I'm not going into this change in detail, as it's a few lines of modifications to splat.rb, compiler.rb and emitter.rb. The significant part of the change is that the splat handling now expects to overwrite %ebx, as it should, and Emitter#with_stack will now set %ebx outright unless it is called after the splat handling, in which case it will add the number of "fixed" arguments to the existing "splat argument count" in %ebx.

(We'll still need to go back and fix the splat handling, as we're still not creating a proper array, and the current support only works for method calls)

Reflections on optimizations

While working on this, it struck me that a future optimization to consider is different entry-points for different variations of the method. While the caller does not really "know" exactly which method will be called, the caller does know how many arguments it has, and so knows that either there is an implementation of a method that can take that number of arguments, or it will trigger an ArgumentError (or should do when we add exceptions).

Thus, if we allocate vtable slots based on the number of provided arguments too, then static/compile-time lookups will fail for method calls where no known possible combination of method name / number of arguments is known at compile time, and it will fall back to the slow path (which we've not yet implemented).

The question of course is how much it would bloa the vtables. However this approach can also reduce the cost of the code, as we can jump past the numargs checks for the version where all arguments are specified etc.

Another approach is to decide on rules for "padding" the argument space allocated, so that the most common cases, of, say 1-2 default arguments can be supported without resorting to extra local variables. This saves some assignments.

Next time

... we'll fix super. Well, add it, as currently it ends up being treated as a regular method call.

Writing a (Ruby) compiler in Ruby bottom up - step 36

Fri, 27 Jun 2014 03:05:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Scanning for problems

Where we left off last time, we'd just barely scratched the surface of what it will take to self-host the Scanner.

This time we'll keep digging into that. I will skip or gloss over fixes to some bugs etc., and focus mostly on the bits that are filling in intentional omissions from earlier that are now finally coming back to bite us, with the exception of some particularly interesting (to me at least) bugs.

One of the bugfixes were actually pushed out with the previous branch. See e6ae4ba - this is worth at least a cursory note as it got the order in which we determined the size of an object instance vs. where I actually counted up the number of immediately visible instance variables wrong. Ouch.

By the time this version is out, I'll also have merged a bunch of fixes to make the code work with Ruby 1.9, finally.

But back to the Scanner code. This part ended up a lot more convoluted than I'd planned. I've skipped over some of the details of my debugging, as it got tedious to write and probably twice as much to read, with lots of jumping back and forth. Th

For the purposes of this series, I've added features/inputs/scanner4.rb which is a variation of the Scanner code and some minor test code that I will make work in this article. I'll walk through a few issues with it at the end.

ScannerString

In scanner.rb we define Scanner::ScannerString. ScannerString is "just" a subclass of String that allows us to have the scanner attach a Position to a token, which again allows us to add position information to the syntax tree for error reporting and debugging.

For this part we will lift ScannerString out of the Scanner class as embedded classes is not yet supported.

The next issue is our lack of attr_accessor. So we end up with this:


    class ScannerString < String
      # Instance variables in inherited classes did not work
    
      def initialize
        @position = 0 # Note: It's still awkward to use "nil", so we cop out for now.
      end
    
      # "=" was not handled correctly for vtable thunks?
      def position= newp
        @position = newp
      end
    
      def position
        @position
      end
    end

Compiling even this, however, proves a challenge, as per the inline comments above. The latter was just a trivial issue with the name handling. Test cases in 8cd9c18 and a one character fix (!) in 55b9d23

The former was trickier - I messed up in some subtle ways when I added the instance variable support that I missed by not testing with instance variables in sub-classes. I added a test case for this in e828033

In fixing this, I muddied things up a bit, and I've been too lazy to untangle the changes, as while tracking down these issues, I added some initial support for #inspect and getting hold of class names. We'll finish up that next, to not leave changes hanging.

In ca6f420 there are some minor changes in GlobalScope that follows from the changes in ClassScope - I'll ignore those - read the commit. The meat is in ClassScope in scope.rb (and later we'll look at changes to compiler.rb):


       @@ -186,14 +194,17 @@ class ClassScope
       #
       # slot 0 is reserved for the vtable pointer for _all_ classes.
       # slot 1 is reserved for @instance_size for objects of class Class
    -  CLASS_IVAR_NUM = 2
    +  # slot 2 is reserved for @name
    +  CLASS_IVAR_NUM = 3
    
    -  def initialize(next_scope, name, offsets)
    +  def initialize(next_scope, name, offsets, superclass)
         @next = next_scope
    +    @superclass = superclass
         @name = name
         @vtable = {}
         @vtableoffsets = offsets
    -    @instance_vars = [:@__class__] # FIXME: Do this properly
    +    @ivaroff = @superclass ? @superclass.instance_size : 0
    +    @instance_vars = !@superclass ? [:@__class__]  : [] # FIXME: Do this properly
         @class_vars = {}
       end

The bump in CLASS_IVAR_NUM is due to adding Class#name as mentioned above. More interestingly we now rectify a long standing omission: The scope chain did not keep track of superclass. We could look it up separately as needed, I guess, but we did not do that either. We now pass in a scope object that represents the super class.

We then assign @ivaroff to represent the offset that instance variables for this class start at. This bug is well into the "embarrassing" category. Without this, when we subclass a class, and add instance variables, the instance variables will get overlapping offsets, and overwrite each other. Oops.

Lastly, we set @instance_vars to start with @__class__ if there is no super class provided, to guarantee that we have a place to stash the class pointer (we could alternatively do this by setting @ivaroff to 1 in the same situation).

Next we ensure @ivaroff is included when we calculate the instance size, so we actually allocate enough memory for the instances too, unlike before (double-oops...)


    @@ -210,7 +221,7 @@ class ClassScope
       end
     
       def instance_size
    -    @instance_vars.size
    +    @instance_vars.size + @ivaroff
       end

Lastly, we ensure we return the right offset from the instance pointer in ClassScope:


    @@ -239,7 +250,14 @@ class ClassScope
           offset = @instance_vars.index(a)
           add_ivar(a) if !offset
           offset = @instance_vars.index(a)
    -      return [:ivar, offset]
    +
    +      # This will show the name of the current class, the superclass name, the instance variable 
    +      # name, the offset of the instance variable relative to the current class "base", and the
    +      # instance variable offset for the current class which comes in quite handy when debugging
    +      # object layout:
    +      #
    +      # STDERR.puts [:ivar, @name, @superclass ? @superclass.name : "",a, offset, @ivaroff].inspect
    +      return [:ivar, offset + @ivaroff]
         end

This isn't quite enough. We also need to update compile_class in compiler.rb:

First we obtain the pointer to the super class, and use that to properly initialize the class scope:


    @@ -635,7 +635,9 @@ class Compiler
       def compile_class(scope, name,superclass, *exps)
         @e.comment("=== class #{name} ===")
    
    -    cscope = ClassScope.new(scope, name, @vtableoffsets)
    +    superc = @classes[superclass]
    +
    +    cscope = ClassScope.new(scope, name, @vtableoffsets, superc)

Note that there's another shortcut here: Ultimately we need to compute this too, as people can do nasty stuff like dynamically picking a class, assigning it to a constant, and subclassing that, so even if we have something that looks like a class name, what we actually have is actually an expression that evaluates to the Class object of the class that should be the superclass. I don't remember if the parser will even allow that at the moment, and I'm not in the mood to fix even the "simple" case of someone assigning stuff to constants and expecting me to treat it as a class, so we'll continue to ignore this for now and stumble over it later.

Then we fix up the assignment to the Class instance for the new class. The inline comment says it all, really:


    @@ -679,7 +681,17 @@ class Compiler
         compile_exp(scope, [:assign, name.to_sym, [:sexp,[:call, :__new_class_object, [cscope.klass_size,superclass,ssize]]]])
         @global_constants << name
     
    -    compile_exp(cscope, [:assign, :@instance_size, cscope.instance_size])
    +    # In the context of "cscope", "self" refers to the Class object of the newly instantiated class.
    +    # Previously we used "@instance_size" directly instead of [:index, :self, 1], but when fixing instance
    +    # variable handling and adding offsets to avoid overwriting instance variables in the superclass,
    +    # this broke, as obviously we should not be able to directly mess with the superclass's instance
    +    # variables, so we're intentionally violating encapsulation here.
    +
    +    compile_exp(cscope, [:assign, [:index, :self, 1], cscope.instance_size])
    +
    +    # We need to store the "raw" name here, rather than a String object,
    +    # as String may not have been initialized yet
    +    compile_exp(cscope, [:assign, [:index, :self, 2], name.to_s])

But all of that is not enough to fix our test-case (features/inputs/ivar.rb) as it turns out - now the instances variables of Foo are undefined in instances of Bar, since Bar#initialize does not call super (nor have we implemented support for super yet...). We need to patch #puts to handle our "fake" nils (that are still actual null values), which once again demonstrates that I need to make a decision on exactly what to do about this (in 10d7c6e):


    --- a/lib/core/object.rb
    +++ b/lib/core/object.rb
    @@ -49,8 +49,12 @@ class Object
         i = 0
         while i < na
           %s(assign raw (index str (callm i __get_raw)))
    -      raw = raw.to_s.__get_raw
    -      %s(if raw (puts raw))
    +      if raw
    +        raw = raw.to_s.__get_raw
    +        %s(if raw (puts raw))
    +      else
    +        puts
    +      end

Adding Class#name to improve #inspect and "send" debug output

Since parts of this made it into the previous commits. e977bfc adds test cases, and this:


    --- a/lib/core/class.rb
    +++ b/lib/core/class.rb
    @@ -40,6 +40,10 @@ class Class
         ob
       end
     
    +  def name
    +    %s(__get_string @name)
    +  end
    +

As mentioned earlier, we store the name "raw" to avoid bootstrap issues with String.

Another insidious little bug reared its head when dealing with the debugging output. The method name needs to be the second argument, since the first argument is our "hidden" place to store any block that gets passed to a method:


    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -522,7 +522,7 @@ class Compiler
           if !off
             # Argh. Ok, then. Lets do send
             off = @vtableoffsets.get_offset(:__send__)
             -        args = [":#{method}".to_sym] + args
             +        args.insert(1,":#{method}".to_sym)
             warning("WARNING: No vtable offset for '#{method}' (with args: #{args.inspect}) -- you're likely to get a method_missing")
             #error(err_msg, scope, [:callm, ob, method, args])
           end

With that out of the way, our failure to handle "send" can now easily be made to produce more useful output for things like this:


    class Foo
    end
    
    f = Foo.new
    f.bar

As of 7fc23ae840 you get something like this, correctly identifying the class name and method:

WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.
WARNING:    Method: 'bar'
WARNING:    symbol address = 0x8a36750
WARNING:    self = 0x8a36740
WARNING:    class 'Foo'

And a first pass on a default #inspect in 8c74cd6. Clearly adding cleaner support for string formatting also needs to go on the big list of outstanding items:

  def inspect
    %s(assign buf (malloc 20))
    %s(snprintf buf 20 "%p" self)
    %s(assign buf (__get_string buf))
    "#"
  end

Chasing rabbits...

Like ScannerString, we'll lift Position out of Scanner. We also avoid using Struct, and so get to write a few lines extra.

Thanks to the changes above, we now get semi-useful debugging output, and get the dubious pleasure of chasing down missing piece after piece. With my "scanner test in progress" it warned of a missing String#empty? used in Scanner#fill. I added String#empty in 334902c.

Next up, I get a method missing for ==. On adding the class name to the method_missing output, I get Class#==, which makes no sense. But String#length is empty, so this represents garbage where we don't properly clear the return value for an empty method. I added a first pass at String#length in c3eac1f.

Next up we're warned about Fixnum#getc?!? Turns out we call @io.getc in Scanner#get, and we stubbed out STDIN as 0 a while back... Changing it to IO.new (in 66e976f) suddenly gets us somewhere: My test code waits for input!

echo Foo | /tmp/scanner4 gave me a "send warning" for Fixnum#chr which I added in 186986f

Repeating this gave me method missing for String#[]. And here we'll spend a little bit more time, as there are (minor) complications ahead.

String#[] and %s(bindex)

First lets look at a not particularly inspired first version of String#[] in 7bc84e6:


    --- a/lib/core/string.rb
    +++ b/lib/core/string.rb
    @@ -16,6 +16,23 @@ class String
         %s(assign @buffer 0)
       end
    
    +  def [] index
    +    l = length
    +    if index < 0
    +      index = l + index
    +      if index < 0
    +        return nil
    +      end
    +    end
    +
    +    if index >= l
    +      return nil
    +    end
    +    %s(assign index (callm index __get_raw))
    +    %s(assign c (bindex @buffer index))
    +    %s(__get_fixnum c)
    +  end
    +

First of all, we need bounds checking. String#length currently counts, which is obviously stupid, but we'll sort that out later. It's really only the last 3 lines we care about here. How do we get a single byte out of our strings? Well, so far we can't easily do that - we haven't exposed any way of addressing single bytes.

Above that's fixed by introducing bindex as a byte-oriented alternative to our 32-bit (or in theory pointer-sized - if/when we add a 64 bit target, it needs to be 64-bit) index primitive.

All the code does is obtain the raw index value, use it to obtain the raw byte value, and then obtain a Fixnum (note, we're still following Ruby 1.8 behaviour here - 1.9+ returns a String -, which we probably should stop with, given that the compiler itself is now updated to support 1.9; but devil you know and all that).

Apart from adding it to the @@keywords set in compiler.rb, we add this, which is a direct parallel to compile_index apart from not scaling the value, and the type we return. If we need more scales we might want to create a more generic version (also in 7bc84e6)


    +  # Compiles an 8-bit array indexing-expression.
    +  # Takes the current scope, the array as well as the index number to access.
    +  def compile_bindex(scope, arr, index)
    +    source = compile_eval_arg(scope, arr)
    +    r = @e.with_register do |reg|
    +      @e.movl(source, reg)
    +      source = compile_eval_arg(scope, index)
    +      @e.save_result(source)
    +      @e.addl(@e.result_value, reg)
    +    end
    +    return [:indirect8, r]
    +  end

This again requires some changes to emitter.rb to add support for loading :indirect8:


    --- a/emitter.rb
    +++ b/emitter.rb
    @@ -234,6 +234,8 @@ class Emitter
           return load_address(aparam)
         when :indirect
           return load_indirect(aparam)
    +    when :indirect8
    +      return load_indirect8(aparam)
         when :arg
           return load_arg(aparam,reg || result_value)
         when :lvar
    @@ -325,6 +327,13 @@ class Emitter
         movl(src,"(%#{dest.to_s})")
       end
    
    +  def load_indirect8(arg)
    +    movzbl("(#{to_operand_value(arg,:stripdollar)})", :eax)
    +    # FIXME: gcc includes this second movzbl; why is it needed?
    +    movzbl(:al,:eax)
    +    :eax
    +  end
    +

In which we unwillingly revisit register allocation

This leads us further down the rabbit hole: A method missing for String#position.... Which should be Scanner#position, accessed via self.position in Scanner#get.

I wish I'd taken better notes of how I tracked down this bug, but it involved lots of printf type debugging making use of our now available Class#name etc., as well as pouring over the asm output. The problem is actually triggered in Scanner#fill, which in my test version looks like this:


      def fill
        if @buf.empty?
          c = @io.getc
          c = c.chr if c
          @buf = c ? c.to_s : ""
        end
      end

Looks innocent, because it is. However, the asm output is not so innocent and reflects how tricky getting register allocation right is. The below fragment reflects just @buf = c ? c.to_s : "".


       # RA: Allocated reg 'ecx' for c
        # [:lvar, 0, :ecx]
        movl    -8(%ebp), %ecx
        testl   %ecx, %ecx
        je  .L189

Above we've loaded c and we're jumping to .L189 if false.

Now we execute c.to_s:


        # callm :c.:to_s
        subl    $8, %esp
        movl    $2, %ebx
        pushl   %ebx
        # RA: Already cached 'ecx' for c
        movl    %ecx, 4(%esp)
        movl    $0, 8(%esp)
        popl    %ebx
        movl    (%esp), %esi
        movl    (%esi), %eax
        call    *384(%eax)
        # Evicting self
        addl    $8, %esp
        # callm c.to_s END
        jmp .L190

At the end, note that we're marking self as evicted from %esi where we put it.

Now for the "else" part, that just returns an empty string:


    .L189:
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L0, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        # RA: Allocated reg 'esi' for self
        # [:arg, 0, :esi]
        movl    8(%ebp), %esi

Hang on? At the end, this reloads self into %esi, which in itself isn't a problem. The problem is that since the very next label, .L190, reflects a merge of two control flows, even though self was just reloaded, unless we know that self will be present in %esi when leaving the "if" arm above too, the code below is broken:

.L190: movl %eax, %ecx # RA: Already cached 'esi' for self movl %ecx, 8(%esi)

... because it assumes self is cached. And in fact, it is totally broken: %esi will reflect the class of c, because of the c.to_s call that is the last part of the ternary-if arm above. There are several ways of fixing this, one of them being to try to prove which registers are safe across both control flows. The other, the brute-force approach, is to assume all bets are off and start afresh.

The change is trivial, so you can see it in 549e091

Method 'comma' ?!?


    echo Foo | /tmp/scanner4
    Got: 70 (PEEK)
    WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.
    WARNING:    Method: 'comma'
    WARNING:    symbol address = 0x8580510
    WARNING:    self = 0x85802e0
    WARNING:    class 'Scanner'
    Method missing: Class#==

We don't have a method comma. So let's break out the debug output with ruby compiler.rb --norequire --parsetree:


          (defm position ()
            (let (pos __env__ __tmp_proc)
              (assign pos (callm Position new (@filename (comma @lineno @col))))
              pos
            )
          )

The relevant part corresponds to:


        pos = Position.new(@filename,@lineno,@col)

So let's add a test case to parser.feature:


    +      | "Position.new(@filename,@lineno,@col)" | [:do, [:callm, :Position, :new, [:"@filename", :"@lineno", :"@col"]]] |       |

The problem here is in treeoutput.rb, which badly needs more comments... The code attempts to simplify the parse tree created by the operator precedence parser, in order to make it easier to work with later.

The relevant part is this, which triggers on method calls etc.. I've included the one line fix as a diff. It's in 13368e0:


          elsif la and leftv[0] == :callm and o.sym == :call
            block = ra && rightv[0] == :flatten && rightv[2].is_a?(Array) && rightv[2][0] == :block
            comma = ra && rightv[0] == :comma
    -       args = comma || block ? flatten(rightv[1..-1]) : rightv
    +       args = comma || block ? flatten(rightv) : rightv          
            args = E[args] if !comma && !block && args.is_a?(Array)
            args = E[args]
            if block
              @vstack << leftv.concat(*args)
            else
              @vstack << leftv + args
            end

The hint to the location comes from seeing the "comma" reference. If we add a --dont-rewrite flag and re-run ruby compiler.rb as above, we get this:


              (assign pos (call (callm Position new) (comma @filename (comma @lineno @col))))

So the rewrite fails to rewrite the last part. The bug probably stems from forgetting that rightv in the above case refers to the entire argument list.

Delayed reaction

The next problem up is a method missing for Class#==, which occurs in Scanner#get where I marked with "(1)":


      def get
        fill
    
        pos = self.position
    
    # (2)
        ch = @buf.slice!(-1,1)
    
        @col = @col + 1
    
    # (1)
        if ch == "\n"
          @lineno = @lineno + 1
          @col = 1
        end

So at (1), ch is of object Class. Since we get ch from @buf.slice!(-1,1) above, that's where we need to look. The immediately obviously reason is that String#slice! was not implemented at all. It is in 5133315 which I'm not in the mood to walk through (but do feel free to ask in the comments if anything is unclear) - it's virtually guaranteed to be possible to clean up. The only thing I want to mention is __copy_raw, which is an alternative to __set_raw that will copy the raw buffer instead of just setting the pointer:


      def __copy_raw(str,len)
        %s(assign len (callm len __get_raw))
        %s(assign @buffer (malloc len))
        %s(memmove @buffer str len)
       end

In the above commit I've also included String#== as that is the "next one out" and quite obviously so from the earlier error. The one thing to worth noting about that, is that "!" is not implemented, and that I also added an Object#true as a workaround. A shameful hack.

Next we need Object#nil?, because "!" does not work, and so a "!" occurrence in Scanner#get was changed to #nil? for the test code.

Fixnum#position !?

Since we've already run into problems with register allocation, I'm not going to go into a lot of detail about the debugging here. Suffice to say that given that we're not actually calling "#position" on what should be a Fixnum, it was time to break out the assembly source, and look at what was actually being called. It was quickly clear that the wrong value was in the register.

I decided it was time to add some rspec tests for regalloc.rb, and you can find the first set in 9bfee76.

That didn't reveal anything, and I had to start digging into #with_register. The test case that reproduces the problem is in 8dcd18b together with the one line fix. The problem turned out to be that #with_register calls evict on a register found in the cache, and then hands the register out, without taking into account that evict put the register back on the free list.

Return

Next is another case of the wrong value being returned. Going over assembly output again, I could find no obvious register allocation issue. Next up was peppering some puts some_object.class.name around to see where the objects got confused, and this let to compile_return. This is likely indirectly a regression caused by the register allocation: As it turns out, previously, we've not used the return statement other than in cases where it was not strictly necessary, as the last computation left the result in %eax. But this is substantially less likely after introducing the register allocation.

#compile_return simply did not ensure the result of the evaluation of its argument would be saved to `%eax:


       def compile_return(scope, arg = nil)
    -    compile_eval_arg(scope, arg) if arg
    +    @e.save_result(compile_eval_arg(scope, arg)) if arg
         @e.leave
         @e.ret
         [:subexpr]

And there we are...

Some notes on scanner4.rb

I'll just briefly mention some remaining problems.

First of all, I found a bug in string interpolation, that I'll likely fix separate from the following articles, unless it proves particularly interesting:


      def inspect
    # Works:
    #    puts self.lineno
    #    puts self.filename
    # FIXME: Seg faults
        #    "line #{self.lineno}, col #{self.col} in #{self.filename}"
    # FIXME: Including self.lineno or self.col seg faults:
        "line #{@lineno}, col #{@col} in #{@filename}"
      end

Secondly there's this:


     # FIXME: += translates to "incr" primitive, which is a low level instrucion
     @col = @col + 1

As above, I might fix that separately. For now I considered the workaround the most expedient way of getting further.

Lastly there's this horrific piece:

# FIXME: ScannerString is broken -- need to handle String.new with an argument
#  - this again depends on handling default arguments

    s = ScannerString.new
    r = ch.__get_raw
    s.__set_raw(r)

This obviously needs to be fixed. The issue is that a proper fix it requires handling default arguments, as well as super so that ScannerString as a subclass of String can pass on the string argument rather than set it after the fact (I could have hidden the #__get_raw and #__set_raw bits in ScannerString, but that would just have obscured the problem)

Next we'll deal with the issue above, of default arguments and super.

Then in the following part, we'll be looking at the next step towards compiling a test program that uses the compiler code to parse s-expressions, which will be to get Scanner#expect to work.

Writing a (Ruby) compiler in Ruby bottom up - step 35

Fri, 16 May 2014 05:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Towards Self Hosting

As mentioned last time, this time around, I've first landed a number of changes that will make the parser able to parse the entire compiler (whether or not it parses it correctly or not remains to be seen, and is outside the scope).

You can find these merged in 37d6a0510 and 44914839a72

Secondly, we'll start looking at small parts of the compiler to break into pieces that are:

Amenable to separate testing
Simple enough to try to compile

The goal is to lay the groundwork for refactoring what we now have into smaller units that at the same time both allow us to unit test the module and use it as a test case for the compiler at the same time. Each module we can compile will then both give increased confidence in the generated code and bring us one step closer to the state where the compiler can fully compile itself.

A good set of candidates to start with appears to be the basic Scanner class, followed by the code to parse and print our "s-expression syntax". Will it prove more challenging than expected? We'll see...

Compiling Scanner

The remarkable thing is that "out of the box" ./compile scanner.rb actually yields a binary, though it will not-so-remarkably run into missing "stuff" on trying to run it:

$ /tmp/scanner
attr_reader col
define_method col
Method missing: __send__

Note that this also means that e.g. it quietly accepts that it has no definition for Struct. However that is actually in line with Ruby semantics, and one of the things that makes efficiency such a problem:

ruby scanner.rb runs all the way through (with no output), as it is legal to reference an un-defined variable - it is first if we try to access it we are meant to get an error.

In reality, for a compiler, we'll likely want to at least warn about the most obvious of these at least (I'm sure I can fill several articles on the topic of adding warnings for "legal but stupid" behaviour in semi-sane ways, but lets wait until we can actually compile a reasonably sized program first).

The challenges

In its present form, Scanner actually presents some challenges off the bat just from a cursory look:

It defines an inner class
It relies on Struct which we haven't done anything to implement (and then re-opens the new class, which we don't yet support.
It relies on attr_accessor
It uses blocks
It uses #respond_to?
It references Tokens::Keyword. Looking up Tokens::Keyword will likely fail

This is why self hosting is such a useful step - you're instantly faced with the practicalities of a real program written in the language. And while this program is in our control, making too drastic changes to it will defeat the purpose, so we have an incentive to fix things properly whenever reasonable.

Some solutions

We now have to consider whether to add support for these, whether full or temporary hacks, or change Scanner accordingly.

#respond_to?: Doing this properly involves a Hash of the methods of a class. We'll make a note the method hash is needed, and defer that to a future part. Instead we'll hack up a default #respond_to? which is rater anaemic, and override it for ScannerString, which is the point here anyway.
We'll ignore the inner classes, and move ScannerString and Position out of Scanner.
Struct: We'll change the code here, and define a "proper" Position class and defer Struct until later.
attr_accessor: We've had our painful trip down this road before. I'm not inclined to revisit it anytime soon. We'll do this the hacky way, and special case attr_accessor / attr_reader / attr_writer to custom generate methods for now at least (it may be the best long term solution, though they were the "test case" for define_method previously)
Blocks could / should work in theory. Lets see what is broken and fix it.
Tokens::Keyword: Lets refactor this part. The code calling Tokens::Keyword does not belong in the Scanner. Lets move it to ParserBase, and thus defer this issue.
#is_a?: Scanner#initialize uses '#is_a?' to see if it has been given a File or a stream.
File.file?, File.expand_path and #path are used if we're given a File object, to extract and expand the path name.

But first of all, lets start chopping Scanner into pieces and creating test cases to see what works and doesn't, and then gradually flesh out a more and more complete equivalent.

The first few tests

STDIN and STDOUT

We will need to be able to read from somewhere for the Scanner class to work, so lets first add a basic test of STDIN and STDOUT:


        STDOUT.puts "Hello world from STDOUT"
    }}}   
    
    This instantly fails, as we haven't even defined STDOUT. We'll remedy for now by adding
    
        STDOUT = IO.new

to lib/core/core.rb (in d24d56b)

Next we add a test of STDIN:


        puts STDIN.getc

and modify our step definition to echo "test" into the compiled binaries. This will also fail because STDIN is missing. We make the same change as for STDOUT, but in this case it is not enough:

WARNING: __send__ bypassing vtable not yet implemented.
WARNING:    Called with 0x8766bf8
WARNING:    self = 0x8766b78
WARNING:    (string: 'getc')

This one comes when there is no allocated vtable slot. The intent is for the class structures to use vtable slots like in C++ for example for most methods. The heuristics used to allocate vtable slots currently considers only methods we have seen defined, not methods that have been otherwise mentioned. In this case #getc has not been defined anywhere yet, and so the compiler should have done a lookup in a hash table for this class, and then ended up falling back on a generic #method_missing, but the hash lookup is not yet implemented.

Anyway, lets put in place a #getc in lib/core/io.rb. This is harder than expected, as our s-expression language does not expose a way to get addresses to stack variables easily. So here's a first, horribly inefficient, stab (in 54a0c13)


        # FIXME: This code is specific to a 32 bit little endian
        # arch, and is also horribly inefficient because we don't
        # have an easy way of getting the address of a stack allocated
        # variable.
        %s(do
             (assign tmp (malloc 4))
             (assign (index tmp 0) 0)
             (read 0 tmp 1)
             (assign c (__get_fixnum (index tmp 0)))
             (free tmp)
             )
        c
      end

Of course we can do a lot better by adding, say, an "(addr var)" construct. This is still horribly bad, though - no error checking from read; and it just reads from STDIN regardless of desired filedescriptor for this IO object, and it does no buffering, and other nastiness. Plenty to deal with later...

The constructor

Our first test case from the actual Scanner class will be the only tricky part in #initialize:


    class Scanner
      def initialize(io)
        # set filename if io is an actual file (instead of STDIN)
        # otherwhise, indicate it comes from a stream
        @filename = io.is_a?(File) && File.file?(io) ? File.expand_path(io.path) : "<stream>"
    
        puts @filename
      end
    end
    
    Scanner.new(STDIN)

However this will fail:

Object#is_a? not implemented
Method missing: file?

Looking more closely into this, we'll find a few things: First I thought I'd not yet implemented the ternary conditional, but the actual problem is that it fails to parse the ternary correctly in the face of the logical and ('&&'). You can see this if you run the compiler like this: ruby compiler.rb --parsetree -norequire features/inputs/scanner1.rb. This is likely "just" a priority issue.

But let's untangle this into two tests - one with the ternary if, and one without.


        if io.is_a?(File) && File.file?(io)
          @filename = File.expand_path(io.path)
        else
          @filename = "<stream>"
        end

Changing the ternary to a full if will still prove interesting. Let us quickly hack in a #is_a? just for File. First we need to add one to lib/core/object.rb (882c71b) :


       def is_a?(c)
          false # We're pessimists
       end

Now for the next surprise: We don't have false, do we? We've defined false/true in lib/core/core.rb, but there they are ordinary local variables, only accessible in the main scope. We really ought to give them special treatment as fake global variables referring to global instances of FalseClass and TrueClass, but that opens another can of worms (we can no longer assume non-null means true and null means false, which will change comparisons.

For the time being we sidestep this by defining false inObject` as a method (!) (I added that too in 882c71b) :


      def false
         %s(sexp 0)
      end

This gives us another surprise when trying to compile features/inputs/scanner2.rb (04b6060) ; the one without the ternary if:

We still get "Method missing file?", which means the second part of the supposedly short-circuiting '&&' expression gets executed, but we're not passing a File object in.

This is yet another of our earlier convenient hacks that now needs to be sorted out: && gets turned into and, which in turn gets interpreted as a method call because the compiler does not have a builtin and construct. As a result, it is evaluated after its arguments. Or rather, it would have been, had not the second argument been a sub-expression which itself fails.

As a lesson in why proper testing is essential, let us use this as an excuse to skip File.file? and File.expand_path and File#path this time around: Instead let use make the compiler handle && properly, so that we never get to them. Well, as long as we're only ever trying to compile from STDIN anyway. It's a start.

Fixing the short circuit operator.

The changes to handle it are absolutely minor: We need to add ':and' to the list of keywords in compiler.rb, and define compile_and (in 75d1ecd62d):


    +  # Shortcircuit 'left && right' is equivalent to 'if left; right; end'
    +  def compile_and scope, left, right
    +    compile_if(scope, left, right)
    +  end
    +

But the test case also reveals another bug: When adding the caching of 'self', I failed to account for the special handle of 'self' in the outermost scope (it's treated as a global variable). Maybe treating the global scope any differently is the mistake, and we should just put that too on the stack, but for now the fix is trivial: Just add a check for [:global,:self] in get_arg:


    -      if arg.first == :lvar || arg.first == :arg
    +      if arg.first == :lvar || arg.first == :arg || (arg.first == :global && arg.last == :self)

Doing a "./compile features/inputes/shortcircuit.rb" (or running the rspec tests) now yields a /tmp/shortcircuit that actually short-circuits.

And features/inputs/scanner2.rb now successfully sidesteaps the methods on File we're being too lazy to implement. Though features/inputs/scanner1.rb that uses the ternary conditional still crashes, so there's that.

This is where we'll leave it for now.

Conclusion

This part probably seems all over the place, but it's part of the fun once you get to a stage where it becomes viable to start looking at bootstrapping the compiler in itself.

I'll make the next few parts shorter than some of the 3000+ word monsters I've put out in the past, to also try to focus them a bit more, but next time will focus on getting Scanner#get and Scanner#unget to work, and then work our way through Scanner#expect and Scanner#ws too. If you look at our intended milestone of getting the s-expression parser to compile, it might look like that brings us almost there.

Not so - look forward to complication after complication being revealed as we stumble into class after class, method after method, that we need to implement at least partially before we get there. And possibly some more simplifying compiler changes to sidestep some of them.

But incidentally, each one of them will make the next parts of the compiler easier to get past too.

Writing a (Ruby) compiler in Ruby bottom up - step 34

Wed, 16 Apr 2014 01:45:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Putting Self In A Register

Where we left off, we had a simple but tolerable register allocator. But as it happens, for now at least the code will not often get all that huge benefits from it, for the simple reason that a huge amount of a typical Ruby application consists of method calls, and most of these method calls causes us to have to evict most of the registers.

However, there is one obvious candidate for the register treatment that we have alreay touched on:

self.

self is even more ubiquitous in Ruby programs than the source lets on: In addition to every method call, every access to an instance variable is conceptually either <self offset> or <self.some_hidden_hash_table var>. Every class variable requires self.class, and thus self. And so on.

And when calling a method on another object, self just temporarily changes - usually the "new self" will be used a number of times before we return.

So then, this is why I "reserved" a register for caching self - we'll use %esi.

I originally intended to include it in the register allocation part, but when that ballooned to 6k words (including source, to be fair), I decided enough was enough.

In comparison, this part will be pleasantly short and simple.

Changing the calling convention

More than just caching self, we will change the calling convention somewhat:

For now, while we still retain self on the stack (I'm not sure whether I'll keep it that way, but I'd rather avoid messing with it right now), we also put it in %esi before we call the method.

The reasons for doing so are fairly simple:

It means we can assume self == %esi throughout a method, except immediately surrounding a method call on another object.
We have been loading the object value into a register in order to use an indirect load to get self.class anyway, so we might as well use that load to load self straight into %esi and leave it there for the duration.
Since %esi is callee saved, we can trust that it won't suddenly change on us in a method call or function call to external code - when the code returns, %esi should still refer to the object we just called a method on
It makes the code pleasantly simple...

Since %esi is callee saved, it means that we should be able to defer reloading self into it after a call until/unless we know it is needed. This will save some reloads, and may also allow it to be reused on occasion when we call multiple methods on the same object in succession. I'll leave that optimization for later, though.

There are a few parts to this change:

Ensure %esi is reloaded on method exit; we'll do this in #output_functions
Changing #compile_callm to load the "new self" for the called method as needed, and reload self if needed
adding a few helpers to Compiler and Emitter as part of refactoring that code
a minor change to the new register allocator in order to recognize %esi's special status.

We'll go through them "from the top" (of the call flow) anyway. You can find all the code for this part in this single commit: 4b190694bc

output_functions

The only change here is that we want to make sure that %esi is returned to its original state.


              @e.comment("Reloading self if evicted:")
              # Ensure %esi is intact on exit, if needed:
              reload_self(fscope)

Note that this is slightly broken: In the case of defun nodes, it will load the global self, but for these nodes, %esi will actually originally contain the calling self. We'll sort that out later - for now theres a little workaround at the end of #compile_defun. This triggers unnecessary self reloads, but it works:


        @e.evict_regs_for(:self)
        reload_self(scope)

compile_callm

The change to compile_callm is pleasantly small. It only involves the block that's called back from #compile_callm_args to handle the actual call, and should be reasonably self-explanatory (but I'll explain it anyway):


          compile_callm_args(scope, ob, args) do

Here, if we're calling a method on an object named anything other than self, we load the address of the object from the top of the stack, where it has been stuffed as part of preparing the arguments anyway. Do note that this is in many cases going to be wasteful: If the method only has static arguments (or no arguments), we can safely load it into %esi first, and then put it onto the stack from %esi, potentially (unless the object is already in a register) saving a memory load. That's one of many low hanging fruits for optimization later on.


            if ob != :self
              @e.load_indirect(@e.sp, :esi)

If, on the other hand, we called a method on self, we "reload" self if needed.


            else
              @e.comment("Reload self?")
              reload_self(scope)
            end

#reload_self is just a tiny helper that calls #get_arg(scope,:self) for now, and relies on the register allocation in #get_arg to reload %esi with self if it has been evicted.

And here's our cleaned up code to load self.class, and call the right vtable offset.


            load_class(scope) # Load self.class into %eax
            @e.callm(off)

Finally, if the object wasn't self, we ensure self is evicted from %esi so that it will be reloaded later if needed.


            if ob != :self
              @e.comment("Evicting self")
              @e.evict_regs_for(:self)
            end
          end

The only other change in Compiler is to evict self when starting a new scope for classes - see the start of #compile_class

Emitter

For the emitter, I've added more debug output as comments to the code - I'll ignore those changes, you can find them in the commit.

Other than that, I've made the following changes.

First, a new #callm method that moves the offset calculations etc. out of Compiler, where it didn't belong:


      # Call an entry in a vtable, by default held in %eax
      def callm(off, reg=:eax)
        @allocator.evict_caller_saved
        emit(:call, "*#{off*Emitter::PTR_SIZE}(%#{reg.to_s})")
      end

Other than that, I've just added a single line to Emitter#func:


        @allocator.cache_reg!(:self)

This ensures that the compiler treats %esi as already holding self when entering a method.

RegisterAllocator

To the register allocator there are a few more changes.

First I've added the name of the cached variable to the cache. I've also added an instance variable holding the register set aside for self, and started refactoring to handle the caller saved variables separately. See #evict_by_cache and #evict_vars for that change.

The main changes, though, are to give self special treatment as a variable with its own special register that won't otherwise be handed out.

This is mainly handled here in #cache_reg!:


    @@ -174,13 +191,18 @@ class RegisterAllocator
       # available, the emitter will use its scratch register (e.g. %eax)
       # instead
       def cache_reg!(var)
    -    if !@order.member?(var.to_sym)
    +    var = var.to_sym
    +    if var == :self
    +      free = @selfreg
    +    elsif !@order.member?(var)
           return nil
    +    else
    +      free = @free_registers.shift
         end
    -    free = @free_registers.shift
    +

self in action

Let us finally take a look at what some of our now slightly less horrible code looks like.

This is one of our test cases, found in features/inputs/method2.rb:


    class Foo
    
      def initialize
      end
    
      def foo
        puts "foo"
      end
    
      def bar arg
        puts arg
      end
    end
    
    f = Foo.new
    f.foo
    f.bar("bar")

And here is the asm output for Foo#bar. You can see the copious comments that the register allocation emits, but I've added some extra commentary inline anyway:


    __method_Foo_bar:
        .stabn  68,0,12,.LM463 -.LFBB126
    .LM463:
    .LFBB126:

At this point %esi holds self, but as a "backup" [:arg,0] in the compiler, which is mapped at 8(%ebp), also holds %esi. Though in this case, we luckily won't need it, as you can see self remains in %esi throughout:


        pushl   %ebp
        movl    %esp, %ebp
        subl    $20, %esp
        # callm :self.:puts
        subl    $12, %esp
        movl    $3, %ebx
        pushl   %ebx

At this point, the compiler is trying to push self onto the stack, and when it checks the register cache, it tells us self is already in %esi, courtesy of explicitly marking it as cached in Emitter#func. it then proceeds to fill in the arguments:


        # RA: Already cached 'esi' for self
        movl    %esi, 4(%esp)
        movl    $0, 8(%esp)
        # RA: Allocated reg 'ecx' for arg
        # [:arg, 2, :ecx]
        movl    16(%ebp), %ecx
        movl    %ecx, 12(%esp)
        popl    %ebx

Here it is checking if it needs to reload self into the register. If the arguments had contained expressions that included calls to methods of other objects, that might have been necessary. But not this time. So it loads self.class via an indirect load from (%esi) (as a reminder, if esi and eax was C variables, movl (%esi), %eax) is equivalent to eax = esi[0] or eax = *esi). Then it does the method call, via the vtable - the address of #puts have happened to get allocated to slot 36.


        # Reload self?
        # RA: Already cached 'esi' for self
        movl    (%esi), %eax
        call    *36(%eax)
        addl    $12, %esp
        # callm self.puts END
        addl    $20, %esp

Finally, we need to check if there's a chance %esi has been evicted but not reloaded yet, so we can ensure %esi has the right value when we return back up to the calling method. In this case, %esi already holds the right thing:


        # Reloading self if evicted:
        # RA: Already cached 'esi' for self
        leave
        ret

Let's take a look at another example too, namely the start of Object#puts (note that Object is not the right place for #puts - it is there temporarily because we don't support modules yet):


    __method_Object_puts:
        .stabn  68,0,36,.LM347 -.LFBB65
    .LM347:
    .LFBB65:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $36, %esp
        .stabn  68,0,37,.LM348 -.LFBB65
    .LM348:
        subl    $4, %esp
        movl    $1, %ebx
        # RA: Allocated reg 'edi' for numargs
        # [:lvar, -1, :edi]
        movl    -4(%ebp), %edi
        movl    %edi, (%esp)
        movl    $__get_fixnum, %eax
        call    *%eax
        addl    $4, %esp

Here we see what currently happens when we call a function defined with %s(defun ...). Because I've been too lazy to ensure it doesn't load the "wrong" self before exit, I added the workaround to forcibly reload self after the call, and that is what is happening here. It's wasteful, so I'll address this soon:


        # RA: Evicted self
        # RA: Allocated reg 'esi' for self
        # [:arg, 0, :esi]
        movl    8(%ebp), %esi

Here comes a call to #==, which gets a double whammy, as the other argument is a literal 2, and so triggers a call to __get_fixnum:


        movl    %eax, -20(%ebp)
        .stabn  68,0,39,.LM349 -.LFBB65
    .LM349:
        # callm :na.:==
        subl    $12, %esp
        movl    $3, %ebx
        pushl   %ebx
        # RA: Allocated reg 'ecx' for na
        # [:lvar, 3, :ecx]
        movl    -20(%ebp), %ecx
        movl    %ecx, 4(%esp)
        movl    $0, 8(%esp)
        subl    $4, %esp
        movl    $1, %ebx
        movl    $2, (%esp)
        movl    $__get_fixnum, %eax
        call    *%eax
        addl    $4, %esp
        # RA: Evicted self
        # RA: Allocated reg 'esi' for self
        # [:arg, 0, :esi]
        movl    8(%ebp), %esi
        movl    %eax, 12(%esp)

This code is still far from optimal. Ignoring all the other problems, in terms of the self caching, we evict self on return from a call node just because the current code doesn't maintain the calling convention properly. But after the previous part, I want to keep this short and focused, so lets leave it here for now.

Next time

... we will revisit an old goal: Self-hosting.

First I'll land a number of changes that will make the parser able to parse the entire compiler (whether or not it parses it correctly or not remains to be seen, and is outside the scope).

Secondly, we'll start looking at small parts of the compiler to break into pieces that are:

Amenable to separate testing
Simple enough to try to compile

The goal is to lay the ground work for refactoring what we now have into smaller units that at the same time both allow us to unit test the module and use it as a test case for the compiler at the same time. Each module we can compile will then both give increased confidence in the generated code and bring us one step closer to the state where the compiler can fully compile itself. </self.some_hidden_hash_table>

The Oberon-07 language report is 17 pages

Sun, 13 Apr 2014 02:00:00 +0000

Niklaus Wirth turned 80 this year, and when stumbling on this link on HackerNews, I was reminded that I have had some notes sitting around in my drafts for a long time.

The Oberon-07 language report

You can find the PDF here

It starts with an Albert Einstein quote:

> Make it as simple as possible, but not simpler.

How Wirth influenced me

Wirth was one of my earliest computer science influences. Ever since we got a copy of Turbo Pascal, 3.3 I think, which my dad got hold of for his new PC - probably in 1987 or so -, I have been fascinated by Wirth. I don't remember why my dad got Turbo Pascal. While he did some programming, and made a living of it for many years, his focus was dBase. He may have considered using it, or it may have been because he thought I'd like it.

You can see why I was fascinated by checking out the TP 3.0 manual (PDF)

What fascinated me was the BNF for Pascal: The entire language syntax was defined in about 5 pages of BNF. As if that was not enough, I soon learned that Niklaus Wirth published on of the first Extended Backus-Naur Form descriptions (there are now many variations).

Soon I was trying to figure out how to write compilers. My earliest experiments were with Turbo Pascal, which required more knowledge of PC internals than I had. I moved back to my C64, and wrote some small initial attempts of demo-oriented micro-languages (e.g. one had a "raster" command that'd generate code for simple interrupt driven raster effects... rather specialised). Later I moved on to the Amiga, and used eventually ended up using Pascal again for one of my most serious compiler efforts.

But Wirth influenced me in deeper ways too, and the Oberon-07 language report in many ways exemplifies what I love about his languages.

For a while I wanted to study at ETH because of him, but while I didn't go ahead with that, for years I've kept track of their computer science research groups. One fun thing is that one of the speakers at the symposium for his 80th birthday was Professor Michael Franz at UC Irvine, one of Wirths Ph.D. students, whose doctoral dissertation from 1994 is one of my all time favourite papers, describing Semantic Dictionary Encoding, an alternative to "normal" CPU independent bytecode. (One of Michael Franz students again, Andreas Gal, is familiar to a lot of people who follow Javascript interpreter work, from his work on Trace Trees)

I'm deeply indebted to Wirth for setting the trajectory of the way I think about programming languages This may seem odd given how much I write about Ruby, a language which in many ways is the anti-thesis of Wirthian languages. But while I love programming in Ruby, one of my motivations for wanting to write a Ruby compiler was in fact trying to make sense of the language, and "untangling" it and trying to understand if there are ways of simplifying it while retaining it's flexibility, much in the spirit of how Wirth's language career was one long journey of reduction of complexity. And this stands as one of his most important legacies:

The simplicity of Oberon should stand as a beacon

The syntax of the entire Oberon-07 language takes up page 16 and half of page 17 of the report.

This is not news, but I like to revisit various parts of Niklaus Wirth's legacy every now and again for the simple reason that his compilers and his languages are exceptional for their simplicity.

Wirth himself has said he was vary about adding features to his language specifications that he did not have a clear idea of how to implement or how they would work. His group did plenty of research on augmentations to his languages, informing the next generation, but each specification is based on careful selection of proven features and lessons learned from the previous languages.

Oberon follows from Modula, follows from Pascal, follows from Algol-W, follows from Euler, following from Wirths work on the Algol-60 committee, presenting an unbroken chain of careful engineering stretching from the 60's until Wirths latest revisions to the Oberon-07 report quite recently (this year).

These languages are under-appreciated, which is particularly sad given the enormous success of products like Turbo Pascal and later Delphi that shaped a huge number of programmers.

It is also particularly silly since these languages are so small and simple to learn. It is 17 pages. And it is not 17 pages of mathematical notation or hugely complicated ideas. It is 15 pages of mostly prose and a few tables, and 1.5 pages of the syntax re-stated formally in BNF.

It is simple prose. Consider section 2. Syntax:

> A language is an infinite set of sentences, namely the sentences well formed according to its > syntax. In Oberon, these sentences are called compilation units. Each unit is a finite sequence of > symbols from a finite vocabulary. The vocabulary of Oberon consists of identifiers, numbers, > strings, operators, delimiters, and comments. They are called lexical symbols and are composed of > sequences of characters. (Note the distinction between symbols and characters.) > > To describe the syntax, an extended Backus-Naur Formalism called EBNF is used. Brackets [ and ] > denote optionality of the enclosed sentential form, and braces { and } denote its repetition (possibly > 0 times). Syntactic entities (non-terminal symbols) are denoted by English words expressing their > intuitive meaning. Symbols of the language vocabulary (terminal symbols) are denoted by strings > enclosed in quote marks or by words in capital letters.

That's it. The BNF rules for the various parts of the language are then presented in each relevant section, as well as restated in the final two pages in one go.

Updated: Fixed the article link; corrected to take into account Paul McJones comments on chronology of Euler and Algol-W

Writing a (Ruby) compiler in Ruby bottom up - step 33

Sun, 06 Apr 2014 03:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

It took me two months to push this out, but I promise it doesn't mean I'm about to stop publishing these again anytime soon. I intend to shorten my "lead time" further again, so I'm hoping to publish the next one in 2-3 weeks time.

Register Allocation

We saw in some of the recent parts that the code is getting more and more prone to problems due to attempts at reusing registers.

Register allocation is the proper solution to this. That is, to introduce a mechanism for determining what code gets to use which registers when, and that handles the situation where too few registers are available properly (by "spilling" registers onto the stack)

Let me first make it clear that the really naive alternative to this is to avoid register allocation entirely, and to declare a few registers to be "scratch" registers that can only be safely used within code where no code generation is delegated further down.

This is possible to do by pushing all intermediate results onto the stack, and popping them off only briefly to carry out necessary operations and push them back onto the stack again (optionally with simple optimizations to operate directly on the top of the stack for single operand operations or when possible with the last of multiple operand instructions).

Basically, this means you're "emulating" a stack machine with registers.

This is an approach taken by many simple compilers for unoptimized code, deferring the problem of register allocation to optimization passes.

In reality we're very close to that, and in some respects I wish I'd kept purely to that approach, not least because it took me two months to get time to wrap up this part properly. But on the other hand, doing very basic register allocation is not that hard, and since we've started down that path we might as well go a bit further.

Only a bit mind you.

We will in fact in this part refactor some code to need register allocation less, to the point where we can get away with only minor adjustments to the original really primitive allocator.

Optimal register allocation is hard, and tends to require analysis that will require or at least strongly favor a solution with a low level intermediate representation that allows more in-depth analysis of register usage.

A first step is generally to analyse "liveness" of each variable, including temporary variables introduced by the compiler. Then the problem basically boils down to finding a way to map as many variable references as possible to registers so that you don't exceed the available number of registers for your architecture at any one point.

The "at any one point" part adds complexity, since reuse of registers is central to minimizing the number of memory accesses, which is the main goal of register allocation:

For most systems, memory accesses are substantially slower than register access (though this is less of an issue in these days of multi-level processor caches than in the old days where every memory access when to external memory; when you fail to hit cache, though, you are far more brutally penalized on modern CPUs as the gap between CPU performance and memory latency has widened)

If you have n registers, and no more than n variables are "live" at once, then you have it easy if you are able to determine wich variables are "live".

The fun begins when (and on an architecture like i386, this is likely to be pretty much all the time) the code block you are allocating registers for is referencing more stuff than you have registers for.

This either means "spilling" the contents of a register to memory in the middle of a function in order to load another variable, or keeping some variables you'd like to have in a register in memory instead, other than when operating on it.

That's where the challenge arises.

(though Ruby reduces this problem through other inefficiences: Almost everything is accessed via methods, which reduces the number of variables that are easy to put into registers; we may hope to improve on that later, but for now it reduces the immediate benefit of register allocation)

Another typical approach is graph coloring, which I'm not going to go into at all, as it's slow and complicated. A more recent approach is Linear Scan allocators, covered on the Wikipedia page for register allocation, which is popular for JIT's etc because it is in general a lot faster (and simpler) at the cost of some performance in the generated code.

In any case, down the rabbit hole you go...

I have no desire to deal with that anytime soon, and especially not on an architecture like i386 where the number of registers is so small. On, say, x86-64, or M68k it'd be a different matter, as you have vastly better chances of being able to keep a substantial proportion of intermediate results in registers and largely avoid spilling the results to the stack, and so you're a real sucker if you don't take maximal advantage of the registers (however, as mentioned above, without other work, we'd have problems taking full advantage).

(translation: I'll have to deal with this some day, but not now)

What we will do for now is to mostly rely on keeping stuff in memory (including on the stack), except for short term loading stuff into %eax when operating on it. As needed we'll also use %edx (see below). Beyond that, we will just guess wildly at some heuristics...

Apart from the guessing wildly at some heuristics part, this is roughly what we've done so far anyway...

But so far we've done the register allocation extremely ad-hoc, so it is worth first establishing our actual conventions. We start with the C calling convention, since we're trying to allow our code to call C code directly:

C calling convention on i386

We roughly follow the cdecl calling convention for i386.

That is, we will aim for %eax, %ecx and %edx to be caller saved. That is, if we rely on them to maintain their values, we will push them onto the stack before calling another method.

In practice we will treat %eax as a scratch register that is only used for short windows, and so we will rarely if ever want to bother to save it, especially as it is also generally used as the return value anyway.

Everything else is to be callee saved (but see caveat below); that is, if they are used in the called method, they will be saved there, and needs to be back to their original value by the time the method returns.

And we store arguments on the stack.

Next we add on some extensions:

Additions for splats and arity

Specifically we store the number of arguments in %ebx as methods needs to be able to determine the precise number of arguments whether due to "splats" or to throw appropriate exceptions to enforce arity (ensure that the number of arguments matches the declared number of arguments for the method; we don't do this yet).

Note that this breaks the "cdecl" calling convention. However this is only a problem if C code (or other code conforming to the cdecl calling convention) calls into our code.

For now we're not sticking our head into that worms nest (though you need to be aware of this if you want to experiment with the code and use C-functions like qsort which uses callbacks), so it's a non-issue (if/when we do, we'll either need to consider preserving %ebx, or more likely we'll need to bridge calls, as the method will likely require %ebx to hold the number of arguments for more than just the splats to work (e.g. Ruby methods are expected to throw ArgumentError if called with the wrong number of arguments, which will eventually force us to add additional checks at the start of each method).

As a result, %ebx is in practice free other than on entering a function, as we save it to the local stack frame. I'm of two minds whether to keep passing the number of arguments this way, as the code has gotten to the point where we end up temporarily pushing it on the stack anyway on call, and pushing it on the stack again afterwards. The only real current benefit of using a register for it is that we can directly call C functions that are totally unaware of how we pass the number of arguments.

These C functions don't know about the "fake" numargs "variable" anyway, and so we could as an alternative introduce a way of indicating we want C calling convention that would just leave out numargs entirely. It'd be slightly more hassle to use, but it'd only ever be used for low level %s() code anyway.

We're not going to change this right now, regardless.

What's left?

Well, on i386 we have %ecx,%edx,%esi, %edi. The "problem" is that all of them have special purposes in some cases. We've run into one of them: %edx is used to hold the high 32 bits of the dividend for idivl, and the remainder of the result, and needs special treatment as a result. There's also a number of floating point registers.

We also have %ebp which we use for the frame pointer to access local variables and method arguments via, and %esp, the stack pointer.

As discussed above, we could in theory use %ebx, with the caveat that while the splat handling is as is is, it'll get clobbered often, so for now I've kept it out.

(There are many other register names on i386, but many of them alias 16- and 8-bit portions of the 32-bit registers referred to above; as someone who grew up with M68k asm, where this kind of thing did not occur, in general I'll pretend I never heard about that wart)

What to use the free registers for?

As I said, we'll guess wildly.

As a first approximation, we'll make %esi hold self from the first reference to self in each method. We'll cover the implementation of that in the next part, so for now we will ignore %esi. This is because method calls and instance variable access both require self, and so we can assume it will be quite frequent, and as I will show next time, this pans out quite nicely.

I toyed with the idea of making %edi hold self.class, based on the same assumption, but this has two problems: It reduces the set of registers available to us further, and it complicates handling of eigenclasses:

The "internal" inheritance chain for Ruby objects can actually change at nearly any time, if someone decides to extend the object with methods tied to the objects meta class / eigenclass. If we cache self.class that limits us in how to handle that further down the line. So for now I won't do anything about that.

This leaves us with %ecx, %edx and %edi free for allocation so far. We further allow "forced" allcation of specific registers in order to handle cases like idivl metioned earlier.

At the same time we'll make some small changes that has the effect of minimizing the amount of time temporary values are kept in registers that has the effect of ensuring we never need many of them.

Then we'll add a "quick and dirty scan" step that will simply create a set of candidate variables as follows:

We only consider local variables or arguments. Considering instance variables etc. adds all sorts of problems that will come back and bite us when we add thread support. I'd rather think about those issues at a later time.
We only consider variables that are not "captured" by a closure, for much the same reason: We lose control over what/who/when effects of assignments etc. might be seen. This can be much improved - e.g. allocating a register for such variables, but "spilling" them when the closure is created, and allocating them again inside the body of the closure should in general be fine, but it's easy to mess it up, so one thing at a time.
We count the number of times the variable is referenced, and sort by that. When we run out of registers, we prefer to evict / free up the registers used to cache the least frequently used (in that method) variables. This is sub-optimal, as we don't make any attempts at figuring out where in a method the variable is used. We'll get back to that (much) later.
In any case ignore anything that's only referenced once (as we'll rather just load that into a scratch register)

Note that at this point we could go the next step and store information about liveness ranges, and use that to allow register usage to overlap, but one step at a time. The main thing is to get the overall mechanism in place.

What will we do with this information?

As little as possible. On accesing any local variables or arguments, we check if they're in a register first, if not we try to load it into a free register if there is one, and if not we fall back on the current behaviour of using %eax (and reloading / saving the variable on each access).

This totally sidesteps the need for liveness analysis, but also means we don't get the full benefit, and it's easy to create pathological cases where it performs really badly (e.g. lots of variables accessed few times, used one after the other, and then once you've referenced enough variables, reference them all again, right after they've been evicted from the registers; repeat - in this way you can construct cases where you get no benefit from the register allocation at all, while if you'd kept a subset of the variables in the registers throughout the code block, you would). But this is still no worse than the code we currently generate.

Abstracting the registers out of Compiler

A number of methods surrently refer to registers through symbols or even strings that directly reference them. A first step is to try to abstract away more of this so that we as much as possible request registers from the Emitter so that the registers can be replaced later if possible/necessary.

As a bonus, this will set us on the right path to make the compiler easier to retarget to other architectures.

This first changeset adds methods for the stack pointer, for using %ebx as scratch register, and a couple of other helpers, as well as start cleaning up the Compiler class to not explicitly mention registers by name so many places. You can see it in 92aa83f - I won't cover that commit in more detail.

Breaking our current primitive allocator

We already have with_register that sort-of tried to do a little bit of very basic register allocation. But with_register comes with substantial caveats: It knows nothing about what to do if it runs out of registers to allocate. So lets try to provoke it to fail, so we have something to fix to start with:


        %s(printf "%d = 2\n" (div (div (div 16 2) 2) 2))

I picked div as our recent rewrite away from runtime.c left us with code in compile_div that does dual nested with_register calls already, so it's well suited to ensure we run out of registers in our current regime.

You should get something like this if you try to compile it:

./emitter.rb:364:in `with_register': Register allocation FAILED (RuntimeError)

The problem is simply that we've only set aside %edx and %ecx, and furthermore we're not doing anything to allow spilling the values to the stack, or even to make them available again when caling into another function.

Triggering this in actual Ruby code is harder, as almost everything quickly devolves into method calls that effectively "reset" the register allocations by virtue of the calling conventions requirements for who saves which registers.

But lets sort this out first of all anyway.

First, since this revealed the danger of the nested with_register calls, which will remain inefficient at best, lets address the simpler case of compile_2 which we've used for dual-operand arithmetic and comparisons:

(You'll find these changes and the div test case in 0fdfb34)


     def compile_2(scope, left, right)
        src = compile_eval_arg(scope,left)
        @e.with_register do |reg|
          @e.movl(src,reg)
          @e.save_result(compile_eval_arg(scope,right))
          yield reg
        end
        [:subexpr]
      end

Just a tiny change here: We've lifted the compile_eval_arg(scope,left) call out. Frankly we should probably remove the need fully, and just use the stack. I'll consider that later. In the meantime this reduces register usage substantially in cases where the left-hand expression tree is deep.

The bigger change is compile_div:


      def compile_div(scope, left, right)
        @e.pushl(compile_eval_arg(scope,left))
    
        res = compile_eval_arg(scope,right)
        @e.with_register(:edx) do |dividend|
          @e.with_register do |divisor|
            @e.movl(res,divisor)
    
            # We need the dividend in %eax *and* sign extended into %edx, so
            # it doesn't matter which one of them we pop it into:
                    
            @e.popl(@e.result)
            @e.movl(@e.result, dividend)
            @e.sarl(31, dividend)
            @e.idivl(divisor)
          end
        end
        [:subexpr]
      end

This is pretty much a rewrite - the old version was horribly messy and brittle, because it tried to work around not being able to tell with_register exactly what it wanted.

So to simplify, lets make with_register handle that.

And at the same time we lift the argument evaluation out of the actual division, which massively simplifies things:

First we evaluate the left, and push the result onto the stack. Then we evaluate the right, and leave the result.

Then we forcibly allocate %edx since we know idivl needs it for both arguments and return value. Then we allocate a register for the divisor (right hand).

We then get the dividend (left hand) off the stack, into %eax, move it into the allocated register, which will be %edx. We then shift right to only leave the sign bit (see last time we dicussed the divisions for more on this).

Finally we do the division.

You may note that this is going to be wasteful in cases where the left hand expression is a static value etc. that we could just load directly into the right register. Adding some code to detect that will save some stack manipulation. But that's not a priority now.

The corresponding change to emitter.rb to expand with_register looks like this for now:


    -  def with_register
    +  def with_register(required_reg = nil)
         # FIXME: This is a hack - for now we just hand out :edx or :ecx
         # and we don't handle spills.
     
         @allocated_registers ||= Set.new
    -    free = @free_registers.shift
    +
    +    if required_reg
    +      free = @free_registers.delete(required_reg)
    +    else
    +      free = @free_registers.shift
    +    end
    +

In other words, this will still blow up spectacularly if we need more registers.

Note that that the changes we've done means the register allocation now only surrounds a handful of instructions doing calculation, and no further calls.

Luckily this means that in reality we shouldn't need more. We'd like more, but most of our register usage will only be for caching variables we've allocated space in memory for.

As such, we know the worst case for the register allocation is that we need to juggle %edx around, as that's the only register we specifically need (so far) for idivl.

As "stage 1" this gets our previous example to compile and run.

For now we'll move on to the meatier part of register allocation: Moving variables into registers.

Identifying variables for our registers

You're not going to like this part. It is hairy and ugly, and involves changing #rewrite_let_env and find_vars in transform.rb, which are not exactly the prettiest part of the compiler to begin with.

The relevant part of rewrite_let_env is the simplest:


     # We use this to assign registers 
    
     freq   = Hash.new(0)
     
     vars,env= find_vars(e[3],scopes,Set.new, freq)

We set aside a Hash with 0 as the default value, to keep count of the variable references we see.

Then we assign the frequency data to a new extra field of the AST nodes:


          e[3].extra[:varfreq] = freq.sort_by {|k,v| -v }.collect{|a| a.first }

extra is simply adding this to AST::Expr (in afdcd99):


    +
    +    def extra
    +      @extra ||= {}
    +    end

Back to transform.rb, the changes to find_vars are more extensive, but most of them are about threading freq through the recursive calls, and some refactoring (especially breaking out #is_special_name. The meat of it is this little change:


          elsif n.is_a?(Symbol)
            sc = in_scopes(scopes,n)
            freq[n] += 1 if !is_special_name?(n)

Specifically, when we get to a "leaf", if it is not a "special" name as defined in the new utility method, we count it as a variable reference to take into account for the later allocation. You can find the full changes to transform.rb here: 3f2ab88

An overview of the register allocator

I've split out the "backend" of the new register allocation code in regalloc.rb in 608adc1.

It could probably do with some refactoring already, but that will have to wait.

Most of the explanations here can be found in the source as well.

The RegisterAllocator class contains the Cache class which is used to hold information about the current state of a register that is currently used to hold a variable.


      class Cache
        # The register this cache entry is for
        attr_accessor :reg
    
        # The block to call to spill this register if the register is dirty (nil if the register is not dirty)
        attr_accessor :spill
    
        # True if this cache item can not be evicted because the register is in use.
        attr_accessor :locked
    
        def initialize reg
          @reg = reg.to_sym
        end
    
        # Spill the (presumed dirty) value in the register in question,
        # and assume that the register is no longer dirty. @spill is presumed
        # to contain a block / Proc / object responding to #call that will
        # handle the spill.
        def spill!
          @spill.call if @spill
          @spill = nil
        end
      end

The RegisterAllocator class itself is initialized like this:


      def initialize
        # This is the list of registers that are available to be allocated
        @registers      = [:edx,:ecx, :edi]
    
        # Initially, all registers start out as free.
        @free_registers = @registers.dup
    
        @cached = {}
        @by_reg = {} # Cache information, by register
        @order = {}
      end

The @cached and @by_reg hashes contains the Cache objects referenced by variable name and register respectively. @order gets assigned an array of variables in descending order of priority. As previously discussed, this in effect means by descending order of number of times the variable is referenced at this point.

Additionally, #with_register initializes two more instance variables as needed: @allocated_registers and @allocators, which holds information on which registers have been allocated for temporary use, and debug information about the code that called #with_register respectively.

I won't go through every little method - you can look at the commit (and feel free to ask questions if anything is not clear), but we'll take a look at #cache_reg! which is used to cache a register, as well as evict which is used to remove a variable from the registers (that is, remove the association in the compiler, we do not generate code to actually clear the register), and #with_register, which is used to allocate temporary registers.

#cache_reg! will only allocate registers for variables that have been "registered" with the register allocator. First we try to obtain a register from the list of free/unallocated/uncached registers:


      def cache_reg!(var)
        if !@order.member?(var.to_sym)
          return nil
        end
        free = @free_registers.shift
        if free
          debug_is_register?(free)

If a register is found, we create a new Cache object, referencing the register. If not, we (for now) output a warning. If a register is found, it is returned, otherwise, we return nil.


          c = Cache.new(free)
          @cached[var.to_sym] = c
          @by_reg[free] = c
        else
          STDERR.puts "NO FREE REGISTER (consider evicting if more important var?)"
        end
        free
      end

We'll look at how this is used later.

evict has the opposite role: When we need to ensure that a variable is retrieved from memory next time, we pass it.

We iterate over the variables passed, and try to delete them from the cache. If they were in fact there, we call the spill handler if one was set. The spill handler is any object (such as a Proc or lambda) that responds to #call, and it is its responsibility to store the contents of the register back to memory before it is freed.

This is only assigned if the in-register version of the variable is intentionally modified.

We then add the register back in the list of free regsiters.

For convenience, I've added an #evict_all method that evicts all currently cached variables.


      def evict vars
        Array(vars).collect do |v|
          cache = @cached.delete(v.to_sym)
          if cache
            r = cache.reg
            debug_is_register?(r)
            cache.spill!
            @by_reg.delete(r)
            @free_registers << r
          end
          r ? v : nil
        end.compact
      end
    
      def evict_all
        evict(@cached.keys)
      end

The longest method in the register allocator for now is #with_register. This has been lifted from Emitter and adapted, and in fact we've covered changes to that one above, but I'll go through it from scratch.

First we check if the client has requested a specific register. If so, we try to retrieve this register. If not, we get the first one available. This is the change we did above to the Emitter version.

If none was immediately vailable, we go through the variables cached from least frequently used (in this method), to most, and evict the first one that is not "locked" in place.

(Note, there's a potential problem here: The client code does need to be able to handle the case where the preferred register is already taken, as we currently don't go on to evict the variable specifically allocated to that register, but I punted on that when changing the version previously in Emitter - we probably should fix that, but now now)


     # Allocate a temporary register. If specified, we try to allocate
      # a specific register.
      def with_register(required_reg = nil)
        @allocated_registers ||= Set.new
    
        if required_reg
          free = @free_registers.delete(required_reg)
        else
          free = @free_registers.shift
        end
    
        if !free
          # If no register was immediately free, but one or more
          # registers is in use as cache, see if we can evict one of
          # them.
    
          if !@cached.empty?
            # Figure out which register to drop, based on order.
            # (least frequently used variable evicted first)
            @order.reverse.each do |v|
              c = @cached[v]
              if c && !c.locked
                reg = c.reg
                evict(v)
                free = reg
                break
              end
            end
          end
        end

The next part is simply debug output, primarily in case we actually run out of registers, which means we're trying to use more temporary registers at one time than the allocator has registers available total (3 currently). It should not happen if we are careful about what we allocate temporary registers for:


        debug_is_register?(free)
    
        if !free
          # This really should not happen, unless we are
          # very careless about #with_register blocks.
    
          STDERR.puts "==="
          STDERR.puts @cached.inspect
          STDERR.puts "--"
          STDERR.puts @free_registers.inspect
          STDERR.puts @allocators.inspect
          raise "Register allocation FAILED"
        end

And some more debug support:


       # This is for debugging of the allocator - we store
        # a backtrace of where in the compiler the allocation
        # was attempted from in case we run out of registers
        # (which we shouldn't)
        @allocators ||= []
        @allocators << caller

Finally, we mark the register as allocated, yield to the client code, and free the register again.


        # Mark the register as allocated, to prevent it from
        # being reused.
        @allocated_registers << free
    
        yield(free)
    
        # ... and clean up afterwards:
    
        @allocators.pop
        @allocated_registers.delete(free)
        debug_is_register?(free)
        @free_registers << free
      end

Tieing the allocator into the Emitter and Compiler

The changes to compiler.rb are fairly minor. We will go through the changes to each of get_arg, output_functions, compile_if, compile_let and compile_assign from e1049e3 separately, and intersperse that with how it ties in with the changes to Emitter in the same commit.

Lets start with #get_arg:


    @@ -86,7 +86,7 @@ class Compiler
       # If a Fixnum is given, it's an int ->   [:int, a]
       # If it's a Symbol, its a variable identifier and needs to be looked up within the given scope.
       # Otherwise, we assume it's a string constant and treat it like one.
    -  def get_arg(scope, a)
    +  def get_arg(scope, a, save = false)
         return compile_exp(scope, a) if a.is_a?(Array)
         return [:int, a] if (a.is_a?(Fixnum))
         return [:int, a.to_i] if (a.is_a?(Float)) # FIXME: uh. yes. This is a temporary hack
    @@ -94,7 +94,23 @@ class Compiler
         if (a.is_a?(Symbol))
           name = a.to_s
           return intern(scope,name.rest) if name[0] == ?:
    -      return scope.get_arg(a)
    +
    +      arg = scope.get_arg(a)
    +
    +      # If this is a local variable or argument, we either
    +      # obtain the argument it is cached in, or we cache it
    +      # if possible. If we are calling #get_arg to get
    +      # a target to *save* a value to (assignment), we need
    +      # to mark it as dirty to ensure we save it back to memory
    +      # (spill it) if we need to evict the value from the
    +      # register to use it for something else.
    +
    +      if arg.first == :lvar || arg.first == :arg
    +        reg = @e.cache_reg!(name, arg.first, arg.last, save)
    +        return [:reg,reg] if reg
    +      end
    +
    +      return arg
         end

The comment says almost all that needs to be said. The main thing to notice here is the "save" argument, which we'll see used later by compile_assign. Let's take a look at Emitter#cache_reg!.

First we see if this variable is currently cached in a register.

If save was passed, we mark this entry as dirty, so that if the variable is later evicted from the register, we spill the value back to memory. Regardless whether or not we got a register back, we return, as we certainly don't want to load the value into memory just to overwrite it and then spill it later.

(Note that we could add code to request a register and fill it with the modified value, and immediately mark it dirty; in some cases this might be worthwhile by potentially saving us a load later on, but that's speculative enough that I'd want to do real tests first)


      def cache_reg!(var, atype, aparam, save = false)
        reg = @allocator.cached_reg(var)
    
        if (save)
          mark_dirty(var, atype, aparam) if reg
          return reg
        end

Then we output some comments for debugging purposes and to make it easier for us to examine the results of the allocation later on (we might strip this out later), and if the register was not already in the cache, we try to request a register to cache it in, and if we get one we load it:


        comment("RA: Already cached '#{reg.to_s}' for #{var}") if reg
        return reg if reg
        reg = @allocator.cache_reg!(var)
        return nil if !reg
        comment("RA: Allocated reg '#{reg.to_s}' for #{var}") if reg
        comment([atype,aparam,reg].inspect)
        load(atype,aparam,reg)
        return reg
      end

Let us also take a quick look at Emitter#mark_dirty:

The most important part here is the lambda that is used installed to handle spills. It simply outputs another debug comment, and saves the register back where it came from:


      def mark_dirty(var, type, src)
        reg = cached_reg(var)
        return if !reg
        comment("Marked #{reg} dirty (#{type.to_s},#{src.to_s})")
        @allocator.mark_dirty(reg, lambda do
                                comment("Saving #{reg} to #{type.to_s},#{src.to_s}")
                                save(type, reg, src)
                              end)
      end

As for Compiler#output_functions, the only big change there is that it now passes the variable frequency information:


        varfreq = func.body.respond_to?(:extra) ? func.body.extra[:varfreq] : []
        @e.func(name, func.rest?, pos, varfreq) do

So lets see what Emitter#func does with it. It ensures all registers are evicted before we generate code for a new function, as the function obviously can't control where it is called from. We then install the new frequency information in the register allocator. And on the way out again, we evict the registers again, for good measure. Actually the latter one is necessary in case any of the registers needs to be spilled. The former one is a precaution - the registers ought to have been evicted before we get there.


    -  def func(name, save_numargs = false, position = nil)
    +  def func(name, save_numargs = false, position = nil,varfreq= nil)
         @out.emit(".stabs  \"#{name}:F(0,0)\",36,0,0,#{name}")
         export(name, :function) if name.to_s[0] != ?.
         label(name)
    @@ -479,12 +518,17 @@ class Emitter
         lineno(position) if position
                            @out.label(".LFBB#{@curfunc}")
    
    +    @allocator.evict_all
    +    @allocator.order(varfreq)
         pushl(:ebp)
         movl(:esp, :ebp)
         pushl(:ebx) if save_numargs
         yield
         leave
         ret
    +
    +    @allocator.evict_all
    +
                              emit(".size", name.to_s, ".-#{name}")
         @scopenum ||= 0
         @scopenum += 1
    @@ -494,6 +538,7 @@ class Emitter
       end

The change to Compiler#compile_if is simple: We simply need to explicitly pass the register to test, rather than rely on it always being %eax:


      def compile_if(scope, cond, if_arm, else_arm = nil)
        res = compile_eval_arg(scope, cond)
        l_else_arm = @e.get_local
        l_end_if_arm = @e.get_local
        @e.jmp_on_false(l_else_arm, res)
        compile_eval_arg(scope, if_arm)
        @e.jmp(l_end_if_arm) if else_arm
        @e.local(l_else_arm)
        compile_eval_arg(scope, else_arm) if else_arm
        @e.local(l_end_if_arm) if else_arm
        return [:subexpr]
      end

In compile_let the only change is that we want to ensure we evict all registers that the %s(let ...) node aliases, as otherwise we will be using values from the wrong variable:


          @e.evict_regs_for(varlist)
          @e.with_local(vars.size) { compile_do(ls, *args) }
          @e.evict_regs_for(varlist)

In compile_assign, our only concern is passing a truthy value for "save":


          args = get_arg(scope,left,:save)

Optimizing temporary register usage for already cached values

We'll do one tiny little additional change, and then we'll look at the resulting code.

In e74d92d we introduce Emitter#with_register_for:


      def with_register_for(maybe_reg)
        c = @allocator.lock_reg(maybe_reg)
        if c
          comment("Locked register #{c.reg}")
          r = yield c.reg
          comment("Unlocked register #{c.reg}")
          c.locked = false
          return r
        end
        with_register {|r| emit(:movl, maybe_reg, r); yield(r) }
      end

The purpose of this is as a small optimization in cases where we need a temporary register to hold a variable, but already have the variable in a register. We need to ensure it doesn't get evicted, same as if we allocate a temporary register.

And here's the only place we use it so far:


      def compile_2(scope, left, right)
        src = compile_eval_arg(scope,left)
        @e.with_register_for(src) do |reg|
    #      @e.emit(:movl, src, reg)
          @e.save_result(compile_eval_arg(scope,right))
          yield reg
        end
        [:subexpr]
      end
    }}}    
       
    If the variable is already in a register, it can save us a movl.
    
    
    ## A quick look at the resulting code ##
    
    Let us compile the example code from earlier. It should give something like this:
    
    -asm-
    __method_Object_foo:
        .stabn  68,0,2,.LM336 -.LFBB61
    .LM336:
    .LFBB61:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $36, %esp
        .stabn  68,0,3,.LM337 -.LFBB61
    .LM337:
        subl    $20, %esp
        movl    $5, -20(%ebp)
        movl    $2, -8(%ebp)
        movl    $5, -12(%ebp)
        movl    $10, -16(%ebp)
        # RA: Allocated reg 'edx' for a
        # [:lvar, 0, :edx]
        movl    -8(%ebp), %edx
        # Locked register edx
        # RA: Allocated reg 'ecx' for b
        # [:lvar, 1, :ecx]
        movl    -12(%ebp), %ecx

Here we see the first uses, and as you can see from the "Locked" comment above, this also made use of the optimization where we'd previously have allocated another register and moved or reloaded the variable:


        movl    %ecx, %eax
        addl    %edx, %eax
        # Unlocked register edx

And here we're assigning the result of (add a b) back to a, which currently lives in %edx. As a result it is marked "dirty": It needs to be written back to memory when evicted.


        # Marked edx dirty (lvar,0)
        movl    %eax, %edx
        # RA: Already cached 'edx' for a
        # Locked register edx
        # RA: Allocated reg 'edi' for c
        # [:lvar, 2, :edi]
        movl    -16(%ebp), %edi

And we use a again, from %edx and start reaping the rewards:


        movl    %edi, %eax
        addl    %edx, %eax
        # Unlocked register edx
        # Marked edx dirty (lvar,0)
        movl    %eax, %edx

Of course, note above, that we could save much more with smarter handling of these registers - in these examples we could have done addl %edi, %edx directly, and saved two further movl's - we have tons of further optimizations to do.

And here are some more examples where we reuse a


        # RA: Already cached 'edx' for a
        # Locked register edx
        movl    $2, %eax
        imull   %edx, %eax
        # Unlocked register edx
        # Marked edx dirty (lvar,0)
        movl    %eax, %edx
        subl    $8, %esp
        movl    $2, %ebx
        movl    $.L83, %eax
        movl    %eax, (%esp)
        # RA: Already cached 'edx' for a
        movl    %edx, 4(%esp)
        movl    $printf, %eax

And here we finally spill a back to memory from %edx, right before we call printf, as %edx can be overwritten:


        # Saving edx to lvar,0
        movl    %edx, -8(%ebp)
        call    *%eax

(Incidentally, this is where liveness analysis makes a big difference: after the last use of a, it'll still get spilled, but that's of course pointless since this is a local variable)

Final words

I'd like to reiterate that this is a trivial and primitive allocator. It misses tons of opportunities, and may do stupid things, like load stuff, use it once, have to evict it, load it again, use it once, have to evict it, and so on.

The important thing, though, is to get some basic infrastructure in place that we can expand on. We can now later add more advanced logic to determine which variables to cache when with much less effort.

Next time, we'll look at another side of this: Caching self in %esi, which we'll handle quite differently (and in a much shorter part...)

Writing a (Ruby) compiler in Ruby bottom up - step 32

Sat, 08 Feb 2014 02:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Testing And Debugging Code Generation

Unit testing code generation poses some particular challenges because so many things can go wrong, and they can go wrong in all kinds of horrible ways that makes them extremely nasty to track down,

If you've paid attention, you have seen some code generation tests (in compiler.feature) that will catch cases where the code blatantly crashes or returns completely wrong results. These can be really nasty to figure out.

But there are many far more insidious types of bugs that can lie latent and that often doesn't get triggered for small test programs:

Randomly overwriting wrong parts of memory - programs can often keep running for a long time with such bugs, until suddenly something gets corrupted.
Updating the stack incorrectly can lead to everything from calculations resulting in wrong results, but often not the one you're testing for, to crashes that often leave you without a stacktrace to hint at where you failed, or pointing at the wrong spot.
Wrong values in registers might not be noticed until combined with another piece of code that suddenly rely on those registers.

And so on.

So let us make the code generation testing more robust, and use these new facilities to see both if we can catch some bugs, and make it easier to track down the causes. Hopefully we can clean the board and fix some of these issues too.

We will add a number of simple facilities to do more comprehensive testing:

We have the option --trace to make the compiler generate debug statements that trace entry and exit from methods, but that one is currently broken. Lets fix it.
The option --stackfence that will make the compiler generate code to push magic values onto the stack at every call site, and code to check for the magic value on return and output an error if it is not present.
%s(saveregs) will return an array of the current value of registers, so that we may compare them against expected values or output them.
The option --memfence that is like --stackfence except it will manipulate memory allocations by replacing calls to malloc with a function that pads the allocated regions on either side with "magic" values.

This is by no means a comprehensive set of possible debugging help we can add, but combined it creates a good foundation to let us catch a whole series of bugs with code generation that might otherwise require a lot of manual inspection and writing very complicated tests.

To see what we can get out of these, we will try to make the rest of the compiler.feature tests run, and generally clean things up.

But first, lets make things harder for ourselves based on some notes I've taken about failing tests:

Tests and more tests.

Here's one that fails spectacularly (added as features/inputs/method.rb in 34e92a2)


    class Foo
    
      def initialize bar
        puts bar
      end
    
    end
    
    Foo.new("baz")

And this one (features/inputs/method2.rb in 34e92a2)


    
    class Foo
    
      def initialize
      end
    
      def foo
        puts "foo"
      end
    
      def bar arg
        puts arg
      end
    end
    
    f = Foo.new
    f.foo
    f.bar("bar")

But this one works (features/inputs/method3.rb in 34e92a2):


    class Foo
    
      def initialize
      end
    
      def foo bar,baz
        puts bar,baz
      end
    end
    
    f = Foo.new
    f.foo("bar","baz")

.. hinting at a problem with single argument methods, perhaps?

And this one hints at problems with the splat (*somearg) handling:


    class Foo
      def foo arg1,arg2
        %s(printf "foo: %d\n" numargs)
        %s(printf "%p\n" arg1)
        %s(printf "%p\n" arg2)
      end
    
      def bar *splat
        %s(printf "bar: %d\n" numargs)
        %s(printf "%p\n" (index splat 0))
        %s(printf "%p\n" (index splat 1))
        foo(*splat)
      end
    end
    
    f = Foo.new
    a = "foo"
    b = "bar"
    
    # Should give same pairs of output 3 times
    f.foo(a,b)
    f.bar(a,b)

This will get us started, combined with what is already there (try rake failing to see what's not completing)

Debugging in the face of crashes

For all of these we can get some limited help from gdb. A lot of help if we have the patience of a monk.

A run of method2 shows us some of the reasons for better test tools, but also gives plenty of hints:


    $ gdb /tmp/method2
    GNU gdb 6.8-debian
    Copyright (C) 2008 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "i486-linux-gnu"...
    (gdb) run
    Starting program: /tmp/method2
    foo
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8ae0f68
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8ae0f68
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8ae0f68
    
    Program received signal SIGSEGV, Segmentation fault.
    0x0804c768 in __method_Object_puts () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/object.rb:46
    46          while i < na
    (gdb)

In this case the real problem is not where the crash happens, but clearly earlier. The "foo" gets printed, so the problem likely arises after that, but well before __method_Object_puts even though that is where the crash happens, as we shouldn't be seeing the __send__ bypassing vtable not yet implemented. warnings.

(Note: If you see something different, that is perfectly normal - stack smashing bugs are notoriously tricky in that the smallest little thing can make the crash occur somewhere entirely different.)

So let's start off by fixing our--trace option and see what that tells us (with the caveat that it will change the code that is output, and so may change the character of the crash)

Trace

Our --trace option will just be a start. There's an endless amount of stuff we can trace. The tricky tradeoff will be to get the right balance to prevent us from spewing far much information. At some point we'll probably want to add more granular tracing functionality. For now, we'll experiment:

We'll add a relatively generic trace method to the Compiler class that will allow us to ouput debug text to stderr if --trace was given to the compiler.
We'll add trace output for expressions an for entering and exiting functions.

Here's a first stab (in b31e22ed8)


      def trace(pos,data)
        return false if !@trace
        
        # A bit ugly, but prevents infinite recursion
        # if we accidentally calls anything "traceworthy":
        @trace = false 
    
        @e.with_stack(2,true) do
            if pos
              pos = pos.short
            end
            sio = StringIO.new
            sio << "#{pos ? pos+":" : "  "} "
    
            if data.is_a?(String)
              sio << data << "\n"
            else
              print_sexp(data,sio,{:prune => true})
            end
            str = sio.string
            ret = compile_eval_arg(nil,str)
            @e.save_to_stack(ret,0)
            @e.movl([:stderr],:eax)
            @e.save_to_stack(:eax,1)
            @e.call("fputs")
          end
          @trace = true
      end

We allocate space for two slots on the stack, outputs the source position if provided, and either a string or an AST fragment serialized as %s() expressions.

Notice the way we go about the call. We use compile_eval_arg only to load the address of the formatted string, and then push it onto the stack, then put the address of the C library's stderr on, and call fputs, but without taking advantage of the compilers built in function call support.

My reason for this is simply to ensure the change of being affected by any weird bugs in other parts of the code generation - I want the generated trace code to be as simple and straight-forward and isolated as possible.

In 42c8dae I added support for the :prune option above, to make the trace output simpler.

In cc98262c4 you can see the added calls to the trace method.

On its own, this does not appear to really help all that much in tracking down the issues raised by the various failing tests.

But here's some example output from compiling features/input/method2.rb with --trace:


    class.rb, @38,5: (sexp (assign (index ob 0) self))
    class.rb, @38,5: (sexp (assign (index ob 0) self))
       (assign (index ob 0) self)
       (index ob 0)
       (callm ob initialize (
        (splat rest)))
       => callm :ob.:initialize
    
    string.rb, @8,3: (let (__env__ __tmp_proc)
      (sexp (assign @buffer 0))
    )
    string.rb, @8,3: (let (__env__ __tmp_proc)
      (sexp (assign @buffer 0))
    )
    string.rb, @16,5: (sexp (assign @buffer 0))
    string.rb, @16,5: (sexp (assign @buffer 0))
       (assign @buffer 0)
       <= callm ob.initialize
    
       <= callm String.new
    
       (callm s __set_raw (str))
       => callm :s.:__set_raw
    
    Segmentation fault

Clearly it can use some more love. But it does make it easier to follow what is actually leading up to the crash, and that might prove useful in finding the exact cause later on.

Adding --stackfence

Stack fencing is conceptually very simple: Before the start of the allocated region for a function call, push one or more items of data, at least one of which ought to be a "magic" value. This can either be a static randomly picked value that is reasonable unlikely to occur by accident (in other words, avoid low integer values), or it can be a value that is randomly chosen for each occurrence. We'll do the latter.

On return, after popping the arguments off the stack, we then want to compare the top of the stack against the magic value, before returning the stack to its original state. If the stack state is invalid, on the other hand, we'll want to output some trace data.

We add the stackfence method in dde1814:


      def stackfence
        if !@stackfence
          return yield
        end
    
        # Note: We don't care if this value is all that random.
        
        val = (rand * (2**32)).floor
        @e.pushl(val)
        r = yield
        @e.cmpl("$#{val}","(%esp)")
        l = @e.get_local
        @e.jz(l)
        trace(nil,"ERROR: Stack fence violation. Expected 0x#{val.to_s(16)}")
        @e.local(l)
        @e.addl(4,:esp)
        r
      end

In c806999 we simply then wrap stackfence do ... end around calls we want to fence.

Somewhat disappointingly, --stackfence doesn't actually help us with the current set of failing tests. At least not directly. But note that due to the nature of many stack trashing bugs, pushing a random value like this onto the stack will often cause crashes earlier (on next function return after the stack trashing), before the fence test is allowed to happen. We can still benefit from that by starting the program under gdb, and requesting a backtrace when the crash happens.

Adding %(saveregs)

So we move on to %(saveregs). We will continue to ignore portability for now (and let you have the fun on watching me clean up that mess a while down the line, as I have a planned part dealing with re-targeting the compiler to another CPU architecture) and just have saveregs dump the registers to a freshly allocated bit of memory with no indication of what they are.

Saveregs can be found in b86ee7c. I do not know if x86 has an instruction to bulk save registers (e.g. the M68k has "MOVEM" which can take a list of registers to copy), nor do I care. As usual the point is not to be efficient, but to get results easily, and quickly.

Note that we don't take care to ensure the registers are unchanged at the end of this.


    class Compiler
    
      # Debug instruction, to save registers 
      # 
      def compile_saveregs(scope)
        # First we push the registers on the stack, to ensure they won't get messed up
        # when we allocate memory.
    
        @e.pushl(:esp)
        @e.pushl(:ebp)
        @e.pushl(:edi)
        @e.pushl(:esi)
        @e.pushl(:edx)
        @e.pushl(:ecx)
        @e.pushl(:ebx)
        @e.pushl(:eax)
    
        # Allocate memory
        @e.pushl(8)
        @e.call("malloc")
        @e.addl(4,:esp)
    
        # We're naughty and assume we get memory:
        @e.popl(:ebx)
        @e.movl(:ebx,"(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"4(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"8(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"12(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"16(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"20(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"24(%eax)")
        @e.popl(:ebx)
        @e.movl(:ebx,"28(%eax)")
    
        [:subexpr]
      end
    end

Now that we have %s(saveregs) we can do this:


    %s(defun printregs (regs) (do
      (printf "eax: %08x, ebx: %08x, ecx: %08x, edx: %08x, esi: %08x, edi: %08x, ebp: %08x, esp: %08x\n"
       (index regs 0)
       (index regs 1)
       (index regs 2)
       (index regs 3)
       (index regs 4)
       (index regs 5)
       (index regs 6)
       (index regs 7))
    ))
    
    def foo
      %s(assign regs (saveregs))
      %s(printregs regs)
    end
    
    %s(assign regs (saveregs))
    %s(printregs regs)
    foo
    %s(assign regs (saveregs))
    %s(printregs regs)

This will dump registers 3 times - once before calling foo, one inside, and one after.

It may be tempting to define a function to save and dump the registers in one go, like this:

%s(defun dumpregs () (printregs (saveregs)))

Or even just do %s(printregs (saveregs))

But this won't work well. The registers will then be saved after we start preparing the stack and registers for the call to printregs, and so the values will not be the same as what we're looking for.

In the hypothetical dumpregs example, it's worse: We've pushed an entirely unrelated stack frame and modified registers just in order to call dumpregs, and then another frame to prepare to call printregs.

Lets take a quick look at the output:


    eax: 0804d47d, ebx: 00000003, ecx: bfb354c8, edx: 0823b184, esi: 080524b0, edi: 08048510, ebp: bfb354d8, esp: bfb354d4
    eax: 0804d47d, ebx: 00000001, ecx: 0823af98, edx: b76ec0f0, esi: 080524b0, edi: 08048510, ebp: bfb354c4, esp: bfb354b0
    eax: 00000077, ebx: 00000009, ecx: 00000000, edx: b76ec0f0, esi: 080524b0, edi: 08048510, ebp: bfb354d8, esp: bfb354d4

There's not that much we will learn from this example. Many of these registers gets trashed regularly. ebp and esp however, won't. In this case we do see that ebp and esp both are unchanged when "outside" foo. That's good - it means the call to foo at the very least returns the stack and local variable frames to what they should be (we index local variables and arguments relative to ebp, remember, as esp frequently changes inside a function).

But lets augment the output. This prints out 32 bytes at (%esp), 4(%esp) etc. and (%ebp), 4(%ebp) etc., giving us a quick way of looking at the arguments and return address of the current function (via ebp) and current state of the stack respectively (via esp).

I first added printregs to lib/core/core.rb as a utility (in 066b8e6), and then augmented it as follows in 20b4abc:


    --- a/lib/core/core.rb
    +++ b/lib/core/core.rb
    @@ -78,4 +78,27 @@ false = 0    # FIXME: Should be an object of FalseClass
        (index regs 5)
        (index regs 6)
        (index regs 7))
    +
    +  (assign sp (index regs 6))
    +  (printf "(ebp): %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x\n"
    +   (index sp 0)
    +   (index sp 1)
    +   (index sp 2)
    +   (index sp 3)
    +   (index sp 4)
    +   (index sp 5)
    +   (index sp 6)
    +   (index sp 7))
    +
    +  (assign sp (index regs 7))
    +  (printf "(esp): %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x\n"
    +   (index sp 0)
    +   (index sp 1)
    +   (index sp 2)
    +   (index sp 3)
    +   (index sp 4)
    +   (index sp 5)
    +   (index sp 6)
    +   (index sp 7))
    +
     ))

In practice - take 1

Let's try to make use of this to track down our regressions. Lets start with features/inputs/method2.rb

First, let's rewrite bar like this:


      def bar arg
          %s(assign r (saveregs))
          %s(printregs r)
          puts arg
      end

I get a bunch of nonsense, and then the register/stack output:


    foo
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8665f68
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8665f68
    WARNING: __send__ bypassing vtable not yet implemented.
    WARNING:    Called with (nil)
    WARNING:    self = 0x8665f68
    eax: 0804e234, ebx: 00000004, ecx: 0866ce28, edx: b76f70f0, esi: 080503d0, edi: 080484c0, ebp: bfc51aa8, esp: bfc51a94
    (ebp): bfc51ac8, 0804a917, 0866d600, 00000000, 00000000, 00000000, 00000000, bfc51ae0
    (esp): 0804a902, 08665f68, 0866d6a0, 0866d6c0, 00000000, bfc51ac8, 0804a917, 0866d600
    Segmentation fault

How do we interpret this? Well. The first curious thing is ebx. Why does it contain "4"? We use ebx to contain the number of arguments passed, and while we need to account for self and an optional block argument, that does not add up to 4 together with arg.

Also note the (ebp) line, which shows what was on the stack right after the start of the method. The top entry is the old value of %ebp. The next one is the return address. Then comes?

We should expect the arguments. But there's just one non-null value, and we expect more. This one does look quite nasty. Nasty enough to look at the asm output again for a change (it is ugly, and in dire need of some love - we'll definitively set aside a part for that soon).

I've added comments to this to explain rather than break up the code segment:


        .stabn  68,0,24,.LM229
    .LM229:
        # callm :f.:bar
        subl    $20, %esp
        movl    $4, %ebx    # This is the offending number of arguments
        pushl   %ebx        # It's being pushed, so that in absence of proper
                            # proper register allocation, we're pre-emptively
                            # making sure it's not trashed. See (1) below
        movl    f, %eax     
        movl    %eax, 4(%esp) # "f" will be "self" inside the method call
        movl    $0, 8(%esp)   # We don't have a block to pass
        # callm :self.:sexp   # Uhm. WTF?!? (2)
        subl    $20, %esp     # Somehow the compiler got the idea we're trying to call 
                              # "sexp" as a method on self.
        movl    $3, %ebx      # ... and that it has arguments

(1) the reason we don't delay loading %ebx until right before the call is that in the case of "splat" handling (*somevar), the value is dynamically created. We should optimize this for the normal case of no splat, but as always performance is low priority.

(2) This points to a weaknes in the %s() syntax: If we add a set of parentheses too many, we'll try to call the return value of an expression. If we have one too little, we'll treat something as an explicit value instead of calling it to obtain a value. Lets take a look at the parse tree.


       (callm f bar (sexp (call __get_string .L1)))

... and this appears to be the likely culprit - a missing set of parentheses surrounding the sexp node.

This is curious. If you look at rewrite_strconst, we explicitly have a line with a "FIXME" in front talking about working around a parser inconsistency. But look a few lines up. is_call determines if this change is applied, and is_call doesn't trigger for method calls, just low level function calls. So we do this (in 245c016):


       def rewrite_strconst(exp)
         exp.depth_first do |e|
           next :skip if e[0] == :sexp
    -      is_call = e[0] == :call
    +      is_call = e[0] == :call || e[0] == :callm
           e.each_with_index do |s,i|
             if s.is_a?(String)
               lab = @string_constants[s]

And method2 now works:


    foo
    eax: 0804e0e6, ebx: 00000003, ecx: 0805059f, edx: 095c3e28, esi: 08050280, edi: 080484c0, ebp: bf7ff3f8, esp: bf7ff3e4
    (ebp): bf7ff418, 0804a857, 095c4600, 00000000, 095c4690, 0804a6d6, 00000000, bf7ff430
    (esp): 00000000, 095c4690, 00000001, 095c46a0, 0804a842, bf7ff418, 0804a857, 095c4600
    bar

How does this frame look? Much better. ebx is 3, which is (self, the optional empty block argument, and arg). I we look at the (ebp) line, we see the old %ebp, the return address, and then arguments: self, 0 for the block argument, and another address which presumably (since the code worked) is the string object for "bar".

(I don't like "presumably" - we can do better by expanding the printargs function to recognize types and dump more extensive data; for now I'll leave that as an exercise to the reader...)

In practice - features/inputs/method.rb

method.rb segmentation faults for me, and so I tried it under gdb:


    $ gdb /tmp/method
    GNU gdb 6.8-debian
    Copyright (C) 2008 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "i486-linux-gnu"...
    (gdb) run
    Starting program: /tmp/method
    
    Program received signal SIGSEGV, Segmentation fault.
    0x0804c90c in __method_Object_puts () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/object.rb:46
    46          while i < na
    (gdb) bt
    #0  0x0804c90c in __method_Object_puts () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/object.rb:46
    #1  0x0804d98d in __method_Foo_initialize () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/features/inputs/method.rb:6
    #2  0x0804e4cc in __method_Class_new () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/class.rb:38
    #3  0x0804a79c in main () at method.rb:12

When instrumented with saverags/printregs in Foo#initialize, I get 5 in ebx... Yikes. --parsetree doesn't reveal any obvious problems to me. So another look at assembler output. Oddly enough, that looks fairly sane. But here's the thing: we of course don't call initialize directly - it's called by Class#new. So the next step is to instrument that too with saveregs.

Unfortunately my tries with that blows up badly. Really badly. Clearly we're close. And it's yet again the assembler output we'll want to look at, I suspect. This time of Class#new, specifically the part where Class#new calls ob.initialize(*rest).

I've annotated it inline:


        # callm :ob.:initialize
        # This part is generated by handle_splat:
        # *rest
        
        # UhOh (2)
        movl    -4(%ebp), %eax   # We get the number of arguments
        sall    $2, %eax         # Multiply it by 4 to get the size
        subl    %eax, %esp       # Allocate enough space to copy it onto the stack again
        movl    %eax, %edx       # Make a copy of the number of bytes
        leal    16(%ebp), %eax   # This is where "rest" is located on the stack
        addl    %eax, %edx       # We add it to our number of bytes, effectively getting the last adress + 1
        movl    %esp, %ecx       # Make a copy of the stack pointer we can use to iterate over
    .L144:
        movl    (%eax), %ebx     # Copy from rest...
        movl    %ebx, (%ecx)     # ..to "new rest"
        addl    $4, %eax         # Bump source address
        addl    $4, %ecx         # Bump destination address
        cmpl    %eax, %edx       # At end?
        jne .L144                # If not, jump back to .L144
        
        # This is a hairy way of getting the number of arguments back:
        subl    %esp, %ecx 
        sarl    $2, %ecx
        
        # *rest end
    
        # UhOh (1)
        subl    $20, %esp        # We allocate 32 bytes (hex $20) on the stack
        movl    $2, %ebx         # Number of arguments  before the *rest
        addl    %ecx, %ebx       # Add number of arguments from *rest
        pushl   %ebx             # Save for later
        movl    -16(%ebp), %eax  # Copy ob to %eax
        movl    %eax, 4(%esp)    # Save ob to stack, above the %ebx we pushed
        movl    $0, 8(%esp)      # Save optional block argument
        popl    %ebx             # Remove %ebx (ob is now at (%esp))
        movl    (%esp), %ecx     # Copy ob into %ecx
        movl    (%ecx), %ecx     # Copy class pointer into %ecx
        movl    40(%ecx), %eax   # Copy vtable entry for #initialize into %eax
        call    *%eax            # call ob.initialize
        addl    $20, %esp        # free stack
        
        # UhOh (3)
        movl    -4(%ebp), %eax   # get numargs
        sall    $2, %eax         # Multiply by 4
        addl    %eax, %esp       # Free splat arguments.
        
        # callm ob.initialize END

Going through it like this suddenly makes it clearer... Or maybe not?

See (1) above. Note that at this point we've spent a lot of time putting the splat arguments onto the stack. Then we go ahead and subtract 32 bytes from %esp even though we're only using 8 for the two arguments. Yikes.

Let's look at Emitter#with_stack which is responsible for this stack allocation:


      def with_stack(args, numargs = false)
        # We normally aim to make the stack frame aligned to 16
        # bytes. This however fails in the presence of the splat operator
        # If a splat is present, we instead allocate exact space, and use
        # %ebx to adjust %esp back again afterwards
        adj = PTR_SIZE + (((args+0.5)*PTR_SIZE/(4.0*PTR_SIZE)).round) * (4*PTR_SIZE)
        
        # If we're messing with the stack, any registers marked for saving will be
        # saved to avoid having to mess with the stack offsets later
            
        if @save_register && @save_register.size > 0
          @save_register.each do |r|
            if r[1] == false
              @out.emit(:pushl,r[0])
              r[1] = true
            end
          end
        end
    
        subl(adj,:esp)
        movl(args, :ebx) if numargs
        yield
        addl(adj, :esp)
      end

The comment looks promising. Except we've forgotten to take care of this.

Thankfully this is easily fixed (in b32ba75)


    -    adj = PTR_SIZE + (((args+0.5)*PTR_SIZE/(4.0*PTR_SIZE)).round) * (4*PTR_SIZE)
    +    if numargs
    +      adj = PTR_SIZE * args
    +    else
    +      adj = PTR_SIZE + (((args+0.5)*PTR_SIZE/(4.0*PTR_SIZE)).round) * (4*PTR_SIZE)
    +    end

But that doesn't fix the odd value in %ebx. Until we look at (2) above (near the top). numargs gives us the number of arguments total. But we're only copying rest.

Later, we actually want the number of elements in rest and that's an entirely different thing.

We can fix that by accounting for the number of fixed arguments (in bcb7668):


    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -457,6 +457,7 @@ class Compiler
         # (needs proper register allocation)
                          @e.comment("*#{args.last.last.to_s}")
         reg = compile_eval_arg(scope,:numargs)
    +    @e.subl(args.size-1,reg)
         @e.sall(2,reg)
         @e.subl(reg,:esp)
         @e.movl(reg,:edx) 
    @@ -472,6 +473,7 @@ class Compiler
         @e.jne(l)
         @e.subl(:esp,:ecx)
         @e.sarl(2,:ecx)
    +    @e.subl(1,:ecx)

Note that this is still one huge hack, in that we're only handling splat properly in a very small subset of cases where it can be used.

That leaves us with (3): We overwrite the return value from #initialize. Of course in this specific case that doesn't matter, as Class.new will ignore that return value. But it's serious in other situations, so lets concoct up a test case.

This is features/inputs/splatreturn.rb:


    def foo(a)
      "Hey!"
    end
    
    def splat *args
      foo(*args)
    end
    
    puts(splat(1))

We expect it to return "Hey!", but it crashes because of the bug we've already found.

We fix it with yet another messy change to the splat handling:


         if splat
    +      @e.pushl(:eax)
           reg = compile_eval_arg(scope,:numargs)
           @e.sall(2,reg)
    -      @e.addl(reg,:esp)
    +      # We assume :ebx has been trashed at this point anyway
    +      @e.movl(reg,:ebx)
    +      @e.popl(:eax)
    +      @e.addl(:ebx,:esp)
         end

The issue is that we need to safeguard :eax and we don't want to use with_register as that might in the future spill registers to the stack. So we push eax onto the stack, and then we want to adjust the stack... But then %eax will be somewhere we don't want it. So we use %ebx which at this point has likely been trashed (we'll reinitialize it from the stack if needed anyway).

But... We're not home free yet. We've changed handle_splat to subtract the size of the pre-existing address list. So we need to apply that here too.

Here's finally a great test case for --stackfence. With that option, this test program gives me:


    $ /tmp/splatreturn
    [...snip...]
       ERROR: Stack fence violation. Expected 0x29fd8512
       ERROR: Stack fence violation. Expected 0x29fd8512
       ERROR: Stack fence violation. Expected 0x29fd8512
    Hey!
       ERROR: Stack fence violation. Expected 0x29fd8512
       ERROR: Stack fence violation. Expected 0x29fd8512

So lets adjust the stack adjustment again. Notice the @e.subl(args.size,reg) (in 8802ce5):


         if splat
    +      @e.pushl(:eax)
           reg = compile_eval_arg(scope,:numargs)
    +      @e.subl(args.size,reg)
           @e.sall(2,reg)
    -      @e.addl(reg,:esp)
    +      # We assume :ebx has been trashed at this point anyway
    +      @e.movl(reg,:ebx)
    +      @e.popl(:eax)
    +      @e.addl(:ebx,:esp)
         end

Final words, and next time

Debugging code generation is hairy. Unlike ordinary debugging you not only deal with broken higher level logic, but all bets are off with respect to what the code actually does. I hope this part has given some ideas about approaches and tools. But it's just a start, and frankly this part has taken me a lot longer to write than I expected, as I tried to ensure I accurately reflected the process of tracking down these bugs and ran into stumbling block after stumbling block.

Ultimately, it is down to tracking values from register to register, and memory location to memory location in some cases.

Anyway. Next time we're moving on to register allocation. There's a lot of hairy code here by now that makes assumptions about register usage that may or may not work only due to luck.

So first order of business is to walk through our calling conventions and document the register usage. Secondly, to create a more sound foundation for using registers, and leaving choice of registers to the code generation backend (and hopefully reducing the dependencies on x86 in the process, though we still have x86 code littered all over the place).

Writing a (Ruby) compiler in Ruby bottom up - step 31

Tue, 31 Dec 2013 06:15:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

I promised to get a second part out in December somewhere, and it seems like I only barely made it. I'm still hoping to push two out in January, but that's contingent on actually getting time to finish the next one too. But there'll be at least one in January, sometimes towards the middle of the month. Anyway...

Stringing things together

With the new, though basic, Fixnum support, it makes sense to want to print the numbers without having to resort to %s(). Let us add some basic output and conversion functionality.

First lets make compiler.feature actually run again. This turned out to be an embarrassing case of me forgetting to check in two files. With 66d56ef you can run these tests again.

Even more embarrassingly that reveals a few regressions - a motivation for the next part, where we will discuss testing og code generation in more detail, since that's definitively a current weak spot.

We will see soon to what extent these regressions affect what comes next, though.

For now we will only support Kernel#puts and Kernel#print, and only the simplest of use cases, though we will actually put them in Object, again due to lack of include support.

We will assume that the output field separator ($,) is always a linefeed, and we will not do anything to explicitly support array arguments.

We add this test case to compiler.feature:


    puts
    puts "Should be one line down due to linefeed above"
    print "Hello "
    puts 42
    print "World\n"
    print "This","is",1,"test\n"
    puts "This","is","test",2

We hope to see at least part of this:

$ ruby features/inputs/06print.rb

Should be one line down due to linefeed above
Hello 42
World
Thisis1test
This
is
test
2

Instead we get a segmentation fault. There's a number of issues here:

There are missing methods
The primitive method_missing "handler" that we added some time ago has broken.
As you will see, even when we stub out the methods, there are regression with argument passing.

Stubbing out the basics

To begin with, we put a stub Fixnum#to_s with an error, and a String#to_s which simply returns self in place, as well as #puts and #print versions in Object (rather than Kernel, as noted above):

See 6af2c31:


       def puts str
    -    %s(puts (callm str __get_raw))
    +    raw = str.to_s.__get_raw
    +    %s(if raw
    +         (puts raw)
    +         (puts "")
    +         )
    +  end
    +
    +  def print str
    +    raw = str.to_s.__get_raw
    +    %s(if raw
    +         (printf "%s" raw)
    +         )
       end

These are woefully incomplete, but at least in theory they ought to not faily completely....

However, let us take a look what happens if we run the compiler with --parsetree:


    $ ruby compiler.rb  --parsetree --norequire features/inputs/06print.rb
    reading from file: features/inputs/06print.rb
    %s(do
      puts
      (call puts (
          (sexp (call __get_string .L0))))
      (call print (
          (sexp (call __get_string .L1))))
      (call puts ())
      (call print (
          (sexp (call __get_string .L2))))
      (call print (
          (sexp (call __get_string .L3)) (sexp (call __get_string .L4)) (sexp (call __get_fixnum 1))
          (sexp (call __get_string .L5))))
      (call puts (
          (sexp (call __get_string .L3)) (sexp (call __get_string .L4)) (sexp (call __get_string .L6))
          (sexp (call __get_fixnum 2))))
    )

Some likely problems to begin with:

The "naked" puts will likely break horribly as the methods specify a single argument, with no default value, and we don't trap that in any way.
Notice how the puts 42 line has resulted in an empty argument list (!)
We obviously will fail on the parameter lists with multiple values as the methods don't use splats at all. However we really need to actually test for that...

Now, while the methods we added are obviously broken, some stuff ought to get executed anyway (subject to buffering, some of it ought to make it to output too), so lets deal with puts 42 first, then add splats to the methods, try to get just puts to work, and then see if we get through any of the above at that point.

Tracking down the 'puts 42' regression

Passing --notransform shows us the likely culprit is the rewrites in transform.rb"


    $ ruby compiler.rb  --parsetree --norequire --notransform features/inputs/06print.rb
    reading from file: features/inputs/06print.rb
    %s(do
      puts
      (call puts Should be one line down due to linefeed above)
      (call print Hello )
      (call puts 42)
      (call print World\n)
      (call print (This is 1 test\n))
      (call puts (This is test 2))
    )

We'll use that to add tests targetting specific the transforms as a whole, and then specifically for rewrite_fixnumconst since that seems like a reasonable place to start.

But first, since running this code from gdb and doing a backtrace consistently shows crashes related to our __send__ fallback or method_missing - neither which should get triggered at this stage, lets change __send__ to make it more resilient to implementation bugs for now (in 1e23ae0) and give better debug output:


    --- a/lib/core/object.rb
    +++ b/lib/core/object.rb
    @@ -19,7 +19,10 @@ class Object
       end
    
       def __send__ sym, *args
    -    %s(printf "WARNING: __send__ bypassing vtable not yet implemented. Called with %s\n" (callm sym to_s))
    +    %s(printf "WARNING: __send__ bypassing vtable not yet implemented.\n")
    +    %s(printf "WARNING:    Called with %p\n" sym)
    +    %s(printf "WARNING:    self = %p\n" self)
    +    %s(if sym (printf "WARNING:    (string: '%s'\n" (callm sym to_s)))
       end

Next I've added a basic test case for 'puts 42' and the expected output only to compiler.feature in ae61dfd

In 5f792c4 I've added a simple test case for the transformations:


        | "puts 42" | [:do, [:call, :puts, [[:sexp,[:call, :__get_fixnum, 42]]]]]

Running it gives us this:


          expected: [:do, [:call, :puts, [[:sexp, [:call, :__get_fixnum, 42]]]]]
               got: [:do, [:call, :puts, [nil]]] (using ==) (RSpec::Expectations::ExpectationNotMetError)
          ./step_definitions/shunting_steps.rb:32:in `/^the parse tree should become (.*)$/'
          transform.feature:10:in `Then the parse tree should become <tree>'

Looking carefully at rewrite_fixnumconst and comparing to rewrite_strconst reveals the source: "FIXME" warning has been subtly broken to use the wrong index.

The correct line reads (in bfecf5d):


    e[i] = E[e[i]] if is_call && i > 1

Fixing this gets us the following output instead for the compiler.feature puts 42 test:

      expected: "42\n"
      got: "Fixnum#to_s is not implemented\n" (using ==)

... which is reasonable, given that we haven't implemented it yet.

Implementing to_s for Fixnum

Handling this in pure Ruby should be possible with what we have available, though probably not very efficiently. And again in pure laziness, let's defer to the C libs snprintf. And leak some memory in the process, but what's a little memory leak amongst friends who aren't freeing anything at all until exit at the moment? ... (yeah, another fun subject we'll have to bite the bullet on)

This takes care of that (in a2f36be):


       def to_s
    -    "Fixnum#to_s is not implemented"
    +    %s(let (buf)
    +       (assign buf (malloc 16))
    +       (snprintf buf 16 "%ld" @value)
    +       (__get_string buf)
    +       )
       end

Our puts 42 test now works.

Handling variable arguments for puts an print

We now want to make puts (with no arguments) and various other variations work. I'll go through tracking down these regressions in some detail debugging code generation is frankly often one of the most annoying and time consuming parts of writing a compiler. And just maybe it'll teach me to write more tests...

So lets start by adding one:


        | inputs/01ctrivial.rb    | outputs/01ctrivial.txt    | A puts with no argument                     |

Where the input looks like this:

   puts

and the output like this:

... and it fails (I've run it directly rather than bothering to let Cucumber run it yet):


    $ gdb /tmp/01ctrivial
    GNU gdb 6.8-debian
    Copyright (C) 2008 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "i486-linux-gnu"...
    (gdb) run
    Starting program: /tmp/01ctrivial
    
    Program received signal SIGSEGV, Segmentation fault.
    0x00000000 in ?? ()
    (gdb) bt
    #0  0x00000000 in ?? ()
    #1  0x0804c128 in __method_Object_puts () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/object.rb:36
    #2  0x0804a622 in main () at 01ctrivial.rb:1
    (gdb) quit

That's def puts str. First problem is that we're currently expecting an argument, but we're not getting any. In reality the compiler should throw an ArgumentError when the method is declared like this and called with too few arguments. But we've not gotten that far. Anyway, first step is to change this to def puts *str. But we still need to handle the difference in argument numbers and it currently won't be very elegant, as we don't convert str to an actual Ruby array or anything, so we have to dip down to %s(numargs) etc.

We first try to add this to the start of Object#puts:


        %s(assign na (call __get_fixnum (numargs)))
        if na == 2
           %s(puts "")
           return
        end

We expect na to be 2 because of self + the optional __closure__ argument we pass (but that is always present).

This fixes puts on its own, but breaks puts 42. The reason is the splat operator - we can't any longer refer directly to str and expect to get an object - str now refers to an address to an array of objects.

So we change the entire puts to this:


      def puts *str
        %s(assign na (__get_fixnum numargs))
    
        if na == 2
          %s(puts "")
          return
        end
    
        %s(assign raw (index str 0))
        raw = raw.to_s.__get_raw
        %s(if raw
             (puts raw)
             (puts "")
             )
      end

Apart from being horribly ugly, this also doesn't handle multiple arguments, but it's a step further.

You find this and test in 6918bf8

So, lets try something more convoluted, like, say, puts "foo", "bar".

Uh-oh. Doesn't work. What more, if we add a debug printout like %s(printf "numargs=%d\n" numargs) we get a nasty surprise: It returns 3. For me at least.

Some probing in the assembler output shows us this:


       # callm :self.:puts
        subl    $20, %esp
        movl    $4, %ebx
        movl    self, %eax
        movl    %eax, (%esp)
        movl    $0, 4(%esp)
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L11, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        movl    %eax, 8(%esp)
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L12, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        movl    %eax, 12(%esp)
        movl    (%esp), %edx
        movl    (%edx), %edx
        movl    36(%edx), %eax
        call    *%eax
        addl    $20, %esp
        # callm self.puts END

Spot the problem? We use %ebx to hold the number of arguments we calculate, but with our new "proper" support for strings, we now call __get_string on the string argument, and each one of them causes %ebx to get clobbered. As, incidentally does __get_string itself, as we don't actually store this value anywhere. We have two choices: Load it "closer" (That's generally a good idea anyway) or calculate it closer (for splat arguments).

This again underlines that we need proper register allocation including ability to "spill" registers to the stack. This is complicated in that if we push and pop values all over the place, we need to be able to adjust all accesses to %esp all over.

For now we "fake" spilling of %ebx by pushing %ebx indiscriminately onto the stack, and adjusting the generation of the arguments accordingly "manualy" so that when we pop it off the stack again everything happens to work. We end up with changing the central parts of Compiler#compile_callm_args as follows (in 6901567)


        @e.with_stack(args.length+1, true) do
          if splat
            @e.addl(:ecx,:ebx)
          end
    
          # we're for now going to assume that %ebx is likely
          # to get clobbered later, in the case of a splat,
          # so we store it here until it's time to call the method.
          @e.pushl(:ebx)
    
          ret = compile_eval_arg(scope, ob)
          @e.save_to_stack(ret, 1)
          args.each_with_index do |a,i|
            param = compile_eval_arg(scope, a)
            @e.save_to_stack(param, i+2)
          end
    
          # This is where the actual call gets done
          # This differs depending on whether it's a normal
          # method call or a closure call.
    
          # But first we pull the number of arguments off the stack.
          @e.popl(:ebx)
          yield
        end

The main change here is the @e.pushl(:ebx) and @e.popl(:ebx) lines. But notice that we change the offsets for self and method arguments accordingly.

This finally allows us to handle #puts and #print reasonably close to can see the result of this in 4511cea:


      def puts *str
        %s(assign na (__get_fixnum numargs))
    
        if na == 2
          %s(puts "")
          return
        end
      
        na = na - 2
        i = 0
        while i < na
          %s(assign raw (index str (callm i __get_raw)))
          raw = raw.to_s.__get_raw
          %s(if raw (puts raw))
          i = i + 1
        end
      end
    
      def print *str
        %s(assign na (__get_fixnum numargs))
    
        if na == 2
          %s(printf "nil")
          return
        end
    
        na = na - 2
        i = 0
        while i < na
          %s(assign raw (index str (callm i __get_raw)))
          raw = raw.to_s.__get_raw
          %s(if raw (printf "%s" raw))
          i = i + 1
        end
      end

It's not pretty, and there's certainly a lot of room for improvement. In particular "proper" access to the splat arguments would help tremendously, so that's on the agendy for soon too, I think, after code generation testing and some cleaner register allocation.

Some string interpolation

While we're at it, we might as well take a look at string interpolation and see what kind of trouble we might run into.

First we add a trivial test case (in c7b4b540bb):


    a = "Hello World"
    b = 42
    
    puts "#{a}, #{b}"

Unsurprisingly it doesn't work, so lets try compiling it with --norequire --parsetree:


    %s(do
      (assign a (sexp (call __get_string .L0)))
      (assign b (sexp (call __get_fixnum 42)))
      (call puts (
          (concat (sexp (call __get_string .L1)) a (sexp (call __get_string .L2)) b)))
    )

This is clearly outdated - we'd expect concat to be a method call on the string.

Let us turn of transformations, to see what the parser actually created:


    $ ruby compiler.rb --parsetree --norequire --notransform features/inputs/interpolate.rb 
    reading from file: features/inputs/interpolate.rb
    %s(do
      (assign a "Hello World")
      (assign b "42")
      (call puts (
          (concat "" a " , " b)))
    )

A-ha. concat nodes were how we implemented interpolation in the parser. So what we need is to transform them to generate the equivalent of "".concat(a.to_s).concat(" , ").concat(b.to_s)

Here is how we do that (in 35d93b0):


      def create_concat(sub)
        right = sub.pop
        right = E[:callm,right,:to_s] if !right.is_a?(Array)
        return right if sub.size == 0
        E[:callm, create_concat(sub), :concat, [right]]
      end
      
      def rewrite_concat(exp)
        exp.depth_first do |e|
          if e[0] == :concat
            e.replace(create_concat(e[1..-1]))
          end
          :next
        end
      end

We replace the existing (concat a b c ...) with a series of method calls to create and convert nodes to strings, and then call String#concat to create the result.

We for now implement String#concat like this:


    +  def concat(other)
    +    %s(do
    +         (assign ro (callm other __get_raw))
    +         (assign osize (strlen ro))
    +         (assign bsize (strlen @buffer))
    +         (assign size (add bsize osize))
    +         (assign size (add size 1))
    +         (assign newb (malloc size))
    +         (strcpy newb @buffer)
    +         (strcat newb ro)
    +         (assign @buffer newb)
    +   )
    +    self
    +  end

While this is simple - it just allocates buffers and copies data into them - it isn't very elegant code. So I might as well admit: Some of the simplicity is because of bugs that rears its head if we make the expressions too advanced - likely due to memory protection issues.

But we will take care of that in our part on testing code generation, next time. For now, this works.

Writing a (Ruby) compiler in Ruby bottom up - step 30

Wed, 04 Dec 2013 01:30:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

The Operators - Part 4: Comparisons

Where we left off last time, we had everything but comparison operators and &&, ! sorted out. When I started replacing runtime.c, I expected to do it in one go, as I've mentioned, but as you have seen there was quite a bit to cover.

This is it, though. runtime.c will finally go, at any cost.

I'll try to keep this short since we've covered most of the steps in the previous parts, and only address differences affecting the remaining operators.

(Note that I'll reduce my "buffer" which is currently about 5 months, as I've been able to consistently write a part ever month since April; that means I'll aim to post the next part in the next week or two, and will probably post two in January too)

Compiling comparisons

Let us dive right in and take a look at the first of the comparison operators first, as they are all very similar:


    ne:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        cmpl    12(%ebp), %eax
        setne   %al
        movzbl  %al, %eax
        popl    %ebp
        ret

This isn't too bad. After the normal setup, one operand is copied into %eax and cmpl is used to compare the second one with %eax.

Then setne is used to set its operand to 1 if the condition flags set by cmpl match the ne (not equal) condition, and there are equivalent variants for a long range of other conditions that matches our comparison operators neatly. %al is part of the ugliness of x86 - it is a register descriptor that maps to the least significant byte of %eax.

movzbl is then used to clear the remaining bytes.

All of the comparisons follow this patterns, with le, ge, ne mapping one to one to set(something) opcodes, lt mapping to setl, gt to setg and eq to sete.

First lets write a simple test program:


    %s(do
       (if (lt 2 5) (call puts ("2 < 5")))
       (if (lt 1 2) (call puts ("1 < 2")))
       (if (le 2 2) (call puts ("2 <= 2")))
       (if (ge 2 2) (call puts ("2 >= 2")))
       (if (gt 3 2) (call puts ("3 > 2")))
       (if (eq 2 2) (call puts ("2 == 2")))
       (if (ne 3 2) (call puts ("3 != 2")))
    
       (puts "false: (no output expected)")
    
       (if (lt 5 2) (call puts ("5 < 2")))
       (if (lt 2 2) (call puts ("2 < 2")))
       (if (le 3 2) (call puts ("3 <= 2")))
       (if (ge 1 2) (call puts ("1 >= 2")))
       (if (gt 2 2) (call puts ("2 > 2")))
       (if (eq 4 2) (call puts ("4 == 2")))
       (if (ne 2 2) (call puts ("2 != 2")))
    
       (puts "done")
    )

The expected output is:

$ /tmp/testcmp 
2 &lt; 5
1 &lt; 2
2 &lt;= 2
2 &gt;= 2
3 &gt; 2
2 == 2
3 != 2
false: (no output expected)
done

The actual compilation is easy. We make use of #compile_2 that we
added in the previous part to compile both operands in turn and preserve
the result, then compare it, and set and extend %eax accordingly: (in bba2c93)


      def compile_comparison(scope, op, left, right)
        compile_2(scope,left,right) do |reg|
          @e.cmpl(:eax,reg)
          @e.emit("set#{op.to_s}".to_sym, :al)
          @e.movzbl(:al,:eax)
        end
      end
    
      def compile_eq(scope,left,right)
        compile_comparison(scope, :e, left,right)
      end

I've only given #compile_eq as an example here, but the code is pretty much identical for the rest - only substituting the op argument according to the "set[op]" variant we want to use.

The rest is a trivial commit to strip these operators out of runtime.c, and register them wth the Compiler class, that you can see in ce6deb9

A first stab of Ruby level comparisons

Our first problem is that most of Ruby's comparisons are mixins in the Comparable module. We'll ignore that for now, and simply implement integer to integer comparisons directly in Fixnum and then generalize. We'll want specializations of the operators for integers anyway, as we don't want to fall back on the <=> operator for integer to integer comparisons.

First a Ruby version of our tests from above:


    if 2 < 5; puts "2 < 5"; end
    if 1 < 2; puts "1 < 2"; end
    if 2 <= 2; puts "2 <= 2"; end
    if 2 >= 2; puts "2 >= 2"; end
    if 3 > 2; puts "3 > 2"; end
    if 2 == 2; puts "2 == 2"; end
    if 3 != 2; puts "3 != 2"; end
    
    puts "false: (no output expected)"
    
    if 5 < 2; puts "5 < 2"; end
    if 2 < 2; puts "2 < 2"; end
    if 3 <=2; puts "3 <= 2"; end
    if 1 >=2; puts "1 >= 2"; end
    if 2 > 2; puts "2 > 2"; end
    if 4 == 2; puts "4 == 2"; end
    if 2 != 2; puts "2 != 2"; end
    
    puts "done"

The we add the operators to Fixnum. It's similar to what we did for Fixnum.+ etc, except we can't turn it back into a Fixnum object, since 0 would never get interpreted as false. Since we don't have the proper true and false yet, we just do this (in a844694):


      def == other
        %s(eq @value (callm other __get_raw))
      end

Note that this will break hopelessly in a number of situations, such as if you try to compare, say, a string with a Fixnum. In Ruby this should result in an ArgumentError exception, but here it'll cause a crash or nasty silent bugs. We'll quash those issues later.

Not and and

The choice above to not treat true and false properly at the Ruby level leaves us in a bit of a pickle. The input to these will often be the outcome of another comparison. If the input is another expression the effect will potentially be entirely different than if checking against variables set to true or false directly. Many results will be totally bogus.

As a result I finally decided on writing this to punt entirely on !. && is in a similar situation, and furthermore it is easy to "emulate" with if, and so we'll punt on that too.

So we'll defer these until we can get a handle on true, false and nil.

We'll however still finally get rid of runtime.c (in 28d246c). I won't cover the specifics - look at the commit.

Writing a (Ruby) compiler in Ruby bottom up - step 29

Mon, 04 Nov 2013 22:00:00 +0000

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

The Operators - Part 3: Operating on our newly minted Fixnums

Where we left off last time, we transform numbers into Fixnum objects, and turn + and other operators into method calls. In theory at least - we haven't actually tested that functionality properly in practice.

Putting them to work

So lets start with the simplest possible test: Can we call Fixnum#+ at all?

Let's compile 5 + 3. Nope. Doesn't work. For starters, we need to add require statements for Numeric and Integer (in 1c51f99)

But that's not enough. So lets try dipping down to our low level syntax, and compile this decidedly non-Ruby test:


        %s(printf "test: %d\n" (callm (call __get_fixnum 5) + ((call __get_fixnum 3))))

The (callm ...) is explicitly meant to do roughly what we should expect the 5 + 3 to get turned into.

(You can compile this with ./compile [filename] in the working directory, and get /tmp/[filename] out if everything worked)

To get it to return something other than junk, let's actually implement Fixnum#+ still using runtime.c to provide add() (in 326ae54):


      def + other
        %s(call add (@value (callm other __get_raw)))
      end

With that in place there's just one little wrinkle to get the example above to compile: Our %s() syntax can't handle operators. So for the sake of convenience, let us fix that by allowing any valid method name (in a7d4c31) by modifying sexp.rb:


       def parse_exp
         ws
    -    ret = expect(Atom, Int, Quoted) || parse_sexp
    +    ret = expect(Atom, Int, Quoted, Methodname) || parse_sexp
         ws
         return ret
       end

At this point you should be able to compile and run the test above, and get the expected test: 8 output. So why is 5 + 3 on its own segmentation faulting?

Luckily we have a debugging tool in the --norequire --parsetree options:


    %s(do
      (callm (sexp (call __get_fixnum 5)) + (sexp (call __get_fixnum 3)))
    )

And there we see an ugly pitfall of this syntax. Spotted it? The second argument to callm is a parameter list enclosed in parantheses, but here we pass it another list/array that happens to be an expression. It does reveal rather weak error handling and consistency checking for this syntax that we probably should do something about, but for now let us focus on the operators.

With a one line fix we get the output we need (in 1d9df53:):


    --- a/transform.rb
    +++ b/transform.rb
    @@ -86,7 +86,7 @@ class Compiler
           next :skip if e[0] == :sexp
     
           if OPER_METHOD.member?(e[0].to_s)
    -        e[3] = e[2]
    +        e[3] = E[e[2]]
             e[2] = e[0]
             e[0] = :callm
           end

And now the parse output looks like this:


    %s(do
      (callm (sexp (call __get_fixnum 5)) + (
          (sexp (call __get_fixnum 3))))
    )
    }}}                                     
    
    Which is far more reasonable, and actually doesn't segfault. So let us test
    that it returns the right value too:
    
    -ruby-
    a = 5 + 3
    
    %s(printf "%d\n" a)

... and that works. And that is wrong. Sigh. What we forgot above is that this whole mess means we have to re-wrap integers into an object every time we get one back. The example above should have been:


    a = 5 + 3
    
    %s(printf "%d\n" (callm a __get_raw))

And that still fails. Until we do this to Fixnum#+ (in 50fcf26)


       def + other
       -    %s(call add (@value (callm other __get_raw))) 
       +    %s(call __get_fixnum ((call add (@value (callm other __get_raw)))))
       end

And now our latest test should work.

I made you look through this intensely frustrating sequence for a reason - it's easy to present the more polished description of this process, but it's important to keep an eye on just how many details are there to trip you up when generating code and trying to debug things based on effects on generated code through several layers like this. It is one of the hardest parts of writing a compiler.

You may have noticed that despite a growing number of unit-tests for the parser components, there's far fewer tests for the code generation, despite the fact that it is far trickier to track down bugs there. One of the upcoming parts will start addressing the difficulties of unit-testing the code generation.

In the meantime, it is now finally time to do what we came here for, and re-implement runtime.c as compiler intrinsics + Ruby.

What does add/sub/etc. do anyway?

Time to break out our old friend gcc, and look at some asm output. To start with, here's add:


    .globl add
        .type   add, @function
    add:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %edx
        movl    8(%ebp), %eax
        addl    %edx, %eax
        popl    %ebp
        ret
        .size   add, .-add

Oh. That was simple. It "just" sets up the stack frame, moves the arguments into %edx and %eax respectively, adds them, and frees the stack frame.

We've put up with runtime.c and do a function call on every add for that? Of course, when we start trying to implement the Ruby semantics, an extra function call doesn't look all that bad (we'll have a lot of fun trying to optimize that out at some point in the future...), since there'll be a full blown method call to begin with.

Not all of them are as simple (do gcc -o runtime.s -S runtime.c and take a look at runtime.s yourself), but none of the few runtime functions we have are all that much work. So let us get to it.

Adding 'add'

First we add a :add keyword in the Compiler class, and include a new file to hold our arithmetic keywords so we don't keep messing up compiler.rb (in dc2bbd8)


    diff --git a/compiler.rb b/compiler.rb
    index 00c857f..059abf4 100644
    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -10,6 +10,8 @@ require 'transform'
     require 'set'
     require 'print_sexp'
     
    +require 'compile_arithmetic'
    +
     class Compiler
       attr_reader :global_functions
       attr_accessor :trace
    @@ -21,7 +23,7 @@ class Compiler
                        :do, :class, :defun, :defm, :if, :lambda,
                        :assign, :while, :index, :let, :case, :ternif,
                        :hash, :return,:sexp, :module, :rescue, :incr, :block,
    -                   :required
    +                   :required, :add
                       ]

We then add a simple implementation in compile_arithmetic.rb:


      def compile_add(scope, left, right)
        @e.with_register do |reg|
          src = compile_eval_arg(scope,left)
          @e.movl(src,reg)
          @e.save_result(compile_eval_arg(scope,right))
          @e.addl(reg, :eax)
        end
        [:subexpr]
      end

Note that this is flawed in many ways: We don't do any simplification even when both arguments are constants; we don't do anything to try to avoid using two registers (if one of the arguments is an integer, we can evaluate the other expression first, and just addl the integer to this result.

We also for good measure comment out add() from runtime.c

As usual, we're being lazy and the above works, as you can show by compiling this:


    %s(printf "test: %d\n" (add 5 3))

Next up we need to make use of this in Fixnum... And we'll find it doesn't work. It turns out the above version is too naive - our with_register is a "fake" start to a register allocator - it only hands out %edx. That's fine for now. But what isn't fine is that it doesn't actually allocate it in any way. You'll find it gets clobbered elsewhere.

So we'll need to implement very basic register allocation. For now we'll just add %ecx to our set of registers to hand out, and actually keep track of them, and raise an error if we run out (which we will sooner or later - at which point we'll need to implement more sophisticated register allocation).

We modify emitter.rb like this (in d84e905):


    @@ -83,6 +83,7 @@ class Emitter
         @out = out
         @basic_main = false
         @section = 0 # Are we in a stabs section?
    +    @free_registers = [:edx,:ecx]
       end
    
    
    @@ -333,9 +334,16 @@ class Emitter
       end
    
       def with_register
    -    # FIXME: This is a hack - for now we just hand out :edx,
    -    # we don't actually do any allocation
    -    yield(:edx)
    +    # FIXME: This is a hack - for now we just hand out :edx or :ecx
    +    # and we don't handle spills.
    +
    +    @allocated_registers ||= Set.new
    +    free = @free_registers.shift
    +    raise "Register allocation FAILED" if !free
    +    @allocated_registers << free
    +    yield(free)
    +    @allocated_registers.delete(free)
    +    @free_registers << free
       end

Basically we've changed from just blindly handing out %edx for code that needs a spare register, to handing out one of %edx or %ecx depending on which one is already in use. But if we try to allocate more than two, we're screwed. The reason I haven't added more registers is because I've not wanted to try to figure out to what extent they're "safe". E.g. we use %eax as our default scratch register all over the place.

The normal way of handle running out of register is "register spilling". That is, we need to "spill" the registers into variables (this is reasonable if we've used the registers to cache variables), or push them onto the stack. The latter adds complexities in that it means we need to ensure we keep track of it when handling offsets to the stack pointer.

For now this will do.

If you try to compile this, you should find it works:


    a = 5 + 3
    
    %s(printf "%d\n" (callm a __get_raw))

(This of course reveals that we now really should have some IO functions that can handle other types - so that will be one of the things to handle in one of the upcoming parts).

Subtracting 'sub' from the runtime.

So lets do the same thing for sub. I won't go over every detail as it's pretty much identical to add. The meat is in 0c6de44. Let's test it.


    a = 7 - 2
    
    %s(printf "%d\n" (callm a __get_raw))

Compiling this gives -5. What gives?

Well, the evaluation order monster reared its head. We didn't spot this for compile_add since addition is commutative. So lets look at compile_sub and figure out a fix we can hopefully also apply to compile_add (this might sound unnecessary, but consider that expected evaluation order matters a great deal in a language with side effects, and few languages have more potential side effects than one in which you can, if you please, redefine even basic arithmetic operators, or modify classes as they are being defined...)


      def compile_sub(scope, left, right)
        @e.with_register do |reg|
          src = compile_eval_arg(scope,left)
          @e.movl(src,reg)
          @e.save_result(compile_eval_arg(scope,right))
          @e.subl(reg, :eax)
        end
        [:subexpr]
      end

We evaluate the left hand, then save it to a register, and we evaluate the right hand. Then we subtract the left hand from the right, and that's obviously wrong...

But if we switch the order, we leave the result in another register than our "result" register %eax, and end up having to move it. We can fix that by evaluating the right side before the left, but that's the wrong evaluation order. We can try to save the result from the left hand evaluation in %eax and save the result of the right hand in %edx, which would solve the problem if it wasn't for the fact that we likely will clobber %eax when evaluating the left hand side.

What we're seeing here is that choices made for simplicity early on are starting to really affect the code-generation. Here are two possible alternatives:

Not treat %eax as a scratch register and allow allocating it. This is still problematic as it will get clobbered by a lot of calls we might want to make to external code. It may still be the best choice in some cases.
Allow returning results in something other than %eax. This is a much more viable choice for many situations. If we can return reg from compile_sub, we push the problem up one level, and its quite possible that the next step up can make use of %edx directly. We may want to go further and not restrict it to variables, as that would allow us to get rid of many instances of that awful call *%eax thing that we currently do for calls.

It may be time to look into this in one of the forthcoming parts - as much as a focus of this series has been about being "lazy" and deferring changes like these, we're now at a point where not being able to do the above actually makes the code more convoluted.

For this part, lets just bite the bullet and fix the order and do a movl at the end for compile_sub (and this allows us to leave #compile_add untouched, since the evaluation order of the operands to the Ruby + operator are left intact):


      def compile_sub(scope, left, right)
        @e.with_register do |reg|
          src = compile_eval_arg(scope,left)
          @e.movl(src,reg)
          @e.save_result(compile_eval_arg(scope,right))
          @e.subl(:eax,reg)
          @e.save_result(reg)
        end
        [:subexpr]
      end

This works, but is not very DRY, when compared with compile_add, so lets add a helper, since we'll keep relying on this same pattern for the remaining bits and pieces (in a23f0d0):


     def compile_2(scope, left, right)
        @e.with_register do |reg|
          src = compile_eval_arg(scope,left)
          @e.movl(src,reg)
          @e.save_result(compile_eval_arg(scope,right))
          yield reg
        end
        [:subexpr]
      end
    
      def compile_add(scope, left, right)
        compile_2(scope,left,right) do |reg|
          @e.addl(reg, :eax)
        end
      end
    
      def compile_sub(scope, left, right)
        compile_2(scope,left,right) do |reg|
          @e.subl(:eax,reg)  
          @e.save_result(reg)
        end
      end

Div and mul

We'll mostly ignore mul, since it's pretty much the same as add except using the imull instruction. See 5036b94 for the details.

Div, however, looks curious, when we disassemble the code generated by gcc for runtime.c. With the normal prolog and epilog stripped out from the div function:


        movl    8(%ebp), %eax
        movl    %eax, -8(%ebp)
        movl    -8(%ebp), %edx
        movl    %edx, %eax
        sarl    $31, %edx
        idivl   12(%ebp)
        leave
        ret

What is going on here? For starters, it doesn't look very optimized. 8(%ebp) and 12(%ebp) are the operands passed in to the function. The moves back and worth between %eax, -8(%ebp) and %edx looks fairly wasteful.

As it turns out, idivl performs signed division of a double-word (64 bit on i386) combination of %edx and %eax registers by a third register or a memory location. The sarl instruction does an Arithmethic Shift Right on a Long.

For those who are still not up on assembler, consider an "arithmetic shift" effectively moving the bits of the binary representation of the value one step in the specified direction. The prefix "arithmetic" is usually used on assembler instructions to indicate that the shift copies in the furthermost bit in the "empty" slots. So if you shift one bit right with an arithmetic shift right, it is equivalent to dividing by two regardless whether or not the value is negative or positive, as the left-most (furthermost for a shift right) bit is the sign bit.

Here is a page that illustrates it with a little graphic

So what is happening here is that it is filling all of %edx by the sign bit from %eax in order to handle negative values correctly.

Lets take a stab at implementing that. I end up with this horrible monstrosity, which is another reason to take another look at the code generation shortly (in 95d642e)


      def compile_div(scope, left, right)
        # FIXME: We really want to be able to request
        # %edx specifically here, as we need it for idivl.
        # Instead we work around that below if we for some
        # reason don't get %edx.
        @e.with_register do |reg|
          src = compile_eval_arg(scope,left)
          @e.movl(:eax,reg)

So far, so good. We've just evaluated the left hand, and moved the result out of the way. Then we evaluate the right hand.


          @e.save_result(compile_eval_arg(scope,right))

And then the ugly stuff starts. Depending on what registers we got allocated, we spit out variout variations up to and including temporarily pushing %edx onto the stack, since we need to have %edx free. This is a mess. One way to make it simpler would be to be able to request two registers, of which one should be %edx and the other doesn't matter. Then we could be assured a cleaner way of setting this up. So another task for when we clean up the code generator shortly.


          @e.with_register do |r2|
            if (reg == :edx)
              @e.movl(:eax,r2)
              @e.movl(:edx,:eax)
              divby = r2
            else
              divby = reg
              if (r2 != :edx)
                save = true
                @e.pushl(:edx)
              end
              @e.movl(reg, :edx)
              @e.movl(:eax,reg)
              @e.movl(:edx,:eax)
            end
            @e.sarl(31, :edx)
            @e.idivl(divby)
    
            # NOTE: This clobber the remainder made available by idivl,
            # which we'll likely want to be able to save in the future
            @e.popl(:edx) if save
          end
        end
        [:subexpr]
      end

Next time

It is finally time for the rest of the operators (for now), and wiping out runtime.c!