kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

strength_reduce_test.c (9619B)

      1 /* strength_reduce_test — asserts the -O0 semantic peephole (src/cg/fold.c)
      2  * turns multiply / unsigned-divide / unsigned-remainder by a power-of-two
      3  * constant into a shift / and, AND that the shift/and is emitted in its
      4  * immediate-operand form (no scratch register spent materializing the count).
      5  *
      6  * Each case builds a tiny
      7  *     i64 f(i64 x) { return x <op> <imm>; }
      8  * through the public CG API, emits an ELF object, and disassembles its .text.
      9  *
     10  * Two layers of assertion:
     11  *   1. The multiply/divide/remainder instruction disappears for power-of-two
     12  *      operands and survives for non-power-of-two (and for signed division,
     13  *      which is deliberately left to -O1+). Checked on mnemonic substrings
     14  *      ("mul"/"div"/"rem"), robust to per-arch aliasing.
     15  *   2. The resulting shift/and carries an immediate operand (x64 "$imm",
     16  *      aa64 "#imm", rv64 i-suffixed mnemonic) rather than a materialized
     17  *      register — the NativeDirectTarget imm_legal pass-through (Piece A) plus
     18  *      the aa64 immediate shift/bitmask encodings (Piece B).
     19  *
     20  * Run by: make test-cg-api
     21  */
     22 
     23 #include <kit/cg.h>
     24 #include <kit/disasm.h>
     25 #include <kit/frontend.h>
     26 #include <kit/object.h>
     27 #include <stdint.h>
     28 #include <stdio.h>
     29 #include <string.h>
     30 
     31 #include "lib/kit_unit.h"
     32 
     33 static KitUnit g_u;
     34 #define EXPECT(cond, ...) CU_EXPECT(&g_u, cond, __VA_ARGS__)
     35 
     36 typedef struct EmitCtx {
     37   KitCgIntBinOp op;
     38   int64_t imm;
     39   KitObjBuilder* ob;
     40 } EmitCtx;
     41 
     42 /* Frontend callback: build `i64 f(i64 x) { return x op imm; }` into ctx->ob. */
     43 static KitStatus emit_binop_fn(KitCompiler* c, void* user) {
     44   EmitCtx* ctx = (EmitCtx*)user;
     45   KitCg* cg = NULL;
     46   KitCgTypeId i64_ty;
     47   KitCgFuncParam param_desc;
     48   KitCgFuncResult sig_result;
     49   KitCgFuncSig sig;
     50   KitCgDecl decl;
     51   KitCgSym sym;
     52   KitCgLocalAttrs attrs;
     53   KitCgLocal param;
     54   KitCodeOptions opts;
     55 
     56   if (kit_obj_builder_new(c, &ctx->ob) != KIT_OK) return KIT_ERR;
     57   if (kit_cg_new(c, &cg) != KIT_OK || !cg) return KIT_ERR;
     58   memset(&opts, 0, sizeof opts);
     59   opts.opt_level = 0; /* the -O0 peephole is the subject under test */
     60   if (kit_cg_begin(cg, ctx->ob, &opts) != KIT_OK) return KIT_ERR;
     61 
     62   i64_ty = kit_cg_type_builtin(c, KIT_CG_BUILTIN_I64);
     63 
     64   memset(&param_desc, 0, sizeof param_desc);
     65   param_desc.type = i64_ty;
     66   memset(&sig_result, 0, sizeof sig_result);
     67   sig_result.type = i64_ty;
     68   memset(&sig, 0, sizeof sig);
     69   sig.params = &param_desc;
     70   sig.nparams = 1;
     71   sig.result = sig_result;
     72   sig.call_conv = KIT_CG_CC_TARGET_C;
     73 
     74   memset(&decl, 0, sizeof decl);
     75   decl.kind = KIT_CG_DECL_FUNC;
     76   decl.linkage_name = kit_sym_intern(c, kit_slice_cstr("f"));
     77   decl.display_name = decl.linkage_name;
     78   decl.type = kit_cg_type_func(c, sig);
     79   decl.sym.bind = KIT_SB_GLOBAL;
     80   decl.sym.visibility = KIT_CG_VIS_DEFAULT;
     81   sym = kit_cg_decl(cg, decl);
     82   if (sym == KIT_CG_SYM_NONE) return KIT_ERR;
     83 
     84   kit_cg_func_begin(cg, sym);
     85   memset(&attrs, 0, sizeof attrs);
     86   attrs.name = kit_sym_intern(c, KIT_SLICE_LIT("x"));
     87   param = kit_cg_param(cg, 0, i64_ty, attrs);
     88   if (param == KIT_CG_LOCAL_NONE) return KIT_ERR;
     89 
     90   /* return x <op> imm; */
     91   kit_cg_push_local(cg, param);
     92   kit_cg_load(cg, (KitCgMemAccess){.type = i64_ty,
     93                                    .align = kit_cg_type_align(c, i64_ty)});
     94   kit_cg_push_int(cg, (uint64_t)ctx->imm, i64_ty);
     95   kit_cg_int_binop(cg, ctx->op, KIT_CG_INTOP_NONE);
     96   kit_cg_ret(cg);
     97   kit_cg_func_end(cg);
     98 
     99   if (kit_cg_finish(cg, NULL) != KIT_OK) return KIT_ERR;
    100   if (kit_cg_detach(cg) != KIT_OK) return KIT_ERR;
    101   kit_cg_free(cg);
    102   return KIT_OK;
    103 }
    104 
    105 typedef struct DisInsn {
    106   char mnem[16];
    107   char ops[64];
    108 } DisInsn;
    109 
    110 static void slice_to_buf(KitSlice s, char* buf, size_t cap) {
    111   size_t n = s.len < cap - 1 ? s.len : cap - 1;
    112   if (s.s && n) memcpy(buf, s.s, n);
    113   buf[n] = '\0';
    114 }
    115 
    116 /* Build the op and disassemble its .text into `out` (up to `cap` insns).
    117  * Returns the instruction count, or -1 on harness failure. */
    118 static int op_disasm(KitArchKind arch, KitCgIntBinOp op, int64_t imm,
    119                      DisInsn* out, int cap) {
    120   KitTargetSpec target = kit_unit_target(arch, KIT_OS_LINUX, KIT_OBJ_ELF);
    121   KitTargetOptions target_opts;
    122   KitTarget* kt = NULL;
    123   KitCompiler* c = NULL;
    124   EmitCtx ctx;
    125   KitWriter* writer = NULL;
    126   KitObjFile* file = NULL;
    127   KitSlice bytes;
    128   KitObjSection text_sec;
    129   const uint8_t* data = NULL;
    130   size_t len = 0;
    131   KitDisasmContext dc;
    132   KitDisasmIter* it = NULL;
    133   KitInsn insn;
    134   int result = -1;
    135   int n = 0;
    136 
    137   memset(&ctx, 0, sizeof ctx);
    138   ctx.op = op;
    139   ctx.imm = imm;
    140 
    141   memset(&target_opts, 0, sizeof target_opts);
    142   target_opts.spec = target;
    143   if (kit_target_new(&g_u.ctx, &target_opts, &kt) != KIT_OK || !kt) return -1;
    144   if (kit_compiler_new(kt, &g_u.ctx, &c) != KIT_OK || !c) goto done;
    145   if (kit_frontend_run(c, emit_binop_fn, &ctx) != KIT_OK) goto done;
    146   if (kit_writer_mem(&g_u.heap, &writer) != KIT_OK || !writer) goto done;
    147   if (kit_obj_builder_emit(ctx.ob, writer) != KIT_OK) goto done;
    148   bytes.data = kit_writer_mem_bytes(writer, &len);
    149   bytes.len = len;
    150   if (kit_obj_open(&g_u.ctx, KIT_SLICE_LIT("<sr-test>"), &bytes, &file) !=
    151       KIT_OK)
    152     goto done;
    153   if (kit_obj_section_by_name(file, KIT_SLICE_LIT(".text"), &text_sec) !=
    154       KIT_OK)
    155     goto done;
    156   if (kit_obj_section_data(file, text_sec, &data, &len) != KIT_OK) goto done;
    157 
    158   memset(&dc, 0, sizeof dc);
    159   dc.target = kt;
    160   dc.context = g_u.ctx;
    161   if (kit_disasm_iter_new(&dc, data, len, 0, file, &it) != KIT_OK || !it)
    162     goto done;
    163   while (n < cap && kit_disasm_iter_next(it, &insn) == KIT_ITER_ITEM) {
    164     slice_to_buf(insn.mnemonic, out[n].mnem, sizeof out[n].mnem);
    165     slice_to_buf(insn.operands, out[n].ops, sizeof out[n].ops);
    166     ++n;
    167   }
    168   result = n;
    169 
    170 done:
    171   if (it) kit_disasm_iter_free(it);
    172   if (file) kit_obj_free(file);
    173   if (writer) kit_writer_close(writer);
    174   if (ctx.ob) kit_obj_builder_free(ctx.ob);
    175   kit_compiler_free(c);
    176   kit_target_free(kt);
    177   return result;
    178 }
    179 
    180 /* 1 if any instruction's mnemonic contains `mnem`. */
    181 static int have_mnem(const DisInsn* in, int n, const char* mnem) {
    182   for (int i = 0; i < n; ++i)
    183     if (strstr(in[i].mnem, mnem)) return 1;
    184   return 0;
    185 }
    186 
    187 /* 1 if the first instruction whose mnemonic contains `mnem` has `marker` in its
    188  * operands (an empty marker matches any). This is how we tell an immediate
    189  * operand form (x64 "$", aa64 "#") from a register form, and — via the
    190  * i-suffixed RISC-V mnemonics — picks out slli/srli/andi over sll/srl/and. */
    191 static int imm_form(const DisInsn* in, int n, const char* mnem,
    192                     const char* marker) {
    193   for (int i = 0; i < n; ++i)
    194     if (strstr(in[i].mnem, mnem)) return strstr(in[i].ops, marker) != NULL;
    195   return 0;
    196 }
    197 
    198 typedef struct ArchExpect {
    199   KitArchKind arch;
    200   const char* name;
    201   const char* shl_mnem; /* immediate shift-left mnemonic (x*2^k) */
    202   const char* shr_mnem; /* immediate logical shift-right (x u/ 2^k) */
    203   const char* and_mnem; /* immediate bitwise-and (x u% 2^k) */
    204   const char* mark; /* operand marker for an immediate ("" if in mnemonic) */
    205 } ArchExpect;
    206 
    207 static void check_arch(const ArchExpect* ex) {
    208   const char* an = ex->name;
    209   DisInsn buf[128];
    210   int n;
    211 
    212   /* --- multiply --- */
    213   n = op_disasm(ex->arch, KIT_CG_INT_MUL, 8, buf, 128);
    214   EXPECT(n > 0, "[%s] mul8 disasm failed", an);
    215   EXPECT(!have_mnem(buf, n, "mul"),
    216          "[%s] x * 8 should strength-reduce to a shift (no 'mul')", an);
    217   EXPECT(imm_form(buf, n, ex->shl_mnem, ex->mark),
    218          "[%s] x * 8 should use the immediate shift form", an);
    219 
    220   n = op_disasm(ex->arch, KIT_CG_INT_MUL, 7, buf, 128);
    221   EXPECT(n > 0 && have_mnem(buf, n, "mul"), "[%s] x * 7 must stay a multiply",
    222          an);
    223 
    224   /* --- unsigned divide --- */
    225   n = op_disasm(ex->arch, KIT_CG_INT_UDIV, 8, buf, 128);
    226   EXPECT(n > 0, "[%s] udiv8 disasm failed", an);
    227   EXPECT(!have_mnem(buf, n, "div"),
    228          "[%s] x u/ 8 should strength-reduce to a shift (no 'div')", an);
    229   EXPECT(imm_form(buf, n, ex->shr_mnem, ex->mark),
    230          "[%s] x u/ 8 should use the immediate shift form", an);
    231 
    232   n = op_disasm(ex->arch, KIT_CG_INT_UDIV, 7, buf, 128);
    233   EXPECT(n > 0 && have_mnem(buf, n, "div"), "[%s] x u/ 7 must stay a divide",
    234          an);
    235 
    236   /* --- unsigned remainder --- */
    237   n = op_disasm(ex->arch, KIT_CG_INT_UREM, 8, buf, 128);
    238   EXPECT(n > 0, "[%s] urem8 disasm failed", an);
    239   EXPECT(!have_mnem(buf, n, "div") && !have_mnem(buf, n, "rem"),
    240          "[%s] x u%% 8 should strength-reduce to an and (no 'div'/'rem')", an);
    241   EXPECT(imm_form(buf, n, ex->and_mnem, ex->mark),
    242          "[%s] x u%% 8 should use the immediate and form", an);
    243 
    244   n = op_disasm(ex->arch, KIT_CG_INT_UREM, 7, buf, 128);
    245   EXPECT(n > 0 && (have_mnem(buf, n, "div") || have_mnem(buf, n, "rem")),
    246          "[%s] x u%% 7 must stay a divide/remainder", an);
    247 
    248   /* --- signed divide: deliberately left for the optimizer --- */
    249   n = op_disasm(ex->arch, KIT_CG_INT_SDIV, 8, buf, 128);
    250   EXPECT(n > 0 && have_mnem(buf, n, "div"),
    251          "[%s] signed x / 8 is left as a divide at -O0", an);
    252 }
    253 
    254 int main(void) {
    255   /* x64 AT&T immediates read "$N"; aa64 reads "#N"; rv64 folds the immediate
    256    * into the mnemonic (slli/srli/andi), so its operand marker is empty. */
    257   static const ArchExpect arches[] = {
    258       {KIT_ARCH_X86_64, "x86_64", "shl", "shr", "and", "$"},
    259       {KIT_ARCH_ARM_64, "aarch64", "lsl", "lsr", "and", "#"},
    260       {KIT_ARCH_RV64, "riscv64", "slli", "srli", "andi", ""},
    261   };
    262   kit_unit_init(&g_u);
    263   g_u.ctx.now = -1;
    264   for (size_t i = 0; i < sizeof arches / sizeof arches[0]; ++i)
    265     check_arch(&arches[i]);
    266   kit_unit_summary(&g_u, "strength_reduce_test");
    267   return kit_unit_status(&g_u);
    268 }