Randomize penalties for aborts and add blacklisting.

author: Mike Pall <mike> 2010-02-23 18:27:39 +0100
committer: Mike Pall <mike> 2010-02-23 19:41:32 +0100
commit: 8ae2f9feaaed874e01a87df6646242b80acceabb (patch)
tree: 0c0e030b007a4ef5b663476f4142f1f860ee3675 /src
parent: d5c8fe4b90c54cbd03924d3eaf04d83dcf2f3cb8 (diff)
download: luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.tar.gz
luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.tar.bz2
luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.zip
5 files changed, 45 insertions, 20 deletions
diff --git a/src/lj_dispatch.h b/src/lj_dispatch.h
index 1aa7dae0..5ef9dcd4 100644
--- a/src/lj_dispatch.h
+++ b/src/lj_dispatch.h
@@ -19,8 +19,6 @@ typedef uint16_t HotCount;
 /* Number of hot counter hash table entries (must be a power of two). */
 #define HOTCOUNT_SIZE           64
 #define HOTCOUNT_PCMASK         ((HOTCOUNT_SIZE-1)*sizeof(HotCount))
-#define HOTCOUNT_MIN_PENALTY    103
-#define HOTCOUNT_MAX_PENALTY    60000
 /* This solves a circular dependency problem -- bump as needed. Sigh. */
 #define GG_NUM_ASMFF    62
diff --git a/src/lj_jit.h b/src/lj_jit.h
index 18069ac9..23adf30d 100644
--- a/src/lj_jit.h
+++ b/src/lj_jit.h
@@ -69,14 +69,14 @@
  _(\007, maxside,      100)    /* Max. # of side traces of a root trace. */ \
  _(\007, maxsnap,      100)    /* Max. # of snapshots for a trace. */ \
  \
-  _(\007, hotloop,      57)     /* # of iterations to detect a hot loop. */ \
+  _(\007, hotloop,      56)     /* # of iter. to detect a hot loop/call. */ \
  _(\007, hotexit,      10)     /* # of taken exits to start a side trace. */ \
  _(\007, tryside,      4)      /* # of attempts to compile a side trace. */ \
  \
  _(\012, instunroll,   4)      /* Max. unroll for instable loops. */ \
  _(\012, loopunroll,   7)      /* Max. unroll for loop ops in side traces. */ \
  _(\012, callunroll,   3)      /* Max. unroll for recursive calls. */ \
-  _(\011, recunroll,    2)      /* Max. unroll for true recursion. */ \
+  _(\011, recunroll,    2)      /* Min. unroll for true recursion. */ \
  \
  /* Size of each machine code area (in KBytes). */ \
  _(\011, sizemcode,    JIT_P_sizemcode_DEFAULT) \
@@ -181,13 +181,15 @@ typedef struct Trace {
 /* Round-robin penalty cache for bytecodes leading to aborted traces. */
 typedef struct HotPenalty {
-  const BCIns *pc;      /* Starting bytecode PC. */
+  MRef pc;              /* Starting bytecode PC. */
  uint16_t val;         /* Penalty value, i.e. hotcount start. */
  uint16_t reason;      /* Abort reason (really TraceErr). */
 } HotPenalty;
-/* Number of slots for the penalty cache. Must be a power of 2. */
+#define PENALTY_SLOTS   64      /* Penalty cache slot. Must be a power of 2. */
-#define PENALTY_SLOTS   16
+#define PENALTY_MIN     36      /* Minimum penalty value. */
+#define PENALTY_MAX     60000   /* Maximum penalty value. */
+#define PENALTY_RNDBITS 4       /* # of random bits to add to penalty value. */
 /* Round-robin backpropagation cache for narrowing conversions. */
 typedef struct BPropEntry {
@@ -264,6 +266,7 @@ typedef struct jit_State {
  HotPenalty penalty[PENALTY_SLOTS];  /* Penalty slots. */
  uint32_t penaltyslot; /* Round-robin index into penalty slots. */
+  uint32_t prngstate;   /* PRNG state for penalty randomization. */
  BPropEntry bpropcache[BPROP_SLOTS];  /* Backpropagation cache slots. */
  uint32_t bpropslot;   /* Round-robin index into bpropcache slots. */
diff --git a/src/lj_record.c b/src/lj_record.c
index 2b63b87d..1ef01386 100644
--- a/src/lj_record.c
+++ b/src/lj_record.c
@@ -419,9 +419,9 @@ static int innerloopleft(jit_State *J, const BCIns *pc)
 {
  ptrdiff_t i;
  for (i = 0; i < PENALTY_SLOTS; i++)
-    if (J->penalty[i].pc == pc) {
+    if (mref(J->penalty[i].pc, const BCIns) == pc) {
      if (J->penalty[i].reason == LJ_TRERR_LLEAVE &&
-          J->penalty[i].val >= 2*HOTCOUNT_MIN_PENALTY)
+          J->penalty[i].val >= 2*PENALTY_MIN)
        return 1;
      break;
    }
@@ -2149,7 +2149,7 @@ void lj_record_ins(jit_State *J)
  case BC_ILOOP:
  case BC_IFUNCF:
  case BC_IFUNCV:
-    lj_trace_err(J, LJ_TRERR_LBLACKL);
+    lj_trace_err(J, LJ_TRERR_BLACKL);
    break;
  case BC_JMP:
diff --git a/src/lj_trace.c b/src/lj_trace.c
index 43104be6..6f63c945 100644
--- a/src/lj_trace.c
+++ b/src/lj_trace.c
@@ -294,27 +294,50 @@ void lj_trace_freestate(global_State *g)
  lj_mem_freevec(g, J->trace, J->sizetrace, Trace *);
 }
-/* -- Trace compiler state machine ---------------------------------------- */
+/* -- Penalties and blacklisting ------------------------------------------ */
+/* Trivial PRNG for randomization of penalties. */
+static uint32_t penalty_prng(jit_State *J, int bits)
+{
+  /* Yes, this LCG is very weak, but that doesn't matter for our use case. */
+  J->prngstate = J->prngstate * 1103515245 + 12345;
+  return J->prngstate >> (32-bits);
+}
+/* Blacklist a bytecode instruction. */
+static void blacklist_pc(GCproto *pt, BCIns *pc)
+{
+  setbc_op(pc, (int)bc_op(*pc)+(int)BC_ILOOP-(int)BC_LOOP);
+  pt->flags |= PROTO_HAS_ILOOP;
+}
-/* Penalize a bytecode instruction by bumping its hot counter. */
+/* Penalize a bytecode instruction. */
-static void hotpenalty(jit_State *J, const BCIns *pc, TraceError e)
+static void penalty_pc(jit_State *J, GCproto *pt, BCIns *pc, TraceError e)
 {
-  uint32_t i, val = HOTCOUNT_MIN_PENALTY;
+  uint32_t i, val = PENALTY_MIN;
  for (i = 0; i < PENALTY_SLOTS; i++)
-    if (J->penalty[i].pc == pc) {
+    if (mref(J->penalty[i].pc, const BCIns) == pc) {  /* Cache slot found? */
-      val = ((uint32_t)J->penalty[i].val << 1) + 1;
+      /* First try to bump its hotcount several times. */
-      if (val > HOTCOUNT_MAX_PENALTY) val = HOTCOUNT_MAX_PENALTY;
+      val = ((uint32_t)J->penalty[i].val << 1) +
+            penalty_prng(J, PENALTY_RNDBITS);
+      if (val > PENALTY_MAX) {
+        blacklist_pc(pt, pc);  /* Blacklist it, if that didn't help. */
+        return;
+      }
      goto setpenalty;
    }
+  /* Assign a new penalty cache slot. */
  i = J->penaltyslot;
  J->penaltyslot = (J->penaltyslot + 1) & (PENALTY_SLOTS-1);
-  J->penalty[i].pc = pc;
+  setmref(J->penalty[i].pc, pc);
 setpenalty:
  J->penalty[i].val = (uint16_t)val;
  J->penalty[i].reason = e;
  hotcount_set(J2GG(J), pc+1, val);
 }
+/* -- Trace compiler state machine ---------------------------------------- */
 /* Start tracing. */
 static void trace_start(jit_State *J)
 {
@@ -433,8 +456,9 @@ static int trace_abort(jit_State *J)
    J->state = LJ_TRACE_ASM;
    return 1;  /* Retry ASM with new MCode area. */
  }
+  /* Penalize or blacklist starting bytecode instruction. */
  if (J->parent == 0)
-    hotpenalty(J, J->startpc, e);  /* Penalize starting instruction. */
+    penalty_pc(J, &gcref(J->cur.startpt)->pt, (BCIns *)J->startpc, e);
  if (J->curtrace) {  /* Is there anything to abort? */
    ptrdiff_t errobj = savestack(L, L->top-1);  /* Stack may be resized. */
    lj_vmevent_send(L, TRACE,
diff --git a/src/lj_traceerr.h b/src/lj_traceerr.h
index abc53024..db7668fe 100644
--- a/src/lj_traceerr.h
+++ b/src/lj_traceerr.h
@@ -10,13 +10,13 @@ TREDEF(RECERR,	"error thrown or hook called during recording")
 TREDEF(TRACEOV, "trace too long")
 TREDEF(STACKOV, "trace too deep")
 TREDEF(SNAPOV,  "too many snapshots")
+TREDEF(BLACKL,  "blacklisted")
 TREDEF(NYIBC,   "NYI: bytecode %d")
 /* Recording loop ops. */
 TREDEF(LLEAVE,  "leaving loop in root trace")
 TREDEF(LINNER,  "inner loop in root trace")
 TREDEF(LUNROLL, "loop unroll limit reached")
-TREDEF(LBLACKL, "blacklisted loop")
 /* Recording calls/returns. */
 TREDEF(BADTYPE, "bad argument type")
author	Mike Pall <mike>	2010-02-23 18:27:39 +0100
committer	Mike Pall <mike>	2010-02-23 19:41:32 +0100
commit	8ae2f9feaaed874e01a87df6646242b80acceabb (patch)
tree	0c0e030b007a4ef5b663476f4142f1f860ee3675 /src
parent	d5c8fe4b90c54cbd03924d3eaf04d83dcf2f3cb8 (diff)
download	luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.tar.gz luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.tar.bz2 luajit-8ae2f9feaaed874e01a87df6646242b80acceabb.zip