src/lj_opt_sink.c

   1 /*
   2 ** SINK: Allocation Sinking and Store Sinking.
   3 ** Copyright (C) 2005-2023 Mike Pall. See Copyright Notice in luajit.h
   4 */
   5
   6 #define lj_opt_sink_c
   7 #define LUA_CORE
   8
   9 #include "lj_obj.h"
  10
  11 #if LJ_HASJIT
  12
  13 #include "lj_ir.h"
  14 #include "lj_jit.h"
  15 #include "lj_iropt.h"
  16 #include "lj_target.h"
  17
  18 /* Some local macros to save typing. Undef'd at the end. */
  19 #define IR(ref)         (&J->cur.ir[(ref)])
  20
  21 /* Check whether the store ref points to an eligible allocation. */
  22 static IRIns *sink_checkalloc(jit_State *J, IRIns *irs)
  23 {
  24   IRIns *ir = IR(irs->op1);
  25   if (!irref_isk(ir->op2))
  26     return NULL;  /* Non-constant key. */
  27   if (ir->o == IR_HREFK || ir->o == IR_AREF)
  28     ir = IR(ir->op1);
  29   else if (!(ir->o == IR_HREF || ir->o == IR_NEWREF ||
  30              ir->o == IR_FREF || ir->o == IR_ADD))
  31     return NULL;  /* Unhandled reference type (for XSTORE). */
  32   ir = IR(ir->op1);
  33   if (!(ir->o == IR_TNEW || ir->o == IR_TDUP || ir->o == IR_CNEW))
  34     return NULL;  /* Not an allocation. */
  35   return ir;  /* Return allocation. */
  36 }
  37
  38 /* Recursively check whether a value depends on a PHI. */
  39 static int sink_phidep(jit_State *J, IRRef ref, int *workp)
  40 {
  41   IRIns *ir = IR(ref);
  42   if (!*workp) return 1;  /* Give up and pretend it does. */
  43   (*workp)--;
  44   if (irt_isphi(ir->t)) return 1;
  45   if (ir->op1 >= REF_FIRST && sink_phidep(J, ir->op1, workp)) return 1;
  46   if (ir->op2 >= REF_FIRST && sink_phidep(J, ir->op2, workp)) return 1;
  47   return 0;
  48 }
  49
  50 /* Check whether a value is a sinkable PHI or loop-invariant. */
  51 static int sink_checkphi(jit_State *J, IRIns *ira, IRRef ref)
  52 {
  53   if (ref >= REF_FIRST) {
  54     IRIns *ir = IR(ref);
  55     if (irt_isphi(ir->t) || (ir->o == IR_CONV && ir->op2 == IRCONV_NUM_INT &&
  56                              irt_isphi(IR(ir->op1)->t))) {
  57       ira->prev++;
  58       return 1;  /* Sinkable PHI. */
  59     }
  60     /* Otherwise the value must be loop-invariant. */
  61     if (ref < J->loopref) {
  62       /* Check for PHI dependencies, but give up after reasonable effort. */
  63       int work = 64;
  64       return !sink_phidep(J, ref, &work);
  65     } else {
  66       return 0;  /* Loop-variant. */
  67     }
  68   }
  69   return 1;  /* Constant (non-PHI). */
  70 }
  71
  72 /* Mark non-sinkable allocations using single-pass backward propagation.
  73 **
  74 ** Roots for the marking process are:
  75 ** - Some PHIs or snapshots (see below).
  76 ** - Non-PHI, non-constant values stored to PHI allocations.
  77 ** - All guards.
  78 ** - Any remaining loads not eliminated by store-to-load forwarding.
  79 ** - Stores with non-constant keys.
  80 ** - All stored values.
  81 */
  82 static void sink_mark_ins(jit_State *J)
  83 {
  84   IRIns *ir, *irlast = IR(J->cur.nins-1);
  85   for (ir = irlast ; ; ir--) {
  86     switch (ir->o) {
  87     case IR_BASE:
  88       return;  /* Finished. */
  89     case IR_ALOAD: case IR_HLOAD: case IR_XLOAD: case IR_TBAR: case IR_ALEN:
  90       irt_setmark(IR(ir->op1)->t);  /* Mark ref for remaining loads. */
  91       break;
  92     case IR_FLOAD:
  93       if (irt_ismarked(ir->t) || ir->op2 == IRFL_TAB_META)
  94         irt_setmark(IR(ir->op1)->t);  /* Mark table for remaining loads. */
  95       break;
  96     case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: {
  97       IRIns *ira = sink_checkalloc(J, ir);
  98       if (!ira || (irt_isphi(ira->t) && !sink_checkphi(J, ira, ir->op2)))
  99         irt_setmark(IR(ir->op1)->t);  /* Mark ineligible ref. */
 100       irt_setmark(IR(ir->op2)->t);  /* Mark stored value. */
 101       break;
 102       }
 103 #if LJ_HASFFI
 104     case IR_CNEWI:
 105       if (irt_isphi(ir->t) &&
 106           (!sink_checkphi(J, ir, ir->op2) ||
 107            (LJ_32 && ir+1 < irlast && (ir+1)->o == IR_HIOP &&
 108             !sink_checkphi(J, ir, (ir+1)->op2))))
 109         irt_setmark(ir->t);  /* Mark ineligible allocation. */
 110 #endif
 111       /* fallthrough */
 112     case IR_USTORE:
 113       irt_setmark(IR(ir->op2)->t);  /* Mark stored value. */
 114       break;
 115 #if LJ_HASFFI
 116     case IR_CALLXS:
 117 #endif
 118     case IR_CALLS:
 119       irt_setmark(IR(ir->op1)->t);  /* Mark (potentially) stored values. */
 120       break;
 121     case IR_PHI: {
 122       IRIns *irl = IR(ir->op1), *irr = IR(ir->op2);
 123       irl->prev = irr->prev = 0;  /* Clear PHI value counts. */
 124       if (irl->o == irr->o &&
 125           (irl->o == IR_TNEW || irl->o == IR_TDUP ||
 126            (LJ_HASFFI && (irl->o == IR_CNEW || irl->o == IR_CNEWI))))
 127         break;
 128       irt_setmark(irl->t);
 129       irt_setmark(irr->t);
 130       break;
 131       }
 132     default:
 133       if (irt_ismarked(ir->t) || irt_isguard(ir->t)) {  /* Propagate mark. */
 134         if (ir->op1 >= REF_FIRST) irt_setmark(IR(ir->op1)->t);
 135         if (ir->op2 >= REF_FIRST) irt_setmark(IR(ir->op2)->t);
 136       }
 137       break;
 138     }
 139   }
 140 }
 141
 142 /* Mark all instructions referenced by a snapshot. */
 143 static void sink_mark_snap(jit_State *J, SnapShot *snap)
 144 {
 145   SnapEntry *map = &J->cur.snapmap[snap->mapofs];
 146   MSize n, nent = snap->nent;
 147   for (n = 0; n < nent; n++) {
 148     IRRef ref = snap_ref(map[n]);
 149     if (!irref_isk(ref))
 150       irt_setmark(IR(ref)->t);
 151   }
 152 }
 153
 154 /* Iteratively remark PHI refs with differing marks or PHI value counts. */
 155 static void sink_remark_phi(jit_State *J)
 156 {
 157   IRIns *ir;
 158   int remark;
 159   do {
 160     remark = 0;
 161     for (ir = IR(J->cur.nins-1); ir->o == IR_PHI; ir--) {
 162       IRIns *irl = IR(ir->op1), *irr = IR(ir->op2);
 163       if (!((irl->t.irt ^ irr->t.irt) & IRT_MARK) && irl->prev == irr->prev)
 164         continue;
 165       remark |= (~(irl->t.irt & irr->t.irt) & IRT_MARK);
 166       irt_setmark(IR(ir->op1)->t);
 167       irt_setmark(IR(ir->op2)->t);
 168     }
 169   } while (remark);
 170 }
 171
 172 /* Sweep instructions and tag sunken allocations and stores. */
 173 static void sink_sweep_ins(jit_State *J)
 174 {
 175   IRIns *ir, *irbase = IR(REF_BASE);
 176   for (ir = IR(J->cur.nins-1) ; ir >= irbase; ir--) {
 177     switch (ir->o) {
 178     case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: {
 179       IRIns *ira = sink_checkalloc(J, ir);
 180       if (ira && !irt_ismarked(ira->t)) {
 181         int delta = (int)(ir - ira);
 182         ir->prev = REGSP(RID_SINK, delta > 255 ? 255 : delta);
 183       } else {
 184         ir->prev = REGSP_INIT;
 185       }
 186       break;
 187       }
 188     case IR_NEWREF:
 189       if (!irt_ismarked(IR(ir->op1)->t)) {
 190         ir->prev = REGSP(RID_SINK, 0);
 191       } else {
 192         irt_clearmark(ir->t);
 193         ir->prev = REGSP_INIT;
 194       }
 195       break;
 196 #if LJ_HASFFI
 197     case IR_CNEW: case IR_CNEWI:
 198 #endif
 199     case IR_TNEW: case IR_TDUP:
 200       if (!irt_ismarked(ir->t)) {
 201         ir->t.irt &= ~IRT_GUARD;
 202         ir->prev = REGSP(RID_SINK, 0);
 203         J->cur.sinktags = 1;  /* Signal present SINK tags to assembler. */
 204       } else {
 205         irt_clearmark(ir->t);
 206         ir->prev = REGSP_INIT;
 207       }
 208       break;
 209     case IR_PHI: {
 210       IRIns *ira = IR(ir->op2);
 211       if (!irt_ismarked(ira->t) &&
 212           (ira->o == IR_TNEW || ira->o == IR_TDUP ||
 213            (LJ_HASFFI && (ira->o == IR_CNEW || ira->o == IR_CNEWI)))) {
 214         ir->prev = REGSP(RID_SINK, 0);
 215       } else {
 216         ir->prev = REGSP_INIT;
 217       }
 218       break;
 219       }
 220     default:
 221       irt_clearmark(ir->t);
 222       ir->prev = REGSP_INIT;
 223       break;
 224     }
 225   }
 226   for (ir = IR(J->cur.nk); ir < irbase; ir++) {
 227     irt_clearmark(ir->t);
 228     ir->prev = REGSP_INIT;
 229     /* The false-positive of irt_is64() for ASMREF_L (REF_NIL) is OK here. */
 230     if (irt_is64(ir->t) && ir->o != IR_KNULL)
 231       ir++;
 232   }
 233 }
 234
 235 /* Allocation sinking and store sinking.
 236 **
 237 ** 1. Mark all non-sinkable allocations.
 238 ** 2. Then sink all remaining allocations and the related stores.
 239 */
 240 void lj_opt_sink(jit_State *J)
 241 {
 242   const uint32_t need = (JIT_F_OPT_SINK|JIT_F_OPT_FWD|
 243                          JIT_F_OPT_DCE|JIT_F_OPT_CSE|JIT_F_OPT_FOLD);
 244   if ((J->flags & need) == need &&
 245       (J->chain[IR_TNEW] || J->chain[IR_TDUP] ||
 246        (LJ_HASFFI && (J->chain[IR_CNEW] || J->chain[IR_CNEWI])))) {
 247     if (!J->loopref)
 248       sink_mark_snap(J, &J->cur.snap[J->cur.nsnap-1]);
 249     sink_mark_ins(J);
 250     if (J->loopref)
 251       sink_remark_phi(J);
 252     sink_sweep_ins(J);
 253   }
 254 }
 255
 256 #undef IR
 257
 258 #endif