kit

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

pass_copy.c (9907B)

      1 #include <string.h>
      2 
      3 #include "opt/opt_internal.h"
      4 
      5 typedef struct ConvertStep {
      6   Val src;
      7   KitCgTypeId src_type;
      8   KitCgTypeId dst_type;
      9   u32 src_width;
     10   u32 dst_width;
     11   u8 kind;
     12 } ConvertStep;
     13 
     14 static int same_val_shape(Func* f, Val a, Val b) {
     15   if (a == VAL_NONE || b == VAL_NONE || a >= f->nvals || b >= f->nvals)
     16     return 0;
     17   return f->val_cls[a] == f->val_cls[b] && f->val_type[a] == f->val_type[b];
     18 }
     19 
     20 static int copy_values(const Inst* in, Val* dst, Val* src) {
     21   if (!in || (IROp)in->op != IR_COPY || in->nopnds < 2) return 0;
     22   if (in->opnds[0].kind != OPK_REG || in->opnds[1].kind != OPK_REG) return 0;
     23   *dst = (Val)in->opnds[0].v.reg;
     24   *src = (Val)in->opnds[1].v.reg;
     25   if (in->def != VAL_NONE && in->def != *dst) return 0;
     26   return 1;
     27 }
     28 
     29 static void replace_one_use(Func* f, const OptUse* use, Val src) {
     30   Inst* in = &f->blocks[use->block].insts[use->inst];
     31   switch ((OptUseKind)use->kind) {
     32     case OPT_USE_OPERAND:
     33       use->operand->v.reg = (Reg)src;
     34       use->operand->type = f->val_type[src];
     35       use->operand->cls = f->val_cls[src];
     36       break;
     37     case OPT_USE_INDIRECT_BASE:
     38       use->operand->v.ind.base = (Reg)src;
     39       break;
     40     case OPT_USE_INDIRECT_INDEX:
     41       use->operand->v.ind.index = (Reg)src;
     42       break;
     43     case OPT_USE_PHI_INPUT: {
     44       IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
     45       if (aux && use->phi_pred_index < aux->npreds)
     46         aux->pred_vals[use->phi_pred_index] = src;
     47       break;
     48     }
     49     default:
     50       break;
     51   }
     52 }
     53 
     54 static void remove_copy_inst(Inst* in) {
     55   in->op = IR_NOP;
     56   in->def = VAL_NONE;
     57   in->ndefs = 0;
     58   in->defs = NULL;
     59   in->nopnds = 0;
     60   in->opnds = NULL;
     61 }
     62 
     63 static void compact_copies(Func* f) {
     64   for (u32 b = 0; b < f->nblocks; ++b) {
     65     Block* bl = &f->blocks[b];
     66     u32 w = 0;
     67     for (u32 i = 0; i < bl->ninsts; ++i) {
     68       if ((IROp)bl->insts[i].op == IR_NOP) continue;
     69       bl->insts[w] = bl->insts[i];
     70       if (bl->insts[w].def != VAL_NONE && bl->insts[w].def < f->nvals) {
     71         f->val_def_block[bl->insts[w].def] = b;
     72         f->val_def_inst[bl->insts[w].def] = w;
     73       }
     74       for (u32 d = 0; d < bl->insts[w].ndefs; ++d) {
     75         Val v = bl->insts[w].defs[d];
     76         if (v != VAL_NONE && v < f->nvals) {
     77           f->val_def_block[v] = b;
     78           f->val_def_inst[v] = w;
     79         }
     80       }
     81       ++w;
     82     }
     83     bl->ninsts = w;
     84   }
     85 }
     86 
     87 static Inst* val_def_inst(Func* f, Val v) {
     88   if (!f || v == VAL_NONE || v >= f->nvals) return NULL;
     89   u32 b = f->val_def_block[v];
     90   u32 i = f->val_def_inst[v];
     91   if (b >= f->nblocks || i >= f->blocks[b].ninsts) return NULL;
     92   return &f->blocks[b].insts[i];
     93 }
     94 
     95 static int int_width(Func* f, KitCgTypeId ty, u32* out) {
     96   u32 width = kit_cg_type_int_width((KitCompiler*)f->c, ty);
     97   if (!width || width > 64u) return 0;
     98   *out = width;
     99   return 1;
    100 }
    101 
    102 static int convert_step(Func* f, const Inst* in, ConvertStep* out) {
    103   if (!f || !in || !out || (IROp)in->op != IR_CONVERT || in->nopnds < 2)
    104     return 0;
    105   if (in->def == VAL_NONE || in->def >= f->nvals) return 0;
    106   if (in->opnds[0].kind != OPK_REG || in->opnds[1].kind != OPK_REG) return 0;
    107 
    108   memset(out, 0, sizeof *out);
    109   out->src = (Val)in->opnds[1].v.reg;
    110   if (out->src == VAL_NONE || out->src >= f->nvals) return 0;
    111   out->src_type = in->opnds[1].type;
    112   out->dst_type = in->opnds[0].type;
    113   out->kind = (u8)in->extra.imm;
    114   if (!int_width(f, out->src_type, &out->src_width) ||
    115       !int_width(f, out->dst_type, &out->dst_width))
    116     return 0;
    117   return 1;
    118 }
    119 
    120 static int conversion_is_noop(const ConvertStep* s) {
    121   if (!s || s->src_width != s->dst_width || s->src_type != s->dst_type)
    122     return 0;
    123   switch ((ConvKind)s->kind) {
    124     case CV_ZEXT:
    125     case CV_SEXT:
    126     case CV_TRUNC:
    127     case CV_BITCAST:
    128       return 1;
    129     default:
    130       return 0;
    131   }
    132 }
    133 
    134 static int extension_kind(u8 kind) {
    135   return kind == CV_ZEXT || kind == CV_SEXT;
    136 }
    137 
    138 static void set_convert_source(Func* f, Inst* in, Val src) {
    139   in->opnds[1].v.reg = (Reg)src;
    140   in->opnds[1].type = f->val_type[src];
    141   in->opnds[1].cls = f->val_cls[src];
    142 }
    143 
    144 static void make_copy_from(Func* f, Inst* in, Val src) {
    145   Val dst = in->def;
    146   Operand* opnds = in->opnds;
    147   if (!opnds) opnds = arena_array(f->arena, Operand, 2);
    148   memset(&opnds[0], 0, sizeof opnds[0]);
    149   memset(&opnds[1], 0, sizeof opnds[1]);
    150   opnds[0].kind = OPK_REG;
    151   opnds[0].type = f->val_type[dst];
    152   opnds[0].cls = f->val_cls[dst];
    153   opnds[0].v.reg = (Reg)dst;
    154   opnds[1].kind = OPK_REG;
    155   opnds[1].type = f->val_type[src];
    156   opnds[1].cls = f->val_cls[src];
    157   opnds[1].v.reg = (Reg)src;
    158   in->op = IR_COPY;
    159   in->type = f->val_type[dst];
    160   in->opnds = opnds;
    161   in->nopnds = 2;
    162 }
    163 
    164 static int simplify_convert_chain(Func* f, Inst* outer, const ConvertStep* o,
    165                                   const ConvertStep* inner) {
    166   if (!f || !outer || !o || !inner) return 0;
    167 
    168   if (conversion_is_noop(o)) {
    169     make_copy_from(f, outer, o->src);
    170     return 1;
    171   }
    172 
    173   if (extension_kind(o->kind) && o->kind == inner->kind &&
    174       inner->src_width <= inner->dst_width &&
    175       inner->dst_width <= o->dst_width) {
    176     set_convert_source(f, outer, inner->src);
    177     return 1;
    178   }
    179 
    180   if (o->kind == CV_TRUNC && extension_kind(inner->kind) &&
    181       o->dst_width <= inner->dst_width) {
    182     set_convert_source(f, outer, inner->src);
    183     if (o->dst_width == inner->src_width && o->dst_type == inner->src_type) {
    184       make_copy_from(f, outer, inner->src);
    185     } else if (o->dst_width > inner->src_width) {
    186       outer->extra.imm = inner->kind;
    187     }
    188     return 1;
    189   }
    190 
    191   return 0;
    192 }
    193 
    194 /* Precompute the number of definitions of every value in a single sweep so the
    195  * batch copy pass can test the def_count==1 removability condition in O(1)
    196  * instead of rescanning the whole function per copy. */
    197 static void compute_def_counts(Func* f, u32* ndef) {
    198   memset(ndef, 0, sizeof(*ndef) * f->nvals);
    199   for (u32 b = 0; b < f->nblocks; ++b) {
    200     Block* bl = &f->blocks[b];
    201     for (u32 i = 0; i < bl->ninsts; ++i) {
    202       Inst* in = &bl->insts[i];
    203       if (in->def != VAL_NONE && in->def < f->nvals) ++ndef[in->def];
    204       for (u32 d = 0; d < in->ndefs; ++d)
    205         if (in->defs[d] != VAL_NONE && in->defs[d] < f->nvals)
    206           ++ndef[in->defs[d]];
    207     }
    208   }
    209 }
    210 
    211 /* Follow the removed-copy chain dst -> src to its final representative: a value
    212  * that is not itself the dst of a removed copy (or a self-copy). `repl[v]` is
    213  * VAL_NONE when v is not a removed-copy dst. Bounded by nvals to stay safe if a
    214  * pathological IR forms a copy cycle. */
    215 static Val resolve_copy(Func* f, const Val* repl, Val v) {
    216   for (u32 hops = 0; hops < f->nvals; ++hops) {
    217     Val next;
    218     if (v == VAL_NONE || v >= f->nvals) break;
    219     next = repl[v];
    220     if (next == VAL_NONE || next == v) break;
    221     v = next;
    222   }
    223   return v;
    224 }
    225 
    226 /* Collect every removable IR_COPY in one def-use pass, resolve copy chains to
    227  * their final source, then redirect all uses and drop the copies together —
    228  * O(N) rather than the O(N^2) "rebuild + remove one" loop. Removing a copy
    229  * never changes another value's def_count (a removable non-self copy is the
    230  * sole def of its dst), so a single pass reaches the fixpoint. */
    231 static int cleanup_copies_pass(Func* f) {
    232   u32* ndef;
    233   Val* repl;
    234   int removed_any = 0;
    235   opt_rebuild_def_use(f);
    236   if (!f->nvals) return 0;
    237   ndef = arena_array(f->arena, u32, f->nvals);
    238   repl = arena_array(f->arena, Val, f->nvals);
    239   for (u32 v = 0; v < f->nvals; ++v) repl[v] = VAL_NONE;
    240   compute_def_counts(f, ndef);
    241   /* First sweep: tag each removable copy's dst with its immediate src. */
    242   for (u32 b = 0; b < f->nblocks; ++b) {
    243     Block* bl = &f->blocks[b];
    244     for (u32 i = 0; i < bl->ninsts; ++i) {
    245       Inst* in = &bl->insts[i];
    246       Val dst = VAL_NONE;
    247       Val src = VAL_NONE;
    248       if (!copy_values(in, &dst, &src)) continue;
    249       if (dst == VAL_NONE || dst >= f->nvals) continue;
    250       if (dst != src && !same_val_shape(f, dst, src)) continue;
    251       if (dst != src && ndef[dst] != 1) continue;
    252       repl[dst] = src;
    253       removed_any = 1;
    254     }
    255   }
    256   if (!removed_any) return 0;
    257   /* Second sweep: redirect uses to the resolved source and erase the copies. */
    258   for (u32 b = 0; b < f->nblocks; ++b) {
    259     Block* bl = &f->blocks[b];
    260     for (u32 i = 0; i < bl->ninsts; ++i) {
    261       Inst* in = &bl->insts[i];
    262       Val dst = VAL_NONE;
    263       Val src = VAL_NONE;
    264       Val final_src;
    265       if (!copy_values(in, &dst, &src)) continue;
    266       if (dst >= f->nvals || repl[dst] == VAL_NONE) continue;
    267       final_src = resolve_copy(f, repl, dst);
    268       if (final_src != dst)
    269         for (u32 u = f->opt_first_use_by_val[dst]; u != OPT_USE_NONE;
    270              u = f->opt_uses[u].next_for_val)
    271           replace_one_use(f, &f->opt_uses[u], final_src);
    272       remove_copy_inst(in);
    273     }
    274   }
    275   opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    276   compact_copies(f);
    277   return 1;
    278 }
    279 
    280 static int cleanup_one_extension(Func* f) {
    281   for (u32 b = 0; b < f->nblocks; ++b) {
    282     Block* bl = &f->blocks[b];
    283     for (u32 i = 0; i < bl->ninsts; ++i) {
    284       Inst* outer = &bl->insts[i];
    285       ConvertStep o;
    286       if (!convert_step(f, outer, &o)) continue;
    287 
    288       Inst* inner_inst = val_def_inst(f, o.src);
    289       ConvertStep inner;
    290       if (!convert_step(f, inner_inst, &inner)) {
    291         if (!conversion_is_noop(&o)) continue;
    292         make_copy_from(f, outer, o.src);
    293       } else if (!simplify_convert_chain(f, outer, &o, &inner)) {
    294         continue;
    295       }
    296 
    297       opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    298       return 1;
    299     }
    300   }
    301   return 0;
    302 }
    303 
    304 void opt_copy_cleanup(Func* f) {
    305   if (!f || f->opt_rewritten) return;
    306   while (cleanup_copies_pass(f)) {
    307   }
    308   opt_rebuild_def_use(f);
    309 }
    310 
    311 void opt_copy_prop(Func* f) {
    312   if (!f || f->opt_rewritten) return;
    313   if (!f->opt_reg_ssa && f->npregs > 1) {
    314     opt_copy_cleanup(f);
    315     return;
    316   }
    317 
    318   opt_copy_cleanup(f);
    319   while (cleanup_one_extension(f)) {
    320     opt_rebuild_def_use(f);
    321     opt_copy_cleanup(f);
    322   }
    323   opt_copy_cleanup(f);
    324 }