Jump Size Optimization Improved...

About a year ago, I wrote a snippet of code which demonstrated a
method of jump size optimization. In my previous attempt, I actually
used memory operations to compensate for increases in branch operation
sizes. I also adjusted two arrays. My previous attempt is too
inefficient to adapt to production code.


The following URL is a link to a cleaner and more efficient
implementation:


    http://snipplr.com/view/8391/jump-size-optimization-improved/


The main concept of this method assumes that a branch operation is
short and should increase as needed.


This process is broken down into 4 phases: 1) parse, 2) target
validation, 3) backpatch, 4) compilation.


Parse Phase:
- Branch targets not declared in a branch operation are declared as a
forward reference
- Normal operations are compiled into an intermediate form without
branch operations
- Branch operations are stored in an array and mark the end of a block
of code
- Assembly menumonics are extremely simplified versions of x86
assembly
    jx = jmp x where x is 0 to 9
    :x = label where x is 0 to 9
    n = nop
    r = ret


Target Validation Phase:
- Target offsets with a value of 0xFFFFFFFF are unused
- Target offsets with a value of 0xFFFFFFFE is undeclared and
referenced
- All other target offsets are absolute offsets into the final
compiled code
- Any target offset with a value of 0xFFFFFFFE results in an error
since a branch operation referenced it, but a label was not declared


Backpatch Phase:
- Each branch operation, stored in an array, is checked
- If the branch target requires an increase in the branch operation's
size, the target offset is adjusted
- Any branch target offset affected by a branch operation size
increase are also adjusted
- Since one increase can result in another increase, this loop repeats
until all target offsets have been adjusted


Compilation Phase:
- Each branch operation marks the end of a code block
- Blocks of normal code operations are written to disk
- Branch operations are finalized and written to disk
- This process repeats until all branch targets have been processed
- Any remaining code is written to disk


In this implementation, branch targets are single labels. In the case
of branch target equations, the branch operation size must be assumed
to be long form from beginning to end since branch operation sizes can
either increase or decrease with each recalculation.


This method can easily be applied to virtual machine byte code and/or
other platforms.


I am donating the source code to my most recent implementation of jump
size optimization to the public domain in the hopes that it is useful
to someone.




Regards,
Orlando
[Branch optimization was studied extensively in the 1970s by Tom
Szymanski and others. The general problem if you allow jumps to jumps
is NP complete, but it's been well known for decades that you can get
pretty close either by starting with all the jumps short and expanding
until the code is valid, or starting with all the jumps long and
shrinking until there's nothing left to shrink. I don't see what's new
here. -John]

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