4

Variable length instruction sets often provide multiple jump instructions with differently sized displacements to optimize the size of the code. For example, the PDP-11 has both

0004XX       BR FOO      # branch always, 8 bit displacement

and

000167 XXXXX JMP FOO     # jump relative, 16 bit displacement

for relative jumps. For a more recent example, the 8086 has both

EB XX        JMP FOO     # jump short, 8 bit displacement

and

E8 XX XX     JMP FOO     # jmp near, 16 bit displacement

available.

An assembler should not burden the programmer with guessing the right kind of jump to use; it should be able to infer the shortest possible encoding such that all jumps reach their targets. This optimisation is even more important when you consider cases where a jump with a big displacement has to be emulated. For example, the 8086 lacks conditional jumps with 16 bit displacements. For code like this:

74 XX        JE FOO      # jump if equal, 8 bit displacement

the assembler should emit code like this if FOO is too far away:

75 03        JNE AROUND  # jump if not equal
E8 XX XX     JMP FOO     # jump near, 16 bit displacement
     AROUND: ...

Since this code is and takes more than twice as long as a JE, it should only be emitted if absolutely necessary.

An easy way to do this is to first try to assembly all jumps with the smallest possible displacements. If any jump doesn't fit, the assembler performs another pass where all jumps that didn't fit previously are replaced with longer jumps. This is iterated until all jumps fit. While easy to implement, this algorithm runs in O(n²) time and is a bit hackish.

Is there a better, preferably linear time algorithm to determine the ideal jump instruction?

As outlined in another question, this start small algorithm is not necessarily optimal given suitably advanced constructs. I would like to assume the following niceness constraints:

  • conditional inclusion of code and macro expansion has already occurred by the time instructions are selected and cannot be influenced by these decisions

  • if the size of a data object is affected by the distance between two explicit or implicit labels, the size grows monotonously with distance. For example, it is legal to write

             .space foo-bar

    if bar does not occur before foo.

  • in violation of the previous constraint, alignment directives may exist
fuz
  • 88,405
  • 25
  • 200
  • 352
  • Related: [Why is the "start small" algorithm for branch displacement not optimal?](https://stackoverflow.com/q/34911142). Finding a good solution can be (and is) done quickly (because the O(n^2) worst-case is rare for the start-small algo), but finding an optimal solution maybe be an NP-complete problem that requires evaluating all possibilities. However (as I mention in my answer), it may be possible to break it into multiple independent sub-problems at boundaries where long encodings are definitely needed anyway, and an ALIGN directive sets a known starting point. – Peter Cordes Oct 15 '18 at 23:08
  • 1
    It is worse, equivalent to the bin-packing problem, NP-awful. But with trivial first-fit/best-fit approximations that don't suck that bad. Along with very low N, so nobody worries about it. – Hans Passant Oct 15 '18 at 23:08
  • @HansPassant I've considered this sort of case (which is why I mentioned macros and conditional compilation). I'm operating under some niceness assumptions, let me add them to the question for you. – fuz Oct 15 '18 at 23:12
  • In the case of Microsoft Masm 6.11 or later version, you can use a [dot directive](https://msdn.microsoft.com/en-us/library/8t163bt0.aspx) for the 8086 conditionals, such as `.if ax = 01234h` `...` (`.else` `...`) `.endif` , which should choose the one or two instruction sequences as needed. – rcgldr Oct 15 '18 at 23:13
  • Macros and conditional compilation don't really come into it. You generate intermediate code, *then* you optimize. By that time, all the text expansion has been done. – Jim Mischel Oct 15 '18 at 23:17
  • 1
    @JimMischel I was thinking about cases where you could conditionally include code based on the distance between labels. Please wait for me to include the niceness conditions. – fuz Oct 15 '18 at 23:18
  • As I showed in my answer on the linked question, just a plain `ALIGN` with branches across it in both directions is sufficient to create a case where start-small isn't optimal. So your niceness constraints are insufficient to make the O(n^2) algorithm acceptable, if you demand truly optimal for as many branches as possible. (Weighting by dynamic count instead of static would be another complication: favour optimizing the hot branches inside loops if there's a tradeoff.) – Peter Cordes Oct 15 '18 at 23:45
  • @PeterCordes I think start-small is still acceptable even in the presence of alignment directives if you strictly extend jumps in increasing order of addresses as extending a jump can only make later jumps shorter wrt. alignment. – fuz Oct 16 '18 at 11:07
  • 1
    I updated [Why is the "start small" algorithm for branch displacement not optimal?](https://stackoverflow.com/a/34940237) with a specific tested example that demonstrates my point with NASM. Using a longer encoding for the first branch is totally unnecessary, though, and if an assembler is going to consider that it should also be considering longer encodings for other instructions ([What methods can be used to efficiently extend instruction length on modern x86?](https://stackoverflow.com/q/48046814)). So my optimality criterion kind of goes beyond just the BDO problem. – Peter Cordes Oct 16 '18 at 15:30

0 Answers0