kit

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

pass_copy.c (7715B)

      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 u32 def_count(Func* f, Val v) {
     30   u32 n = 0;
     31   if (v == VAL_NONE) return 0;
     32   for (u32 b = 0; b < f->nblocks; ++b) {
     33     Block* bl = &f->blocks[b];
     34     for (u32 i = 0; i < bl->ninsts; ++i) {
     35       Inst* in = &bl->insts[i];
     36       if (in->def == v) ++n;
     37       for (u32 d = 0; d < in->ndefs; ++d)
     38         if (in->defs[d] == v) ++n;
     39     }
     40   }
     41   return n;
     42 }
     43 
     44 static void replace_one_use(Func* f, const OptUse* use, Val src) {
     45   Inst* in = &f->blocks[use->block].insts[use->inst];
     46   switch ((OptUseKind)use->kind) {
     47     case OPT_USE_OPERAND:
     48       use->operand->v.reg = (Reg)src;
     49       use->operand->type = f->val_type[src];
     50       use->operand->cls = f->val_cls[src];
     51       break;
     52     case OPT_USE_INDIRECT_BASE:
     53       use->operand->v.ind.base = (Reg)src;
     54       break;
     55     case OPT_USE_INDIRECT_INDEX:
     56       use->operand->v.ind.index = (Reg)src;
     57       break;
     58     case OPT_USE_PHI_INPUT: {
     59       IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
     60       if (aux && use->phi_pred_index < aux->npreds)
     61         aux->pred_vals[use->phi_pred_index] = src;
     62       break;
     63     }
     64     default:
     65       break;
     66   }
     67 }
     68 
     69 static void remove_copy_inst(Inst* in) {
     70   in->op = IR_NOP;
     71   in->def = VAL_NONE;
     72   in->ndefs = 0;
     73   in->defs = NULL;
     74   in->nopnds = 0;
     75   in->opnds = NULL;
     76 }
     77 
     78 static void compact_copies(Func* f) {
     79   for (u32 b = 0; b < f->nblocks; ++b) {
     80     Block* bl = &f->blocks[b];
     81     u32 w = 0;
     82     for (u32 i = 0; i < bl->ninsts; ++i) {
     83       if ((IROp)bl->insts[i].op == IR_NOP) continue;
     84       bl->insts[w] = bl->insts[i];
     85       if (bl->insts[w].def != VAL_NONE && bl->insts[w].def < f->nvals) {
     86         f->val_def_block[bl->insts[w].def] = b;
     87         f->val_def_inst[bl->insts[w].def] = w;
     88       }
     89       for (u32 d = 0; d < bl->insts[w].ndefs; ++d) {
     90         Val v = bl->insts[w].defs[d];
     91         if (v != VAL_NONE && v < f->nvals) {
     92           f->val_def_block[v] = b;
     93           f->val_def_inst[v] = w;
     94         }
     95       }
     96       ++w;
     97     }
     98     bl->ninsts = w;
     99   }
    100 }
    101 
    102 static Inst* val_def_inst(Func* f, Val v) {
    103   if (!f || v == VAL_NONE || v >= f->nvals) return NULL;
    104   u32 b = f->val_def_block[v];
    105   u32 i = f->val_def_inst[v];
    106   if (b >= f->nblocks || i >= f->blocks[b].ninsts) return NULL;
    107   return &f->blocks[b].insts[i];
    108 }
    109 
    110 static int int_width(Func* f, KitCgTypeId ty, u32* out) {
    111   u32 width = kit_cg_type_int_width((KitCompiler*)f->c, ty);
    112   if (!width || width > 64u) return 0;
    113   *out = width;
    114   return 1;
    115 }
    116 
    117 static int convert_step(Func* f, const Inst* in, ConvertStep* out) {
    118   if (!f || !in || !out || (IROp)in->op != IR_CONVERT || in->nopnds < 2)
    119     return 0;
    120   if (in->def == VAL_NONE || in->def >= f->nvals) return 0;
    121   if (in->opnds[0].kind != OPK_REG || in->opnds[1].kind != OPK_REG) return 0;
    122 
    123   memset(out, 0, sizeof *out);
    124   out->src = (Val)in->opnds[1].v.reg;
    125   if (out->src == VAL_NONE || out->src >= f->nvals) return 0;
    126   out->src_type = in->opnds[1].type;
    127   out->dst_type = in->opnds[0].type;
    128   out->kind = (u8)in->extra.imm;
    129   if (!int_width(f, out->src_type, &out->src_width) ||
    130       !int_width(f, out->dst_type, &out->dst_width))
    131     return 0;
    132   return 1;
    133 }
    134 
    135 static int conversion_is_noop(const ConvertStep* s) {
    136   if (!s || s->src_width != s->dst_width || s->src_type != s->dst_type)
    137     return 0;
    138   switch ((ConvKind)s->kind) {
    139     case CV_ZEXT:
    140     case CV_SEXT:
    141     case CV_TRUNC:
    142     case CV_BITCAST:
    143       return 1;
    144     default:
    145       return 0;
    146   }
    147 }
    148 
    149 static int extension_kind(u8 kind) {
    150   return kind == CV_ZEXT || kind == CV_SEXT;
    151 }
    152 
    153 static void set_convert_source(Func* f, Inst* in, Val src) {
    154   in->opnds[1].v.reg = (Reg)src;
    155   in->opnds[1].type = f->val_type[src];
    156   in->opnds[1].cls = f->val_cls[src];
    157 }
    158 
    159 static void make_copy_from(Func* f, Inst* in, Val src) {
    160   Val dst = in->def;
    161   Operand* opnds = in->opnds;
    162   if (!opnds) opnds = arena_array(f->arena, Operand, 2);
    163   memset(&opnds[0], 0, sizeof opnds[0]);
    164   memset(&opnds[1], 0, sizeof opnds[1]);
    165   opnds[0].kind = OPK_REG;
    166   opnds[0].type = f->val_type[dst];
    167   opnds[0].cls = f->val_cls[dst];
    168   opnds[0].v.reg = (Reg)dst;
    169   opnds[1].kind = OPK_REG;
    170   opnds[1].type = f->val_type[src];
    171   opnds[1].cls = f->val_cls[src];
    172   opnds[1].v.reg = (Reg)src;
    173   in->op = IR_COPY;
    174   in->type = f->val_type[dst];
    175   in->opnds = opnds;
    176   in->nopnds = 2;
    177 }
    178 
    179 static int simplify_convert_chain(Func* f, Inst* outer, const ConvertStep* o,
    180                                   const ConvertStep* inner) {
    181   if (!f || !outer || !o || !inner) return 0;
    182 
    183   if (conversion_is_noop(o)) {
    184     make_copy_from(f, outer, o->src);
    185     return 1;
    186   }
    187 
    188   if (extension_kind(o->kind) && o->kind == inner->kind &&
    189       inner->src_width <= inner->dst_width &&
    190       inner->dst_width <= o->dst_width) {
    191     set_convert_source(f, outer, inner->src);
    192     return 1;
    193   }
    194 
    195   if (o->kind == CV_TRUNC && extension_kind(inner->kind) &&
    196       o->dst_width <= inner->dst_width) {
    197     set_convert_source(f, outer, inner->src);
    198     if (o->dst_width == inner->src_width && o->dst_type == inner->src_type) {
    199       make_copy_from(f, outer, inner->src);
    200     } else if (o->dst_width > inner->src_width) {
    201       outer->extra.imm = inner->kind;
    202     }
    203     return 1;
    204   }
    205 
    206   return 0;
    207 }
    208 
    209 static int cleanup_one_copy(Func* f) {
    210   opt_rebuild_def_use(f);
    211   for (u32 b = 0; b < f->nblocks; ++b) {
    212     Block* bl = &f->blocks[b];
    213     for (u32 i = 0; i < bl->ninsts; ++i) {
    214       Inst* in = &bl->insts[i];
    215       Val dst = VAL_NONE;
    216       Val src = VAL_NONE;
    217       if (!copy_values(in, &dst, &src)) continue;
    218       if (dst != src && !same_val_shape(f, dst, src)) continue;
    219       if (dst != src && def_count(f, dst) != 1) continue;
    220       for (u32 u = f->opt_first_use_by_val[dst]; u != OPT_USE_NONE;
    221            u = f->opt_uses[u].next_for_val)
    222         replace_one_use(f, &f->opt_uses[u], src);
    223       remove_copy_inst(in);
    224       opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    225       compact_copies(f);
    226       return 1;
    227     }
    228   }
    229   return 0;
    230 }
    231 
    232 static int cleanup_one_extension(Func* f) {
    233   for (u32 b = 0; b < f->nblocks; ++b) {
    234     Block* bl = &f->blocks[b];
    235     for (u32 i = 0; i < bl->ninsts; ++i) {
    236       Inst* outer = &bl->insts[i];
    237       ConvertStep o;
    238       if (!convert_step(f, outer, &o)) continue;
    239 
    240       Inst* inner_inst = val_def_inst(f, o.src);
    241       ConvertStep inner;
    242       if (!convert_step(f, inner_inst, &inner)) {
    243         if (!conversion_is_noop(&o)) continue;
    244         make_copy_from(f, outer, o.src);
    245       } else if (!simplify_convert_chain(f, outer, &o, &inner)) {
    246         continue;
    247       }
    248 
    249       opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
    250       return 1;
    251     }
    252   }
    253   return 0;
    254 }
    255 
    256 void opt_copy_cleanup(Func* f) {
    257   if (!f || f->opt_rewritten) return;
    258   while (cleanup_one_copy(f)) {
    259   }
    260   opt_rebuild_def_use(f);
    261 }
    262 
    263 void opt_copy_prop(Func* f) {
    264   if (!f || f->opt_rewritten) return;
    265   if (!f->opt_reg_ssa && f->npregs > 1) {
    266     opt_copy_cleanup(f);
    267     return;
    268   }
    269 
    270   opt_copy_cleanup(f);
    271   while (cleanup_one_extension(f)) {
    272     opt_rebuild_def_use(f);
    273     opt_copy_cleanup(f);
    274   }
    275   opt_copy_cleanup(f);
    276 }