Re: How to optimize Intel's JMP instruction?

I lifted this piece of comment from my compiler; The algorithm came
from a VERY old paper from somewhere else:
[ See http://compilers.iecc.com/comparch/article/91-01-005
    This problem was well understood in the 1970s. -John ]


/***
    * This code implements relocation where even the jumps them selves are
    * relocated so that we don't have to emit long form jumps all the time...
    *
    *
    *
    * The algorithm to do complete relocation is as follows:
    *
    * 1) assign addresses (....done
already by GNU as) *
    * 2) make short assumptions where possible (....done
already by GNU as)
    *
    * 3) make 2 tables, 1 entry for each sdi:
    * LONG[i] 0: when unknown, lengh
saved otherwise
    * INCREMENT[i]
    * SPAN[j] : distance jumped
    *
    * 4) make table per label:
    * PREC[i] = sdi's preceding label i
    *
    * 5) make a graph, one node per sdi:
    * SDI_DEP[i] = {}, added to when i lies
between sdi[j] and i
ts target
    *
    *************
    *
    * Comment: LONG[i] == 0, means we've given it a chance and it was
too far,
    * we can ignore it for now (effectually deleted)
    *
    * removed_something = true;
    * while (removed_something)
    * {
    * removed_something = false;
    * for (i=0;i<SDIS;i++)
    * {
    * if (LONG[i] == 0 && SPAN[i] >
MAX_SHORT_JUMP_DISTANCE)
    * {
    * LONG[i] += LONG_JUMP_INSN - SHORT_JUMP_INSN;
    * for all dependents J in SDI_DEP[i] do
    * SPAN[j] += LONG[i]
    * remove i
    * removed_something = true;
    * }
    * }
    * }
    *
    * int INCREMENT[SDIS] = {0,}
    *
    * INCREMENT[0] = 0;
    * for (i=0;i<SDIS;i++)
    * {
    * INCREMENT[i] = INCREMENT[i-1] + LONG[i];
    * }
    *
    * int seen_sdi = 0;
    * for (i=0;i<insns;i++)
    * {
    * if (insn[i] == sdi)
    * address += INCREMENT[i]
    * seen_sdi++
    * }
    *
    *
    * sdi = span dependend instruction
    *
    */




Li Ping wrote:
> This problem seems more complex than I thought. A good
> compiler/assembler should use the short jump instruction whenever
> possible. However, it's not as easy as it appears. Because there could
> be other optimizable JMP instructions between this one and the target
> label. ...

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