Re: asm -> structured form

Erik Lundh <el@compelcon.se> wrote:
>Have a look at Christina Cifuentes work with decompilers at
>http://www.it.uq.edu.au/groups/csm/dcc.html
>Also, have a look at Frans Faase's excellent compilation of decompiler
>efforts at http://wwwis.cs.utwente.nl:8080/~faase/Ha/decompile.html
>(There is a disclaimer at the top of the page that Mr Faase has left
>the faculty and might be unable to maintain the page. But the last
>update is dated in december 1997... Hope he can keep it!)


Software Migration Ltd's FermaT tool will convert IBM assembler to
structured WSL (Wide Spectrum Language) and C. A COBOL translator is
currently under development. The tool first does a simple
line-by-line translation of each assembler instruction into an
equivalent block of WSL code. The blocks of WSL form an "Action
System": each block ends with a call to the next block in sequence,
and may contains other calls. The tool then applies a large number of
formal program transformations to the WSL code: the WSL language has
been developed over the past twelve years in parallel with the
development of a transformation theory. The result is a high-level
structured WSL program, equivalent to the original assembler program.


See http://www.dur.ac.uk/~dcs0mpw/ for the technical details,
including papers. SML's web site is: http://www.SMLtd.com/


For example, here is a fragment of assembler:


                  ST R3,N Numbers of elements
                  SLL R3,2 * 4
                  LR R10,R1
                  ST R14,SAVER14
                  BAL 14,BIN
                  LM R1,R2,SA
                  L R14,SAVER14
                  BR 14
BIN L R4,ONE
                  L R5,N
                  S R10,M Address of zero'th key
* Body of Loop ...
LOOP L R6,ZERO
                  LA R7,0(R4,R5) R7 = R4+R5
                  D R6,=F'2' R7 / R2
                  LR R3,R7 Save R7 in R3
                  M R6,M Displacement fro zero key
                  C R2,0(R7,R10) sum of regs 7,10 is addr of j'key
                  BE SUCC
                  BH ADJI
* Adjusment step
                  LR R5,R3
                  S R5,ONE
                  B COMPIK
ADJI LA R4,1(,R3)
* Test for exit
COMPIK CR R4,R5
                  BL LOOP
* Leave loop
                  BH FAIL
                  LR R7,R5
                  M R6,M
                  C R2,0(R7,R10)
                  BE SUCC
FAIL SR R3,R3
                  BR 14
SUCC LA R3,0(R7,R10)
* end of search segment
NEXT ST R3,N
                  XR R15,R15
                  BR 14






FermaT converts this to the following WSL code
(with no manual intervention required):


BEGIN
    C:" Numbers of elements ";
    N := r3;
    C:" * 4 ";
    SAVER14 := 0;
    r4 := ONE;
    r5 := N;
    C:" Address of zero'th key ";
    r10 := r1 - M;
    C:" * Body of Loop ... ";
    DO C:" R7 = R4+R5 ";
          C:" R7 / R2 ";
          IF ZERO = 0
              THEN r7 := (r4 + r5) DIV 2
              ELSE r7 := !XF div_64(ZERO, r4 + r5, 2) FI;
          C:" Save R7 in R3 ";
          r3 := r7;
          C:" Displacement fro zero key ";
          r7 := M * r7;
          C:" sum of regs 7,10 is addr of j'key ";
          IF a[(r7 + r1) - M, 4] = r2
              THEN SUCC(); EXIT(1) FI;
          IF a[(r7 + r1) - M, 4] < r2
              THEN r4 := r3 + 1; C:" * Test for exit "
              ELSE C:" * Adjusment step ";
                        r5 := r3 - ONE FI;
          IF r4 = r5
              THEN r7 := M * r5;
                        IF a[(r1 + M * r5) - M, 4] = r2
                            THEN SUCC() FI;
                        EXIT(1)
          ELSIF r4 >= r5
              THEN EXIT(1) FI;
          C:" * Leave loop " OD
  WHERE
    PROC SUCC() ==
            C:" * end of search segment "; N := r10 + r7 END
  END




Note that FermaT has created the procedure SUCC (choosing the name
from a label in the assembler) in order to avoid duplicating
two statements (a comment statement and an assignment).




This, in turn, is converted to the following C code:


int
main()
{
    /* Numbers of elements */
    n = regs.r3;
    /* * 4 */
    saver14 = 0;
    regs.r4 = one;
    regs.r5 = n;
    /* Address of zero'th key */
    regs.r10 = (regs.r1 - m);
    /* * Body of Loop ... */
    for (;;) { /* DO loop 1 */
        /* R7 = R4+R5 */
        /* R7 / R2 */
        if (zero == 0) {
            regs.r7 = ((regs.r4 + regs.r5) / 2);
        } else {
            regs.r7 = div_64(zero, (regs.r4 + regs.r5), 2);
        }
        /* Save R7 in R3 */
        regs.r3 = regs.r7;
        /* Displacement fro zero key */
        regs.r7 = (m * regs.r7);
        /* sum of regs 7,10 is addr of j'key */
        if (!(memcmp((BYTE *) ((regs.r7 + regs.r1) - m),
            (BYTE *) & regs.r2, 4))) {
            succ_p();
            break;
        }
        if (memcmp((BYTE *) ((regs.r7 + regs.r1) - m),
            (BYTE *) & regs.r2, 4) < 0) {
            regs.r4 = (regs.r3 + 1);
            /* * Test for exit */
        } else {
            /* * Adjusment step
              */
            regs.r5 = (regs.r3 - one);
        }
        if (regs.r4 == regs.r5) {
            regs.r7 = (m * regs.r5);
            if (!(memcmp((BYTE *) ((regs.r1 + (m * regs.r5)) - m),
                (BYTE *) & regs.r2, 4))) {
                succ_p();
            }
            break;
        } else if (regs.r4 >= regs.r5) {
            break;
        }
        /* * Leave loop */
    } /* OD */
}


void
succ_p()
{
    /* * end of search segment */
    n = (regs.r10 + regs.r7);
    return;
}




I am currently working on reducing the number of memcmp and memmove calls.


Martin


Martin.Ward@durham.ac.uk http://www.dur.ac.uk/~dcs0mpw
Maintainer of the G.K.Chesterton web site: http://www.dur.ac.uk/~dcs0mpw/gkc/
--

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