kit

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

pass_dce.c (6210B)

      1 #include "core/arena.h"
      2 #include "opt/opt_internal.h"
      3 
      4 /* A value-producing op whose destination is an OPK_LOCAL operand writes to an
      5  * address-taken (frame-homed) local. cg_ir_lower emits those as a value op with
      6  * a frame destination rather than a separate IR_STORE, so the write is a memory
      7  * side effect even though the op itself (e.g. IR_LOAD_IMM, IR_COPY) is
      8  * otherwise pure. Without this, dead-def elimination drops stores to escaped
      9  * locals. */
     10 static int opt_inst_writes_frame_local(const Inst* in) {
     11   switch ((IROp)in->op) {
     12     case IR_LOAD_IMM:
     13     case IR_LOAD_CONST:
     14     case IR_LOAD_LABEL_ADDR:
     15     case IR_COPY:
     16     case IR_LOAD:
     17     case IR_ADDR_OF:
     18     case IR_TLS_ADDR_OF:
     19     case IR_BINOP:
     20     case IR_UNOP:
     21     case IR_CMP:
     22     case IR_CONVERT:
     23       return in->nopnds > 0 && in->opnds[0].kind == OPK_LOCAL;
     24     default:
     25       return 0;
     26   }
     27 }
     28 
     29 int opt_inst_has_side_effect(Func* f, const Inst* in) {
     30   (void)f;
     31   if (opt_inst_writes_frame_local(in)) return 1;
     32   switch ((IROp)in->op) {
     33     case IR_LOAD:
     34       return opt_mem_observable(&in->extra.mem);
     35     case IR_BITFIELD_LOAD: {
     36       IRBitFieldAux* aux = (IRBitFieldAux*)in->extra.aux;
     37       return aux && opt_mem_observable(&aux->access.storage);
     38     }
     39     case IR_ALLOCA:
     40     case IR_PARAM_DECL:
     41     case IR_STORE:
     42     case IR_AGG_COPY:
     43     case IR_AGG_SET:
     44     case IR_BITFIELD_STORE:
     45     case IR_CALL:
     46     case IR_BR:
     47     case IR_CONDBR:
     48     case IR_CMP_BRANCH:
     49     case IR_SWITCH:
     50     case IR_INDIRECT_BRANCH:
     51     case IR_LOCAL_STATIC_DATA_BEGIN:
     52     case IR_LOCAL_STATIC_DATA_WRITE:
     53     case IR_LOCAL_STATIC_DATA_LABEL_ADDR:
     54     case IR_LOCAL_STATIC_DATA_END:
     55     case IR_RET:
     56     case IR_UNREACHABLE:
     57     case IR_SCOPE_BEGIN:
     58     case IR_SCOPE_END:
     59     case IR_BREAK_TO:
     60     case IR_CONTINUE_TO:
     61     case IR_VA_START:
     62     case IR_VA_ARG:
     63     case IR_VA_END:
     64     case IR_VA_COPY:
     65     case IR_ATOMIC_LOAD:
     66     case IR_ATOMIC_STORE:
     67     case IR_ATOMIC_RMW:
     68     case IR_ATOMIC_CAS:
     69     case IR_FENCE:
     70     case IR_ASM_BLOCK:
     71     case IR_INTRINSIC:
     72       return 1;
     73     default:
     74       return 0;
     75   }
     76 }
     77 
     78 static int val_has_uses(Func* f, Val v) {
     79   return v != VAL_NONE && v < f->nvals && f->opt_first_use_by_val &&
     80          f->opt_first_use_by_val[v] != OPT_USE_NONE;
     81 }
     82 
     83 static int ssa_dce_candidate(const Inst* in) {
     84   switch ((IROp)in->op) {
     85     case IR_CONST_I:
     86     case IR_CONST_BYTES:
     87     case IR_LOAD_IMM:
     88     case IR_LOAD_CONST:
     89     case IR_LOAD_LABEL_ADDR:
     90     case IR_COPY:
     91     case IR_BINOP:
     92     case IR_UNOP:
     93     case IR_CMP:
     94     case IR_CONVERT:
     95     case IR_PHI:
     96       return 1;
     97     default:
     98       return 0;
     99   }
    100 }
    101 
    102 static int inst_all_defs_unused(Func* f, const Inst* in) {
    103   if (in->def != VAL_NONE && val_has_uses(f, in->def)) return 0;
    104   for (u32 i = 0; i < in->ndefs; ++i)
    105     if (val_has_uses(f, in->defs[i])) return 0;
    106   return in->def != VAL_NONE || in->ndefs != 0;
    107 }
    108 
    109 static void refresh_def_locations(Func* f) {
    110   for (u32 b = 0; b < f->nblocks; ++b) {
    111     Block* bl = &f->blocks[b];
    112     for (u32 i = 0; i < bl->ninsts; ++i) {
    113       Inst* in = &bl->insts[i];
    114       if (in->def != VAL_NONE && in->def < f->nvals) {
    115         f->val_def_block[in->def] = b;
    116         f->val_def_inst[in->def] = i;
    117       }
    118       for (u32 d = 0; d < in->ndefs; ++d) {
    119         Val v = in->defs[d];
    120         if (v == VAL_NONE || v >= f->nvals) continue;
    121         f->val_def_block[v] = b;
    122         f->val_def_inst[v] = i;
    123       }
    124     }
    125   }
    126 }
    127 
    128 static void compact_nops(Func* f) {
    129   for (u32 b = 0; b < f->nblocks; ++b) {
    130     Block* bl = &f->blocks[b];
    131     u32 w = 0;
    132     for (u32 i = 0; i < bl->ninsts; ++i) {
    133       if ((IROp)bl->insts[i].op == IR_NOP) continue;
    134       bl->insts[w++] = bl->insts[i];
    135     }
    136     bl->ninsts = w;
    137   }
    138   refresh_def_locations(f);
    139 }
    140 
    141 void opt_ssa_dce(Func* f) {
    142   if (!f || f->opt_rewritten) return;
    143   int changed = 0;
    144   int again = 1;
    145   opt_rebuild_def_use(f);
    146   while (again) {
    147     again = 0;
    148     for (u32 b = 0; b < f->nblocks; ++b) {
    149       Block* bl = &f->blocks[b];
    150       for (u32 i = 0; i < bl->ninsts; ++i) {
    151         Inst* in = &bl->insts[i];
    152         if (!ssa_dce_candidate(in)) continue;
    153         if (opt_inst_has_side_effect(f, in)) continue;
    154         if (!inst_all_defs_unused(f, in)) continue;
    155         in->op = IR_NOP;
    156         in->def = VAL_NONE;
    157         in->ndefs = 0;
    158         in->defs = NULL;
    159         in->nopnds = 0;
    160         in->opnds = NULL;
    161         changed = 1;
    162         again = 1;
    163       }
    164     }
    165     if (again) opt_rebuild_def_use(f);
    166   }
    167   if (changed) {
    168     opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    169     compact_nops(f);
    170   }
    171   opt_rebuild_def_use(f);
    172 }
    173 
    174 void opt_dce(Func* f) {
    175   opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    176   OptHardBlockLive* hard_live = opt_maybe_build_hard_live(f);
    177   for (u32 b = 0; b < f->nblocks; ++b) {
    178     Block* bl = &f->blocks[b];
    179     if (f->opt_rewritten) {
    180       OptHardRegSet live =
    181           opt_hard_live_out_for_block(hard_live ? &hard_live[b] : NULL);
    182       Inst* new_insts = arena_array(f->arena, Inst, bl->ninsts);
    183       u32 w = 0;
    184       for (u32 ri = bl->ninsts; ri > 0; --ri) {
    185         u32 i = ri - 1u;
    186         Inst* in = &bl->insts[i];
    187         OptHardRegSet use, def;
    188         if ((IROp)in->op == IR_NOP) continue;
    189         opt_hard_inst_use_def(f, in, &use, &def);
    190         if (!opt_inst_has_side_effect(f, in) && !opt_hard_empty(&def) &&
    191             !opt_hard_intersects(&def, &live)) {
    192           continue;
    193         }
    194         if (!opt_inst_has_side_effect(f, in) && opt_hard_empty(&def) &&
    195             in->nopnds == 0) {
    196           continue;
    197         }
    198         new_insts[w++] = *in;
    199         opt_hard_live_step(&live, &use, &def);
    200       }
    201       for (u32 i = 0; i < w / 2; ++i) {
    202         Inst tmp = new_insts[i];
    203         new_insts[i] = new_insts[w - 1u - i];
    204         new_insts[w - 1u - i] = tmp;
    205       }
    206       bl->insts = new_insts;
    207       bl->ninsts = w;
    208       bl->cap = w;
    209       continue;
    210     }
    211 
    212     u32 w = 0;
    213     for (u32 i = 0; i < bl->ninsts; ++i) {
    214       Inst* in = &bl->insts[i];
    215       if ((IROp)in->op == IR_NOP) continue;
    216       if (!opt_inst_has_side_effect(f, in) && in->def == VAL_NONE &&
    217           in->ndefs == 0 && in->nopnds == 0)
    218         continue;
    219       bl->insts[w++] = *in;
    220     }
    221     bl->ninsts = w;
    222   }
    223   refresh_def_locations(f);
    224 }