Code Generation With Address Expressions

For this problem, I think it is easier to see what is happening if we use a problem definition that uses actual instructions (instead of the more abstract instructions G&J use in their definition).  So I am taking this problem description from the paper by Szymanski that has the reduction.

The problem: Code Generation With Address Expressions.  This is problem PO7 in the appendix.

The description: The PDP-11 has the following instructions:

  • Unconditional Branch (“br”), is two bytes long, and can only be used if the branch target is within 256 bytes or so of the branch instruction (technically 256 larger or 254 smaller).
  • Unconditional Jump (“jmp”), which works similarly to “br”, but is 4 bytes long and has no limit to the distance to the target.
  • Conditional branches (“beq” and “bne”), which like “br” are two bytes long and require the target to be within a fixed distance of the instruction
  • Extended conditional branches (“jbr”, “jeq”, and “jne”).  These instructions are either translated into “br”, “beq”, and “bne” if the targets are close enough, or they are treated as jmp instructions or conditional branches to a jmp instruction if the destination is too far.

Given a program with a series of these extended conditional branch instructions, and a goal size s, can we implement the program (by replacing the extended conditional statements with branches and jumps as appropriate) in s bytes or less?

Example: First, let’s look at how these jumps can happen.

Suppose I have:

    jbr  L1
    (some number of bytes of instructions without
     branches or jumps)

.. if the number of bytes in between is small, I can replace that with:

    br L1
    (the instructions just like before)

But if the size of the intermediate instructions is too large to allow a branch, we need to do:

     jmp L1
     (the instructions just like before)

Since a jmp is 4 bytes long and a br is 2 bytes long, the second option leads to a larger number of bytes at the end.

Here’s another example from the paper:

X: jne Y
   252 bytes of instructions
   jbr X

If we make the jbr instruction into a jump, then there is 256 bytes (+ the length of the jne instruction)  between the jne instruction and X, so the jne will also have to be a jump.  But if we make the jbr instruction into a br, then there are 254 bytes of instructions in between X and Y, so the jne can become a branch as well (so the distance between X and Y is 256 bytes), meaning that the jbr correctly was used as a branch (if the jne was a jump, the jump back to X would have covered too much space).

Reduction: Szymanski uses 3SAT.  So we start with a 3SAT instance with n variables and m clauses.  For each variable xi, we add the following lines to our program:

Yi:  jbr
     254 bytes of non-branching or jumping code

(I’m a little confused by this because he doesn’t list a destination for the jbr here.  I think we’re supposed to go to Zi, so that we can potentially replace the jbr with a br)

For every clause Cj = {lj,1, lj,2, lj,3} we add the following lines to our program:

    246 lines of non-branching or jumping code
    jbr Tj1
    jbr Tj2
    jbr Tj3

..where if lj,k is an un-negated version of variable xi, Tjk is an address calculated as the current address +Zi-Yi. If lj,k is a negated version of variable xi, Tjk is calculated as the current address +Zi-Yi-512.

We also add to the end of every clause n+3m+1 copies of a jbr statement to a line Bj-Aj bytes away from the current line.

The total length of this program is: 256n + 254m + 2nm + 6m2 + 2q, where q is the number of times we need to use a long jump instruction.  We have n+3m+m(n+3m+1) jbr instructions to deal with.  Our goal size s is 258n+280m+2nm+6m2, which we can only reach if we have at most n+3m jmp instructions (the rest being replaced by br’s)

Each of the Yi jumps can either be replaced by “br” instructions (which we will interpret as setting variable i to true) making the distance between Zi and Yi 256 bytes), or by jmp instructions (which we will interpret as setting variable i to false), making the distance between Zi and Yi 258 bytes.

The distance between each of the Ai and Bi in the clause pieces is 246 bytes + 2 bytes for each br we use or 4 bytes for each jmp we use.  So the total distance is 252, 254, 256, or 258 bytes,  Notice that we can only do a short translation if the corresponding literal is true, meaning that there are 256 or fewer bytes in the clause fragment if and only if the clause can be satisfied.

So, if the original formula is satisfiable, we will be able to find a way to satisfy each clause j to make the distance between the Aj and Bj labels 256 bytes or less.  So all of the “extra” jbr instructions at the end of each clause can be given short translations, so we will have our total program be of size s or less.

If the original formula is unsatisfiable, then no matter what we decide to do with our variables, there will be at least one clause where we have to give the long (258 byte) distance between Aj and Bj (this is the clause that is unsatisfied by whatever variable assignment we choose).  This means that the extra jbr Bj-Aj instructions at the end of that clause must turn into jmp instructions that are 4 bytes long each, making the overall size of the program too long.

Difficulty: 7.  It takes a while to understand the distances, and one of the consequences of using the real PDP-11 machine is the difference in distance between forward jumps that can be turned into branches (256 bytes) and backward ones (252 bytes), which makes the arithmetic and algebra a bit harder than I’d like.  But I think this is a neat reduction.

Leave a Reply

Your email address will not be published.