Optimizing comparison instruction count (PDP-11)

Question

For PDP-11, how can I change the following snippet of assembly so that it's only two instructions, yet does the same work as these four?

tst r0
blt label
cmp r0, #75
bgt label

Answer 1

Assuming you want to jump to the same label if the result of the comparison is either greater than or less than, then you can get it down to two instructions by using a branch-if-not-equal instruction (because a != b when a < b && a > b), and one other instruction.

Hint: it's not a test instruction.

Answer 2

I've never worked with a PDP-11, but I have some experience with the way testing and branching works on x86 systems, and this looks like it may be similar.

On the x86 instruction set, the "test" instruction is equivalent to a comparison against 0; the "less than" flag is set if the value is less than 0, etc. I'm going to guess that #75 means a numeric literal in hexadecimal -- 0x75.

If my assumptions are correct, the code you have there is doing two signed comparisons:

• Is the (signed) value of r0 less than 0?
• Is the (signed) value of r0 greater than 0x75?

If you instead treat it as an unsigned value, then -- assuming PDP-11 systems use 2's-complement encoding -- values that were negative become values greater than or equal to 0x8000 (since the PDP-11 is a 16-bit system). Thus, if you do an unsigned comparison, checking against 0x75 will take care of the negative values as well; the smallest possible value becomes 0, which is acceptable for the tests here.

I'm not sure whether an unsigned comparison on the PDP-11 is a different comparison opcode or a different flag, but I'm sure you can figure that part out. :-)

Answer 3

Probably too late for your homework now, so here's the answer:

cmp r0,#75
bcc label    ; branch if r0 contains 75..65535, ie 75..32767, -32768..-1

bcc has an assembly synonym of bhis (branch if HIgher or Same unsigned).