Decided I needed a break from graphics programming so decided to revisit Om, my scripting language. For those who didn't read the entries about this a few months ago, I came heavily unstuck in my last iteration of this project, since I had decided to implement deterministic destruction in a dynamically typed, JavaScript-like language and it didn't occur to me until it was pretty much all written that the problem of cyclic references basically makes this impossible.

E.g. if you have an object a that has a reference to object b, then you assign a reference in object b to a:

var a ={};var b = { ref = a;};a.ref = b;Then no amount of reference counting and clever trickery in the world is going to end up freeing those objects.

So, I have restarted Om from scratch and made a few decisions at the very start this time that, so far, are leading to a far more stable-feeling codebase.

• The language will use a stop-the-world mark-and-sweep garbage collector (for now)
  
• Objects will not offer user-defined destructors - we'll find other solutions to RAII if we need it
  
• This one might not go down well, but I decided to use exceptions to report compiler and runtime errors
  

I have the garbage collection working now in a very simple way. I did some profiling and it can collect 100,000 entities in less than a tenth of a second, so I'm confident a stop-the-world approach will be fast enough. Haven't tested it yet with really deep trees of object-references though so we'll see.

I've also taken the time, while we are in the early stages, to tackle optimisation so that it is already in place and I can improve it as we go along. I'll go into a bit of detail about how the optimisation system works today, since I've rambled on about the language itself in previous entries and this is all new.

So I guess the minimum you need to know is that the compilation side of this project is based on building an abstract syntax tree based on a [font='courier new']Node[/font] base class:

enum class NodeQuery : int;class Node{public: explicit Node(Context &c); virtual ~Node(); void generate(Context &c); void generateAssign(Context &c); virtual void generateImp(Context &c) = 0; virtual void generateAssignImp(Context &c); virtual void optimise(Context &c, Node *parent) = 0; virtual void replace(Node *before, Node *after) = 0; virtual void remove(Node *node); virtual Variant query(NodeQuery query) const; virtual void output(std::ostream &os, int i) const = 0;};typedef scoped_ptr NodePtr;typedef ptr_vector NodeList;The new methods relevant to optimisation are [font='courier new']optimise()[/font], [font='courier new']replace()[/font], [font='courier new']remove()[/font] and [font='courier new']query()[/font].

[font='courier new']optimise()[/font] is a visitor method that each subclass calls recursively on any nodes it owns, then does any optimisation that it can do on itself.

Often this results in the node needing to replace itself with a new node - for example when a [font='courier new']BinaryNode[/font] detects that both of its child nodes are constants, it can do its operation on the children at compile time then replace itself with a new [font='courier new']LiteralNode[/font] representing the result.

So [font='courier new']optimise()[/font] passes a reference to the parent node, and [font='courier new']replace()[/font] and [font='courier new']remove()[/font] are implemented in each node so that a child node can request itself be replaced with a new node it supplies.

For example:

namespace{Variant compute(State &state, OpCode::Type type, const Variant &a, const Variant &b){ switch(type) { case OpCode::Type::Add: return mathOp(state, a, b); case OpCode::Type::Sub: return mathOp(state, a, b); case OpCode::Type::Mul: return mathOp(state, a, b); case OpCode::Type::Div: return mathOp(state, a, b); default: return Variant(); }}}void BinaryNode::optimise(Context &c, Node *parent){ left->optimise(c, this); right->optimise(c, this); Variant a = left->query(NodeQuery::AsVariant); Variant b = right->query(NodeQuery::AsVariant); if(a.valid() && b.valid()) { parent->replace(this, LiteralNode::fromVariant(c, compute(c.state, type, a, b))); }}void BinaryNode::replace(Node *before, Node *after){ if(left == before) left = after; if(right == before) right = after;}Here we see the use of the [font='courier new']query()[/font] method. [font='courier new']query()[/font] returns a [font='courier new']Variant[/font] which is a simple internal type capable of storing an [font='courier new']int[/font], [font='courier new']float[/font], [font='courier new']bool[/font] and [font='courier new']std::string[/font]. It also has an invalid state. Nodes implement [font='courier new']query()[/font] and respond in different ways depending on the query type.

The only nodes that respond to [font='courier new']NodeQuery::AsVariant[/font] are the literal nodes. For example:

Variant IntNode::query(NodeQuery query) const{ return query == NodeQuery::AsVariant ? Variant(value) : Variant();}Variant StringNode::query(NodeQuery query) const{ return query == NodeQuery::AsVariant ? Variant(value) : Variant();}So [font='courier new']BinaryNode[/font] is effectively asking "Are both my child nodes literals?" If so, it uses [font='courier new']compute()[/font] to calculate the expression at compile-time, returned as a [font='courier new']Variant[/font] again, then [font='courier new']LiteralNode::fromVariant()[/font] to create a new literal node representing the result, then finally calls its parent's [font='courier new']replace()[/font] method to replace itself with the new node.

Obviously we have to be cautious using replace and make sure we don't touch any of the members of the class in question after this call, since it will delete the node.

Another example is the [font='courier new']WhileNode[/font]. This can use [font='courier new']NodeQuery::AsVariant[/font] to check if its expression is constant, and if so, either remove itself entirely if the expression is false or remember to not bother generating its expression if the expression is constant and true:

void WhileNode::generateImp(Context &c){ uint top = c.pm().position(); ByteStreamPatch end; c.pushScope(); c.pushBreaks(c.locals().total()); if(!exprVar.valid()) { expr->generate(c); c.pm() << OpCode::Type::JmpF << end; } uint exprTotal = c.locals().scopeTotal(); block->generate(c); c.pop(c.locals().scopeTotal()); c.pm() << OpCode::Type::Jmp << top; if(!exprVar.valid()) { end = c.pm().position(); } c.pop(exprTotal); c.patchBreaks(c.pm().position()); c.popScope(); c.popBreaks();}void WhileNode::optimise(Context &c, Node *parent){ expr->optimise(c, this); block->optimise(c, this); exprVar = expr->query(NodeQuery::AsVariant); if(exprVar.valid() && !exprVar.toBool()) parent->remove(this);}Here [font='courier new']exprVar[/font] is a member variable of [font='courier new']WhileNode[/font] which is defaulted to invalid. It is then set in the [font='courier new']optimise()[/font] method and, if constant and false, we ask the parent to remove the [font='courier new']WhileNode[/font] altogether. If it is constant and true, we use this state to modify the code generation phase slightly to not bother generating the expression - just create an infinite loop instead.

Another minor optimisation is trimming out unreachable code. [font='courier new']ReturnNode[/font] and [font='courier new']BreakNode[/font] both respond with a [font='courier new']Variant(true)[/font] to the [font='courier new']NodeQuery::TerminatesBlock[/font], which [font='courier new']BlockNode[/font] uses to check for unreachable code:

void BlockNode::optimise(Context &c, Node *parent){ for(auto i = nodes.begin(); i != nodes.end(); ++i) { i->optimise(c, this); if(i->query(NodeQuery::TerminatesBlock).toBool()) { nodes.erase(i + 1, nodes.end()); return; } }}Since every scope creates its own [font='courier new']BlockNode[/font], it is demonstrably true that any nodes following a [font='courier new']ReturnNode[/font] or [font='courier new']BreakNode[/font] are unreachable, and can thus be deleted from the tree before we start generating bytecode.

So that is about the current state of play regarding optimisation.

Thanks, as always, for stopping by.