The JHCR Rewrite Engines

The goal of JHCR is to reduce the editing cycle of mapping WarCraft 3 Maps. As we’ve seen previously we compile the changed code to some form of bytecode. Now we also have certain limits given we work with the WarCraft 3 engine: we can only load a certain amount at a time into a running game instance and we can only process a certain amount of bytecode changes. So we actually want to minimize the bytecode before we send it out to the game. But that is in direct contrast to our fast iteration process. So we have to make some compromises on how we handle the bytecode compilation and optimisation.

To keep the compilation fast we used the most straight-forward way of compiling the code. This of course produces less than optimal code but it should be quick enough. Then we use the same idea at two points in our compilation pipeline to hopefully produce better and smaller code.

Rewriting the Ast

Let’s start by the higher-level implementation of the Ast rewrtie engine. It was heavily influenced by the GHC Rewrite Rules although far less powerful and more risky due to jass’s non-pure nature. Neverthelss we can achieve some nice results as long as we tread with a bit of care. The implementation is not too interesting except that we actually unify variables. That means we could actually rewrite something like a+a into 2*a for the same expression a on both sides of the +. But unfortunately that’s not a valid optimisation in jass ¹.

To create a rewrite rule we use the mkRR :: [String] -> String -> String -> Rule smart constructor to allow a stringy usage of the rewrite engine ². You can see all used rules here but let’s examine a few differents uses-cases of these rules.

Some rules use the knowledge of specific WarCraft 3 Built-in functions like for example these:

Again, we have to be careful to not change the actual execution of the jass program. So something like mkRR ["a"] "a and a" "a" would not be valid because a could have side effects and could be execute twice in the original but only once in the optimised version. You don’t have such problems in Haskell.

Rewriting the Bytecode

Of even greater value is the bytecode rewrite engine. This engine was organically grown to handle the patterns that emerge from the compiler. Let’s look at some examples from here.

    [ "lit real %t r'2"
    , "mul real x %t s"
    ] -->
    [ "add real x s s"]

Again we use a string based approach so that we technically could load them from outside the compiler even though we don’t use it at this momment. The (-->) is just a cute smart constructor for the Rule data type.

As we’ve previously seen we create many temporary registers while compiling jass code. In the above example we can see how to match such an temp register by prefixing the name with %. The r'2 part means the float literal 2.0.

So what does the first bytecode sequence mean? It loads the literal 2.0 into some temp register and then multiplies the value stored in s by %t = 2.0 and stores it in the register x.

And the sequence after the --> means that we add s and s together and store it in x. We achieved what was previously impossible on the AST level, that is replacing 2*x with x+x ³.

Let’s look at another example to see some special forms of this rewrite engine:

    [ "neg * #z *"
    , "ret type"
    ] -->
    [ "ret type"]

Here * means “any value at all”, that is any kind of register or literal value and #z means a register that is not the 0 register (which – we remember – stores the return value of a function). So what does this snippet do? It removes any neg operation which does not target the 0-register before a return instruction. So we can remove the useless negate computation because we know it would target a non-0 register just before exiting that function which means that resulting value is never used.

Just using these few capabilities JHCR is able to remove and improve the resulting bytecode substantially and i consider it more worth than for example the AST-based rewriting engine (at least in its current form).