kit

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

pass_dce.c (6396B)

      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 &&
     24              (in->opnds[0].kind == OPK_LOCAL ||
     25               in->opnds[0].kind == OPK_STACK);
     26     default:
     27       return 0;
     28   }
     29 }
     30 
     31 int opt_inst_has_side_effect(Func* f, const Inst* in) {
     32   (void)f;
     33   if (opt_inst_writes_frame_local(in)) return 1;
     34   switch ((IROp)in->op) {
     35     case IR_LOAD:
     36       return opt_mem_observable(&in->extra.mem);
     37     case IR_BITFIELD_LOAD: {
     38       IRBitFieldAux* aux = (IRBitFieldAux*)in->extra.aux;
     39       return aux && opt_mem_observable(&aux->access.storage);
     40     }
     41     case IR_ALLOCA:
     42     case IR_PARAM_DECL:
     43     case IR_STORE:
     44     case IR_AGG_COPY:
     45     case IR_AGG_SET:
     46     case IR_BITFIELD_STORE:
     47     case IR_CALL:
     48     case IR_BR:
     49     case IR_CONDBR:
     50     case IR_CMP_BRANCH:
     51     case IR_SWITCH:
     52     case IR_INDIRECT_BRANCH:
     53     case IR_LOCAL_STATIC_DATA_BEGIN:
     54     case IR_LOCAL_STATIC_DATA_WRITE:
     55     case IR_LOCAL_STATIC_DATA_LABEL_ADDR:
     56     case IR_LOCAL_STATIC_DATA_END:
     57     case IR_RET:
     58     case IR_UNREACHABLE:
     59     case IR_SCOPE_BEGIN:
     60     case IR_SCOPE_END:
     61     case IR_BREAK_TO:
     62     case IR_CONTINUE_TO:
     63     case IR_VA_START:
     64     case IR_VA_ARG:
     65     case IR_VA_END:
     66     case IR_VA_COPY:
     67     case IR_ATOMIC_LOAD:
     68     case IR_ATOMIC_STORE:
     69     case IR_ATOMIC_RMW:
     70     case IR_ATOMIC_CAS:
     71     case IR_FENCE:
     72     case IR_ASM_BLOCK:
     73     case IR_INTRINSIC:
     74       return 1;
     75     default:
     76       return 0;
     77   }
     78 }
     79 
     80 static int val_has_uses(Func* f, Val v) {
     81   return v != VAL_NONE && v < f->nvals && f->opt_first_use_by_val &&
     82          f->opt_first_use_by_val[v] != OPT_USE_NONE;
     83 }
     84 
     85 static int ssa_dce_candidate(const Inst* in) {
     86   switch ((IROp)in->op) {
     87     case IR_CONST_I:
     88     case IR_CONST_BYTES:
     89     case IR_LOAD_IMM:
     90     case IR_LOAD_CONST:
     91     case IR_LOAD_LABEL_ADDR:
     92     case IR_COPY:
     93     case IR_BINOP:
     94     case IR_UNOP:
     95     case IR_CMP:
     96     case IR_CONVERT:
     97     case IR_PHI:
     98       return 1;
     99     default:
    100       return 0;
    101   }
    102 }
    103 
    104 static int inst_all_defs_unused(Func* f, const Inst* in) {
    105   if (in->def != VAL_NONE && val_has_uses(f, in->def)) return 0;
    106   for (u32 i = 0; i < in->ndefs; ++i)
    107     if (val_has_uses(f, in->defs[i])) return 0;
    108   return in->def != VAL_NONE || in->ndefs != 0;
    109 }
    110 
    111 static void refresh_def_locations(Func* f) {
    112   for (u32 b = 0; b < f->nblocks; ++b) {
    113     Block* bl = &f->blocks[b];
    114     for (u32 i = 0; i < bl->ninsts; ++i) {
    115       Inst* in = &bl->insts[i];
    116       if (in->def != VAL_NONE && in->def < f->nvals) {
    117         f->val_def_block[in->def] = b;
    118         f->val_def_inst[in->def] = i;
    119       }
    120       for (u32 d = 0; d < in->ndefs; ++d) {
    121         Val v = in->defs[d];
    122         if (v == VAL_NONE || v >= f->nvals) continue;
    123         f->val_def_block[v] = b;
    124         f->val_def_inst[v] = i;
    125       }
    126     }
    127   }
    128 }
    129 
    130 static void compact_nops(Func* f) {
    131   for (u32 b = 0; b < f->nblocks; ++b) {
    132     Block* bl = &f->blocks[b];
    133     u32 w = 0;
    134     for (u32 i = 0; i < bl->ninsts; ++i) {
    135       if ((IROp)bl->insts[i].op == IR_NOP) continue;
    136       bl->insts[w++] = bl->insts[i];
    137     }
    138     bl->ninsts = w;
    139   }
    140   refresh_def_locations(f);
    141 }
    142 
    143 void opt_ssa_dce(Func* f) {
    144   if (!f || f->opt_rewritten) return;
    145   int changed = 0;
    146   int again = 1;
    147   opt_rebuild_def_use(f);
    148   while (again) {
    149     again = 0;
    150     for (u32 b = 0; b < f->nblocks; ++b) {
    151       Block* bl = &f->blocks[b];
    152       for (u32 i = 0; i < bl->ninsts; ++i) {
    153         Inst* in = &bl->insts[i];
    154         if (!ssa_dce_candidate(in)) continue;
    155         if (opt_inst_has_side_effect(f, in)) continue;
    156         if (!inst_all_defs_unused(f, in)) continue;
    157         in->op = IR_NOP;
    158         in->def = VAL_NONE;
    159         in->ndefs = 0;
    160         in->defs = NULL;
    161         in->nopnds = 0;
    162         in->opnds = NULL;
    163         changed = 1;
    164         again = 1;
    165       }
    166     }
    167     if (again) opt_rebuild_def_use(f);
    168   }
    169   if (changed) {
    170     opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    171     compact_nops(f);
    172   }
    173   opt_rebuild_def_use(f);
    174 }
    175 
    176 void opt_dce(Func* f) {
    177   opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    178   OptHardBlockLive* hard_live = opt_maybe_build_hard_live(f);
    179   for (u32 b = 0; b < f->nblocks; ++b) {
    180     Block* bl = &f->blocks[b];
    181     if (f->opt_rewritten) {
    182       OptHardRegSet live =
    183           opt_hard_live_out_for_block(hard_live ? &hard_live[b] : NULL);
    184       Inst* new_insts = arena_array(f->arena, Inst, bl->ninsts);
    185       u32 w = 0;
    186       for (u32 ri = bl->ninsts; ri > 0; --ri) {
    187         u32 i = ri - 1u;
    188         Inst* in = &bl->insts[i];
    189         OptRegEffects effects;
    190         OptHardRegSet kills;
    191         if ((IROp)in->op == IR_NOP) continue;
    192         opt_inst_reg_effects(f, in, &effects);
    193         opt_reg_effect_kills(&effects, &kills);
    194         if (!opt_inst_has_side_effect(f, in) &&
    195             !opt_hard_empty(&effects.defs) &&
    196             !opt_hard_intersects(&effects.defs, &live)) {
    197           continue;
    198         }
    199         if (!opt_inst_has_side_effect(f, in) &&
    200             opt_hard_empty(&effects.defs) && in->nopnds == 0) {
    201           continue;
    202         }
    203         new_insts[w++] = *in;
    204         opt_hard_live_step(&live, &effects.uses, &kills);
    205       }
    206       for (u32 i = 0; i < w / 2; ++i) {
    207         Inst tmp = new_insts[i];
    208         new_insts[i] = new_insts[w - 1u - i];
    209         new_insts[w - 1u - i] = tmp;
    210       }
    211       bl->insts = new_insts;
    212       bl->ninsts = w;
    213       bl->cap = w;
    214       continue;
    215     }
    216 
    217     u32 w = 0;
    218     for (u32 i = 0; i < bl->ninsts; ++i) {
    219       Inst* in = &bl->insts[i];
    220       if ((IROp)in->op == IR_NOP) continue;
    221       if (!opt_inst_has_side_effect(f, in) && in->def == VAL_NONE &&
    222           in->ndefs == 0 && in->nopnds == 0)
    223         continue;
    224       bl->insts[w++] = *in;
    225     }
    226     bl->ninsts = w;
    227   }
    228   refresh_def_locations(f);
    229 }