Gen.h

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdint.h>
#include <stdlib.h>

#define NULL_REG SIZE_MAX

typedef size_t Reg;
typedef size_t Lbl;
typedef struct Op {
	enum {
		RET,

		NUM,
		PARAM,
		LOCAL,

		STORE,
		LOAD,

		ADD,
		SUB,
		MUL,
		DIV,
		SDIV,
		CMPEQ,
		CMPNE,
		CMPLT,
		CMPGT,

		FNUM,
		FADD,
		FSUB,
		FMUL,
		FDIV,

		LABEL,
		GOTO,
		IFZ,
		IFNZ,
	} type;
	union {
		long long num;
		long long param;
		struct { Reg a, b; } bin_op;
		struct { Reg cond; Lbl lbl; } if_;
		Lbl goto_lbl;
		Lbl lbl;
		Reg ret;
		Reg load;
	};
} Op;

void Gen_Begin();
void Gen_End();
Reg Gen_Label(long long n);
Reg Gen_Local();
Reg Gen_Goto(Lbl n);
void Gen_Ifnz(Reg cond, Lbl l);
void Gen_Ifz(Reg cond, Lbl l);
void Gen_Store(Reg addr, Reg val);
Reg Gen_Load(Reg addr);
Reg Gen_Num(long long n);
Reg Gen_Param(long long n);
Reg Gen_Cmpeq(Reg a, Reg b);
Reg Gen_Cmpne(Reg a, Reg b);
Reg Gen_Cmplt(Reg a, Reg b);
Reg Gen_Cmpgt(Reg a, Reg b);
Reg Gen_Add(Reg a, Reg b);
void Gen_Ret(Reg a);

main.c

#include "Gen.h"

// Test
int main() {
	Gen_Begin();

	Reg temp = Gen_Local();
	Gen_Store(temp, Gen_Num(0));

	Gen_Label(0);

	// if (!(temp < 10)) goto loop_end
	Gen_Ifz(Gen_Cmplt(Gen_Load(temp), Gen_Num(10)), 2);

	Gen_Label(1);

	// temp += 1
	Gen_Store(temp, Gen_Add(Gen_Load(temp), Gen_Num(1)));

	Gen_Goto(0);
	Gen_Label(2);

	Gen_Ret(Gen_Load(temp));
	Gen_End();

	return 0;
}

PPC_Gen.c

#include "Gen.h"

typedef enum Cond {
	COND_E, COND_NE, COND_L, COND_GE, COND_LE, COND_G,
} Cond;

typedef struct Value {
	enum {
		Value_None,
		Value_Num,
		Value_Gpr,
		Value_Mem,
		Value_Cond
	} type;
	union {
		long long num;
		int gpr;
		struct { int offset; int base; } mem;
		Cond cond;
	};
} Value;

typedef struct AddressDesc {
	Value v;
	int cache;
    int is_mutated;
} AddressDesc;

static size_t op_count;
static Op ops[256];

static long long basic_block_names[256];
static AddressDesc address_desc[256];

static int bb_terminated = 0;

static int label_counter = 0;
static int bb_counter = 0;
static unsigned int allocated_gpr_bits = (1 << 1) | (1 << 2);

// NOTE: In the event we are copying registers it helps to just 
// tell the GPR allocator that we prefer a certain destination
static unsigned int desired_gpr = 0;

static unsigned int local_stack_usage = 0;

static const char* JMP_COND[] = {
	"be", "bne", "blt", "bge", "ble", "bgt"
};

static Value Resolve(Reg r);

static unsigned int AllocateGPR() {
	if ((allocated_gpr_bits & (1u << desired_gpr)) == 0) {
		allocated_gpr_bits |= (1u << desired_gpr);
		return desired_gpr;
	}

	// Find next free which is next inline
	for (unsigned int i = 0; i < 32; i++) {
		if ((allocated_gpr_bits & (1u << i)) == 0) {
			allocated_gpr_bits |= (1u << i);
			return i;
		}
	}

	assert(0);
}

static void FreeGPR(unsigned int r) {
	allocated_gpr_bits &= ~(1u << r);
}

static Reg CSE(int type, Reg a, Reg b) {
	for (size_t i = 0; i < op_count; i++) {
		if (ops[i].type == type && ops[i].bin_op.a == a && ops[i].bin_op.b == b) {
			return i;
		}
	}
	return NULL_REG;
}

static int ReferenceIntoReg(Reg r) {
	AddressDesc* a = &address_desc[r];
	if (a->cache >= 0) return a->cache;
	if (a->v.type == Value_None) a->v = Resolve(r);

	if (a->v.type == Value_Gpr) {
		//printf("\tmr r%d, r%d\n", dst, v.gpr);
		return a->v.gpr;
	} else if (a->v.type == Value_Num) {
		int dst = AllocateGPR();
		printf("\tlis r%d, 0x%llx\n", dst, a->v.num);
		a->cache = dst;
		return dst;
	} else if (a->v.type == Value_Mem) {
		int dst = AllocateGPR();
		printf("\tld r%d, %d(r%d)\n", dst, a->v.mem.offset, a->v.mem.base);
		a->cache = dst;
		return dst;
	} else {
		assert(0);
	}
}

static int LoadIntoReg(Reg r) {
	AddressDesc* a = &address_desc[r];
	if (a->cache >= 0) return a->cache;
	if (a->v.type == Value_None) a->v = Resolve(r);

	int dst = AllocateGPR();
	if (a->v.type == Value_Gpr) {
		//printf("\tmr r%d, r%d\n", dst, v.gpr);
		return a->v.gpr;
	} else if (a->v.type == Value_Num) {
		printf("\tld r%d, 0x%llx\n", dst, a->v.num);
	} else if (a->v.type == Value_Mem) {
		printf("\tld r%d, %d(r%d)\n", dst, a->v.mem.offset, a->v.mem.base);
	} else {
		assert(0);
	}

	a->cache = dst;
	return dst;
}

static void TerminateBlock() {
    printf("\t# Terminator\n");
	for (int i = 0; i < 256; i++) {
        if (address_desc[i].is_mutated && address_desc[i].cache >= 0) {
            if (address_desc[i].v.type == Value_Mem) {
                printf("\tstw %d(r%d), r%d\n", address_desc[i].v.mem.offset, address_desc[i].v.mem.base, address_desc[i].cache);
            } else if (address_desc[i].v.type == Value_Gpr) {
	            local_stack_usage -= 4;
	            address_desc[i].cache = -1;
	            address_desc[i].v = (Value){ .type = Value_Mem, .mem = {.offset = local_stack_usage, .base = 1 } };
	
                printf("\tstw %d(r%d), r%d\n", address_desc[i].v.mem.offset, address_desc[i].v.mem.base, address_desc[i].cache);
            }
            address_desc[i].cache = -1;
            address_desc[i].is_mutated = 0;
        }
    }
}

static Value Resolve(Reg r) {
	Op* op = &ops[r];
	switch (op->type) {
	case ADD: {
		int dst = AllocateGPR();

		if (ops[op->bin_op.b].type == NUM) {
			int a = ReferenceIntoReg(op->bin_op.a);

			printf("\taddi r%d, r%d, 0x%llx\n", dst, a, ops[op->bin_op.b].num);
			return (Value) { .type = Value_Gpr, .gpr = dst };
		} else {
			int a = ReferenceIntoReg(op->bin_op.a);
			int b = ReferenceIntoReg(op->bin_op.b);

			printf("\tadd r%d, r%d, r%d\n", dst, a, b);
			return (Value) { .type = Value_Gpr, .gpr = dst };
		}
	}
	case CMPEQ:
		printf("\tcmp r%d, r%d\n", ReferenceIntoReg(op->bin_op.a), ReferenceIntoReg(op->bin_op.b));
		return (Value) { .type = Value_Cond, .cond = COND_E };
	case CMPNE:
		printf("\tcmp r%d, r%d\n", ReferenceIntoReg(op->bin_op.a), ReferenceIntoReg(op->bin_op.b));
		return (Value) { .type = Value_Cond, .cond = COND_NE };
	case CMPLT:
		printf("\tcmp r%d, r%d\n", ReferenceIntoReg(op->bin_op.a), ReferenceIntoReg(op->bin_op.b));
		return (Value) { .type = Value_Cond, .cond = COND_L };
	case CMPGT:
		printf("\tcmp r%d, r%d\n", ReferenceIntoReg(op->bin_op.a), ReferenceIntoReg(op->bin_op.b));
		return (Value) { .type = Value_Cond, .cond = COND_G };
	case LOAD: {
		return (Value) { .type = Value_Gpr, .gpr = LoadIntoReg(op->load) };
	}
	default: return address_desc[r].v;
	}
}

void Gen_Begin() {
	for (int i = 0; i < 256; i++) address_desc[i].cache = -1;
}

void Gen_End() {

}

Lbl Gen_NewLabelId() {
    return label_counter++;
}

Reg Gen_Num(long long n) {
	Reg r = op_count++;
	ops[r] = (Op){ .type = NUM, .num = n };
	address_desc[r].cache = -1;
	address_desc[r].v = (Value){ .type = Value_Num, .num = n };
	return r;
}

void Gen_Label(Lbl l) {
    TerminateBlock();

	Reg r = op_count++;
	ops[r] = (Op){ .type = LABEL, .lbl = l };

    basic_block_names[l] = bb_counter++;
	printf(".BB%lld:\n", basic_block_names[l]);
}

void Gen_Ifnz(Reg cond, Lbl l) {
    TerminateBlock();

	Reg r = op_count++;
	ops[r] = (Op){ .type = IFNZ, .if_ = { cond, l } };

	if (ops[cond].type >= CMPEQ && ops[cond].type <= CMPGT) {
		Value cond_val = Resolve(cond);
		Cond c = cond_val.cond; // invert
		if (c & 1) c &= ~1;
		else c |= 1;
		
		printf("\t%s .BB%lld\n", JMP_COND[c], basic_block_names[l]);
	} else {
		assert(0);
	}
}

void Gen_Ifz(Reg cond, Lbl l) {
    TerminateBlock();

	Reg r = op_count++;
	ops[r] = (Op){ .type = IFZ, .if_ = { cond, l } };

	if (ops[cond].type >= CMPEQ && ops[cond].type <= CMPGT) {
		Value cond_val = Resolve(cond);

		printf("\t%s .BB%lld\n", JMP_COND[cond_val.cond], basic_block_names[l]);
	} else {
		assert(0);
	}
}

void Gen_Goto(Lbl n) {
	Reg r = op_count++;
	ops[r] = (Op){ .type = GOTO, .goto_lbl = n };

	printf("\tb .BB%lld\n", n);
}

void Gen_Store(Reg addr, Reg val) {
	int src = ReferenceIntoReg(val);

	if (ops[addr].type == LOCAL) {
		printf("\tstw %d(r%d), r%d\n", address_desc[addr].v.mem.offset, address_desc[addr].v.mem.base, src);
	} else {
		assert(0);
	}
}

Reg Gen_Load(Reg addr) {
	Reg r = op_count++;
	ops[r] = (Op){ .type = LOAD, .load = addr };

	return r;
}

Reg Gen_Param(long long n) {
	Reg r = op_count++;
	ops[r] = (Op){ .type = PARAM, .param = n };

	if (n < 8) address_desc[r].cache = 3 + n;
	address_desc[r].v = (Value){ .type = Value_Mem, .mem = {.offset = (n + 1) * 8, .base = 1 } };

	return r;
}

Reg Gen_Local() {
	Reg r = op_count++;
	ops[r] = (Op){ .type = LOCAL };

	local_stack_usage -= 4;
	address_desc[r].cache = -1;
	address_desc[r].v = (Value){ .type = Value_Mem, .mem = {.offset = local_stack_usage, .base = 1 } };
	
	return r;
}

Reg Gen_Cmpeq(Reg a, Reg b) {
	Reg cse = CSE(CMPEQ, a, b);
	if (cse != NULL_REG) return cse;

	Reg r = op_count++;
	if (ops[a].type == NUM & ops[b].type == NUM) ops[r] = (Op){ .type = NUM, .num = ops[a].num == ops[b].num };
	else ops[r] = (Op){ .type = CMPEQ, .bin_op = { a, b } };

	return r;
}

Reg Gen_Cmpne(Reg a, Reg b) {
	Reg cse = CSE(CMPNE, a, b);
	if (cse != NULL_REG) return cse;

	Reg r = op_count++;
	if (ops[a].type == NUM & ops[b].type == NUM) ops[r] = (Op){ .type = NUM, .num = ops[a].num != ops[b].num };
	else ops[r] = (Op){ .type = CMPNE, .bin_op = { a, b } };

	return r;
}

Reg Gen_Cmplt(Reg a, Reg b) {
	Reg cse = CSE(CMPLT, a, b);
	if (cse != NULL_REG) return cse;

	Reg r = op_count++;
	if (ops[a].type == NUM & ops[b].type == NUM) ops[r] = (Op){ .type = NUM, .num = ops[a].num < ops[b].num };
	else ops[r] = (Op){ .type = CMPLT, .bin_op = { a, b } };

	return r;
}

Reg Gen_Cmpgt(Reg a, Reg b) {
	Reg cse = CSE(CMPGT, a, b);
	if (cse != NULL_REG) return cse;

	Reg r = op_count++;
	if (ops[a].type == NUM & ops[b].type == NUM) ops[r] = (Op){ .type = NUM, .num = ops[a].num > ops[b].num };
	else ops[r] = (Op){ .type = CMPGT, .bin_op = { a, b } };

	return r;
}

Reg Gen_Add(Reg a, Reg b) {
	Reg cse = CSE(ADD, a, b);
	if (cse != NULL_REG) return cse;

	Reg r = op_count++;
	if (ops[a].type == NUM & ops[b].type == NUM) ops[r] = (Op){ .type = NUM, .num = ops[a].num + ops[b].num };
	else ops[r] = (Op){ .type = ADD, .bin_op = { a, b } };

	return r;
}

void Gen_Ret(Reg a) {
    TerminateBlock();

	desired_gpr = 3;
	Value r = Resolve(a);
	if (r.type == Value_Gpr) {
		if (r.gpr != 3) printf("\tmr r3, r%d\n", r.gpr);
	} else if (r.type == Value_Num) {
		printf("\tlis r3, 0x%llx\n", r.num);
	} else if (r.type == Value_Mem) {
		printf("\tld r3, %d(r%d)\n", r.mem.offset, r.mem.base);
	}
	printf("\tblr\n");
	desired_gpr = 3;

	ops[op_count++] = (Op){ .type = RET, .ret = a };
}