Re: variable length instructions, was Chicken or the Egg?

In the discussion about whether to expand short instructions to longer
ones or vice versa, our esteemed moderator asked the reasonable
question:
> [As I think we've said three times now, this is certainly possible in
> theory. I'd still like to hear whether it occurs in practice often
> enough to matter. -John]


Well, it shouldn't be hard to roughly calculate what the probability
of it mattering is.


Lets make short instructions 2 bytes and long instructions 4 bytes.
Lets give short instructions a reach of say 512 bytes. Let's also
speculate that most jumps are relatively short, say following Zipf's
law (a Poisson curve would likely be a better model, but beyond my
modest statistical abilities). Finally, lets assume a jump
instruction is likely in the code 1 instruction out of 8.


Okay, in the 512 byte reach of a short instruction, one can put 256
short instructions. Thus, with maximal packing (since most branch
instructions will be short), on average there will be 256/8 or 32
branch instructions in the reach of a short instruction.


Now, our model of the probability is that roughly 1/2 of those (16)
instructions will have a 2 instruction reach, 1/3 (10) will have a 3
instruction reach 1/4 (8) will have a 4 instruction reach, etc. (Note
this doesn't sum correctly, so they are only approximate numbers and
in fact they are "too large" so we will be over estimating the
frequency of the problem.) In our model, about 1/256th of the
instructions will have exactly a 256 instruction reach.


Given our simple probability model, it is unlikely that an instruction
reaching the boundary of its range will include another instruction
that also must be expanded.


Let, us see what cases will cause us to have a problem with the long
to short but not short to long.


1) The case where the instruction itself jumps 256 instructions (or it
      might be the 255 case, it doesn't matter for this handwaving). If
      the instruction is made short it fits, but starting with the long
      case it won't. That case will occur in 1/256th of the jump
      instructions. That will occur about the 0.39% of the time (less
      than 1/2 percent).


2) The case where the instruction jumps 255 instructions and jumps
      over an instruction that jumps 256 instructions where making the
      2nd instruction short will make the first one short also. That
      happens an even more rare 1/255 * 1/256th of the time (.00153%)


3) The case where the instruction jumps 255 instructions and jumps
      over an instruction that jumps 255 instructions and making either
      one short allows making both of them short. This case occurs only
      1/255 * 1/255th of the time (or slightly less rare than the previous
      case).


4) The 3, 4, 5 (and up to 256) instruction interactions, each becoming
      increasingly more rare.


However, as one can see from the way these approximate probabilities
sum (and they should over estimate the problem), the total is less
than 1/2 percent of the time.


Now, I fall in the camp of prefering short to long expansion.
However, if there is anything about the instruction set that would
make this complicated, the statistics suggest that it is not going to
be a very worthwhile path to follow.


The first rule of optimization is to measure what you are planning on
optimizing first. If something is infrequent enough, it isn't worth
optimizing unless it is free to do so.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.