program.c

/* Copyright (c) 2020 tevador <tevador@gmail.com> */
/* See LICENSE for licensing information */
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#include "program.h"
#include "unreachable.h"
#include "siphash_rng.h"
 
/* instructions are generated until this CPU cycle */
#define TARGET_CYCLE 192
 
/* requirements for the program to be acceptable */
#define REQUIREMENT_SIZE 512
#define REQUIREMENT_MUL_COUNT 192
#define REQUIREMENT_LATENCY 195
 
/* R5 (x86 = r13) register cannot be used as the destination of INSTR_ADD_RS */
#define REGISTER_NEEDS_DISPLACEMENT 5
 
#define PORT_MAP_SIZE (TARGET_CYCLE + 4)
#define NUM_PORTS 3
#define MAX_RETRIES 1
#define LOG2_BRANCH_PROB 4
#define BRANCH_MASK 0x80000000
 
#define TRACE false
#define TRACE_PRINT(...) do { if (TRACE) printf(__VA_ARGS__); } while (false)
 
#define MAX(a,b) ((a) > (b) ? (a) : (b))
 
/* If the instruction is a multiplication.  */
static inline bool is_mul(instr_type type) {
        return type <= INSTR_MUL_R;
}
 
#ifdef HASHX_PROGRAM_STATS
/* If the instruction is a 64x64->128 bit multiplication.  */
static inline bool is_wide_mul(instr_type type) {
        return type < INSTR_MUL_R;
}
#endif
 
/* Ivy Bridge integer execution ports: P0, P1, P5 */
typedef enum execution_port {
        PORT_NONE = 0,
        PORT_P0 = 1,
        PORT_P1 = 2,
        PORT_P5 = 4,
        PORT_P01 = PORT_P0 | PORT_P1,
        PORT_P05 = PORT_P0 | PORT_P5,
        PORT_P015 = PORT_P0 | PORT_P1 | PORT_P5
} execution_port;
 
static const char* execution_port_names[] = {
        "PORT_NONE", "PORT_P0", "PORT_P1", "PORT_P01", "PORT_P5", "PORT_P05", "PORT_P15", "PORT_P015"
};
 
typedef struct instr_template {
        instr_type type;          /* instruction type */
        const char* x86_asm;      /* x86 assembly */
        int x86_size;             /* x86 code size */
        int latency;              /* latency in cycles */
        execution_port uop1;      /* ex. ports for the 1st uop */
        execution_port uop2;      /* ex. ports for the 2nd uop */
        uint32_t immediate_mask;  /* mask for imm32 */
        instr_type group;         /* instruction group */
        bool imm_can_be_0;        /* if imm32 can be zero */
        bool distinct_dst;        /* if dst and src must be distinct */
        bool op_par_src;          /* operation parameter is equal to src */
        bool has_src;             /* if the instruction has a source operand */
        bool has_dst;             /* if the instr. has a destination operand */
} instr_template;
 
typedef struct register_info {
        int latency;              /* cycle when the register value will be ready */
        instr_type last_op;       /* last op applied to the register */
        uint32_t last_op_par;     /* parameter of the last op (~0 = constant) */
} register_info;
 
typedef struct program_item {
        const instr_template** templates;
        uint32_t mask0;
        uint32_t mask1;
        bool duplicates;
} program_item;
 
typedef struct generator_ctx {
        int cycle;
        int sub_cycle;
        int mul_count;
        bool chain_mul;
        int latency;
        siphash_rng gen;
        register_info registers[8];
        execution_port ports[PORT_MAP_SIZE][NUM_PORTS];
} generator_ctx;
 
static const instr_template tpl_umulh_r = {
        .type = INSTR_UMULH_R,
        .x86_asm = "mul r",
        .x86_size = 9, /* mov, mul, mov */
        .latency = 4,
        .uop1 = PORT_P1,
        .uop2 = PORT_P5,
        .immediate_mask = 0,
        .group = INSTR_UMULH_R,
        .imm_can_be_0 = false,
        .distinct_dst = false,
        .op_par_src = false,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_smulh_r = {
        .type = INSTR_SMULH_R,
        .x86_asm = "imul r",
        .x86_size = 9, /* mov, mul, mov */
        .latency = 4,
        .uop1 = PORT_P1,
        .uop2 = PORT_P5,
        .immediate_mask = 0,
        .group = INSTR_SMULH_R,
        .imm_can_be_0 = false,
        .distinct_dst = false,
        .op_par_src = false,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_mul_r = {
        .type = INSTR_MUL_R,
        .x86_asm = "imul r,r",
        .x86_size = 4,
        .latency = 3,
        .uop1 = PORT_P1,
        .uop2 = PORT_NONE,
        .immediate_mask = 0,
        .group = INSTR_MUL_R,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = true,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_sub_r = {
        .type = INSTR_SUB_R,
        .x86_asm = "sub r,r",
        .x86_size = 3,
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_NONE,
        .immediate_mask = 0,
        .group = INSTR_ADD_RS,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = true,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_xor_r = {
        .type = INSTR_XOR_R,
        .x86_asm = "xor r,r",
        .x86_size = 3,
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_NONE,
        .immediate_mask = 0,
        .group = INSTR_XOR_R,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = true,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_add_rs = {
        .type = INSTR_ADD_RS,
        .x86_asm = "lea r,r+r*s",
        .x86_size = 4,
        .latency = 1,
        .uop1 = PORT_P01,
        .uop2 = PORT_NONE,
        .immediate_mask = 3,
        .group = INSTR_ADD_RS,
        .imm_can_be_0 = true,
        .distinct_dst = true,
        .op_par_src = true,
        .has_src = true,
        .has_dst = true,
};
 
static const instr_template tpl_ror_c = {
        .type = INSTR_ROR_C,
        .x86_asm = "ror r,i",
        .x86_size = 4,
        .latency = 1,
        .uop1 = PORT_P05,
        .uop2 = PORT_NONE,
        .immediate_mask = 63,
        .group = INSTR_ROR_C,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = false,
        .has_src = false,
        .has_dst = true,
};
 
static const instr_template tpl_add_c = {
        .type = INSTR_ADD_C,
        .x86_asm = "add r,i",
        .x86_size = 7,
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_NONE,
        .immediate_mask = UINT32_MAX,
        .group = INSTR_ADD_C,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = false,
        .has_src = false,
        .has_dst = true,
};
 
static const instr_template tpl_xor_c = {
        .type = INSTR_XOR_C,
        .x86_asm = "xor r,i",
        .x86_size = 7,
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_NONE,
        .immediate_mask = UINT32_MAX,
        .group = INSTR_XOR_C,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = false,
        .has_src = false,
        .has_dst = true,
};
 
 
static const instr_template tpl_target = {
        .type = INSTR_TARGET,
        .x86_asm = "cmovz esi, edi",
        .x86_size = 5, /* test, cmovz */
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_P015,
        .immediate_mask = 0,
        .group = INSTR_TARGET,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = false,
        .has_src = false,
        .has_dst = false,
};
 
static const instr_template tpl_branch = {
        .type = INSTR_BRANCH,
        .x86_asm = "jz target",
        .x86_size = 10, /* or, test, jz */
        .latency = 1,
        .uop1 = PORT_P015,
        .uop2 = PORT_P015,
        .immediate_mask = BRANCH_MASK,
        .group = INSTR_BRANCH,
        .imm_can_be_0 = false,
        .distinct_dst = true,
        .op_par_src = false,
        .has_src = false,
        .has_dst = false,
};
 
static const instr_template* instr_lookup[] = {
        &tpl_ror_c,
        &tpl_xor_c,
        &tpl_add_c,
        &tpl_add_c,
        &tpl_sub_r,
        &tpl_xor_r,
        &tpl_xor_c,
        &tpl_add_rs,
};
 
static const instr_template* wide_mul_lookup[] = {
        &tpl_smulh_r,
        &tpl_umulh_r
};
 
static const instr_template* mul_lookup = &tpl_mul_r;
static const instr_template* target_lookup = &tpl_target;
static const instr_template* branch_lookup = &tpl_branch;
 
static const program_item item_mul = {
        .templates = &mul_lookup,
        .mask0 = 0,
        .mask1 = 0,
        .duplicates = true
};
 
static const program_item item_target = {
        .templates = &target_lookup,
        .mask0 = 0,
        .mask1 = 0,
        .duplicates = true
};
 
static const program_item item_branch = {
        .templates = &branch_lookup,
        .mask0 = 0,
        .mask1 = 0,
        .duplicates = true
};
 
static const program_item item_wide_mul = {
        .templates = wide_mul_lookup,
        .mask0 = 1,
        .mask1 = 1,
        .duplicates = true
};
 
static const program_item item_any = {
        .templates = instr_lookup,
        .mask0 = 7,
        .mask1 = 3, /* instructions that don't need a src register */
        .duplicates = false
};
 
static const program_item* program_layout[] = {
        &item_mul,
        &item_target,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_wide_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_branch,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_wide_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
        &item_mul,
        &item_any,
        &item_any,
};
 
static const instr_template* select_template(generator_ctx* ctx, instr_type last_instr, int attempt) {
        const program_item* item = program_layout[ctx->sub_cycle % 36];
        const instr_template* tpl;
        do {
                int index = item->mask0 ? hashx_siphash_rng_u8(&ctx->gen) & (attempt > 0 ? item->mask1 : item->mask0) : 0;
                tpl = item->templates[index];
        } while (!item->duplicates && tpl->group == last_instr);
        return tpl;
}
 
static uint32_t branch_mask(siphash_rng* gen) {
        uint32_t mask = 0;
        int popcnt = 0;
        while (popcnt < LOG2_BRANCH_PROB) {
                int bit = hashx_siphash_rng_u8(gen) % 32;
                uint32_t bitmask = 1U << bit;
                if (!(mask & bitmask)) {
                        mask |= bitmask;
                        popcnt++;
                }
        }
        return mask;
}
 
static void instr_from_template(const instr_template* tpl, siphash_rng* gen, instruction* instr) {
        instr->opcode = tpl->type;
        if (tpl->immediate_mask) {
                if (tpl->immediate_mask == BRANCH_MASK) {
                        instr->imm32 = branch_mask(gen);
                }
                else do {
                        instr->imm32 = hashx_siphash_rng_u32(gen) & tpl->immediate_mask;
                } while (instr->imm32 == 0 && !tpl->imm_can_be_0);
        }
        if (!tpl->op_par_src) {
                if (tpl->distinct_dst) {
                        instr->op_par = UINT32_MAX;
                }
                else {
                        instr->op_par = hashx_siphash_rng_u32(gen);
                }
        }
        if (!tpl->has_src) {
                instr->src = -1;
        }
        if (!tpl->has_dst) {
                instr->dst = -1;
        }
}
 
static bool select_register(int available_regs[8], int regs_count, siphash_rng* gen, int* reg_out) {
        if (regs_count == 0)
                return false;
 
        int index;
 
        if (regs_count > 1) {
                index = hashx_siphash_rng_u32(gen) % regs_count;
        }
        else {
                index = 0;
        }
        *reg_out = available_regs[index];
        return true;
}
 
static bool select_destination(const instr_template* tpl, instruction* instr, generator_ctx* ctx, int cycle) {
        int available_regs[8];
        int regs_count = 0;
        /* Conditions for the destination register:
        // * value must be ready at the required cycle
        // * cannot be the same as the source register unless the instruction allows it
        //   - this avoids optimizable instructions such as "xor r, r" or "sub r, r"
        // * register cannot be multiplied twice in a row unless chain_mul is true
        //   - this avoids accumulation of trailing zeroes in registers due to excessive multiplication
        //   - allowChainedMul is set to true if an attempt to find source/destination registers failed (this is quite rare, but prevents a catastrophic failure of the generator)
        // * either the last instruction applied to the register or its source must be different than this instruction
        //   - this avoids optimizable instruction sequences such as "xor r1, r2; xor r1, r2" or "ror r, C1; ror r, C2" or "add r, C1; add r, C2"
        // * register r5 cannot be the destination of the IADD_RS instruction (limitation of the x86 lea instruction) */
        for (int i = 0; i < 8; ++i) {
                bool available = ctx->registers[i].latency <= cycle;
                available &= ((!tpl->distinct_dst) | (i != instr->src));
                available &= (ctx->chain_mul | (tpl->group != INSTR_MUL_R) | (ctx->registers[i].last_op != INSTR_MUL_R));
                available &= ((ctx->registers[i].last_op != tpl->group) | (ctx->registers[i].last_op_par != instr->op_par));
                available &= ((instr->opcode != INSTR_ADD_RS) | (i != REGISTER_NEEDS_DISPLACEMENT));
                available_regs[regs_count] = available ? i : 0;
                regs_count += available;
        }
        return select_register(available_regs, regs_count, &ctx->gen, &instr->dst);
}
 
static bool select_source(const instr_template* tpl, instruction* instr, generator_ctx* ctx, int cycle) {
        int available_regs[8];
        int regs_count = 0;
        /* all registers that are ready at the cycle */
        for (int i = 0; i < 8; ++i) {
                if (ctx->registers[i].latency <= cycle)
                        available_regs[regs_count++] = i;
        }
        /* if there are only 2 available registers for ADD_RS and one of them is r5, select it as the source because it cannot be the destination */
        if (regs_count == 2 && instr->opcode == INSTR_ADD_RS) {
                if (available_regs[0] == REGISTER_NEEDS_DISPLACEMENT || available_regs[1] == REGISTER_NEEDS_DISPLACEMENT) {
                        instr->op_par = instr->src = REGISTER_NEEDS_DISPLACEMENT;
                        return true;
                }
        }
        if (select_register(available_regs, regs_count, &ctx->gen, &instr->src)) {
                if (tpl->op_par_src)
                        instr->op_par = instr->src;
                return true;
        }
        return false;
}
 
static int schedule_uop(execution_port uop, generator_ctx* ctx, int cycle, bool commit) {
        /* The scheduling here is done optimistically by checking port availability in order P5 -> P0 -> P1 to not overload
           port P1 (multiplication) by instructions that can go to any port. */
        for (; cycle < PORT_MAP_SIZE; ++cycle) {
                if ((uop & PORT_P5) && !ctx->ports[cycle][2]) {
                        if (commit) {
                                ctx->ports[cycle][2] = uop;
                        }
                        TRACE_PRINT("%s scheduled to port P5 at cycle %i (commit = %i)\n", execution_port_names[uop], cycle, commit);
                        return cycle;
                }
                if ((uop & PORT_P0) && !ctx->ports[cycle][0]) {
                        if (commit) {
                                ctx->ports[cycle][0] = uop;
                        }
                        TRACE_PRINT("%s scheduled to port P0 at cycle %i (commit = %i)\n", execution_port_names[uop], cycle, commit);
                        return cycle;
                }
                if ((uop & PORT_P1) != 0 && !ctx->ports[cycle][1]) {
                        if (commit) {
                                ctx->ports[cycle][1] = uop;
                        }
                        TRACE_PRINT("%s scheduled to port P1 at cycle %i (commit = %i)\n", execution_port_names[uop], cycle, commit);
                        return cycle;
                }
        }
        return -1;
}
 
static int schedule_instr(const instr_template* tpl, generator_ctx* ctx, bool commit) {
        if (tpl->uop2 == PORT_NONE) {
                /* this instruction has only one uOP */
                return schedule_uop(tpl->uop1, ctx, ctx->cycle, commit);
        }
        else {
                /* instructions with 2 uOPs are scheduled conservatively by requiring both uOPs to execute in the same cycle */
                for (int cycle = ctx->cycle; cycle < PORT_MAP_SIZE; ++cycle) {
 
                        int cycle1 = schedule_uop(tpl->uop1, ctx, cycle, false);
                        int cycle2 = schedule_uop(tpl->uop2, ctx, cycle, false);
 
                        if (cycle1 >= 0 && cycle1 == cycle2) {
                                if (commit) {
                                        schedule_uop(tpl->uop1, ctx, cycle, true);
                                        schedule_uop(tpl->uop2, ctx, cycle, true);
                                }
                                return cycle1;
                        }
                }
        }
 
        return -1;
}
 
static void print_registers(const generator_ctx* ctx) {
        for (int i = 0; i < 8; ++i) {
                printf("   R%i = %i\n", i, ctx->registers[i].latency);
        }
}
 
bool hashx_program_generate(const siphash_state* key, hashx_program* program) {
        generator_ctx ctx = {
                .cycle = 0,
                .sub_cycle = 0, /* 3 sub-cycles = 1 cycle */
                .mul_count = 0,
                .chain_mul = false,
                .latency = 0,
                .ports = {{ 0 }}
        };
        hashx_siphash_rng_init(&ctx.gen, key);
#ifdef HASHX_RNG_CALLBACK
        ctx.gen.callback = program->rng_callback;
        ctx.gen.callback_user_data = program->rng_callback_user_data;
#endif
        for (int i = 0; i < 8; ++i) {
                ctx.registers[i].last_op = -1;
                ctx.registers[i].latency = 0;
                ctx.registers[i].last_op_par = (uint32_t)-1;
        }
        program->code_size = 0;
 
        int attempt = 0;
        instr_type last_instr = -1;
#ifdef HASHX_PROGRAM_STATS
        program->x86_size = 0;
#endif
 
        while (program->code_size < HASHX_PROGRAM_MAX_SIZE) {
                instruction* instr = &program->code[program->code_size];
                TRACE_PRINT("CYCLE: %i/%i\n", ctx.sub_cycle, ctx.cycle);
 
                /* select an instruction template */
                const instr_template* tpl = select_template(&ctx, last_instr, attempt);
                last_instr = tpl->group;
 
                TRACE_PRINT("Template: %s\n", tpl->x86_asm);
 
                instr_from_template(tpl, &ctx.gen, instr);
 
                /* calculate the earliest cycle when this instruction (all of its uOPs) can be scheduled for execution */
                int scheduleCycle = schedule_instr(tpl, &ctx, false);
                if (scheduleCycle < 0) {
                        TRACE_PRINT("Unable to map operation '%s' to execution port (cycle %i)\n", tpl->x86_asm, ctx.cycle);
                        /* __debugbreak(); */
                        break;
                }
 
                ctx.chain_mul = attempt > 0;
 
                /* find a source register (if applicable) that will be ready when this instruction executes */
                if (tpl->has_src) {
                        if (!select_source(tpl, instr, &ctx, scheduleCycle)) {
                                TRACE_PRINT("; src STALL (attempt %i)\n", attempt);
                                if (attempt++ < MAX_RETRIES) {
                                        continue;
                                }
                                if (TRACE) {
                                        printf("; select_source FAILED at cycle %i\n", ctx.cycle);
                                        print_registers(&ctx);
                                        /* __debugbreak(); */
                                }
                                ctx.sub_cycle += 3;
                                ctx.cycle = ctx.sub_cycle / 3;
                                attempt = 0;
                                continue;
                        }
                        TRACE_PRINT("; src = r%i\n", instr->src);
                }
 
                /* find a destination register that will be ready when this instruction executes */
                if (tpl->has_dst) {
                        if (!select_destination(tpl, instr, &ctx, scheduleCycle)) {
                                TRACE_PRINT("; dst STALL (attempt %i)\n", attempt);
                                if (attempt++ < MAX_RETRIES) {
                                        continue;
                                }
                                if (TRACE) {
                                        printf("; select_destination FAILED at cycle %i\n", ctx.cycle);
                                        print_registers(&ctx);
                                        /* __debugbreak(); */
                                }
                                ctx.sub_cycle += 3;
                                ctx.cycle = ctx.sub_cycle / 3;
                                attempt = 0;
                                continue;
                        }
                        TRACE_PRINT("; dst = r%i\n", instr->dst);
                }
                attempt = 0;
 
                /* recalculate when the instruction can be scheduled for execution based on operand availability */
                scheduleCycle = schedule_instr(tpl, &ctx, true);
 
                if (scheduleCycle < 0) {
                        TRACE_PRINT("Unable to map operation '%s' to execution port (cycle %i)\n", tpl->x86_asm, ctx.cycle);
                        break;
                }
 
                /* terminating condition */
                if (scheduleCycle >= TARGET_CYCLE) {
                        break;
                }
 
                if (tpl->has_dst) {
                        register_info* ri = &ctx.registers[instr->dst];
                        int retireCycle = scheduleCycle + tpl->latency;
                        ri->latency = retireCycle;
                        ri->last_op = tpl->group;
                        ri->last_op_par = instr->op_par;
                        ctx.latency = MAX(retireCycle, ctx.latency);
                        TRACE_PRINT("; RETIRED at cycle %i\n", retireCycle);
                }
 
                program->code_size++;
#ifdef HASHX_PROGRAM_STATS
                program->x86_size += tpl->x86_size;
#endif
 
                ctx.mul_count += is_mul(instr->opcode);
 
                ++ctx.sub_cycle;
                ctx.sub_cycle += (tpl->uop2 != PORT_NONE);
                ctx.cycle = ctx.sub_cycle / 3;
        }
 
#ifdef HASHX_PROGRAM_STATS
        memset(program->asic_latencies, 0, sizeof(program->asic_latencies));
 
        program->counter = ctx.gen.counter;
        program->wide_mul_count = 0;
        program->mul_count = ctx.mul_count;
 
        /* Calculate ASIC latency:
           Assumes 1 cycle latency for all operations and unlimited parallelization. */
        for (size_t i = 0; i < program->code_size; ++i) {
                instruction* instr = &program->code[i];
                if (instr->dst < 0)
                        continue;
                int last_dst = program->asic_latencies[instr->dst] + 1;
                int lat_src = instr->dst != instr->src ? program->asic_latencies[instr->src] + 1 : 0;
                program->asic_latencies[instr->dst] = MAX(last_dst, lat_src);
                program->wide_mul_count += is_wide_mul(instr->opcode);
        }
 
        program->asic_latency = 0;
        program->cpu_latency = 0;
        for (int i = 0; i < 8; ++i) {
                program->asic_latency = MAX(program->asic_latency, program->asic_latencies[i]);
                program->cpu_latencies[i] = ctx.registers[i].latency;
                program->cpu_latency = MAX(program->cpu_latency, program->cpu_latencies[i]);
        }
 
        program->ipc = program->code_size / (double)program->cpu_latency;
        program->branch_count = 0;
        memset(program->branches, 0, sizeof(program->branches));
 
        if (TRACE) {
                printf("; ALU port utilization:\n");
                printf("; (* = in use, _ = idle)\n");
                for (int i = 0; i < PORT_MAP_SIZE; ++i) {
                        printf("; %3i ", i);
                        for (int j = 0; j < NUM_PORTS; ++j) {
                                printf("%c", (ctx.ports[i][j] ? '*' : '_'));
                        }
                        printf("\n");
                }
        }
#endif
 
        /* reject programs that don't meet the uniform complexity requirements */
        /* this happens in less than 1 seed out of 10000 */
        return
                (program->code_size == REQUIREMENT_SIZE) &&
                (ctx.mul_count == REQUIREMENT_MUL_COUNT) &&
                (ctx.latency == REQUIREMENT_LATENCY - 1); /* cycles are numbered from 0 */
}
 
static const char* x86_reg_map[] = { "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15" };
 
void hashx_program_asm_x86(const hashx_program* program) {
        size_t target = 0;
        for (size_t i = 0; i < program->code_size; ++i) {
                const instruction* instr = &program->code[i];
                switch (instr->opcode)
                {
                case INSTR_SUB_R:
                        printf("sub %s, %s\n", x86_reg_map[instr->dst], x86_reg_map[instr->src]);
                        break;
                case INSTR_XOR_R:
                        printf("xor %s, %s\n", x86_reg_map[instr->dst], x86_reg_map[instr->src]);
                        break;
                case INSTR_ADD_RS:
                        printf("lea %s, [%s+%s*%u]\n", x86_reg_map[instr->dst], x86_reg_map[instr->dst], x86_reg_map[instr->src], 1 << instr->imm32);
                        break;
                case INSTR_MUL_R:
                        printf("imul %s, %s\n", x86_reg_map[instr->dst], x86_reg_map[instr->src]);
                        break;
                case INSTR_ROR_C:
                        printf("ror %s, %u\n", x86_reg_map[instr->dst], instr->imm32);
                        break;
                case INSTR_ADD_C:
                        printf("add %s, %i\n", x86_reg_map[instr->dst], instr->imm32);
                        break;
                case INSTR_XOR_C:
                        printf("xor %s, %i\n", x86_reg_map[instr->dst], instr->imm32);
                        break;
                case INSTR_UMULH_R:
                        printf("mov rax, %s\n", x86_reg_map[instr->dst]);
                        printf("mul %s\n", x86_reg_map[instr->src]);
                        printf("mov %s, rdx\n", x86_reg_map[instr->dst]);
                        break;
                case INSTR_SMULH_R:
                        printf("mov rax, %s\n", x86_reg_map[instr->dst]);
                        printf("imul %s\n", x86_reg_map[instr->src]);
                        printf("mov %s, rdx\n", x86_reg_map[instr->dst]);
                        break;
                case INSTR_TARGET:
                        printf("test edi, edi\n");
                        printf("target_%i: cmovz esi, edi\n", (int)i);
                        target = i;
                        break;
                case INSTR_BRANCH:
                        printf("or edx, esi\n");
                        printf("test edx, %i\n", instr->imm32);
                        printf("jz target_%i\n", (int)target);
                        break;
                default:
                        UNREACHABLE;
                }
        }
}