kit

strength_reduce_test.c (9658B)

---

 /* strength_reduce_test — asserts the -O0 semantic peephole (src/cg/fold.c)
  * turns multiply / unsigned-divide / unsigned-remainder by a power-of-two
  * constant into a shift / and, AND that the shift/and is emitted in its
  * immediate-operand form (no scratch register spent materializing the count).
  *
  * Each case builds a tiny
  *     i64 f(i64 x) { return x <op> <imm>; }
  * through the public CG API, emits an ELF object, and disassembles its .text.
  *
  * Two layers of assertion:
  *   1. The multiply/divide/remainder instruction disappears for power-of-two
  *      operands and survives for non-power-of-two (and for signed division,
  *      which is deliberately left to -O1+). Checked on mnemonic substrings
  *      ("mul"/"div"/"rem"), robust to per-arch aliasing.
  *   2. The resulting shift/and carries an immediate operand (x64 "$imm",
  *      aa64 "#imm", rv64 i-suffixed mnemonic) rather than a materialized
  *      register — the NativeDirectTarget imm_legal pass-through (Piece A) plus
  *      the aa64 immediate shift/bitmask encodings (Piece B).
  *
  * Run by: make test-cg-api
  */
 
 #include <kit/cg.h>
 #include <kit/disasm.h>
 #include <kit/frontend.h>
 #include <kit/object.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <string.h>
 
 #include "lib/kit_unit.h"
 
 static KitUnit g_u;
 #define EXPECT(cond, ...) CU_EXPECT(&g_u, cond, __VA_ARGS__)
 
 typedef struct EmitCtx {
   KitCgIntBinOp op;
   int64_t imm;
   KitObjBuilder* ob;
 } EmitCtx;
 
 /* Frontend callback: build `i64 f(i64 x) { return x op imm; }` into ctx->ob. */
 static KitStatus emit_binop_fn(KitCompiler* c, void* user) {
   EmitCtx* ctx = (EmitCtx*)user;
   KitCg* cg = NULL;
   KitCgBuiltinTypes bi;
   KitCgTypeId i64_ty;
   KitCgFuncParam param_desc;
   KitCgFuncResult sig_result;
   KitCgFuncSig sig;
   KitCgDecl decl;
   KitCgSym sym;
   KitCgLocalAttrs attrs;
   KitCgLocal param;
   KitCodeOptions opts;
 
   if (kit_obj_builder_new(c, &ctx->ob) != KIT_OK) return KIT_ERR;
   if (kit_cg_new(c, &cg) != KIT_OK || !cg) return KIT_ERR;
   memset(&opts, 0, sizeof opts);
   opts.opt_level = 0; /* the -O0 peephole is the subject under test */
   if (kit_cg_begin(cg, ctx->ob, &opts) != KIT_OK) return KIT_ERR;
 
   bi = kit_cg_builtin_types(c);
   i64_ty = bi.id[KIT_CG_BUILTIN_I64];
 
   memset(&param_desc, 0, sizeof param_desc);
   param_desc.type = i64_ty;
   memset(&sig_result, 0, sizeof sig_result);
   sig_result.type = i64_ty;
   memset(&sig, 0, sizeof sig);
   sig.params = &param_desc;
   sig.nparams = 1;
   sig.result = sig_result;
   sig.call_conv = KIT_CG_CC_TARGET_C;
 
   memset(&decl, 0, sizeof decl);
   decl.kind = KIT_CG_DECL_FUNC;
   decl.linkage_name = kit_sym_intern(c, kit_slice_cstr("f"));
   decl.display_name = decl.linkage_name;
   decl.type = kit_cg_type_func(c, sig);
   decl.sym.bind = KIT_SB_GLOBAL;
   decl.sym.visibility = KIT_CG_VIS_DEFAULT;
   sym = kit_cg_decl(cg, decl);
   if (sym == KIT_CG_SYM_NONE) return KIT_ERR;
 
   kit_cg_func_begin(cg, sym);
   memset(&attrs, 0, sizeof attrs);
   attrs.name = kit_sym_intern(c, KIT_SLICE_LIT("x"));
   param = kit_cg_param(cg, 0, i64_ty, attrs);
   if (param == KIT_CG_LOCAL_NONE) return KIT_ERR;
 
   /* return x <op> imm; */
   kit_cg_push_local(cg, param);
   kit_cg_load(cg, (KitCgMemAccess){.type = i64_ty,
                                    .align = kit_cg_type_align(c, i64_ty)});
   kit_cg_push_int(cg, (uint64_t)ctx->imm, i64_ty);
   kit_cg_int_binop(cg, ctx->op, KIT_CG_INTOP_NONE);
   kit_cg_ret(cg);
   kit_cg_func_end(cg);
 
   if (kit_cg_finish(cg, NULL) != KIT_OK) return KIT_ERR;
   if (kit_cg_detach(cg) != KIT_OK) return KIT_ERR;
   kit_cg_free(cg);
   return KIT_OK;
 }
 
 typedef struct DisInsn {
   char mnem[16];
   char ops[64];
 } DisInsn;
 
 static void slice_to_buf(KitSlice s, char* buf, size_t cap) {
   size_t n = s.len < cap - 1 ? s.len : cap - 1;
   if (s.s && n) memcpy(buf, s.s, n);
   buf[n] = '\0';
 }
 
 /* Build the op and disassemble its .text into `out` (up to `cap` insns).
  * Returns the instruction count, or -1 on harness failure. */
 static int op_disasm(KitArchKind arch, KitCgIntBinOp op, int64_t imm,
                      DisInsn* out, int cap) {
   KitTargetSpec target = kit_unit_target(arch, KIT_OS_LINUX, KIT_OBJ_ELF);
   KitTargetOptions target_opts;
   KitTarget* kt = NULL;
   KitCompiler* c = NULL;
   EmitCtx ctx;
   KitWriter* writer = NULL;
   KitObjFile* file = NULL;
   KitSlice bytes;
   KitObjSection text_sec;
   const uint8_t* data = NULL;
   size_t len = 0;
   KitDisasmContext dc;
   KitDisasmIter* it = NULL;
   KitInsn insn;
   int result = -1;
   int n = 0;
 
   memset(&ctx, 0, sizeof ctx);
   ctx.op = op;
   ctx.imm = imm;
 
   memset(&target_opts, 0, sizeof target_opts);
   target_opts.spec = target;
   if (kit_target_new(&g_u.ctx, &target_opts, &kt) != KIT_OK || !kt) return -1;
   if (kit_compiler_new(kt, &g_u.ctx, &c) != KIT_OK || !c) goto done;
   if (kit_frontend_run(c, emit_binop_fn, &ctx) != KIT_OK) goto done;
   if (kit_writer_mem(&g_u.heap, &writer) != KIT_OK || !writer) goto done;
   if (kit_obj_builder_emit(ctx.ob, writer) != KIT_OK) goto done;
   bytes.data = kit_writer_mem_bytes(writer, &len);
   bytes.len = len;
   if (kit_obj_open(&g_u.ctx, KIT_SLICE_LIT("<sr-test>"), &bytes, &file) !=
       KIT_OK)
     goto done;
   if (kit_obj_section_by_name(file, KIT_SLICE_LIT(".text"), &text_sec) !=
       KIT_OK)
     goto done;
   if (kit_obj_section_data(file, text_sec, &data, &len) != KIT_OK) goto done;
 
   memset(&dc, 0, sizeof dc);
   dc.target = kt;
   dc.context = g_u.ctx;
   if (kit_disasm_iter_new(&dc, data, len, 0, file, &it) != KIT_OK || !it)
     goto done;
   while (n < cap && kit_disasm_iter_next(it, &insn) == KIT_ITER_ITEM) {
     slice_to_buf(insn.mnemonic, out[n].mnem, sizeof out[n].mnem);
     slice_to_buf(insn.operands, out[n].ops, sizeof out[n].ops);
     ++n;
   }
   result = n;
 
 done:
   if (it) kit_disasm_iter_free(it);
   if (file) kit_obj_free(file);
   if (writer) kit_writer_close(writer);
   if (ctx.ob) kit_obj_builder_free(ctx.ob);
   kit_compiler_free(c);
   kit_target_free(kt);
   return result;
 }
 
 /* 1 if any instruction's mnemonic contains `mnem`. */
 static int have_mnem(const DisInsn* in, int n, const char* mnem) {
   for (int i = 0; i < n; ++i)
     if (strstr(in[i].mnem, mnem)) return 1;
   return 0;
 }
 
 /* 1 if the first instruction whose mnemonic contains `mnem` has `marker` in its
  * operands (an empty marker matches any). This is how we tell an immediate
  * operand form (x64 "$", aa64 "#") from a register form, and — via the
  * i-suffixed RISC-V mnemonics — picks out slli/srli/andi over sll/srl/and. */
 static int imm_form(const DisInsn* in, int n, const char* mnem,
                     const char* marker) {
   for (int i = 0; i < n; ++i)
     if (strstr(in[i].mnem, mnem)) return strstr(in[i].ops, marker) != NULL;
   return 0;
 }
 
 typedef struct ArchExpect {
   KitArchKind arch;
   const char* name;
   const char* shl_mnem; /* immediate shift-left mnemonic (x*2^k) */
   const char* shr_mnem; /* immediate logical shift-right (x u/ 2^k) */
   const char* and_mnem; /* immediate bitwise-and (x u% 2^k) */
   const char* mark; /* operand marker for an immediate ("" if in mnemonic) */
 } ArchExpect;
 
 static void check_arch(const ArchExpect* ex) {
   const char* an = ex->name;
   DisInsn buf[128];
   int n;
 
   /* --- multiply --- */
   n = op_disasm(ex->arch, KIT_CG_INT_MUL, 8, buf, 128);
   EXPECT(n > 0, "[%s] mul8 disasm failed", an);
   EXPECT(!have_mnem(buf, n, "mul"),
          "[%s] x * 8 should strength-reduce to a shift (no 'mul')", an);
   EXPECT(imm_form(buf, n, ex->shl_mnem, ex->mark),
          "[%s] x * 8 should use the immediate shift form", an);
 
   n = op_disasm(ex->arch, KIT_CG_INT_MUL, 7, buf, 128);
   EXPECT(n > 0 && have_mnem(buf, n, "mul"), "[%s] x * 7 must stay a multiply",
          an);
 
   /* --- unsigned divide --- */
   n = op_disasm(ex->arch, KIT_CG_INT_UDIV, 8, buf, 128);
   EXPECT(n > 0, "[%s] udiv8 disasm failed", an);
   EXPECT(!have_mnem(buf, n, "div"),
          "[%s] x u/ 8 should strength-reduce to a shift (no 'div')", an);
   EXPECT(imm_form(buf, n, ex->shr_mnem, ex->mark),
          "[%s] x u/ 8 should use the immediate shift form", an);
 
   n = op_disasm(ex->arch, KIT_CG_INT_UDIV, 7, buf, 128);
   EXPECT(n > 0 && have_mnem(buf, n, "div"), "[%s] x u/ 7 must stay a divide",
          an);
 
   /* --- unsigned remainder --- */
   n = op_disasm(ex->arch, KIT_CG_INT_UREM, 8, buf, 128);
   EXPECT(n > 0, "[%s] urem8 disasm failed", an);
   EXPECT(!have_mnem(buf, n, "div") && !have_mnem(buf, n, "rem"),
          "[%s] x u%% 8 should strength-reduce to an and (no 'div'/'rem')", an);
   EXPECT(imm_form(buf, n, ex->and_mnem, ex->mark),
          "[%s] x u%% 8 should use the immediate and form", an);
 
   n = op_disasm(ex->arch, KIT_CG_INT_UREM, 7, buf, 128);
   EXPECT(n > 0 && (have_mnem(buf, n, "div") || have_mnem(buf, n, "rem")),
          "[%s] x u%% 7 must stay a divide/remainder", an);
 
   /* --- signed divide: deliberately left for the optimizer --- */
   n = op_disasm(ex->arch, KIT_CG_INT_SDIV, 8, buf, 128);
   EXPECT(n > 0 && have_mnem(buf, n, "div"),
          "[%s] signed x / 8 is left as a divide at -O0", an);
 }
 
 int main(void) {
   /* x64 AT&T immediates read "$N"; aa64 reads "#N"; rv64 folds the immediate
    * into the mnemonic (slli/srli/andi), so its operand marker is empty. */
   static const ArchExpect arches[] = {
       {KIT_ARCH_X86_64, "x86_64", "shl", "shr", "and", "$"},
       {KIT_ARCH_ARM_64, "aarch64", "lsl", "lsr", "and", "#"},
       {KIT_ARCH_RV64, "riscv64", "slli", "srli", "andi", ""},
   };
   kit_unit_init(&g_u);
   g_u.ctx.now = -1;
   for (size_t i = 0; i < sizeof arches / sizeof arches[0]; ++i)
     check_arch(&arches[i]);
   kit_unit_summary(&g_u, "strength_reduce_test");
   return kit_unit_status(&g_u);
 }