Date: Tue, 10 Dec 1996 22:41:58 GMT Server: NCSA/1.4.2 Content-type: text/html Last-modified: Sat, 02 Nov 1996 19:51:27 GMT Content-length: 24614 Runtime Code Generation (RTCG)

Runtime Code Generation (RTCG)

Terms

Runtime Code Generation (RTCG) is a general name for structured techniques that change a program's instruction space while the program is running. There are a variety of other common, overlapping names, such as ``dynamic compilation'' and ``self-modifying code''; there are also a variety of other less-polite names.

``Friends don't let friends use SMC'' -- email .signature
The term "demand-driven compilation" is narrower than RTCG. It typically means that some or all parts of the language translation process are performed on a unit of code when that unit is invoked. Demand-driven compilation may be contrasted with runtime code generation that is performed speculatively; with demand-driven dynamic linking in which the address space is modified without "compilation"; and self-modifying code in which a code unit is updated by itself which, necessarily, is after the unit has been invoked. The term dynamic compilation is also narrower, typically encompassing code that is generated dynamically but which does not self-modify. Dynamic compilation is most often applied to systems using general-purpose in-core code generators and performing code generation over sophisticated inputs (e.g., expressions, rather than simple values) or over dynamically-loaded source code or pseudocode. (Beware that the term ``dynamic compilation'' is nowadays often(?) used also to mean ``a compilation of literary works which is done on an ongoing and/or incremental basis'', e.g. here.)

Dynamic linking adds code to the instruction space of the program. The code is typically generated using a code generator that is outside of the program. The ``new code'' may have been generated on demand for the application; dynamically-linked code is also used to implement language-independent enhancement and extension, to elilminate machine-dependencies from binaries, and to reduce the size of binaries. (Unfortunately, the term is also sometimes used to describe ``building hypermedia connections on an ongoing or incremental basis''.)

The term runtime compilation is often used to describe loop parallelization that is done at runtime and which performs no code generation. The idea of runtime compilation is that loop-carried data dependencies for, e.g., ``x[i] = y[i+2] + z[i-5]'' can be discovered by a static compiler, but that, e.g., ``x[a[i]] = y[a[i+2]] + z[a[i-5]]'' cannot. The system thus examines the values of a at runtime, and performs parallelization at runtime, based on the values. The system thus ``compiles'' information at runtime but performs no code generation. Write to Shun-Tak Leung (shuntak@cs.washington.edu) for more information.

Instruction-Space Modification is a general term, including any topic that changes bits in an instruction space, whether the change comes from inside the application or from outside.

Just-In-Time Comiplation (JIT) is the general idea that some steps of compilation may be deferred until the code is invoked. At the moment (1996) most systems that use "JIT" by name are systems that use dynamic compilation to get good performance from a portable (machine and/or OS-independent) program representation. Typically, the unit of translation is a loadable unit, or smaller; for example, modules, procedures, statements, etc., and the input is some virtual machine byte code rather than source text, trees, etc. JIT is used to refer to code generation at dynamic link time as well as invocation time. In contrast, many other systems perform compilation "just in time" but with the goal of fine-tuning machine-dependent code, etc. A more preceise (but longer) name for "classical" JIT is probably something like: "demand-driven specialization to processor architecture at the [module|procedure|...] level".

The term self-modifying code or SMC also refers to RTCG but it is harder to pin down because there are many interpretations of ``modify'' and so many ways to pronounce ``self''. ``Modification'' may mean that an instruction is executed, manipulated in place, and then executed again; it may mean that a region of memory is reused, and holds several instructions over its lifetime; or, it may mean that the instruction space changes, even if no part of it is reused. As for the problem with ``self'', Adam Kao phrased it nicely:

What I'm trying to say is, what constitutes ``self'' and ``other'' depends on your point of view. ... Try this simple exercise. Point a finger at your belly-button. Poke. You poked yourself. Your finger didn't poke itself.
Some various sensible interpretations include: (a) instructions that manipulate themselves; (b) instructions that manipulate other instructions in the same basic block; (c) instructions from one source code module manipuate other instructions in the same module (d) instructions in one module manipulte instructions that are created on behalf of that module; (e) instructions in one address space manipulate other instructions in the same address space; (f) instructions in one protection somain mainpulate other instructions in the same protection domain (g) instructions being used to solve onen problem manipulate instructions that are also used to solve the same problem.

The terms code and data are used here in a limited sense. ``Code'' is used to refer to native machine code that is executable except that it may live in a data space instead of a code space. ``Data'' is used to refer to all other state, including bits in an instruction space that are not executable (e.g. are not well-formed instructions) and things that will be manipulted to become code but which are not yet executable native machine code. These definitions are limited because a more general definition of ``code'' defines it relative to some engine of execution. In particular, ``code'' in a more general sense might include virtual machine code instructions, source text, etc. and might also include data values that are used to affect processor execution in specific ways.


Pardo's RTCG stuff


Mail archive of postings to the rtcg mailing list.

Other RTCG stuff

Dynamic Linking

Not RTCG but related


pardo@cs.washington.edu