Or runtime environments that enforce some of these constraints on binaries for variable-length-instruction architectures [1] :)
Variable-length instructions, when done right, closely approximate Huffman coding your binary, so you can get big code size wins, but there are definitely hardware/system software complexity and security disadvantages to be aware of. An intermediate point between, say, MIPS and x86, is something like ARM's Thumb, where you have one set of small instructions for your most common operations, and you can distinguish between the two in hardware without much hassle.
Agreed -- you can get large code size wins. This would require actively managing the instruction set so that the most common instructions are shortest. In theory, this could be done.
However, this doesn't work for a legacy architecture like x86, because many of the short opcodes are no longer the commonly used ones. Some are even actively deprecated. So overall, ARM wins in code size. I'm not sure about x86/64, maybe it is better there...
Variable-length instructions, when done right, closely approximate Huffman coding your binary, so you can get big code size wins, but there are definitely hardware/system software complexity and security disadvantages to be aware of. An intermediate point between, say, MIPS and x86, is something like ARM's Thumb, where you have one set of small instructions for your most common operations, and you can distinguish between the two in hardware without much hassle.
[1] http://code.google.com/p/nativeclient/