[openrisc] Huffman encoding operands

[Larry Doolittle <ldoolitt@recycle.lbl.gov>]

Damjan said:
> But don't you think we could use huffman's encoding
> for opcodes to get most out of encoding space. For example couldn't the
> following opcodes be squeezed in 4 bits and then you can have another
> register in the instruction?

Jimmy said:
> both opcode and operands. We can widen the opcode of
> the seldom used insn, but it still has operands...operands can not be
> Huffman encoded...

Damjan said:
> No, not operands. Just opcodes.

I disagree.  Instruction set compression (not necessarily Huffman)
is a good thing, we all know, as it reduces memory bandwidth, and
increases (fixed size) cache effectiveness, at the expense of slightly
more complex instruction decoding.  And yes, you can compress operands.

The mechanism used by all compression techniques is to hold some state
across symbol boundaries.  In particular, to avoid Damjan's objection
to hard-coding r9 in the ISA, define a new register "C", which is not
encoded in each individual instruction, but is part of the processor
state.  Add one more instruction so the program can change the 4-bit
value of C.  Now you can build infrequently used instructions (that
therefore have a lot of op-code bits) that refer to rC (thereby saving
insn bits), and you don't lock it into a particular register.
    h.configrC <4-bits>
For "prior art" of holding state to compress the instruction set,
look the the i386 string direction bit, and the xsoc immediate prefix.

It's not easy to imagine good compiler support for this feature,
except taking the cheap way out and always setting rC before using
one of these instructions.  By hand, you could do much better, and
might even want to extend this concept to have a few such implied
and configurable registers.

There is great value in sliding the boundary between hardware and
software support around to its most economical location.  For instance,
you shouldn't demand that stock gcc generate a beautiful and efficient
strcpy, and sweat blood on the compiler and ISA front to make it happen.
Instead, just make sure the hardware can do it, and write a few lines
of in-line assembler to do it.  For a canonical list of operations that
need support in that manner, look at Linux's
   /usr/include/asm/{atomic,bitops,checksum,string}.h
It's helpful to put in weird instructions, that these macros can use,
even if gcc itself never generates them.

   - Larry Doolittle  <LRDoolittle@lbl.gov>

P.S. To get really exotic, you could set rC automatically.  On every
instruction (compressed or not), set the 4-bit value that identifies
rC to be the destination register (if such a concept makes sense).
Now these compressed instructions would, by default, use the value
that was just computed.  OTOH, slip h.configrC into the instruction
stream, and you can perform the general case.  Hey, h.configrC is
itself no longer a special instruction, it's just h.or rA,0 !