aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2017-09-07 17:51:43 +0200
committerBjörn Gustavsson <[email protected]>2017-09-14 10:16:15 +0200
commita8e391f3baf2cfbcfa57e46d4cfe95c089921100 (patch)
tree7e443b378e6b2b818d802028c0a44629ac9d344e /erts
parentcfe29c3386477b76a1daf4d631b1178dc7359a40 (diff)
downloadotp-a8e391f3baf2cfbcfa57e46d4cfe95c089921100.tar.gz
otp-a8e391f3baf2cfbcfa57e46d4cfe95c089921100.tar.bz2
otp-a8e391f3baf2cfbcfa57e46d4cfe95c089921100.zip
Rewrite select_val_bins so that its labels can be packed
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/beam_debug.c16
-rw-r--r--erts/emulator/beam/beam_load.c52
-rw-r--r--erts/emulator/beam/select_instrs.tab19
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);