Nynaeve

Last time, I outlined the basic scope of one of my recent side projects, a JIT engine for NWScript. Although I provided a brief, very high-level overview of the NWScript environment, it’s necessary to understand more details about the inner workings of the instruction set in order for various design decisions in the JIT project to make sense.

Based on the way the NWScript instruction set functions, we can derive the following probable design goals for the instruction set:

• Extensibility. It should be easy to expose new APIs to the script environment without modifying the compiler or the core script VM logic itself. Furthermore, it should be possible to add new script APIs without breaking previously compiled scripts. Although BioWare’s game engines have evolved significantly since NWScript made its public debut in Neverwinter Nights 1 (“Aurora”), the script instruction set has seen comparatively minor revisions despite a wide range of hosting environments.
• Portability. The compiled NWScript instruction set should be easily executable on any particular architecture (i.e. there should be no need to write a compiler for each platform the game is ported to, nor should one need to compile again for each platform supported). Neverwinter Nights 1 supported Win32 and Linux, and Dragon Age supports Win32 and Xbox360.
• Safety (containment). End-users should be free to download custom content with custom script code without fear of the script code taking control over their machine.
• Suspend / resume (coroutine-like) support. NWScript is designed to easily support timed deferral of various operations at well-defined sequence points in a way that is very natural to program, which is implemented by a coroutine-like saved state mechanism that should be simple to support in the execution environment.

With these design principles in mind, let’s dive in deeper as to how the script instruction set operates. The first major concept that one needs to understand about NWScript is that of the VM stack (or simply stack for short).

Note: For the curious, I have mirrored a copy of Tim Smith’s original NWScript instruction set reference here. There are several errata in Tim’s documentation that have since been identified, but it remains the definitive source on the subject. This posting series generally will not discuss or mention every single instruction in great detail, so the instruction set reference itself is optional reading.

NWScript VM stack

Due to its design nature as an intended interpretive-only scripting environmen, the NWScript instruction set is purely stack-based. That is to say that the primary (and only) data store of a program authored in NWScript is the VM stack, which is an abstract data store that the execution environment provides. This is a common paradigm among other compiled, interpretive languages, designed for ease of use by the interpreter. Remember that NWScript was not originally designed to be executed natively, so any registers that the instruction language provided would most likely be handled by memory indirections anyway.

(To be pedantic, there are three pseudo-registers that a NWScript VM must keep track of — the current program counter (PC), the current top of stack pointer (SP), and the auxiliary stack pointer (BP). These pseudo-register values are generally only implicitly referenced by NWScript instructions in the form of relative address operands.)

The stack is laid out as an expand-up array of uniformly-sized stack cells. Each stack cell holds a single data element, and, as mentioned, all stack cells consume the same amount of space on the logical VM stack (4 addresses per stack cell). In practice, a program is ill-formed if it acesses the stack at a misaligned stack cell offset, so for all intents and purposes the stack cell can be considered the atomic data unit size on the VM stack.

(Why 4 addresses (‘bytes’) per stack cell, you might ask? This is actually an area where NWScript presents a somewhat leaky abstraction; the BioWare NWScript VM internally treats the VM stack as essentially a byte array within which either a raw data element or a pointer to that data element may be stored (the BioWare VM only supports 32-bit targets, making for 4 addresses consumed per stack cell). Nonetheless, all stack references in a program must be aligned to multiples of a size of a stack cell for the program to be considered well-formed.)

Nearly every instruction in the NWScript instruction set that takes a non-constant argument receives that argument from the VM stack (typically the top of the stack). Furthermore, because most instructions only act on the top of the stack, and there is no secondary data store for local variables (as in, say, MSIL), a NWScript program will often spend a non-trivial amount of time moving data around the VM stack.

For example, consider a NWScript subroutine that has two integer local variables, i and j. If this subroutine contains code structured along the lines of i = i + j;, one could expect to see the following general sequence of operations:

1. Create a copy of j on the top of the stack (via CPTOPSP).
2. Create a copy of i on the top of the stack (via CPTOPSP).
3. Add the two variables together (via ADDII). This results in the two integer values at the top of the stack being popped off, and their sum being pushed on to the top of the stack.
4. Copy the result back down to the permanent copy of i (via CPDOWNSP).
5. Delete the temporary result of the addition from the top of the stack (via MOVSP).

While this logic is perfectly functional, it leaves plenty of room for improvement by a JIT system (four out of five instructions generated are merely artifacts of the stack-based instruction set versus performing the actual work of the operation).

Extraneous temporary copies could be removed (particularly if the language that the JIT backend translates to supports any sort of optimization of its own), and a number of type and validity checks on each stack reference that the interpretive VM must perform on most instructions could be dispensed with (having been enforced at JIT compilation time).

Data types

There are several fundamental data types recognized by the script instruction set. Each data type is logically stored by value on the stack, and each of these data types consumes a single stack cell:

• int, the 32-bit signed integer.
• float, the 32-bit (single precision) IEEE float.
• object, a 32-bit unsigned quantity which cannot be directly modified by the core instruction set (except the creation of a constant value of type object with two well-known constant values). There are no built-in instructions that can operate on a value of type object (aside from constant creation and raw equality testing on the 32-bit unsigned bit pattern), but an extension API exposed to the script program by the script host may make use of object typed values. Generally, an object-typed value is used as a handle to reference a game entity (such as a door or a creature), but the script instruction set imposes no particular meaning on this type.
• string, a counted 8-bit character string. Strings are logically stored by value on the stack (and as such, they are essentially immutable, in that any operation that ‘modifies’ a string simply creates a new string with the modified value).
• vector, a set of three loating point (float) values. A vector is not actually a discrete type, but a rather triplet of three float values allocated adjacent on the stack. Several instructions have forms optimized to operate on this data construct, but a vector is simply otherwise created and manipulated as three float stack cells on the stack. (There is no hard binding of the three floats, rather they are simply three float values created adjacent to one another.)

Additionally, the instruction set allows for a customizable set of up to 10 engine structure types. Engine structure types are opaque to the instruction set itself (and thus, by extension, the source text compiler). They are used to safely package up a data structure maintained by the script host for transmission across a script program authored in NWScript. An engine structure type allows the creation of an empty (or null) value, and supports equality testing by means of a well-defined callout to the script host to compare the equality of two engine structures of the same type.

Additionally, there is an internal data type that may be stored on the stack: stack pointer, which represents a saved value of the current stack pointer. This data type is generally not directly referenced by script code, and is used only during the creation of global variables. (My script VM, NWScriptVM, treats the stack pointer type as a unique type, whereas the BioWare VM technically treats it as an int. A well-formed script program should not read or write a value of this type directly, and it is used only as a side effect by certain instructions.)

Conspicuously missing from the list of data types available for storage is that of an instruction pointer. While NWScript supports the concept of subroutines and subroutine calls, the return instruction pointer is saved in a separate region that is inaccessible to the script program itself. Furthermore, all control transfers must come to either specific extension points, or hardwired subroutine addresses specified as operands to instructions (i.e. there is no concept of a virtual method call or a function pointer in NWScript).

Global variables

If you’ve been following along, you may have noticed a seemingly contradictory set of points. Namely, that I have made reference to the fact that a script program can support global variables, despite that a script is essentially a completely unstructured instruction stream.

In the NWScript instruction set, global variables are referenced relative to an auxiliary stack pointer value (internally known as BP, or base pointer). This auxiliary stack pointer value generally points to the top of a call frame set up by a special compiler-emitted subroutine (internally called #globals) that runs before the main program entry point. The #globals subroutine creates a data elements on its stack frame, and then uses a special-purpose pair of instructions (SAVEBP and RESTOREBP) in order to establish or de-establish a global variable frame, by assigning the current top of stack address to the active base pointer value.

Once #globals has finished preparing a script program’s global variables, it transfers control to the user’s entry point subroutine (i.e. main()).

Aggregates

Although the NWScript source text compiler supports the notion of aggregate types, the instruction set only has a very minimal awareness of aggregates at the instruction level.

All fields of an aggregate type are allocated adjacent on the stack. Operand forms are provided for several instructions to allow them to be repeated over a range of stack locations (to compare structures, for example), and several instructions have special support for performing built-in operations on a the built-in vector structure (a tuple of three floats); for example, there is a derivative of the MUL instruction to support multiplying one float and a series of three other floats in a fashion consistent with vector/scalar multiplication.

Next time, we’ll take a closer look at how subroutine calls, script host extension point (action service handler) calls, and saved states operate.

Erratum for Tim Smith’s NWScript documentation

The following are known errata with respect to Tim Smith’s documentation on the NWScript instruction set:

• SAVEBP and RESTOREBP are incorrectly documented as not modifying the current value of SP. The current BP value (on entry to SAVEBP) is pushed onto the stack, and similarly restored from the current top of stack by SAVEBP.
• Several legal opcode + type opcode combinations are omitted from the documentation.

Tags: NWN2

This entry was posted on Tuesday, August 3rd, 2010 at 7:00 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.