Brainf*ck to NASM converter written in C

Question

I have made a very simple Brainfuck to NASM converter, that is usable for practically all programs. It has one trivial optimisation (to subsitute ADD for INC with large numbers). How can I make the generated code smaller and/or faster? I would prefer smaller over faster, if I had to choose.

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>
#include <unistd.h>
#include <sys/types.h>

static void usage(const char *);
static void compile_and_write(int);
static void print_header(void);
static void print_footer(void);

static FILE *in = NULL;
static FILE *out = NULL;

int
main(
    int argc,
    char *argv[])
{
    int ch;
    int opt;

    while ((opt = getopt(argc, argv, "i:o:h")) != -1) {
        switch (opt) {
        case 'i':
            in = fopen(optarg, "r");
            break;
        case 'o':
            out = fopen(optarg, "w");
            break;
        case 'h':
            usage(argv[0]);
            return EXIT_SUCCESS;
        default:
            usage(argv[0]);
            return EXIT_FAILURE;
        }
    }

    if (in == NULL) {
        in = stdin;
    }

    if (out == NULL) {
        out = stdout;
    }

    print_header();

    while ((ch = fgetc(in)) != EOF) {
        compile_and_write(ch);
    }

    print_footer();

    fclose(in);
    fclose(out);
    return EXIT_SUCCESS;
}

static void
print_header(
    void)
{
    fputs("[bits 64]\n", out);
    fputs("[section .bss]\n", out);
    fputs("mem:resb 32768\n", out);

    fputs("[section .text]\n", out);
    fputs("[global _start]\n", out);

    fputs("putc:\n", out);
    fputs("xor rax, rax\n", out);
    fputs("inc rax\n", out);
    fputs("xor rdi, rdi\n", out);
    fputs("inc rdi\n", out);
    fputs("xor rdx, rdx\n", out);
    fputs("inc rdx\n", out);
    fputs("syscall\n", out);
    fputs("ret\n", out);

    fputs("getc:\n", out);
    fputs("xor rax, rax\n", out);
    fputs("xor rdi, rdi\n", out);
    fputs("xor rdx, rdx\n", out);
    fputs("inc rdx\n", out);
    fputs("syscall\n", out);
    fputs("ret\n", out);

    fputs("_start:\n", out);
    fputs("mov rsi, mem\n", out);
}

static void
print_footer(
    void)
{
    fputs("mov rax, 60\n", out);
    fputs("xor rdi, rdi\n", out);
    fputs("syscall\n", out);
}

static void
compile_and_write(
    int ch)
{
    static int loop = 0;
    static int loops[0x10000] = {0};
    static size_t lp = 0;
    static unsigned cnt = 1;
    static int last = ' ';

    if (ch == last) {
        ++cnt;
        return;
    }

    switch (last) {
    case '+':
        if (cnt == 1) {
            fputs("inc byte [rsi]\n", out);
        } else {
            fprintf(out, "add byte [rsi], %u\n", cnt);
        }
        break;
    case '-':
        if (cnt == 1) {
            fputs("dec byte [rsi]\n", out);
        } else {
            fprintf(out, "sub byte [rsi], %u\n", cnt);
        }
        break;
    case '>':
        if (cnt == 1) {
            fputs("inc rsi\n", out);
        } else {
            fprintf(out, "add rsi, %u\n", cnt);
        }
        break;
    case '<':
        if (cnt == 1) {
            fputs("dec rsi\n", out);
        } else {
            fprintf(out, "sub rsi, %u\n", cnt);
        }
        break;
    case '.':
        while (cnt--) {
            fputs("call putc\n", out);
        }
        break;
    case ',':
        while (cnt--) {
            fputs("call getc\n", out);
        }
        break;
    case '[':
        while (cnt--) {
            loops[lp] = loop++;
            fprintf(out, "L%d:\n", loops[lp]);
            fprintf(out, "cmp byte [rsi], 0\n");
            fprintf(out, "jz E%d\n", loops[lp]);
            ++lp;
        }
        break;
    case ']':
        while (cnt--) {
            --lp;
            fprintf(out, "jmp L%d\n", loops[lp]);
            fprintf(out, "E%d:\n", loops[lp]);
        }
        break;
    default:
        break;
    }

    last = ch;
    cnt = 1;
}

static void
usage(
    const char *pname)
{
    fprintf(stderr, "usage: %s [-h] -i input -o output\n", pname);
}

Compilation command:

$ clang -Weverything -Werror -O2 -march=native -s -o bfc bfc.c

Usage (assume brainfuck input is mandelbrot.b and output is mandelbrot):

$ ./bfc -i mandelbrot.b -o mandelbrot.asm
$ nasm -Ox -w+all -w+error mandelbrot.asm
$ ld.gold -s -o mandelbrot mandelbrot.o

Note: this generates x86_64 assembly code for Linux (or compatible kernels) only. I might add i386 support later (perhaps in follow-up post).

Answer 1

I'll skip any consideration about C code and comment only generated assembly code (as per your question).

1) In your generated code:

XOR AX, AX
INC RAX
XOR RDI, RDI
INC RDI
XOR RDX, RDX
INC RDX

You're stalling your pipeline, shuffle your instructions and you may also gain because of using available ALUs. More about this on instruction scheduling.

XOR RAX, RAX
XOR RDI, RDI
XOR RDX, RDX
INC RAX
INC RDX
INC RDI

2) On same code I see you have often this pattern:

XOR reg, reg
INC reg

If you replace it with:

MOV reg, 1

You will have same size but it may result on a small speed improvement (but it varies according to CPU).

3) You're extensively using INC and DEC, you may have a small performance gain using ADD and SUB (at least if you do not target an ancient CPU):

INC rsi

Also simplifying (and slightly speed-up) your C code it should be rewritten as:

ADD rsi, 1

4) Now you have:

CMP BYTE [rsi], 0
JZ ...

You're testing for zero using CMP. With a small change you will not gain in size but (again) in speed:

TEST BYTE [rsi], 0
JZ ...

TEST is faster than CMP but unfortunately they both can't be macro-fused with JZ if second operand is an immediate value. Best would be to increase size in favor of speed (if you want so):

MOVZB AL, BYTE [rsi]
TEST AL, AL
JZ ...

4) If you do not really care about speed you can gain some extra bytes using LOOP instruction. For . and , commands you generate multiple CALL instructions. When cnt >= 3 you may replace this:

CALL getc
CALL getc
CALL getc

With:

C0: MOV CX, 3
    CALL getc
    LOOPNZ C0

Note that LOOP instruction is (usually) pretty bad from performance point of view then you should do this only if you really want to optimize for size. Same optimization also may apply for [ and ] refactoring code little bit more.

5) In generated code you often have patterns, if you're optimizing for size then you may detect them to compress code replacing blocks with jumps (see this somehow as the opposite of inlining). For example <+ is common pattern and it generates:

SUB rsi, 1
ADD BYTE [rsi], 1

If you detect this pattern then you will create a sub for it:

LTP1: SUB rsi, 1
      ADD BYTE [rsi], 1
      RET

And each time you find that code you simply:

CALL LPT1

This can be done both as post-processing on generated assembly or during you compilation phase. During compilation is easier (but you have to handle each pattern by hand) however it makes easy to also handle sequences like <+++ simply passing an argument through register.

6) All these done you should consider to perform multi-step optimization:

• First generate an intermediate code easier to analyze and optimize.
• Optimize this code using high-level knowledge (locally, across functions and whole program). You may add loops, pre-calculate invariants and so on. See also Is inline assembly language slower than native C++ code?.
• Generate assembly code from intermediate code.
• Optimize generated assembly code (if assembler you're using isn't doing this for you). Sometimes this kind of optimizations are called peephole optimizations and they're highly local (for example one jump followed by a MOV may simply perform a conditional MOV and you may use faster and shorter CMOV instead).

Answer 2

Adriano Repetti already did a wonderful job reviewing your generated assembly, so I'm mainly going to touch into the C a little bit.

---

static void usage(const char *);

What is with all the static functions? This is the main C file and, as far as I can tell, the only C file in this project. These statics aren't needed.

---

You have waaaaaaaaaaaaaaaaaayyyyyyyyyyyy to many function calls:

fputs("[bits 64]\n", out);
fputs("[section .bss]\n", out);
fputs("mem:resb 32768\n", out);

fputs("[section .text]\n", out);
fputs("[global _start]\n", out);

fputs("putc:\n", out);
fputs("xor rax, rax\n", out);
fputs("inc rax\n", out);
...

You repeat something like this a lot in your code. And, each time you have a big chunk of these writes like this, you are always doing the same thing: writing something to out.

It would be a whole lot faster if you just used one function call for each chunk of these:

fputs("[bits 64]\n"
      "[section .bss]\n"
      "mem:resb 32768\n"
      ...
      ..., out);

---

Always prefer local variables over global ones in C; it is much better practice as it is less error-prone and more maintainable.

I'm not going to go into how you can refactor some of these global variables, but take a look at the ones you have and see if there is a way you can make them local.

For example, that compiling function declares a few at the start. Instead, you might be able to return that information as a struct like compilation_data (or something like that) and have it accept a compilation data struct as an argument. This could also allow for some interesting future features.

---

    if (cnt == 1) {
        fputs("inc byte [rsi]\n", out);
    } else {
        fprintf(out, "add byte [rsi], %u\n", cnt);
    }

Save yourself the conditional: add is faster than inc, so why not just use add?

fprintf(out, 'add byte [rsi], %u\n", cnt);

---