root/lj_opt_sink.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. sink_checkalloc
  2. sink_phidep
  3. sink_checkphi
  4. sink_mark_ins
  5. sink_mark_snap
  6. sink_remark_phi
  7. sink_sweep_ins
  8. lj_opt_sink

   1 /*
   2 ** SINK: Allocation Sinking and Store Sinking.
   3 ** Copyright (C) 2005-2017 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)
  40 {
  41   IRIns *ir = IR(ref);
  42   if (irt_isphi(ir->t)) return 1;
  43   if (ir->op1 >= REF_FIRST && sink_phidep(J, ir->op1)) return 1;
  44   if (ir->op2 >= REF_FIRST && sink_phidep(J, ir->op2)) return 1;
  45   return 0;
  46 }
  47 
  48 /* Check whether a value is a sinkable PHI or loop-invariant. */
  49 static int sink_checkphi(jit_State *J, IRIns *ira, IRRef ref)
  50 {
  51   if (ref >= REF_FIRST) {
  52     IRIns *ir = IR(ref);
  53     if (irt_isphi(ir->t) || (ir->o == IR_CONV && ir->op2 == IRCONV_NUM_INT &&
  54                              irt_isphi(IR(ir->op1)->t))) {
  55       ira->prev++;
  56       return 1;  /* Sinkable PHI. */
  57     }
  58     /* Otherwise the value must be loop-invariant. */
  59     return ref < J->loopref && !sink_phidep(J, ref);
  60   }
  61   return 1;  /* Constant (non-PHI). */
  62 }
  63 
  64 /* Mark non-sinkable allocations using single-pass backward propagation.
  65 **
  66 ** Roots for the marking process are:
  67 ** - Some PHIs or snapshots (see below).
  68 ** - Non-PHI, non-constant values stored to PHI allocations.
  69 ** - All guards.
  70 ** - Any remaining loads not eliminated by store-to-load forwarding.
  71 ** - Stores with non-constant keys.
  72 ** - All stored values.
  73 */
  74 static void sink_mark_ins(jit_State *J)
  75 {
  76   IRIns *ir, *irlast = IR(J->cur.nins-1);
  77   for (ir = irlast ; ; ir--) {
  78     switch (ir->o) {
  79     case IR_BASE:
  80       return;  /* Finished. */
  81     case IR_CALLL:  /* IRCALL_lj_tab_len */
  82     case IR_ALOAD: case IR_HLOAD: case IR_XLOAD: case IR_TBAR:
  83       irt_setmark(IR(ir->op1)->t);  /* Mark ref for remaining loads. */
  84       break;
  85     case IR_FLOAD:
  86       if (irt_ismarked(ir->t) || ir->op2 == IRFL_TAB_META)
  87         irt_setmark(IR(ir->op1)->t);  /* Mark table for remaining loads. */
  88       break;
  89     case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: {
  90       IRIns *ira = sink_checkalloc(J, ir);
  91       if (!ira || (irt_isphi(ira->t) && !sink_checkphi(J, ira, ir->op2)))
  92         irt_setmark(IR(ir->op1)->t);  /* Mark ineligible ref. */
  93       irt_setmark(IR(ir->op2)->t);  /* Mark stored value. */
  94       break;
  95       }
  96 #if LJ_HASFFI
  97     case IR_CNEWI:
  98       if (irt_isphi(ir->t) &&
  99           (!sink_checkphi(J, ir, ir->op2) ||
 100            (LJ_32 && ir+1 < irlast && (ir+1)->o == IR_HIOP &&
 101             !sink_checkphi(J, ir, (ir+1)->op2))))
 102         irt_setmark(ir->t);  /* Mark ineligible allocation. */
 103       /* fallthrough */
 104 #endif
 105     case IR_USTORE:
 106       irt_setmark(IR(ir->op2)->t);  /* Mark stored value. */
 107       break;
 108 #if LJ_HASFFI
 109     case IR_CALLXS:
 110 #endif
 111     case IR_CALLS:
 112       irt_setmark(IR(ir->op1)->t);  /* Mark (potentially) stored values. */
 113       break;
 114     case IR_PHI: {
 115       IRIns *irl = IR(ir->op1), *irr = IR(ir->op2);
 116       irl->prev = irr->prev = 0;  /* Clear PHI value counts. */
 117       if (irl->o == irr->o &&
 118           (irl->o == IR_TNEW || irl->o == IR_TDUP ||
 119            (LJ_HASFFI && (irl->o == IR_CNEW || irl->o == IR_CNEWI))))
 120         break;
 121       irt_setmark(irl->t);
 122       irt_setmark(irr->t);
 123       break;
 124       }
 125     default:
 126       if (irt_ismarked(ir->t) || irt_isguard(ir->t)) {  /* Propagate mark. */
 127         if (ir->op1 >= REF_FIRST) irt_setmark(IR(ir->op1)->t);
 128         if (ir->op2 >= REF_FIRST) irt_setmark(IR(ir->op2)->t);
 129       }
 130       break;
 131     }
 132   }
 133 }
 134 
 135 /* Mark all instructions referenced by a snapshot. */
 136 static void sink_mark_snap(jit_State *J, SnapShot *snap)
 137 {
 138   SnapEntry *map = &J->cur.snapmap[snap->mapofs];
 139   MSize n, nent = snap->nent;
 140   for (n = 0; n < nent; n++) {
 141     IRRef ref = snap_ref(map[n]);
 142     if (!irref_isk(ref))
 143       irt_setmark(IR(ref)->t);
 144   }
 145 }
 146 
 147 /* Iteratively remark PHI refs with differing marks or PHI value counts. */
 148 static void sink_remark_phi(jit_State *J)
 149 {
 150   IRIns *ir;
 151   int remark;
 152   do {
 153     remark = 0;
 154     for (ir = IR(J->cur.nins-1); ir->o == IR_PHI; ir--) {
 155       IRIns *irl = IR(ir->op1), *irr = IR(ir->op2);
 156       if (!((irl->t.irt ^ irr->t.irt) & IRT_MARK) && irl->prev == irr->prev)
 157         continue;
 158       remark |= (~(irl->t.irt & irr->t.irt) & IRT_MARK);
 159       irt_setmark(IR(ir->op1)->t);
 160       irt_setmark(IR(ir->op2)->t);
 161     }
 162   } while (remark);
 163 }
 164 
 165 /* Sweep instructions and tag sunken allocations and stores. */
 166 static void sink_sweep_ins(jit_State *J)
 167 {
 168   IRIns *ir, *irfirst = IR(J->cur.nk);
 169   for (ir = IR(J->cur.nins-1) ; ir >= irfirst; ir--) {
 170     switch (ir->o) {
 171     case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: {
 172       IRIns *ira = sink_checkalloc(J, ir);
 173       if (ira && !irt_ismarked(ira->t)) {
 174         int delta = (int)(ir - ira);
 175         ir->prev = REGSP(RID_SINK, delta > 255 ? 255 : delta);
 176       } else {
 177         ir->prev = REGSP_INIT;
 178       }
 179       break;
 180       }
 181     case IR_NEWREF:
 182       if (!irt_ismarked(IR(ir->op1)->t)) {
 183         ir->prev = REGSP(RID_SINK, 0);
 184       } else {
 185         irt_clearmark(ir->t);
 186         ir->prev = REGSP_INIT;
 187       }
 188       break;
 189 #if LJ_HASFFI
 190     case IR_CNEW: case IR_CNEWI:
 191 #endif
 192     case IR_TNEW: case IR_TDUP:
 193       if (!irt_ismarked(ir->t)) {
 194         ir->t.irt &= ~IRT_GUARD;
 195         ir->prev = REGSP(RID_SINK, 0);
 196         J->cur.sinktags = 1;  /* Signal present SINK tags to assembler. */
 197       } else {
 198         irt_clearmark(ir->t);
 199         ir->prev = REGSP_INIT;
 200       }
 201       break;
 202     case IR_PHI: {
 203       IRIns *ira = IR(ir->op2);
 204       if (!irt_ismarked(ira->t) &&
 205           (ira->o == IR_TNEW || ira->o == IR_TDUP ||
 206            (LJ_HASFFI && (ira->o == IR_CNEW || ira->o == IR_CNEWI)))) {
 207         ir->prev = REGSP(RID_SINK, 0);
 208       } else {
 209         ir->prev = REGSP_INIT;
 210       }
 211       break;
 212       }
 213     default:
 214       irt_clearmark(ir->t);
 215       ir->prev = REGSP_INIT;
 216       break;
 217     }
 218   }
 219 }
 220 
 221 /* Allocation sinking and store sinking.
 222 **
 223 ** 1. Mark all non-sinkable allocations.
 224 ** 2. Then sink all remaining allocations and the related stores.
 225 */
 226 void lj_opt_sink(jit_State *J)
 227 {
 228   const uint32_t need = (JIT_F_OPT_SINK|JIT_F_OPT_FWD|
 229                          JIT_F_OPT_DCE|JIT_F_OPT_CSE|JIT_F_OPT_FOLD);
 230   if ((J->flags & need) == need &&
 231       (J->chain[IR_TNEW] || J->chain[IR_TDUP] ||
 232        (LJ_HASFFI && (J->chain[IR_CNEW] || J->chain[IR_CNEWI])))) {
 233     if (!J->loopref)
 234       sink_mark_snap(J, &J->cur.snap[J->cur.nsnap-1]);
 235     sink_mark_ins(J);
 236     if (J->loopref)
 237       sink_remark_phi(J);
 238     sink_sweep_ins(J);
 239   }
 240 }
 241 
 242 #undef IR
 243 
 244 #endif

/* [<][>][^][v][top][bottom][index][help] */