combine_cse_test.c (16970B)
1 #include <stdio.h> 2 #include <string.h> 3 4 #include "lib/kit_unit.h" 5 #include "opt/opt_internal.h" 6 7 typedef struct CseFixture { 8 KitCompiler* kc; 9 Func* f; 10 u32 block; 11 KitCgTypeId i8_type; 12 KitCgTypeId i32_type; 13 KitCgTypeId i64_type; 14 } CseFixture; 15 16 static Operand reg_op(Reg reg, KitCgTypeId type) { 17 Operand op; 18 memset(&op, 0, sizeof op); 19 op.kind = OPK_REG; 20 op.cls = RC_INT; 21 op.type = type; 22 op.v.reg = reg; 23 return op; 24 } 25 26 static Operand global_op(ObjSymId sym, KitCgTypeId type) { 27 Operand op; 28 memset(&op, 0, sizeof op); 29 op.kind = OPK_GLOBAL; 30 op.cls = RC_INT; 31 op.type = type; 32 op.v.global.sym = sym; 33 return op; 34 } 35 36 static Operand stack_op(FrameSlot slot, KitCgTypeId type) { 37 Operand op; 38 memset(&op, 0, sizeof op); 39 op.kind = OPK_STACK; 40 op.cls = RC_INT; 41 op.type = type; 42 op.v.frame_slot = slot; 43 return op; 44 } 45 46 static int fixture_init(KitUnit* u, CseFixture* fx) { 47 CGFuncDesc desc; 48 memset(fx, 0, sizeof *fx); 49 if (kit_unit_compiler_new( 50 u, kit_unit_target(KIT_ARCH_X86_64, KIT_OS_LINUX, KIT_OBJ_ELF), 51 &fx->kc) != KIT_OK || 52 !fx->kc) 53 return 0; 54 55 fx->i8_type = kit_cg_type_builtin(fx->kc, KIT_CG_BUILTIN_I8); 56 fx->i32_type = kit_cg_type_builtin(fx->kc, KIT_CG_BUILTIN_I32); 57 fx->i64_type = kit_cg_type_builtin(fx->kc, KIT_CG_BUILTIN_I64); 58 memset(&desc, 0, sizeof desc); 59 desc.fn_type = fx->i64_type; 60 desc.result_type = fx->i64_type; 61 fx->f = ir_func_new((Compiler*)fx->kc, &desc); 62 if (!fx->f) return 0; 63 fx->block = ir_block_new(fx->f); 64 fx->f->entry = fx->block; 65 return 1; 66 } 67 68 static Inst* emit_load(CseFixture* fx, Reg dst, KitCgTypeId result_type, 69 MemAccess mem) { 70 Inst* in = ir_emit(fx->f, fx->block, IR_LOAD); 71 in->type = result_type; 72 in->nopnds = 2; 73 in->opnds = arena_array(fx->f->arena, Operand, 2); 74 in->opnds[0] = reg_op(dst, result_type); 75 in->opnds[1] = global_op(1u, mem.type); 76 in->extra.mem = mem; 77 return in; 78 } 79 80 static Inst* emit_add(CseFixture* fx, Reg dst, KitCgTypeId result_type, 81 KitCgTypeId lhs_type, KitCgTypeId rhs_type, 82 u8 rhs_shift) { 83 Inst* in = ir_emit(fx->f, fx->block, IR_BINOP); 84 in->type = result_type; 85 in->nopnds = 3; 86 in->opnds = arena_array(fx->f->arena, Operand, 3); 87 in->opnds[0] = reg_op(dst, result_type); 88 in->opnds[1] = reg_op(4u, lhs_type); 89 in->opnds[2] = reg_op(5u, rhs_type); 90 in->opnds[2].shift = rhs_shift; 91 in->extra.imm = BO_IADD; 92 return in; 93 } 94 95 static Inst* emit_store(CseFixture* fx, Reg src, KitCgTypeId type, u32 size) { 96 Inst* in = ir_emit(fx->f, fx->block, IR_STORE); 97 in->nopnds = 2; 98 in->opnds = arena_array(fx->f->arena, Operand, 2); 99 in->opnds[0] = global_op(2u, type); 100 in->opnds[1] = reg_op(src, type); 101 in->extra.mem.type = type; 102 in->extra.mem.size = size; 103 in->extra.mem.align = size; 104 in->extra.mem.alias.kind = ALIAS_GLOBAL; 105 in->extra.mem.alias.v.global = 2u; 106 return in; 107 } 108 109 static FrameSlot add_spill_slot(CseFixture* fx, KitCgTypeId type, u32 size, 110 u32 align) { 111 FrameSlotDesc desc; 112 memset(&desc, 0, sizeof desc); 113 desc.type = type; 114 desc.size = size; 115 desc.align = align; 116 desc.kind = FS_SPILL; 117 return ir_frame_slot_new(fx->f, &desc); 118 } 119 120 static Inst* emit_stack_copy(CseFixture* fx, Operand dst, Operand src) { 121 Inst* in = ir_emit(fx->f, fx->block, IR_COPY); 122 in->type = dst.type; 123 in->nopnds = 2u; 124 in->opnds = arena_array(fx->f->arena, Operand, 2u); 125 in->opnds[0] = dst; 126 in->opnds[1] = src; 127 return in; 128 } 129 130 static Inst* find_inst(CseFixture* fx, InstId id) { 131 Block* block = &fx->f->blocks[fx->block]; 132 for (u32 i = 0; i < block->ninsts; ++i) 133 if (block->insts[i].id == id) return &block->insts[i]; 134 return NULL; 135 } 136 137 static u32 count_op(const CseFixture* fx, IROp op) { 138 const Block* block = &fx->f->blocks[fx->block]; 139 u32 count = 0; 140 for (u32 i = 0; i < block->ninsts; ++i) 141 if ((IROp)block->insts[i].op == op) ++count; 142 return count; 143 } 144 145 static int is_copy_between(const Inst* in, Reg dst, Reg src, 146 KitCgTypeId type) { 147 return in && (IROp)in->op == IR_COPY && in->flags == 0u && 148 in->type == type && in->nopnds == 2u && in->opnds != NULL && 149 in->opnds[0].kind == OPK_REG && in->opnds[0].cls == RC_INT && 150 in->opnds[0].type == type && in->opnds[0].v.reg == dst && 151 in->opnds[1].kind == OPK_REG && in->opnds[1].cls == RC_INT && 152 in->opnds[1].type == type && in->opnds[1].v.reg == src; 153 } 154 155 static int has_reg_destination(const Inst* in, IROp op, Reg dst, 156 KitCgTypeId type) { 157 return in && (IROp)in->op == op && in->type == type && in->nopnds >= 1u && 158 in->opnds != NULL && in->opnds[0].kind == OPK_REG && 159 in->opnds[0].cls == RC_INT && in->opnds[0].type == type && 160 in->opnds[0].v.reg == dst; 161 } 162 163 static int is_store_from(const Inst* in, Reg src, KitCgTypeId type) { 164 return in && (IROp)in->op == IR_STORE && in->nopnds == 2u && 165 in->opnds != NULL && in->opnds[1].kind == OPK_REG && 166 in->opnds[1].cls == RC_INT && in->opnds[1].type == type && 167 in->opnds[1].v.reg == src; 168 } 169 170 static MemAccess byte_mem(const CseFixture* fx) { 171 MemAccess mem; 172 memset(&mem, 0, sizeof mem); 173 mem.type = fx->i8_type; 174 mem.size = 1u; 175 mem.align = 1u; 176 mem.alias.kind = ALIAS_GLOBAL; 177 mem.alias.v.global = 1u; 178 return mem; 179 } 180 181 static void exact_load_key_is_reused(KitUnit* u) { 182 CseFixture fx; 183 if (!fixture_init(u, &fx)) { 184 CU_EXPECT(u, 0, "compiler allocation failed for exact load CSE test"); 185 return; 186 } 187 MemAccess mem = byte_mem(&fx); 188 InstId producer_id = emit_load(&fx, 1u, fx.i32_type, mem)->id; 189 InstId replacement_id = emit_load(&fx, 2u, fx.i32_type, mem)->id; 190 /* Make r2 observable. Combine must forward this memory write to the earlier 191 * loaded value, while any surviving r2 definition remains a valid copy. */ 192 InstId store_id = emit_store(&fx, 2u, fx.i32_type, 4u)->id; 193 194 opt_combine(fx.f, NULL); 195 CU_EXPECT(u, count_op(&fx, IR_LOAD) == 1u, 196 "identical loads were not CSE'd"); 197 { 198 Inst* producer = find_inst(&fx, producer_id); 199 Inst* replacement = find_inst(&fx, replacement_id); 200 Inst* store = find_inst(&fx, store_id); 201 CU_EXPECT(u, 202 has_reg_destination(producer, IR_LOAD, 1u, fx.i32_type) && 203 is_store_from(store, 1u, fx.i32_type), 204 "load CSE did not preserve r2 as the destination and reuse " 205 "the value produced in r1 at its consumer"); 206 CU_EXPECT(u, 207 !replacement || 208 is_copy_between(replacement, 2u, 1u, fx.i32_type), 209 "surviving load-CSE replacement does not define r2 from r1"); 210 } 211 kit_compiler_free(fx.kc); 212 } 213 214 static void load_flags_are_part_of_key(KitUnit* u) { 215 CseFixture fx; 216 if (!fixture_init(u, &fx)) { 217 CU_EXPECT(u, 0, "compiler allocation failed for load flag CSE test"); 218 return; 219 } 220 MemAccess plain = byte_mem(&fx); 221 MemAccess sext = plain; 222 sext.flags |= MF_SEXT_LOAD; 223 emit_load(&fx, 1u, fx.i32_type, plain); 224 emit_load(&fx, 2u, fx.i32_type, sext); 225 226 opt_combine(fx.f, NULL); 227 CU_EXPECT(u, count_op(&fx, IR_LOAD) == 2u, 228 "load CSE discarded MF_SEXT_LOAD semantics"); 229 kit_compiler_free(fx.kc); 230 } 231 232 static void load_result_type_is_part_of_key(KitUnit* u) { 233 CseFixture fx; 234 if (!fixture_init(u, &fx)) { 235 CU_EXPECT(u, 0, "compiler allocation failed for load result CSE test"); 236 return; 237 } 238 MemAccess mem = byte_mem(&fx); 239 emit_load(&fx, 1u, fx.i32_type, mem); 240 emit_load(&fx, 2u, fx.i64_type, mem); 241 242 opt_combine(fx.f, NULL); 243 CU_EXPECT(u, count_op(&fx, IR_LOAD) == 2u, 244 "load CSE reused a differently typed result"); 245 kit_compiler_free(fx.kc); 246 } 247 248 static void load_access_type_is_part_of_key(KitUnit* u) { 249 CseFixture fx; 250 if (!fixture_init(u, &fx)) { 251 CU_EXPECT(u, 0, "compiler allocation failed for access type CSE test"); 252 return; 253 } 254 MemAccess byte = byte_mem(&fx); 255 MemAccess other = byte; 256 other.type = fx.i32_type; 257 emit_load(&fx, 1u, fx.i32_type, byte); 258 emit_load(&fx, 2u, fx.i32_type, other); 259 260 opt_combine(fx.f, NULL); 261 CU_EXPECT(u, count_op(&fx, IR_LOAD) == 2u, 262 "load CSE ignored the MemAccess object type"); 263 kit_compiler_free(fx.kc); 264 } 265 266 static void load_alignment_is_part_of_key(KitUnit* u) { 267 CseFixture fx; 268 if (!fixture_init(u, &fx)) { 269 CU_EXPECT(u, 0, "compiler allocation failed for alignment CSE test"); 270 return; 271 } 272 MemAccess byte = byte_mem(&fx); 273 MemAccess aligned = byte; 274 aligned.align = 4u; 275 emit_load(&fx, 1u, fx.i32_type, byte); 276 emit_load(&fx, 2u, fx.i32_type, aligned); 277 278 opt_combine(fx.f, NULL); 279 CU_EXPECT(u, count_op(&fx, IR_LOAD) == 2u, 280 "load CSE ignored MemAccess alignment metadata"); 281 kit_compiler_free(fx.kc); 282 } 283 284 static void exact_compute_key_is_reused(KitUnit* u) { 285 CseFixture fx; 286 if (!fixture_init(u, &fx)) { 287 CU_EXPECT(u, 0, "compiler allocation failed for exact compute CSE test"); 288 return; 289 } 290 InstId producer_id = 291 emit_add(&fx, 1u, fx.i64_type, fx.i64_type, fx.i64_type, 0u)->id; 292 InstId replacement_id = 293 emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 0u)->id; 294 InstId store_id = emit_store(&fx, 2u, fx.i64_type, 8u)->id; 295 296 opt_combine(fx.f, NULL); 297 CU_EXPECT(u, count_op(&fx, IR_BINOP) == 1u, 298 "identical computes were not CSE'd"); 299 { 300 Inst* producer = find_inst(&fx, producer_id); 301 Inst* replacement = find_inst(&fx, replacement_id); 302 Inst* store = find_inst(&fx, store_id); 303 CU_EXPECT(u, 304 has_reg_destination(producer, IR_BINOP, 1u, fx.i64_type) && 305 is_store_from(store, 1u, fx.i64_type), 306 "compute CSE did not preserve r2 as the destination and reuse " 307 "the value produced in r1 at its consumer"); 308 CU_EXPECT(u, 309 !replacement || 310 is_copy_between(replacement, 2u, 1u, fx.i64_type), 311 "surviving compute-CSE replacement does not define r2 from r1"); 312 } 313 kit_compiler_free(fx.kc); 314 } 315 316 static void location_mir_spill_uses_block_dse(KitUnit* u) { 317 CseFixture fx; 318 FrameSlot slot; 319 320 if (!fixture_init(u, &fx)) { 321 CU_EXPECT(u, 0, "compiler allocation failed for spill-use DSE guard"); 322 return; 323 } 324 slot = add_spill_slot(&fx, fx.i64_type, 8u, 8u); 325 { 326 InstId first_id = 327 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 328 reg_op(1u, fx.i64_type)) 329 ->id; 330 Inst* use = emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 0u); 331 use->opnds[1] = stack_op(slot, fx.i64_type); 332 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 333 reg_op(3u, fx.i64_type)); 334 opt_combine(fx.f, NULL); 335 CU_EXPECT(u, find_inst(&fx, first_id) != NULL, 336 "spill DSE crossed a direct OPK_STACK value use"); 337 } 338 kit_compiler_free(fx.kc); 339 340 if (!fixture_init(u, &fx)) { 341 CU_EXPECT(u, 0, 342 "compiler allocation failed for indirect spill-use DSE guard"); 343 return; 344 } 345 slot = add_spill_slot(&fx, fx.i64_type, 8u, 8u); 346 { 347 InstId first_id = 348 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 349 reg_op(1u, fx.i64_type)) 350 ->id; 351 MemAccess mem = byte_mem(&fx); 352 Inst* load = emit_load(&fx, 2u, fx.i64_type, mem); 353 memset(&load->opnds[1], 0, sizeof load->opnds[1]); 354 load->opnds[1].kind = OPK_INDIRECT; 355 load->opnds[1].cls = RC_INT; 356 load->opnds[1].type = fx.i64_type; 357 load->opnds[1].v.ind.base_kind = OPT_INDIRECT_FRAME; 358 load->opnds[1].v.ind.base = slot; 359 load->opnds[1].v.ind.base_type = fx.i64_type; 360 load->opnds[1].v.ind.index_kind = OPT_INDIRECT_REG; 361 load->opnds[1].v.ind.index = (Reg)REG_NONE; 362 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 363 reg_op(3u, fx.i64_type)); 364 opt_combine(fx.f, NULL); 365 CU_EXPECT(u, find_inst(&fx, first_id) != NULL, 366 "spill DSE crossed an indirect frame-component use"); 367 } 368 kit_compiler_free(fx.kc); 369 } 370 371 static void compute_result_type_is_part_of_key(KitUnit* u) { 372 CseFixture fx; 373 if (!fixture_init(u, &fx)) { 374 CU_EXPECT(u, 0, "compiler allocation failed for compute result CSE test"); 375 return; 376 } 377 emit_add(&fx, 1u, fx.i32_type, fx.i64_type, fx.i64_type, 0u); 378 emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 0u); 379 380 opt_combine(fx.f, NULL); 381 CU_EXPECT(u, count_op(&fx, IR_BINOP) == 2u, 382 "compute CSE reused a differently typed destination"); 383 kit_compiler_free(fx.kc); 384 } 385 386 static void compute_reg_input_type_is_part_of_key(KitUnit* u) { 387 CseFixture fx; 388 if (!fixture_init(u, &fx)) { 389 CU_EXPECT(u, 0, "compiler allocation failed for compute input CSE test"); 390 return; 391 } 392 emit_add(&fx, 1u, fx.i64_type, fx.i64_type, fx.i32_type, 0u); 393 emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 0u); 394 395 opt_combine(fx.f, NULL); 396 CU_EXPECT(u, count_op(&fx, IR_BINOP) == 2u, 397 "compute CSE ignored a register operand's type"); 398 kit_compiler_free(fx.kc); 399 } 400 401 static void compute_shift_rider_is_part_of_key(KitUnit* u) { 402 CseFixture fx; 403 if (!fixture_init(u, &fx)) { 404 CU_EXPECT(u, 0, "compiler allocation failed for compute rider CSE test"); 405 return; 406 } 407 emit_add(&fx, 1u, fx.i64_type, fx.i64_type, fx.i64_type, 0u); 408 emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 2u); 409 410 opt_combine(fx.f, NULL); 411 CU_EXPECT(u, count_op(&fx, IR_BINOP) == 2u, 412 "compute CSE ignored a shifted-register rider"); 413 kit_compiler_free(fx.kc); 414 } 415 416 static void compute_semantic_flags_are_part_of_key(KitUnit* u) { 417 CseFixture fx; 418 if (!fixture_init(u, &fx)) { 419 CU_EXPECT(u, 0, "compiler allocation failed for compute flag CSE test"); 420 return; 421 } 422 Inst* portable = emit_add(&fx, 1u, fx.i64_type, fx.i64_type, fx.i64_type, 423 0u); 424 Inst* target = emit_add(&fx, 2u, fx.i64_type, fx.i64_type, fx.i64_type, 0u); 425 portable->extra.imm = BO_SHL; 426 target->extra.imm = BO_SHL; 427 target->flags = CG_IR_INST_TARGET_SHIFT_EDGES; 428 429 opt_combine(fx.f, NULL); 430 CU_EXPECT(u, count_op(&fx, IR_BINOP) == 2u, 431 "compute CSE ignored per-instruction semantic flags"); 432 kit_compiler_free(fx.kc); 433 } 434 435 static void location_mir_spill_copies_are_compacted(KitUnit* u) { 436 CseFixture fx; 437 FrameSlot slot; 438 Inst* replacement; 439 InstId replacement_id; 440 441 if (!fixture_init(u, &fx)) { 442 CU_EXPECT(u, 0, "compiler allocation failed for spill-copy forwarding"); 443 return; 444 } 445 slot = add_spill_slot(&fx, fx.i64_type, 8u, 8u); 446 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 447 reg_op(1u, fx.i64_type)); 448 replacement_id = 449 emit_stack_copy(&fx, reg_op(2u, fx.i64_type), 450 stack_op(slot, fx.i64_type)) 451 ->id; 452 opt_combine(fx.f, NULL); 453 replacement = find_inst(&fx, replacement_id); 454 CU_EXPECT(u, 455 replacement && 456 is_copy_between(replacement, 2u, 1u, fx.i64_type), 457 "location-MIR spill reload was not forwarded from the stored " 458 "register"); 459 kit_compiler_free(fx.kc); 460 461 if (!fixture_init(u, &fx)) { 462 CU_EXPECT(u, 0, "compiler allocation failed for spill-copy elision"); 463 return; 464 } 465 slot = add_spill_slot(&fx, fx.i64_type, 8u, 8u); 466 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 467 reg_op(1u, fx.i64_type)); 468 replacement_id = 469 emit_stack_copy(&fx, reg_op(1u, fx.i64_type), 470 stack_op(slot, fx.i64_type)) 471 ->id; 472 opt_combine(fx.f, NULL); 473 CU_EXPECT(u, find_inst(&fx, replacement_id) == NULL, 474 "location-MIR same-register spill reload survived compaction"); 475 kit_compiler_free(fx.kc); 476 477 if (!fixture_init(u, &fx)) { 478 CU_EXPECT(u, 0, "compiler allocation failed for spill overwrite DSE"); 479 return; 480 } 481 slot = add_spill_slot(&fx, fx.i64_type, 8u, 8u); 482 { 483 InstId first_id = 484 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 485 reg_op(1u, fx.i64_type)) 486 ->id; 487 InstId second_id = 488 emit_stack_copy(&fx, stack_op(slot, fx.i64_type), 489 reg_op(2u, fx.i64_type)) 490 ->id; 491 opt_combine(fx.f, NULL); 492 CU_EXPECT(u, 493 find_inst(&fx, first_id) == NULL && 494 find_inst(&fx, second_id) != NULL, 495 "location-MIR spill overwrite did not retire the dead store"); 496 } 497 kit_compiler_free(fx.kc); 498 } 499 500 int main(void) { 501 KitUnit u; 502 kit_unit_init(&u); 503 exact_load_key_is_reused(&u); 504 load_flags_are_part_of_key(&u); 505 load_result_type_is_part_of_key(&u); 506 load_access_type_is_part_of_key(&u); 507 load_alignment_is_part_of_key(&u); 508 exact_compute_key_is_reused(&u); 509 compute_result_type_is_part_of_key(&u); 510 compute_reg_input_type_is_part_of_key(&u); 511 compute_shift_rider_is_part_of_key(&u); 512 compute_semantic_flags_are_part_of_key(&u); 513 location_mir_spill_copies_are_compacted(&u); 514 location_mir_spill_uses_block_dse(&u); 515 kit_unit_summary(&u, "combine-cse"); 516 return kit_unit_status(&u); 517 }