Linked by Peter Gerdes on Mon 10th Jan 2005 17:35 UTC
Editorial As a recent ACM Queue article observes the evolution of computer language is toward later and later binding and evaluation. So while one might quibble about the virtues of Java or the CLI (also known as microsoft.net) it seems inevitable that more and more software will be written for or at least compiled to virtual machines. While this trend has many virtues, not the least of which is compatibility, current implementations have several drawbacks. However, by cleverly incorporating these features into the OS, or at least including support for them, we can overcome these limitations and in some cases even turn them into strengths.
Permalink for comment
To read all comments associated with this story, please click here.

So some people have been praising AOT C style compilers because they always put the processor in a known state. I think this is a mistake and this is actually a great deficency in their operation tolerated because it is too hard to do anything else.

In any program the processor should always be in a known state, i.e., the processor state is completly determined by the input and the prior instructions. What we really mean by known state in this case is that the compiler has a convention about what the processor state must look like at particular times in the program. This means extra instructions are being used to bring the state into accordance with this convention even when it is not needed.

For instance consider the convention that after a function call the return value is stored in some particular register. This may often make sense but the return value may be entierly ignored by the calling code on every call, or always immediatly stored back to memory and not used for some time so it would make much more sense for the function to ignore the return value or place it in a temporary memory location itself so as to avoid spilling a register.

In fact much of compiler optimizations are about violating these conventions. The state of instruction selection theory today, I hope someday it will change to a more general algorithm, seems to be to start with strict conventions that are known to produce the correct result and then apply optimizations which abridge these conventions in a manner known not to screw up the program.

Unfortunatly, most of these processor level optimizations are performed using peephole analysis after code has been generated, i.e. the generated code is scanned with a relativly small window and if the optimizer recognizes a series of instructions that can be replaced with a faster version it does the replacement. As I understand it a BURS system is an advanced way to accomplish this task, basically it organizes instructions into dependency trees and then scans for matching sets of instructions it transforms via rewrite rules.

As should be apparent such a strategy depends heavily on finding efficent rewrite rules and the longer instruction sequences considered the more optimizations possible. As an example (which may or may not be real world reasonable) imagine a bunch of code which rests between a call saving the DS register and restoring it which makes no use of the data segment in between these points. If this entire sequence is subjected to a rewrite at once it may be able to make optimizations to store a variable in DS while if it only considers sequences of a smaller length it can never know it is safe to overwrite DS. However, one can hardly go through all instruction sequences of even length 20 so if one wants this optimizaiton to have a large window it depends on succesfully identifying commonly used code blocks and appropriate optimizations.

It was exactly this understanding and problem which lead me to suggest OS updates improving JIT compilation. As coders identify commonly used code segments and an optimization of that segment this rewrite rule can be sent to JIT, or even AOT, users. Since it is easy to verify that two code sequences are equivalent users can benefit from this optimization in all of their programs without any security risk.