& NWScript

The attentive might have wondered why I bothered to spend a moderate amount of timewriting about a topic I'd already moved past, which is kind of uncharacteristic of me. As I said before, I had looked at LLVM for a couple days a couple weeks prior to the corresponding blog post, then moved on (I can't recall if there was anything in between LLVM and cache-oblivious algorithms).

Well, part of the reason I didn't spend too much time on LLVM was because while it's neat, I didn't have an immediate use for it. However, a few days before I wrote said post Skywing randomly came up to me and asked if I wanted to write a native code compiler for NWScript, the scripting language in NeverWinter Nights 1 and 2, for the client and server he's been writing. Suddenly I had an immediate and interesting use for LLVM.

NWScript (for more information see this) is a language based on C, and supports a subset of the features. It supports only a small number of data types: int, float, string, and a number of opaque types that are more or less handles to game structures accessed solely via APIs. It also supports user-defined structures, including the built-in type vector (consisting of 3 floats), though it does not support arrays, pointers, etc. All variables and functions are strongly typed, although some game objects - those referred to with handles, such as the "object" type - may not be fully described by their scripting type. NWScript has a special kind of callback pointer called an action (a term which, confusingly, has at least two additional meanings in NWScript), which is more or less a deferred function call that may be invoked in the future - specifically, by the engine - and consists of a function pointer and the set of arguments to pass to that function (a call to an action takes no parameters from the caller itself).

NWScript is compiled by the level editor into a bytecode that is interpreted by a virtual machine within the games. Like the Java and .NET VMs, the VM for NWScript is a stack system, where a strongly-typed stack is used for opcode and function parameters and return values. Parameters to assembly instructions, as with function calls, are pushed on the top of the stack, and instructions and function calls pop the parameters and, if there is one, push the result/return value onto the top of the stack. Data down the stack is copied to the top of the stack with load operations, and copied from the top of the stack to locations further down by store operations.

Unlike those VMs, however, NWScript uses a pure, integrated stack system, implementing global and local variables through the stack, as well. Global variables are accessed through instructions that load/store values at indices relative to the global variable pointer BP, which is an index into the stack. Normally, global variables are at the very bottom of the stack, pushed in a wrapper function called #globals before the script's main function is called; there are opcodes to alter BP, though this is not known to ever be used. Local variables are accessed by loads and stores relative to the top of the stack, just as with the x86 (ignoring the CPU registers). Unlike the x86, however, return addresses are not kept on the stack, but like Itanium are maintained in a separate, program-inaccessible stack.

Oh, and for those wondering, the Java and .NET VMs have separate mechanisms for global and local variables that do not use the stack. This is actually rather surprising - you would expect them to use the stack at least for local variables, as actual processor architectures do (when they run out of registers to assign).

The following show a couple random pieces of NWScript bytecode with some comments:

; Allocate int and object local variables on the stack
0000007F 02 03                    RSADDI
00000081 02 06                    RSADDO
; Push parameter 0
00000083 04 06 00000000           CONSTO 00000000
; Call game API function
00000089 05 00 0360 01            ACTION GetControlledCharacter(0360), 01
; Copy return value to the object local variable
0000008E 01 01 FFFFFFF8 0004      CPDOWNSP FFFFFFF8, 0004
; Pop the return value
00000096 1B 00 FFFFFFFC           MOVSP FFFFFFFC

; Allocate float on stack
00000015 02 04                    RSADDF
; Incredibly stupid way of setting the float to 3.0f
00000017 04 04 40400000           CONSTF 3.000000
0000001D 01 01 FFFFFFF8 0004      CPDOWNSP FFFFFFF8, 0004
00000025 1B 00 FFFFFFFC           MOVSP FFFFFFFC
; Assign the current stack frame to BP
0000002B 2A 00                    SAVEBP
; Call main()
0000002D 1E 00 00000010           JSR fn_0000003D
; Restore BP to what it was before (not that it was anything)
00000033 2B 00                    RESTOREBP
; Clean up the global variables
00000035 1B 00 FFFFFFFC           MOVSP FFFFFFFC
0000003B 20 00                    RETN

; Push last two parameters to FloatToString
0000043C 04 03 00000009           CONSTI 00000009
00000442 04 03 00000012           CONSTI 00000012
; Divide 5.0f by 2.0f
00000448 04 04 40A00000           CONSTF 5.000000
0000044E 04 04 40000000           CONSTF 2.000000
00000454 17 21                    DIVFF
; Return value of DIVFF is the first parameter to FloatToString
00000456 05 00 0003 03            ACTION FloatToString(0003), 03
; Return value is second parameter to SendMessageToPC. Push first parameter.
0000045B 04 06 00000000           CONSTO 00000000
00000461 05 00 0176 02            ACTION SendMessageToPC(0176), 02

Stack systems - especially this one, where everything is held on the stack - make for VMs that are very simple and easy to implement, and Merlin told me in the past that they're easy to compile to native code, as well. So it's not surprising that the developers used this architecture for NWScript.

You might notice that Skywing has started a series of his own on the project, today. I actually wrote this post several weeks ago, but was waiting until the project was done to post about it. But now that it looks like he's gonna cover it, I need to start posting or I'll end up posting after him despite starting before him.