kit

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

native_argmove.c (4921B)

      1 #include "cg/native_argmove.h"
      2 
      3 /* Upper bound on moves in one shuffle. Callers (per-call register args, entry
      4  * param binds) are bounded by the ABI register pools (<= 16 per class); 32
      5  * covers both classes with headroom. */
      6 #define NATIVE_ARG_SHUFFLE_MAX 32u
      7 
      8 /* The register a move reads, or REG_NONE if it reads none (immediate, frame
      9  * slot, or an address derived from fp/sp/a global). Only a register source can
     10  * be invalidated by another move writing its destination register, so only
     11  * these constrain the emission order. */
     12 static Reg nam_src_reg(const NativeArgMove* m, NativeAllocClass* cls_out) {
     13   if (!m->is_addr && m->src.kind == NATIVE_LOC_REG) {
     14     *cls_out = (NativeAllocClass)m->src.cls;
     15     return m->src.v.reg;
     16   }
     17   return REG_NONE;
     18 }
     19 
     20 void native_arg_shuffle(const NativeArgShuffle* s, NativeArgMove* moves,
     21                         u32 n) {
     22   u8 done[NATIVE_ARG_SHUFFLE_MAX];
     23   u32 emitted = 0;
     24   if (n > NATIVE_ARG_SHUFFLE_MAX)
     25     compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     26                    "native arg shuffle: too many moves");
     27   memset(done, 0, sizeof done);
     28   /* Mark-and-sweep over the move set. Each pass emits every move whose
     29    * destination is no longer needed as a source (topological order); when only
     30    * a true cycle remains, break one member and continue. */
     31   while (emitted < n) {
     32     int progress = 0;
     33     u32 i, j;
     34     for (i = 0; i < n; ++i) {
     35       int blocked = 0;
     36       if (done[i]) continue;
     37       for (j = 0; j < n && !blocked; ++j) {
     38         NativeAllocClass sc;
     39         Reg sr;
     40         if (j == i || done[j]) continue;
     41         sr = nam_src_reg(&moves[j], &sc);
     42         if (sr != REG_NONE && sr == moves[i].dst.v.reg &&
     43             sc == (NativeAllocClass)moves[i].dst.cls)
     44           blocked = 1;
     45       }
     46       if (!blocked) {
     47         s->emit_one(s->t, &moves[i]);
     48         done[i] = 1;
     49         emitted++;
     50         progress = 1;
     51       }
     52     }
     53     if (!progress) {
     54       /* Every remaining move is part of a cycle; a cycle's ring is reg->reg, so
     55        * at least one remaining move is register-sourced. Break on such a move:
     56        * its destination register still holds a pending source value, so copy it
     57        * to the class scratch and point that value's readers at the scratch. */
     58       u32 k = 0;
     59       NativeAllocClass bc, sc;
     60       NativeLoc scratchloc;
     61       Reg scratch;
     62       Reg broken_reg;
     63       KitCgTypeId val_type;
     64       while (k < n && (done[k] || nam_src_reg(&moves[k], &sc) == REG_NONE)) ++k;
     65       if (k == n)
     66         compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     67                        "native arg shuffle: blocked move set has no register "
     68                        "cycle");
     69       bc = (NativeAllocClass)moves[k].dst.cls;
     70       broken_reg = moves[k].dst.v.reg;
     71       if (bc >= NATIVE_REG_CLASS_COUNT)
     72         compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     73                        "native arg shuffle: invalid class scratch");
     74       if ((s->scratch_class_mask & (1u << bc)) == 0u)
     75         compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     76                        "native arg shuffle: missing class scratch");
     77       scratch = s->scratch[bc];
     78       if (scratch >= NATIVE_MAX_HARD_REGS)
     79         compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     80                        "native arg shuffle: invalid class scratch");
     81       for (j = 0; j < n; ++j) {
     82         Reg sr = nam_src_reg(&moves[j], &sc);
     83         if (done[j]) continue;
     84         if (((NativeAllocClass)moves[j].dst.cls == bc &&
     85              moves[j].dst.v.reg == scratch) ||
     86             (sr != REG_NONE && sc == bc && sr == scratch))
     87           compiler_panic(s->t->c, (SrcLoc){0, 0, 0},
     88                          "native arg shuffle: cycle scratch aliases a live "
     89                          "move register");
     90       }
     91       /* The value parked in broken_reg is whatever the cycle's readers consume,
     92        * and its width is their *source* type — not moves[k].dst's own incoming
     93        * type, which can be narrower (e.g. a 4-byte int rotating into the slot a
     94        * reader treats as an 8-byte pointer). Saving at the destination's width
     95        * would truncate the parked value before the reader loads it back, so use
     96        * a reader's source type to preserve every bit. */
     97       val_type = moves[k].dst.type;
     98       for (j = 0; j < n; ++j) {
     99         Reg sr = nam_src_reg(&moves[j], &sc);
    100         if (!done[j] && sr == broken_reg && sc == bc) {
    101           val_type = moves[j].src.type;
    102           break;
    103         }
    104       }
    105       memset(&scratchloc, 0, sizeof scratchloc);
    106       scratchloc.kind = NATIVE_LOC_REG;
    107       scratchloc.cls = (u8)bc;
    108       scratchloc.type = val_type;
    109       scratchloc.v.reg = scratch;
    110       s->reg_move(s->t, scratchloc, moves[k].dst);
    111       for (j = 0; j < n; ++j) {
    112         Reg sr = nam_src_reg(&moves[j], &sc);
    113         if (!done[j] && sr != REG_NONE && sr == broken_reg && sc == bc) {
    114           moves[j].src = scratchloc;
    115           moves[j].src_offset = 0;
    116         }
    117       }
    118     }
    119   }
    120 }