2009-10-14

Post date: Oct 17, 2009 5:19:11 PM

Transforming high-level structured control flow into either conditional or unconditional jump in C, in a form that is closer to how assembly language does control flow.

    • In C, we have goto for unconditional jump. The goto targets are labels, which is an identifier at the beginning of a line followed by a colon.
      • the_label:
            • The goto statement can jump below,
              • /* do something... */ goto label_below; /* this code is skipped... */ label_below: /* continue... */
            • or jump above,
              • label_above: /* do something... */ goto label_above;
    • Conditional jump in C is simulated by an if statement with only a goto in the then-clause.
      • if (cond) goto label;
    • Structured if's can be translated to conditional and unconditional jump like this.
            • Original
              • if (cond) { /* then-statement */ } else { /* else-statement */ } /* ... */
            • Translated
              • if (!cond) goto else_begin; /* then-statement */ goto else_end; else_begin: /* else-statement */ else_end: /* ... */

Translating loops:

    • While loop
            • Original
              • while (cond) { /* while-body */ }
            • translates into
              • loop_begin: if (!cond) goto loop_end; /* while-body */ goto loop_begin; loop_end:
    • For loop like this:
      • for (initialize; cond; update) { /* for-body */ }
    • is first translated into a while loop
      • initialize; while (cond) { /* for-body */ update; }
    • Then it can be translated into goto like above.

Examples and exercises:

    • Fibonacci, using while loop (see fib.c below) and using goto (fib-goto.c below).
    • Factorial, using while loop (see factorial.c below). Exercise.
    • Prime factorization, using for loop (see prime-factor.c below). Exercise.

(Note that their original location in my home directory has been removed.)