Re: Jump size optimization info...

        Thanks to those who responded! I figured out what I did wrong with
the +1/-1 problem, it now works...


        This method assumes that branch instructions are short, and
increases when neccessary. I wrote a really simple test program using
Visual C++ 6 Pro. For the interested, I pasted it at the following
URL...


        http://snipplr.com/view/2151/jump-size-optimization/


        To keep the scanner and parser simple, the 16-bit Real Mode x86
instructions are abbreviated as follows...


n = nop
jx = jmp where x is 0..9
0..9: = label
r = ret


        Jump size optimization is done in 1 pass through the source code,
and x passes through the compiled binary.


        The way it works is basically...


Parse Loop
* If a label is declared, register its target address
* Upon reaching a jmp instruction
    - Emit a short jmp machine code (assume 0 for the relative target
address)
    - Register jmp instruction, source address and target ID in the
branch list
* Emit other recognized instructions
* Repeat until EOF or error


Fixup loop
* Initialize size adjustment to 0
* For each branch instruction in the target
    - Calculate abs(target - source)
    - If result is greater than 128 and instruction size has not been
adjusted
        > For each target address greater than end of instruction,
increase target address by 1
        > For each branch instruction in the branch list whose source
address is greater, increase source address by 1
        > Insert 1 byte into the compiled code after current branch
instruction
        > Overwrite short instruction form with long instruction form
        > Add to size adjustment
* Repeat while size adjustment is non-zero


Backpatching loop
* For each branch instruction in branch list
    - Output 8-bit or 16-bit relative target address




        I like arrays, so that's what I used. This method can be
significantly improved on, but I haven't looked into it yet.


        The 3 bottlenecks are: 1) linear traversal of branch list for
source address adjustment, 2) linear traversal of target list for
target address adjustment, 3) shifting all bytes upwards when
instruction size increases.


        The person who responded to my e-mail a few years ago, and a
glance at Syzmanski's paper from a few years ago, suggested keeping a
variable which keeps track of the size increase/decrease. This method
would eliminate the need for immediate insertion upon instruction size
increase, but would require some form of recursion to calculate the
desired address. Keeping some kind of running total could eliminate
the need for recursion, but I'm not sure yet.


        This code helped me understand the concept without getting
distracted by the output. It is my hope that this was useful in some
way to someone :)




See ya!
Orlando

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