kit

pass_simplify.c (20427B)

---

 #include <kit/cg.h>
 #include <string.h>
 
 #include "cg/ir_eval.h"
 #include "opt/opt_internal.h"
 
 /* O1.md / O1-PATTERNS.md L9: same-block forward LOAD_IMM -> known-value tracker
  * for the local (pre-SSA) simplify pass. A bounded per-PReg `reg -> constant`
  * map, populated when an instruction is an IR_LOAD_IMM / IR_CONST_I and
  * invalidated whenever any later instruction in the block (re)defines that PReg.
  * It is rebuilt from empty at every block boundary -- a single forward scan, no
  * SSA, no cross-block reasoning, so -O1 stays linear. Feeding it into
  * operand_const lets the existing BO_UDIV/BO_SDIV/BO_IMUL identity folds and
  * simplify_cmp fire (and a const-op-const fold below) when the operand is a
  * constant materialized into a register rather than an inline OPK_IMM -- the
  * classic `sizeof(X)/sizeof(Y)` and the SIZE_MAX/sizeof(T) >= N growvector
  * guard, which kit otherwise leaves as a runtime udiv + cmp.
  *
  * NULL in the SSA pass (opt_simplify), which uses the def-use index instead. */
 typedef struct LocalConst {
   i64* val;  /* val[r] is the constant in PReg r when known[r] */
   u8* known; /* per-PReg validity bit */
   u32 n;     /* == f->npregs; PRegs >= n are never tracked */
 } LocalConst;
 
 /* simplify's PTR-aware width derivation is its own type policy; the masking and
  * commutativity below are the shared cg/ir_eval core (src/cg/ir_eval.h). */
 static u32 simplify_width(Func* f, KitCgTypeId ty) {
   u32 width = kit_cg_type_int_width((KitCompiler*)f->c, ty);
   if (width && width <= 64u) return width;
   if (kit_cg_type_kind((KitCompiler*)f->c, ty) == KIT_CG_TYPE_PTR) {
     u64 size = kit_cg_type_size((KitCompiler*)f->c, ty);
     if (size && size <= 8u) return (u32)(size * 8u);
   }
   return 0;
 }
 
 static int imm_value(Func* f, const Operand* op, u32 width, i64* out) {
   (void)f;
   if (!op || op->kind != OPK_IMM) return 0;
   *out = (i64)kit_ir_mask_width((u64)op->v.imm, width);
   return 1;
 }
 
 static Inst* def_inst(Func* f, Val v) {
   if (!f || v == VAL_NONE || v >= f->nvals) return NULL;
   u32 b = f->val_def_block[v];
   u32 i = f->val_def_inst[v];
   if (b >= f->nblocks || i >= f->blocks[b].ninsts) return NULL;
   Inst* in = &f->blocks[b].insts[i];
   return in->def == v ? in : NULL;
 }
 
 static int val_load_imm(Func* f, Val v, i64* out) {
   Inst* in = def_inst(f, v);
   if (!in || ((IROp)in->op != IR_LOAD_IMM && (IROp)in->op != IR_CONST_I))
     return 0;
   *out = in->extra.imm;
   return 1;
 }
 
 /* Same-block tracker lookup: is PReg `r` a currently-known constant? */
 static int local_const_lookup(const LocalConst* lc, Reg r, i64* out) {
   if (!lc || r == (Reg)REG_NONE || (u32)r >= lc->n || !lc->known[r]) return 0;
   *out = lc->val[r];
   return 1;
 }
 
 static int operand_const(Func* f, const LocalConst* lc, const Operand* op,
                          u32 width, i64* out) {
   if (imm_value(f, op, width, out)) return 1;
   if (!op || op->kind != OPK_REG) return 0;
   /* SSA pass: chase the unique def via the def-use index. Local pass: consult
    * the bounded same-block forward tracker. Exactly one of the two is active. */
   if (f->opt_reg_ssa) {
     if (!val_load_imm(f, (Val)op->v.reg, out)) return 0;
   } else {
     if (!local_const_lookup(lc, op->v.reg, out)) return 0;
   }
   *out = (i64)kit_ir_mask_width((u64)*out, width);
   return 1;
 }
 
 static int same_reg(const Operand* a, const Operand* b) {
   return a && b && a->kind == OPK_REG && b->kind == OPK_REG &&
          a->v.reg == b->v.reg;
 }
 
 static int same_shape(Func* f, Val dst, Val src) {
   if (dst == src) return 1;
   if (dst == VAL_NONE || src == VAL_NONE || dst >= f->nvals || src >= f->nvals)
     return 0;
   return f->val_type[dst] == f->val_type[src] &&
          f->val_cls[dst] == f->val_cls[src];
 }
 
 static void make_load_imm(Func* f, Inst* in, i64 value) {
   Operand* opnds = in->opnds;
   Val dst = in->def;
   KitCgTypeId ty = in->type;
   u8 cls = RC_INT;
   if (dst != VAL_NONE && dst < f->nvals) {
     ty = f->val_type[dst] ? f->val_type[dst] : ty;
     cls = f->val_cls[dst];
   } else if (in->nopnds >= 1) {
     ty = in->opnds[0].type;
     cls = in->opnds[0].cls;
   }
   if (!opnds) opnds = arena_array(f->arena, Operand, 1);
   memset(&opnds[0], 0, sizeof opnds[0]);
   opnds[0].kind = OPK_REG;
   opnds[0].type = ty;
   opnds[0].cls = cls;
   opnds[0].v.reg = (Reg)(dst != VAL_NONE ? dst : in->opnds[0].v.reg);
   in->op = IR_LOAD_IMM;
   in->type = ty;
   in->opnds = opnds;
   in->nopnds = 1;
   in->extra.imm = value;
 }
 
 static void make_copy(Func* f, Inst* in, const Operand* src) {
   Operand* opnds = in->opnds;
   Val dst = in->def;
   KitCgTypeId dst_ty = in->type;
   u8 dst_cls = RC_INT;
   if (dst != VAL_NONE && dst < f->nvals) {
     dst_ty = f->val_type[dst] ? f->val_type[dst] : dst_ty;
     dst_cls = f->val_cls[dst];
   } else if (in->nopnds >= 1) {
     dst_ty = in->opnds[0].type;
     dst_cls = in->opnds[0].cls;
   }
   if (!opnds) opnds = arena_array(f->arena, Operand, 2);
   memset(&opnds[0], 0, sizeof opnds[0]);
   opnds[0].kind = OPK_REG;
   opnds[0].type = dst_ty;
   opnds[0].cls = dst_cls;
   opnds[0].v.reg = (Reg)(dst != VAL_NONE ? dst : in->opnds[0].v.reg);
   opnds[1] = *src;
   in->op = IR_COPY;
   in->type = dst_ty;
   in->opnds = opnds;
   in->nopnds = 2;
 }
 
 static int convert_noop(Func* f, const Inst* in) {
   if (!in || (IROp)in->op != IR_CONVERT || in->nopnds < 2) return 0;
   KitCgTypeId dst_ty = in->opnds[0].type;
   KitCgTypeId src_ty = in->opnds[1].type;
   u32 w = simplify_width(f, dst_ty);
   if (!w || w != simplify_width(f, src_ty)) return 0;
   /* A same-width int/zext/trunc/bitcast keeps every bit, so it is a pure copy
    * even when the named types differ -- the common case being a pointer bitcast
    * (`int* -> char*`) the frontend records around `&*p`-style casts, which would
    * otherwise lower to a register move that copy-prop cannot then chase (the MIR
    * combine only forwards a convert into another convert). The one same-width
    * convert that is NOT a copy is a cross-class bitcast (int <-> float), which
    * really moves between register files; reject it by requiring the operands to
    * agree on float-ness. */
   int dst_flt = kit_cg_type_kind((KitCompiler*)f->c, dst_ty) == KIT_CG_TYPE_FLOAT;
   int src_flt = kit_cg_type_kind((KitCompiler*)f->c, src_ty) == KIT_CG_TYPE_FLOAT;
   if (dst_flt != src_flt) return 0;
   switch ((ConvKind)in->extra.imm) {
     case CV_ZEXT:
     case CV_SEXT:
     case CV_TRUNC:
     case CV_BITCAST:
       return 1;
     default:
       return 0;
   }
 }
 
 /* Constant integer divide/remainder at `width` bits. Mirrors the authoritative
  * constant-expression semantics in src/cg/const.c (const_divrem64) exactly:
  *
  *   - DIVISION BY ZERO IS NEVER FOLDED (returns 0): leaving the runtime
  *     udiv/sdiv in place preserves the program's fault behavior, matching what
  *     the existing inline-immediate path does (kit_ir_eval_binop also declines
  *     div/rem, and the identity folds only fire for a non-zero divisor).
  *   - Unsigned ops mask to `width` and divide/modulo the masked values.
  *   - Signed ops compute on the magnitudes and reapply the sign, so INT_MIN/-1
  *     wraps to INT_MIN (an == bn, no negate) -- the defined two's-complement
  *     result the hardware sdiv also produces, so the fold is value-preserving.
  *
  * Returns 1 and stores the masked result, or 0 (b==0, or not a div/rem). */
 static int simplify_divrem(BinOp op, u32 width, i64 a64, i64 b64, i64* out) {
   u64 mask = kit_ir_width_mask(width);
   u64 a = (u64)a64 & mask;
   u64 b = (u64)b64 & mask;
   if (b == 0) return 0; /* preserve the runtime trap -- do NOT fold /0 */
   switch (op) {
     case BO_UDIV:
       *out = (i64)((a / b) & mask);
       return 1;
     case BO_UREM:
       *out = (i64)((a % b) & mask);
       return 1;
     case BO_SDIV:
     case BO_SREM: {
       int an = width && ((a >> (width - 1u)) & 1u) != 0;
       int bn = width && ((b >> (width - 1u)) & 1u) != 0;
       u64 aa = an ? (((~a) + 1u) & mask) : a;
       u64 bb = bn ? (((~b) + 1u) & mask) : b;
       u64 r;
       if (bb == 0) return 0;
       if (op == BO_SDIV) {
         r = aa / bb;
         if (an != bn) r = ((~r) + 1u) & mask;
       } else {
         r = aa % bb;
         if (an) r = ((~r) + 1u) & mask;
       }
       *out = (i64)(r & mask);
       return 1;
     }
     default:
       return 0;
   }
 }
 
 /* Fold a fully-constant integer binop to its value. Delegates the wrapping
  * arithmetic/bitwise/shift ops to the shared cg/ir_eval core and the div/rem
  * ops (which that core deliberately declines) to simplify_divrem above, so the
  * /0 guard and signed/width semantics match the constant-expression evaluator
  * exactly. Returns 1 (and stores the masked result) only when the op is
  * genuinely constant-foldable; div-by-zero returns 0. */
 static int simplify_fold_const(BinOp op, u32 width, i64 a, i64 b, i64* out) {
   if (kit_ir_eval_binop(op, width, a, b, out)) return 1;
   return simplify_divrem(op, width, a, b, out);
 }
 
 /* Commutative integer binops the canonicalizer below may swap operands of: the
  * shared integer predicate (kit_ir_binop_is_commutative_int). Floating-point
  * commutative ops are intentionally excluded here -- the shared predicate
  * excludes them too: the backend routes FP through the fp branch (which doesn't
  * consult imm_legal) so canonicalization gains nothing, and IEEE-754 may
  * distinguish operand order for NaN payloads. Non-commutative ops (sub, shifts,
  * div/rem) are skipped. */
 
 static int simplify_binop(Func* f, const LocalConst* lc, Inst* in) {
   if (!in || (IROp)in->op != IR_BINOP || in->flags || in->nopnds < 3) return 0;
   if (in->opnds[0].kind != OPK_REG) return 0;
   u32 width = simplify_width(f, in->type ? in->type : in->opnds[0].type);
   if (!width) return 0;
 
   /* Canonicalize commutative binops to put any inline OPK_IMM on the rhs.
    * The native emitter and the loop-imm-hoist pass both inspect only opnds[2]
    * for imm-legality; putting the constant there lets aa64 strength-reduce
    * `mul x, 5` to a shifted-add and lets the hoist pass lift loop-invariant
    * non-foldable imms. Value-preserving by commutativity. */
   if (kit_ir_binop_is_commutative_int((BinOp)in->extra.imm) &&
       in->opnds[1].kind == OPK_IMM && in->opnds[2].kind != OPK_IMM) {
     Operand tmp = in->opnds[1];
     in->opnds[1] = in->opnds[2];
     in->opnds[2] = tmp;
   }
 
   Operand* a = &in->opnds[1];
   Operand* b = &in->opnds[2];
   i64 av = 0;
   i64 bv = 0;
   /* A constant operand is either an inline OPK_IMM or a register whose value is
    * known -- via the def-use index (SSA pass) or the same-block forward tracker
    * (local pass). operand_const handles both, masking to the op width. */
   int ac = operand_const(f, lc, a, width, &av);
   int bc = operand_const(f, lc, b, width, &bv);
   u64 all = kit_ir_width_mask(width);
 
   /* const op const -> the value. Folds the classic sizeof/sizeof and the
    * SIZE_MAX/sizeof guard's udiv into a single LOAD_IMM; the resulting constant
    * then lets simplify_cmp decide the always-true compare. simplify_fold_const
    * declines div-by-zero (and the non-arithmetic ops), so the runtime trap and
    * any non-foldable op fall through to the identity folds below unchanged. */
   if (ac && bc) {
     i64 r;
     if (simplify_fold_const((BinOp)in->extra.imm, width, av, bv, &r)) {
       make_load_imm(f, in, r);
       return 1;
     }
   }
 
   switch ((BinOp)in->extra.imm) {
     case BO_IADD:
       if (bc && bv == 0 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (ac && av == 0 && b->kind == OPK_REG) {
         make_copy(f, in, b);
         return 1;
       }
       break;
     case BO_ISUB:
       if (bc && bv == 0 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (same_reg(a, b)) {
         make_load_imm(f, in, 0);
         return 1;
       }
       break;
     case BO_IMUL:
       if (bc && bv == 1 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (ac && av == 1 && b->kind == OPK_REG) {
         make_copy(f, in, b);
         return 1;
       }
       if ((bc && bv == 0) || (ac && av == 0)) {
         make_load_imm(f, in, 0);
         return 1;
       }
       break;
     case BO_SDIV:
     case BO_UDIV:
       if (bc && bv == 1 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       break;
     case BO_SREM:
     case BO_UREM:
       if (bc && bv == 1) {
         make_load_imm(f, in, 0);
         return 1;
       }
       break;
     case BO_AND:
       if (bc && (u64)bv == all && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (ac && av == (i64)all && b->kind == OPK_REG) {
         make_copy(f, in, b);
         return 1;
       }
       if ((bc && bv == 0) || (ac && av == 0)) {
         make_load_imm(f, in, 0);
         return 1;
       }
       if (same_reg(a, b)) {
         make_copy(f, in, a);
         return 1;
       }
       break;
     case BO_OR:
       if (bc && bv == 0 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (ac && av == 0 && b->kind == OPK_REG) {
         make_copy(f, in, b);
         return 1;
       }
       if ((bc && (u64)bv == all) || (ac && (u64)av == all)) {
         make_load_imm(f, in, (i64)all);
         return 1;
       }
       if (same_reg(a, b)) {
         make_copy(f, in, a);
         return 1;
       }
       break;
     case BO_XOR:
       if (bc && bv == 0 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       if (ac && av == 0 && b->kind == OPK_REG) {
         make_copy(f, in, b);
         return 1;
       }
       if (same_reg(a, b)) {
         make_load_imm(f, in, 0);
         return 1;
       }
       break;
     case BO_SHL:
     case BO_SHR_S:
     case BO_SHR_U:
       if (bc && bv == 0 && a->kind == OPK_REG) {
         make_copy(f, in, a);
         return 1;
       }
       break;
     default:
       break;
   }
   return 0;
 }
 
 /* addr_of [base + 0] with no index == base. The frontend leaves the `&*p` /
  * `p + 0` idiom as an explicit IR_ADDR_OF of a zero-offset indirect; without
  * this fold it lowers to `add base, #0` (a register move that copy-prop must
  * then chase). Folding it to a copy here collapses the address computation at
  * the source, on every consumer of the pipeline (O1 native, O2, interp tap).
  * Address-of-local (OPK_LOCAL) and global (OPK_GLOBAL) sources are untouched —
  * only a zero-offset register indirect is a pure copy of its base. */
 static int simplify_addr_of(Func* f, Inst* in) {
   (void)f;
   if (!in || (IROp)in->op != IR_ADDR_OF || in->flags || in->nopnds < 2) return 0;
   if (in->opnds[0].kind != OPK_REG) return 0;
   const Operand* src = &in->opnds[1];
   if (src->kind != OPK_INDIRECT) return 0;
   if (src->v.ind.ofs != 0 || src->v.ind.index != (Reg)REG_NONE) return 0;
   if (src->v.ind.base == (Reg)REG_NONE) return 0;
   Operand base;
   memset(&base, 0, sizeof base);
   base.kind = OPK_REG;
   base.cls = RC_INT;
   base.type = in->opnds[0].type;
   base.v.reg = src->v.ind.base;
   make_copy(f, in, &base);
   return 1;
 }
 
 static int simplify_cmp(Func* f, const LocalConst* lc, Inst* in) {
   if (!in || (IROp)in->op != IR_CMP || in->nopnds < 3) return 0;
   u32 width = simplify_width(f, in->opnds[1].type);
   if (!width) return 0;
 
   /* const cmp const -> its boolean. This is what decides the always-true
    * SIZE_MAX/sizeof(T) >= N growvector guard once the udiv above has folded its
    * dividend/divisor into a known constant; the dead arm then drops via the
    * existing branch/CFG cleanup. Mask/sign-extend handling lives in the shared
    * kit_ir_eval_cmp (signed predicates compare the sign-extended values). */
   {
     i64 av;
     i64 bv;
     i64 r;
     if (operand_const(f, lc, &in->opnds[1], width, &av) &&
         operand_const(f, lc, &in->opnds[2], width, &bv) &&
         kit_ir_eval_cmp((CmpOp)in->extra.imm, width, av, bv, &r)) {
       make_load_imm(f, in, r);
       return 1;
     }
   }
 
   if (!same_reg(&in->opnds[1], &in->opnds[2])) return 0;
   switch ((CmpOp)in->extra.imm) {
     case CMP_EQ:
     case CMP_LE_S:
     case CMP_LE_U:
     case CMP_GE_S:
     case CMP_GE_U:
       make_load_imm(f, in, 1);
       return 1;
     case CMP_NE:
     case CMP_LT_S:
     case CMP_LT_U:
     case CMP_GT_S:
     case CMP_GT_U:
       make_load_imm(f, in, 0);
       return 1;
     default:
       return 0;
   }
 }
 
 static int simplify_unop_ssa(Func* f, Inst* in) {
   if (!f->opt_reg_ssa || !in || (IROp)in->op != IR_UNOP || in->nopnds < 2 ||
       (UnOp)in->extra.imm != UO_BNOT || in->opnds[1].kind != OPK_REG)
     return 0;
   Inst* inner = def_inst(f, (Val)in->opnds[1].v.reg);
   if (!inner || (IROp)inner->op != IR_UNOP || inner->nopnds < 2 ||
       (UnOp)inner->extra.imm != UO_BNOT || inner->opnds[1].kind != OPK_REG)
     return 0;
   if (!same_shape(f, in->def, (Val)inner->opnds[1].v.reg)) return 0;
   make_copy(f, in, &inner->opnds[1]);
   return 1;
 }
 
 static int simplify_convert_chain_ssa(Func* f, Inst* in) {
   if (!f->opt_reg_ssa || !in || (IROp)in->op != IR_CONVERT || in->nopnds < 2 ||
       in->opnds[1].kind != OPK_REG)
     return 0;
   Inst* inner = def_inst(f, (Val)in->opnds[1].v.reg);
   if (!inner || (IROp)inner->op != IR_CONVERT || inner->nopnds < 2 ||
       inner->opnds[1].kind != OPK_REG)
     return 0;
   if ((ConvKind)in->extra.imm != CV_BITCAST ||
       (ConvKind)inner->extra.imm != CV_BITCAST)
     return 0;
   if (in->opnds[0].type != inner->opnds[1].type) return 0;
   if (!same_shape(f, in->def, (Val)inner->opnds[1].v.reg)) return 0;
   u32 dw = simplify_width(f, in->opnds[0].type);
   u32 sw = simplify_width(f, inner->opnds[1].type);
   if (!dw || dw != sw) return 0;
   make_copy(f, in, &inner->opnds[1]);
   return 1;
 }
 
 static int simplify_one(Func* f, const LocalConst* lc, Inst* in, int ssa) {
   switch ((IROp)in->op) {
     case IR_BINOP:
       return simplify_binop(f, lc, in);
     case IR_CMP:
       return simplify_cmp(f, lc, in);
     case IR_CONVERT:
       if (convert_noop(f, in)) {
         make_copy(f, in, &in->opnds[1]);
         return 1;
       }
       return ssa ? simplify_convert_chain_ssa(f, in) : 0;
     case IR_ADDR_OF:
       return simplify_addr_of(f, in);
     case IR_UNOP:
       return ssa ? simplify_unop_ssa(f, in) : 0;
     default:
       return 0;
   }
 }
 
 /* Record the constant a (possibly just-rewritten) LOAD_IMM / CONST_I puts in its
  * destination PReg, and invalidate the tracker entry for every other PReg the
  * instruction defines. Both kinds carry the immediate in extra.imm and the dst
  * PReg in opnds[0] (LOAD_IMM) -- the same shape make_load_imm produces, so a
  * binop/cmp this pass just folded to a constant becomes visible to the next
  * instruction in the same block (e.g. the SIZE_MAX/sizeof udiv feeding a cmp). */
 static void local_const_update(LocalConst* lc, Inst* in) {
   Reg made = (Reg)REG_NONE;
   if (((IROp)in->op == IR_LOAD_IMM || (IROp)in->op == IR_CONST_I) &&
       in->nopnds >= 1 && in->opnds[0].kind == OPK_REG &&
       in->opnds[0].cls == RC_INT) {
     made = in->opnds[0].v.reg;
     if (made != (Reg)REG_NONE && (u32)made < lc->n) {
       lc->val[made] = in->extra.imm;
       lc->known[made] = 1;
     }
   }
   /* Any def that is not the freshly-recorded constant invalidates its slot. */
   if (in->def != VAL_NONE && in->def != made && (u32)in->def < lc->n)
     lc->known[in->def] = 0;
   for (u32 i = 0; i < in->ndefs; ++i) {
     Reg d = (Reg)in->defs[i];
     if (d != made && d != (Reg)REG_NONE && (u32)d < lc->n) lc->known[d] = 0;
   }
 }
 
 static void simplify_run(Func* f, int ssa) {
   if (!f || f->opt_rewritten) return;
   if (ssa) opt_rebuild_def_use(f);
   int changed = 0;
   LocalConst lc;
   LocalConst* lcp = NULL;
   if (!ssa && f->npregs) {
     lc.n = f->npregs;
     lc.val = arena_array(f->arena, i64, lc.n);
     lc.known = arena_array(f->arena, u8, lc.n);
     lcp = &lc;
   }
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     /* The tracker is rebuilt from empty at each block boundary -- no cross-block
      * reasoning, so the pass stays a single linear forward scan per block. */
     if (lcp) memset(lcp->known, 0, sizeof(u8) * lcp->n);
     for (u32 i = 0; i < bl->ninsts; ++i) {
       Inst* in = &bl->insts[i];
       if (simplify_one(f, lcp, in, ssa)) changed = 1;
       if (lcp) local_const_update(lcp, in);
     }
   }
   if (changed) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
   if (ssa || changed) opt_rebuild_def_use(f);
 }
 
 void opt_simplify_local(Func* f) { simplify_run(f, 0); }
 
 void opt_simplify(Func* f) { simplify_run(f, 1); }