Randomize penalties for aborts and add blacklisting.

6 files changed, 50 insertions, 23 deletions

diff --git a/doc/running.html b/doc/running.html
index 247457d6..bc09d9e5 100644
--- a/doc/running.html
+++ b/doc/running.html
@@ -203,7 +203,7 @@ Here are the parameters and their default settings:
 <tr class="odd">
 <td class="param_name">maxsnap</td><td class="param_default">100</td><td class="param_desc">Max. number of snapshots for a trace</td></tr>
 <tr class="even separate">
-<td class="param_name">hotloop</td><td class="param_default">57</td><td class="param_desc">Number of iterations to detect a hot loop</td></tr>
+<td class="param_name">hotloop</td><td class="param_default">56</td><td class="param_desc">Number of iterations to detect a hot loop or hot call</td></tr>
 <tr class="odd">
 <td class="param_name">hotexit</td><td class="param_default">10</td><td class="param_desc">Number of taken exits to start a side trace</td></tr>
 <tr class="even">
@@ -214,9 +214,11 @@ Here are the parameters and their default settings:
 <td class="param_name">loopunroll</td><td class="param_default">7</td><td class="param_desc">Max. unroll factor for loop ops in side traces</td></tr>
 <tr class="odd">
 <td class="param_name">callunroll</td><td class="param_default">3</td><td class="param_desc">Max. unroll factor for pseudo-recursive calls</td></tr>
-<tr class="even separate">
+<tr class="even">
+<td class="param_name">recunroll</td><td class="param_default">2</td><td class="param_desc">Min. unroll factor for true recursion</td></tr>
+<tr class="odd separate">
 <td class="param_name">sizemcode</td><td class="param_default">32</td><td class="param_desc">Size of each machine code area in KBytes (Windows: 64K)</td></tr>
-<tr class="odd">
+<tr class="even">
 <td class="param_name">maxmcode</td><td class="param_default">512</td><td class="param_desc">Max. total size of all machine code areas in KBytes</td></tr>
 </table>
 <br class="flush">
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	16
+#define PENALTY_SLOTS	64	/* Penalty cache slot. Must be a power of 2. */
+#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. */
-static void hotpenalty(jit_State *J, const BCIns *pc, TraceError e)
+/* Penalize a bytecode instruction. */
+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) {
-      val = ((uint32_t)J->penalty[i].val << 1) + 1;
-      if (val > HOTCOUNT_MAX_PENALTY) val = HOTCOUNT_MAX_PENALTY;
+    if (mref(J->penalty[i].pc, const BCIns) == pc) {  /* Cache slot found? */
+      /* First try to bump its hotcount several times. */
+      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")