Wie wird ein relativer JMP (x86) in einem Assembler implementiert?

Question

Während meines Assembler für die x86-Plattform bauen traf ich einige Probleme mit Codierung die JMP Anweisung:

OPCODE INSTRUCTION SIZE 
EB cb  JMP rel8  2 
E9 cw  JMP rel16 4 (because of 0x66 16-bit prefix) 
E9 cd  JMP rel32 5 
... 

(von meiner Lieblings-x86-Befehl Website, http://siyobik.info/index.php?module=x86&id=147)

All relativ Sprünge sind, wobei die Größe jeder Codierung (Operation + Operand) in der dritten Spalte liegt.

Jetzt mein ursprüngliches (und folglich Störung wegen) Entwurf reservierte den maximalen Raum (5 Bytes) für jede Anweisung. Der Operand ist noch nicht bekannt, weil es ein Sprung zu einem noch unbekannten Ort ist. Also habe ich einen "rewrite" -Mechanismus implementiert, der die Operanden an der richtigen Stelle im Speicher neu schreibt, wenn der Sprung bekannt ist, und den Rest mit NOP s füllt. Dies ist ein ernsthaftes Problem in engen Schleifen.

Nun mein Problem ist mit der folgenden Situation:

b: XXX 
c: JMP a 
e: XXX 
    ... 
    XXX 
d: JMP b 
a: XXX  (where XXX is any instruction, depending 
      on the to-be assembled program) 

Das Problem ist, dass ich die kleinste mögliche Codierung für eine JMP Anweisung will (und keine NOP Füllung).

ich habe die Größe der Anweisung an c wissen, bevor ich den relativen Abstand zwischen a und b für die Operanden bei d berechnen kann. Das gleiche gilt für die JMP bei c: es muss die Größe von d kennen, bevor es den relativen Abstand zwischen e und a berechnen kann.

Wie lösen bestehende Assemblierer dieses Problem, oder wie würden Sie dies tun?

Das ist, was ich denke welche löst das Problem:

Zuerst kodieren alle Anweisungen Opcodes zwischen dem JMP und es ist Ziel, wenn diese Region eine variabler Größe Opcode enthält, die maximale Größe verwenden , z.B 5 für eine JMP. Dann kodieren Sie den relativen JMP zum Ziel, indem Sie die kleinstmögliche Kodierungsgröße (3, 4 oder 5) wählen und den Abstand berechnen. Wenn ein Opcode mit variabler Größe codiert ist, ändern Sie alle absoluten Operanden vor und alle relativen Befehle, die diese codierte Anweisung überspringen: Sie werden neu codiert, wenn sich ihr Operand ändert, um die kleinstmögliche Größe zu wählen. Diese Methode endet garantiert, da Opcodes mit variabler Größe nur schrumpfen können (weil sie die maximale Größe verwenden).

Ich frage mich, vielleicht ist dies ein over-engineered Lösung, deshalb habe ich diese Frage stellen.

Answer 1

Hier ist ein Ansatz, den ich verwendet habe, die ineffizient erscheinen, aber stellt sich heraus, nicht für die meisten realen Code (Pseudo-Code) zu sein:

IP := 0; 
do 
{ 
    done = true; 
    while (IP < length) 
    { 
    if Instr[IP] is jump 
     if backwards 
     { Target known 
      Encode short/long as needed } 
     else 
     { Target unknown 
      if (!marked as needing long encoding) // see below 
      Encode short 
      Record location for fixup } 
    IP++; 
    } 
    foreach Fixup do 
    if Jump > short 
     Mark Jump location as requiring long encoding 
     PC := FixupLocation; // restart at instruction that needs size change 
     done = false; 
     break; // out of foreach fixup 
    else 
     encode jump 
} while (!done); 

Answer 2

Im ersten Durchlauf haben Sie eine sehr gute Näherung, um jmp Code zu verwenden, der eine pessimistische Bytezählung für alle Sprungbefehle verwendet.

Im zweiten Durchgang können Sie die Sprünge mit dem gewählten pessimistischen Opcode ausfüllen. Sehr wenige Sprünge könnten dann umgeschrieben werden, um ein Byte oder zwei weniger zu verwenden, nur solche, die ursprünglich sehr nahe an dem Sprungschwellwert von 8/16 Bit oder 16/32 Byte waren.Da die Kandidaten alle Sprünge von vielen Bytes sind, sind sie weniger wahrscheinlich in kritischen Schleifensituationen, so dass Sie wahrscheinlich feststellen werden, dass weitere Durchgänge wenig oder keinen Vorteil gegenüber einer Lösung mit zwei Durchgängen bieten.