pass_simplify.c (11126B)
1 #include <kit/cg.h> 2 #include <string.h> 3 4 #include "cg/ir_eval.h" 5 #include "opt/opt_internal.h" 6 7 /* simplify's PTR-aware width derivation is its own type policy; the masking and 8 * commutativity below are the shared cg/ir_eval core (src/cg/ir_eval.h). */ 9 static u32 simplify_width(Func* f, KitCgTypeId ty) { 10 u32 width = kit_cg_type_int_width((KitCompiler*)f->c, ty); 11 if (width && width <= 64u) return width; 12 if (kit_cg_type_kind((KitCompiler*)f->c, ty) == KIT_CG_TYPE_PTR) { 13 u64 size = kit_cg_type_size((KitCompiler*)f->c, ty); 14 if (size && size <= 8u) return (u32)(size * 8u); 15 } 16 return 0; 17 } 18 19 static int imm_value(Func* f, const Operand* op, u32 width, i64* out) { 20 (void)f; 21 if (!op || op->kind != OPK_IMM) return 0; 22 *out = (i64)kit_ir_mask_width((u64)op->v.imm, width); 23 return 1; 24 } 25 26 static Inst* def_inst(Func* f, Val v) { 27 if (!f || v == VAL_NONE || v >= f->nvals) return NULL; 28 u32 b = f->val_def_block[v]; 29 u32 i = f->val_def_inst[v]; 30 if (b >= f->nblocks || i >= f->blocks[b].ninsts) return NULL; 31 Inst* in = &f->blocks[b].insts[i]; 32 return in->def == v ? in : NULL; 33 } 34 35 static int val_load_imm(Func* f, Val v, i64* out) { 36 Inst* in = def_inst(f, v); 37 if (!in || ((IROp)in->op != IR_LOAD_IMM && (IROp)in->op != IR_CONST_I)) 38 return 0; 39 *out = in->extra.imm; 40 return 1; 41 } 42 43 static int operand_const(Func* f, const Operand* op, u32 width, i64* out) { 44 if (imm_value(f, op, width, out)) return 1; 45 if (!f->opt_reg_ssa || !op || op->kind != OPK_REG) return 0; 46 if (!val_load_imm(f, (Val)op->v.reg, out)) return 0; 47 *out = (i64)kit_ir_mask_width((u64)*out, width); 48 return 1; 49 } 50 51 static int same_reg(const Operand* a, const Operand* b) { 52 return a && b && a->kind == OPK_REG && b->kind == OPK_REG && 53 a->v.reg == b->v.reg; 54 } 55 56 static int same_shape(Func* f, Val dst, Val src) { 57 if (dst == src) return 1; 58 if (dst == VAL_NONE || src == VAL_NONE || dst >= f->nvals || src >= f->nvals) 59 return 0; 60 return f->val_type[dst] == f->val_type[src] && 61 f->val_cls[dst] == f->val_cls[src]; 62 } 63 64 static void make_load_imm(Func* f, Inst* in, i64 value) { 65 Operand* opnds = in->opnds; 66 Val dst = in->def; 67 KitCgTypeId ty = in->type; 68 u8 cls = RC_INT; 69 if (dst != VAL_NONE && dst < f->nvals) { 70 ty = f->val_type[dst] ? f->val_type[dst] : ty; 71 cls = f->val_cls[dst]; 72 } else if (in->nopnds >= 1) { 73 ty = in->opnds[0].type; 74 cls = in->opnds[0].cls; 75 } 76 if (!opnds) opnds = arena_array(f->arena, Operand, 1); 77 memset(&opnds[0], 0, sizeof opnds[0]); 78 opnds[0].kind = OPK_REG; 79 opnds[0].type = ty; 80 opnds[0].cls = cls; 81 opnds[0].v.reg = (Reg)(dst != VAL_NONE ? dst : in->opnds[0].v.reg); 82 in->op = IR_LOAD_IMM; 83 in->type = ty; 84 in->opnds = opnds; 85 in->nopnds = 1; 86 in->extra.imm = value; 87 } 88 89 static void make_copy(Func* f, Inst* in, const Operand* src) { 90 Operand* opnds = in->opnds; 91 Val dst = in->def; 92 KitCgTypeId dst_ty = in->type; 93 u8 dst_cls = RC_INT; 94 if (dst != VAL_NONE && dst < f->nvals) { 95 dst_ty = f->val_type[dst] ? f->val_type[dst] : dst_ty; 96 dst_cls = f->val_cls[dst]; 97 } else if (in->nopnds >= 1) { 98 dst_ty = in->opnds[0].type; 99 dst_cls = in->opnds[0].cls; 100 } 101 if (!opnds) opnds = arena_array(f->arena, Operand, 2); 102 memset(&opnds[0], 0, sizeof opnds[0]); 103 opnds[0].kind = OPK_REG; 104 opnds[0].type = dst_ty; 105 opnds[0].cls = dst_cls; 106 opnds[0].v.reg = (Reg)(dst != VAL_NONE ? dst : in->opnds[0].v.reg); 107 opnds[1] = *src; 108 in->op = IR_COPY; 109 in->type = dst_ty; 110 in->opnds = opnds; 111 in->nopnds = 2; 112 } 113 114 static int convert_noop(Func* f, const Inst* in) { 115 if (!in || (IROp)in->op != IR_CONVERT || in->nopnds < 2) return 0; 116 KitCgTypeId dst_ty = in->opnds[0].type; 117 KitCgTypeId src_ty = in->opnds[1].type; 118 if (dst_ty != src_ty) return 0; 119 if (simplify_width(f, dst_ty) != simplify_width(f, src_ty)) return 0; 120 switch ((ConvKind)in->extra.imm) { 121 case CV_ZEXT: 122 case CV_SEXT: 123 case CV_TRUNC: 124 case CV_BITCAST: 125 return 1; 126 default: 127 return 0; 128 } 129 } 130 131 /* Commutative integer binops the canonicalizer below may swap operands of: the 132 * shared integer predicate (kit_ir_binop_is_commutative_int). Floating-point 133 * commutative ops are intentionally excluded here -- the shared predicate 134 * excludes them too: the backend routes FP through the fp branch (which doesn't 135 * consult imm_legal) so canonicalization gains nothing, and IEEE-754 may 136 * distinguish operand order for NaN payloads. Non-commutative ops (sub, shifts, 137 * div/rem) are skipped. */ 138 139 static int simplify_binop(Func* f, Inst* in, int ssa) { 140 if (!in || (IROp)in->op != IR_BINOP || in->flags || in->nopnds < 3) return 0; 141 if (in->opnds[0].kind != OPK_REG) return 0; 142 u32 width = simplify_width(f, in->type ? in->type : in->opnds[0].type); 143 if (!width) return 0; 144 145 /* Canonicalize commutative binops to put any inline OPK_IMM on the rhs. 146 * The native emitter and the loop-imm-hoist pass both inspect only opnds[2] 147 * for imm-legality; putting the constant there lets aa64 strength-reduce 148 * `mul x, 5` to a shifted-add and lets the hoist pass lift loop-invariant 149 * non-foldable imms. Value-preserving by commutativity. */ 150 if (kit_ir_binop_is_commutative_int((BinOp)in->extra.imm) && 151 in->opnds[1].kind == OPK_IMM && in->opnds[2].kind != OPK_IMM) { 152 Operand tmp = in->opnds[1]; 153 in->opnds[1] = in->opnds[2]; 154 in->opnds[2] = tmp; 155 } 156 157 Operand* a = &in->opnds[1]; 158 Operand* b = &in->opnds[2]; 159 i64 av = 0; 160 i64 bv = 0; 161 int ac = ssa ? operand_const(f, a, width, &av) : imm_value(f, a, width, &av); 162 int bc = ssa ? operand_const(f, b, width, &bv) : imm_value(f, b, width, &bv); 163 u64 all = kit_ir_width_mask(width); 164 165 switch ((BinOp)in->extra.imm) { 166 case BO_IADD: 167 if (bc && bv == 0 && a->kind == OPK_REG) { 168 make_copy(f, in, a); 169 return 1; 170 } 171 if (ac && av == 0 && b->kind == OPK_REG) { 172 make_copy(f, in, b); 173 return 1; 174 } 175 break; 176 case BO_ISUB: 177 if (bc && bv == 0 && a->kind == OPK_REG) { 178 make_copy(f, in, a); 179 return 1; 180 } 181 if (same_reg(a, b)) { 182 make_load_imm(f, in, 0); 183 return 1; 184 } 185 break; 186 case BO_IMUL: 187 if (bc && bv == 1 && a->kind == OPK_REG) { 188 make_copy(f, in, a); 189 return 1; 190 } 191 if (ac && av == 1 && b->kind == OPK_REG) { 192 make_copy(f, in, b); 193 return 1; 194 } 195 if ((bc && bv == 0) || (ac && av == 0)) { 196 make_load_imm(f, in, 0); 197 return 1; 198 } 199 break; 200 case BO_SDIV: 201 case BO_UDIV: 202 if (bc && bv == 1 && a->kind == OPK_REG) { 203 make_copy(f, in, a); 204 return 1; 205 } 206 break; 207 case BO_SREM: 208 case BO_UREM: 209 if (bc && bv == 1) { 210 make_load_imm(f, in, 0); 211 return 1; 212 } 213 break; 214 case BO_AND: 215 if (bc && (u64)bv == all && a->kind == OPK_REG) { 216 make_copy(f, in, a); 217 return 1; 218 } 219 if (ac && av == (i64)all && b->kind == OPK_REG) { 220 make_copy(f, in, b); 221 return 1; 222 } 223 if ((bc && bv == 0) || (ac && av == 0)) { 224 make_load_imm(f, in, 0); 225 return 1; 226 } 227 if (same_reg(a, b)) { 228 make_copy(f, in, a); 229 return 1; 230 } 231 break; 232 case BO_OR: 233 if (bc && bv == 0 && a->kind == OPK_REG) { 234 make_copy(f, in, a); 235 return 1; 236 } 237 if (ac && av == 0 && b->kind == OPK_REG) { 238 make_copy(f, in, b); 239 return 1; 240 } 241 if ((bc && (u64)bv == all) || (ac && (u64)av == all)) { 242 make_load_imm(f, in, (i64)all); 243 return 1; 244 } 245 if (same_reg(a, b)) { 246 make_copy(f, in, a); 247 return 1; 248 } 249 break; 250 case BO_XOR: 251 if (bc && bv == 0 && a->kind == OPK_REG) { 252 make_copy(f, in, a); 253 return 1; 254 } 255 if (ac && av == 0 && b->kind == OPK_REG) { 256 make_copy(f, in, b); 257 return 1; 258 } 259 if (same_reg(a, b)) { 260 make_load_imm(f, in, 0); 261 return 1; 262 } 263 break; 264 case BO_SHL: 265 case BO_SHR_S: 266 case BO_SHR_U: 267 if (bc && bv == 0 && a->kind == OPK_REG) { 268 make_copy(f, in, a); 269 return 1; 270 } 271 break; 272 default: 273 break; 274 } 275 return 0; 276 } 277 278 static int simplify_cmp(Func* f, Inst* in) { 279 if (!in || (IROp)in->op != IR_CMP || in->nopnds < 3) return 0; 280 if (!same_reg(&in->opnds[1], &in->opnds[2])) return 0; 281 if (!simplify_width(f, in->opnds[1].type)) return 0; 282 switch ((CmpOp)in->extra.imm) { 283 case CMP_EQ: 284 case CMP_LE_S: 285 case CMP_LE_U: 286 case CMP_GE_S: 287 case CMP_GE_U: 288 make_load_imm(f, in, 1); 289 return 1; 290 case CMP_NE: 291 case CMP_LT_S: 292 case CMP_LT_U: 293 case CMP_GT_S: 294 case CMP_GT_U: 295 make_load_imm(f, in, 0); 296 return 1; 297 default: 298 return 0; 299 } 300 } 301 302 static int simplify_unop_ssa(Func* f, Inst* in) { 303 if (!f->opt_reg_ssa || !in || (IROp)in->op != IR_UNOP || in->nopnds < 2 || 304 (UnOp)in->extra.imm != UO_BNOT || in->opnds[1].kind != OPK_REG) 305 return 0; 306 Inst* inner = def_inst(f, (Val)in->opnds[1].v.reg); 307 if (!inner || (IROp)inner->op != IR_UNOP || inner->nopnds < 2 || 308 (UnOp)inner->extra.imm != UO_BNOT || inner->opnds[1].kind != OPK_REG) 309 return 0; 310 if (!same_shape(f, in->def, (Val)inner->opnds[1].v.reg)) return 0; 311 make_copy(f, in, &inner->opnds[1]); 312 return 1; 313 } 314 315 static int simplify_convert_chain_ssa(Func* f, Inst* in) { 316 if (!f->opt_reg_ssa || !in || (IROp)in->op != IR_CONVERT || in->nopnds < 2 || 317 in->opnds[1].kind != OPK_REG) 318 return 0; 319 Inst* inner = def_inst(f, (Val)in->opnds[1].v.reg); 320 if (!inner || (IROp)inner->op != IR_CONVERT || inner->nopnds < 2 || 321 inner->opnds[1].kind != OPK_REG) 322 return 0; 323 if ((ConvKind)in->extra.imm != CV_BITCAST || 324 (ConvKind)inner->extra.imm != CV_BITCAST) 325 return 0; 326 if (in->opnds[0].type != inner->opnds[1].type) return 0; 327 if (!same_shape(f, in->def, (Val)inner->opnds[1].v.reg)) return 0; 328 u32 dw = simplify_width(f, in->opnds[0].type); 329 u32 sw = simplify_width(f, inner->opnds[1].type); 330 if (!dw || dw != sw) return 0; 331 make_copy(f, in, &inner->opnds[1]); 332 return 1; 333 } 334 335 static int simplify_one(Func* f, Inst* in, int ssa) { 336 switch ((IROp)in->op) { 337 case IR_BINOP: 338 return simplify_binop(f, in, ssa); 339 case IR_CMP: 340 return simplify_cmp(f, in); 341 case IR_CONVERT: 342 if (convert_noop(f, in)) { 343 make_copy(f, in, &in->opnds[1]); 344 return 1; 345 } 346 return ssa ? simplify_convert_chain_ssa(f, in) : 0; 347 case IR_UNOP: 348 return ssa ? simplify_unop_ssa(f, in) : 0; 349 default: 350 return 0; 351 } 352 } 353 354 static void simplify_run(Func* f, int ssa) { 355 if (!f || f->opt_rewritten) return; 356 if (ssa) opt_rebuild_def_use(f); 357 int changed = 0; 358 for (u32 b = 0; b < f->nblocks; ++b) { 359 Block* bl = &f->blocks[b]; 360 for (u32 i = 0; i < bl->ninsts; ++i) 361 if (simplify_one(f, &bl->insts[i], ssa)) changed = 1; 362 } 363 if (changed) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 364 if (ssa || changed) opt_rebuild_def_use(f); 365 } 366 367 void opt_simplify_local(Func* f) { simplify_run(f, 0); } 368 369 void opt_simplify(Func* f) { simplify_run(f, 1); }