How to optimize the size of jump tables?

Question

Consider a typical enumeration type in a C-like language like this:

enum foo {
    FOO_A,
    FOO_B,
    FOO_C,
    /* ... */
    FOO_N
};

There are switch statement over values of type enum foo, possibly not handling certain enumeration values:

enum foo bar;
/* ... */
switch (bar) {
case FOO_A: /* ... */
case FOO_B: /* ... */
case FOO_D: /* ... */
case FOO_L: /* ... */
default: /* ... */
}

Now, for a sufficiently high amount of enumeration values handled, the compiler will to implement the switch statement using a jump table with size (<highest handled value> - <lowest handled value> + 1) * sizeof(void*).

Consider I have multiple such switch statements that are known to use jump tables, for each one is known which values are being handled and which values aren't. How can I reorder the values in enum foo in a way, that the total size of all jump tables generated is minimal?

Example

Here is a slightly simplified example which assumes that the compiler generates jump tables for all switch statements. This is the enumeration:

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D
};

And these are the two switch-statements:

enum example a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
default: /* ... */
}

For this example, the compiler would generate two jump tables with three entries each (in the first case from EX_A to EX_C, in the second case from EX_B to EX_D), amounting to a total of 6 machine words used for jump tables. If I did reorder the enumeration like this:

enum example {
    EX_A,
    EX_C,
    EX_B,
    EX_D
};

I would only need 4 data words for the jump tables.

Answer 1

This problem is NP-hard, because it generalizes the minimum linear arrangement problem (MinLA) from graphs to hypergraphs, and MinLA is NP-hard (Garey--Johnson--Stockmeyer 1976).

Some research has been done on solving MinLA, both exactly and approximately. There's a Theta(2^n m)-time dynamic program (Koren--Harel 2002) that looks generalizable. There's a lot of work on linear programming relaxations, both to obtain guaranteed approximations and for use in branch-and-bound. Unfortunately, these relaxations all seem to be rather too large for direct consumption by a solver. Probably someone's tried constraint programming, but my cursory searches turned up nothing. There are many heuristics, including the following cute idea due to Juvan and Mohar (1992): sort the labels according the second eigenvector of the Laplacian.

With only 50 labels, I wouldn't be surprised if a provably optimal arrangement could be found, but I would be surprised if it didn't take several rounds of novel algorithm design, implementation, and experiments on the instance(s) of interest. If you want to learn some of the techniques involved, I would recommend Pascal van Hentenryck's Discrete Optimization course on Coursera (I took an earlier version from when he was affiliated with Brown University).