Rewrite select_val_bins so that its labels can be packed

3 files changed, 24 insertions, 63 deletions

diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c
index 9ba65e2464..df152f1605 100644
--- a/erts/emulator/beam/beam_debug.c
+++ b/erts/emulator/beam/beam_debug.c
@@ -632,6 +632,8 @@ print_op(fmtfn_t to, void *to_arg, int op, int size, BeamInstr* addr)
     switch (op) {
     case op_i_select_val_lins_xfI:
     case op_i_select_val_lins_yfI:
+    case op_i_select_val_bins_xfI:
+    case op_i_select_val_bins_yfI:
 	{
 	    int n = ap[-1];
 	    int ix = n;
@@ -651,20 +653,6 @@ print_op(fmtfn_t to, void *to_arg, int op, int size, BeamInstr* addr)
             size += (n+1) / 2;
 	}
 	break;
-    case op_i_select_val_bins_xfI:
-    case op_i_select_val_bins_yfI:
-	{
-	    int n = ap[-1];
-
-	    while (n > 0) {
-                BeamInstr* target = f_to_addr(addr, op, ap+1);
-		erts_print(to, to_arg, "%T f(" HEXF ") ", (Eterm) ap[0], target);
-		ap += 2;
-		size += 2;
-		n--;
-	    }
-	}
-	break;
     case op_i_select_tuple_arity_xfI:
     case op_i_select_tuple_arity_yfI:
         {
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 9bb5866cb3..944ff7bc4c 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -4039,7 +4039,6 @@ gen_select_val(LoaderState* stp, GenOpArg S, GenOpArg Fail,
     int i, j, align = 0;
 
     if (size == 2) {
-
 	/*
 	 * Use a special-cased instruction if there are only two values.
 	 */
@@ -4056,47 +4055,19 @@ gen_select_val(LoaderState* stp, GenOpArg S, GenOpArg Fail,
 	op->a[5] = Rest[3];
 
 	return op;
-
-    } else if (size > 10) {
-
-	/* binary search instruction */
-
-	NEW_GENOP(stp, op);
-	op->next = NULL;
-	op->op = genop_i_select_val_bins_3;
-	GENOP_ARITY(op, arity);
-	op->a[0] = S;
-	op->a[1] = Fail;
-	op->a[2].type = TAG_u;
-	op->a[2].val = size;
-	for (i = 3; i < arity; i++) {
-	    op->a[i] = Rest[i-3];
-	}
-
-	/*
-	 * Sort the values to make them useful for a binary search.
-	 */
-
-	qsort(op->a+3, size, 2*sizeof(GenOpArg),
-		(int (*)(const void *, const void *)) genopargcompare);
-#ifdef DEBUG
-	for (i = 3; i < arity-2; i += 2) {
-	    ASSERT(op->a[i].val < op->a[i+2].val);
-	}
-#endif
-	return op;
     }
 
-    /* linear search instruction */
-
-    align = 1;
+    if (size <= 10) {
+        /* Use linear search. Reserve place for a sentinel. */
+        align = 1;
+    }
 
     arity += 2*align;
     size  += align;
 
     NEW_GENOP(stp, op);
     op->next = NULL;
-    op->op = genop_i_select_val_lins_3;
+    op->op = (align == 0) ? genop_i_select_val_bins_3 : genop_i_select_val_lins_3;
     GENOP_ARITY(op, arity);
     op->a[0] = S;
     op->a[1] = Fail;
@@ -4110,7 +4081,7 @@ gen_select_val(LoaderState* stp, GenOpArg S, GenOpArg Fail,
     }
 
     /*
-     * Sort the values to make them useful for a sentinel search
+     * Sort the values to make them useful for a binary or sentinel search.
      */
 
     qsort(tmp, size - align, 2*sizeof(GenOpArg),
@@ -4125,11 +4096,12 @@ gen_select_val(LoaderState* stp, GenOpArg S, GenOpArg Fail,
 
     erts_free(ERTS_ALC_T_LOADER_TMP, (void *) tmp);
 
-    /* add sentinel */
-
-    op->a[j].type = TAG_u;
-    op->a[j].val  = ~((BeamInstr)0);
-    op->a[j+size] = Fail;
+    if (align) {
+        /* Add sentinel for linear search. */
+        op->a[j].type = TAG_u;
+        op->a[j].val  = ~((BeamInstr)0);
+        op->a[j+size] = Fail;
+    }
 
 #ifdef DEBUG
     for (i = 0; i < size - 1; i++) {
diff --git a/erts/emulator/beam/select_instrs.tab b/erts/emulator/beam/select_instrs.tab
index 6b59f02925..4a8d9cce96 100644
--- a/erts/emulator/beam/select_instrs.tab
+++ b/erts/emulator/beam/select_instrs.tab
@@ -30,16 +30,15 @@ select_val_bins.fetch(Src) {
 }
 
 select_val_bins.select(Fail, NumElements) {
-    struct Pairs {
+    struct Singleton {
         BeamInstr val;
-        Eterm offset;
     };
-    struct Pairs* low;
-    struct Pairs* high;
-    struct Pairs* mid;
+    struct Singleton* low;
+    struct Singleton* high;
+    struct Singleton* mid;
     int bdiff; /* int not long because the arrays aren't that large */
 
-    low = (struct Pairs *) (&$NumElements + 1);
+    low = (struct Singleton *) ($NEXT_INSTRUCTION);
     high = low + $NumElements;
 
     /* The pointer subtraction (high-low) below must produce
@@ -60,15 +59,17 @@ select_val_bins.select(Fail, NumElements) {
      *
      */
     while ((bdiff = (int)((char*)high - (char*)low)) > 0) {
-        unsigned int boffset = ((unsigned int)bdiff >> 1) & ~(sizeof(struct Pairs)-1);
+        unsigned int boffset = ((unsigned int)bdiff >> 1) & ~(sizeof(struct Singleton)-1);
 
-        mid = (struct Pairs*)((char*)low + boffset);
+        mid = (struct Singleton*)((char*)low + boffset);
         if (select_val < mid->val) {
             high = mid;
         } else if (select_val > mid->val) {
             low = mid + 1;
         } else {
-            $JUMP(mid->offset);
+            Sint32* jump_tab = (Sint32 *) ($NEXT_INSTRUCTION + $NumElements);
+            Sint32 offset = jump_tab[mid - (struct Singleton *)($NEXT_INSTRUCTION)];
+            $JUMP(offset);
         }
     }
     $JUMP($Fail);