kit

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

pass_hard_live.c (9604B)

      1 #include <string.h>
      2 
      3 #include "core/arena.h"
      4 #include "opt/opt_internal.h"
      5 
      6 u32 opt_call_clobber_mask_for(Func* f, const Inst* in, u8 cls) {
      7   if (cls >= OPT_REG_CLASSES) return 0;
      8   if (in && (IROp)in->op == IR_CALL) {
      9     IRCallAux* aux = (IRCallAux*)in->extra.aux;
     10     if (aux && aux->plan_valid) return aux->plan.clobber_mask[cls];
     11   }
     12   return f->opt_caller_saved[cls];
     13 }
     14 static void hard_add(OptHardRegSet* s, u8 cls, Reg r) {
     15   if (cls >= OPT_REG_CLASSES || r >= 32) return;
     16   s->cls[cls] |= 1u << r;
     17 }
     18 
     19 int opt_hard_empty(const OptHardRegSet* s) {
     20   for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
     21     if (s->cls[c]) return 0;
     22   return 1;
     23 }
     24 
     25 int opt_hard_intersects(const OptHardRegSet* a, const OptHardRegSet* b) {
     26   for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
     27     if (a->cls[c] & b->cls[c]) return 1;
     28   return 0;
     29 }
     30 
     31 static int hard_eq(const OptHardRegSet* a, const OptHardRegSet* b) {
     32   for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
     33     if (a->cls[c] != b->cls[c]) return 0;
     34   return 1;
     35 }
     36 
     37 static void hard_or(OptHardRegSet* dst, const OptHardRegSet* src) {
     38   for (u32 c = 0; c < OPT_REG_CLASSES; ++c) dst->cls[c] |= src->cls[c];
     39 }
     40 
     41 static void hard_live_in_from_out(OptHardRegSet* dst, const OptHardRegSet* use,
     42                                   const OptHardRegSet* out,
     43                                   const OptHardRegSet* def) {
     44   for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
     45     dst->cls[c] = use->cls[c] | (out->cls[c] & ~def->cls[c]);
     46 }
     47 
     48 void opt_hard_live_step(OptHardRegSet* live, const OptHardRegSet* use,
     49                         const OptHardRegSet* def) {
     50   for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
     51     live->cls[c] = (live->cls[c] & ~def->cls[c]) | use->cls[c];
     52 }
     53 
     54 static void hard_use_operand(OptHardRegSet* s, const Operand* op) {
     55   if (!op) return;
     56   if (op->kind == OPK_REG) {
     57     hard_add(s, op->cls, op->v.reg);
     58   } else if (op->kind == OPK_INDIRECT) {
     59     hard_add(s, RC_INT, op->v.ind.base);
     60     if (op->v.ind.index != (Reg)REG_NONE) hard_add(s, RC_INT, op->v.ind.index);
     61   }
     62 }
     63 
     64 static void hard_def_operand(OptHardRegSet* s, const Operand* op) {
     65   if (op && op->kind == OPK_REG) hard_add(s, op->cls, op->v.reg);
     66 }
     67 
     68 static void hard_def_clobber_mask(OptHardRegSet* s, const u32* masks) {
     69   if (!masks) return;
     70   for (u32 c = 0; c < OPT_REG_CLASSES; ++c) s->cls[c] |= masks[c];
     71 }
     72 
     73 static void hard_use_abivalue(OptHardRegSet* use, const CGABIValue* v) {
     74   if (!v) return;
     75   hard_use_operand(use, &v->storage);
     76   for (u32 i = 0; i < v->nparts; ++i) hard_use_operand(use, &v->parts[i].op);
     77 }
     78 
     79 static void hard_def_abivalue(OptHardRegSet* def, const CGABIValue* v) {
     80   if (!v) return;
     81   hard_def_operand(def, &v->storage);
     82   for (u32 i = 0; i < v->nparts; ++i) hard_def_operand(def, &v->parts[i].op);
     83 }
     84 
     85 void opt_hard_inst_use_def(Func* f, const Inst* in, OptHardRegSet* use,
     86                            OptHardRegSet* def) {
     87   memset(use, 0, sizeof *use);
     88   memset(def, 0, sizeof *def);
     89   switch ((IROp)in->op) {
     90     case IR_LOAD_IMM:
     91     case IR_LOAD_CONST:
     92     case IR_TLS_ADDR_OF:
     93       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
     94       break;
     95     case IR_COPY:
     96     case IR_CONVERT:
     97     case IR_UNOP:
     98     case IR_VA_ARG:
     99       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    100       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    101       break;
    102     case IR_LOAD:
    103     case IR_ADDR_OF:
    104     case IR_BITFIELD_LOAD:
    105     case IR_ATOMIC_LOAD:
    106       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    107       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    108       break;
    109     case IR_BINOP:
    110     case IR_CMP:
    111       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    112       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    113       if (in->nopnds >= 3) hard_use_operand(use, &in->opnds[2]);
    114       break;
    115     case IR_STORE:
    116     case IR_AGG_COPY:
    117     case IR_AGG_SET:
    118     case IR_BITFIELD_STORE:
    119     case IR_VA_COPY:
    120       if (in->nopnds >= 1) hard_use_operand(use, &in->opnds[0]);
    121       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    122       break;
    123     case IR_CALL: {
    124       IRCallAux* aux = (IRCallAux*)in->extra.aux;
    125       if (!aux) break;
    126       if (aux->use_plan_replay) {
    127         hard_use_operand(use, &aux->plan.callee);
    128         for (u32 i = 0; i < aux->plan.nargs; ++i) {
    129           hard_use_operand(use, &aux->plan.args[i].src);
    130           if (aux->plan.args[i].dst_kind == CG_CALL_PLAN_REG)
    131             hard_add(def, aux->plan.args[i].cls, aux->plan.args[i].dst_reg);
    132         }
    133         for (u32 i = 0; i < aux->plan.nrets; ++i) {
    134           hard_add(def, aux->plan.rets[i].cls, aux->plan.rets[i].src_reg);
    135           hard_def_operand(def, &aux->plan.rets[i].dst);
    136         }
    137       } else {
    138         hard_use_operand(use, &aux->desc.callee);
    139         for (u32 i = 0; i < aux->desc.nargs; ++i)
    140           hard_use_abivalue(use, &aux->desc.args[i]);
    141         hard_def_abivalue(def, &aux->desc.ret);
    142       }
    143       for (u32 c = 0; c < OPT_REG_CLASSES; ++c) {
    144         u32 idx = c;
    145         u32 mask = opt_call_clobber_mask_for(f, in, (u8)idx);
    146         u32 old = def->cls[idx];
    147         def->cls[idx] = old | mask;
    148       }
    149       break;
    150     }
    151     case IR_CMP_BRANCH:
    152     case IR_CONDBR:
    153     case IR_SWITCH:
    154     case IR_INDIRECT_BRANCH:
    155       for (u32 i = 0; i < in->nopnds; ++i) hard_use_operand(use, &in->opnds[i]);
    156       break;
    157     case IR_LOAD_LABEL_ADDR:
    158       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    159       break;
    160     case IR_RET: {
    161       IRRetAux* aux = (IRRetAux*)in->extra.aux;
    162       if (aux && aux->present) hard_use_abivalue(use, &aux->val);
    163       break;
    164     }
    165     case IR_SCOPE_BEGIN:
    166       break;
    167     case IR_ALLOCA:
    168       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    169       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    170       break;
    171     case IR_VA_START:
    172     case IR_VA_END:
    173       if (in->nopnds >= 1) hard_use_operand(use, &in->opnds[0]);
    174       break;
    175     case IR_ATOMIC_STORE:
    176       if (in->nopnds >= 1) hard_use_operand(use, &in->opnds[0]);
    177       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    178       break;
    179     case IR_ATOMIC_RMW:
    180       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    181       if (in->nopnds >= 2) hard_use_operand(use, &in->opnds[1]);
    182       if (in->nopnds >= 3) hard_use_operand(use, &in->opnds[2]);
    183       break;
    184     case IR_ATOMIC_CAS:
    185       if (in->nopnds >= 1) hard_def_operand(def, &in->opnds[0]);
    186       if (in->nopnds >= 2) hard_def_operand(def, &in->opnds[1]);
    187       if (in->nopnds >= 3) hard_use_operand(use, &in->opnds[2]);
    188       if (in->nopnds >= 4) hard_use_operand(use, &in->opnds[3]);
    189       if (in->nopnds >= 5) hard_use_operand(use, &in->opnds[4]);
    190       break;
    191     case IR_ASM_BLOCK: {
    192       IRAsmAux* aux = (IRAsmAux*)in->extra.aux;
    193       if (!aux) break;
    194       for (u32 i = 0; i < aux->nin; ++i) hard_use_operand(use, &aux->in_ops[i]);
    195       for (u32 i = 0; i < aux->nout; ++i)
    196         hard_def_operand(def, &aux->out_ops[i]);
    197       hard_def_clobber_mask(def, aux->clobber_mask);
    198       break;
    199     }
    200     case IR_INTRINSIC: {
    201       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
    202       if (!aux) break;
    203       for (u32 i = 0; i < aux->narg; ++i) hard_use_operand(use, &aux->args[i]);
    204       for (u32 i = 0; i < aux->ndst; ++i) hard_def_operand(def, &aux->dsts[i]);
    205       break;
    206     }
    207     default:
    208       break;
    209   }
    210 }
    211 
    212 static void hard_live_blocks(Func* f, OptHardBlockLive* live) {
    213   for (u32 b = 0; b < f->nblocks; ++b) {
    214     Block* bl = &f->blocks[b];
    215     OptHardRegSet seen_def;
    216     memset(&seen_def, 0, sizeof seen_def);
    217     memset(&live[b], 0, sizeof live[b]);
    218     for (u32 i = 0; i < bl->ninsts; ++i) {
    219       OptHardRegSet use, def;
    220       opt_hard_inst_use_def(f, &bl->insts[i], &use, &def);
    221       for (u32 c = 0; c < OPT_REG_CLASSES; ++c)
    222         live[b].live_use.cls[c] |= use.cls[c] & ~seen_def.cls[c];
    223       hard_or(&seen_def, &def);
    224       hard_or(&live[b].live_def, &def);
    225     }
    226   }
    227 
    228   int changed;
    229   do {
    230     changed = 0;
    231     for (u32 bi = f->nblocks; bi > 0; --bi) {
    232       u32 b = bi - 1u;
    233       Block* bl = &f->blocks[b];
    234       OptHardRegSet new_out, new_in;
    235       memset(&new_out, 0, sizeof new_out);
    236       for (u32 s = 0; s < bl->nsucc; ++s) {
    237         u32 t = bl->succ[s];
    238         if (t < f->nblocks) hard_or(&new_out, &live[t].live_in);
    239       }
    240       hard_live_in_from_out(&new_in, &live[b].live_use, &new_out,
    241                             &live[b].live_def);
    242       if (!hard_eq(&live[b].live_out, &new_out)) {
    243         live[b].live_out = new_out;
    244         changed = 1;
    245       }
    246       if (!hard_eq(&live[b].live_in, &new_in)) {
    247         live[b].live_in = new_in;
    248         changed = 1;
    249       }
    250     }
    251   } while (changed);
    252 }
    253 
    254 static int hard_live_out_has_phys_reg(const OptHardBlockLive* live,
    255                                       const Operand* r) {
    256   if (!live || !r || r->kind != OPK_REG || r->cls >= OPT_REG_CLASSES ||
    257       r->v.reg >= 32)
    258     return 0;
    259   return (live->live_out.cls[r->cls] & (1u << r->v.reg)) != 0;
    260 }
    261 
    262 OptHardBlockLive* opt_maybe_build_hard_live(Func* f) {
    263   if (!f->opt_rewritten) return NULL;
    264   OptHardBlockLive* live =
    265       arena_zarray(f->arena, OptHardBlockLive, f->nblocks ? f->nblocks : 1u);
    266   hard_live_blocks(f, live);
    267   return live;
    268 }
    269 
    270 OptHardRegSet opt_hard_live_out_for_block(const OptHardBlockLive* live) {
    271   OptHardRegSet out;
    272   memset(&out, 0, sizeof out);
    273   if (live) out = live->live_out;
    274   return out;
    275 }
    276 
    277 int opt_block_live_out_has_phys_reg(Func* f, const OptHardBlockLive* hard_live,
    278                                     u32 block, const Operand* r) {
    279   (void)f;
    280   if (!hard_live || block >= f->nblocks) return 0;
    281   return hard_live_out_has_phys_reg(&hard_live[block], r);
    282 }