Locally optimal optimisation of code fragments
If we assume a code fragment of 4 instructions of 32 bit each and the two input registers to be 32 bit then we have: 2324 * 232 * 232 possible combinations of code and data. This number is so large that there is no hope of testing all possible combinations to verify that two different code fragments give the same result for all possible input. The search space is practically infinite.
Boolean logic is different from arithmetic in that every bit is computed completely independently from the others. So it makes no difference if we use the full 32 bit or just one bit, changing the value of one bit will never affect the others. That means we now have 2324 * 21 * 21 possible combinations of code and data, a huge improvement but still impossibly large. So it is clear that using brute force alone will not work.
Since we now have reduced the input to two bits then there are just 22 = 4 possible inputs.
A B 0 0 0 1 1 0 1 1
since the result of each input is either 0 or 1 then all possible outputs from the function fits in 4 bits and we can write down the result of the function in a separate column and we have what is called a truth table. For the Eor function (T = A EOR B) it would be:
A B T 0 0 0 0 1 1 1 0 1 1 1 0
The truth column T contains omly 4 bits so we have exactly 24 = 16 possible boolean functions with two inputs. So out of all those trillions of code fragments there are only 16 unique functions and from that it follows that it must exist 16 unique code fragments that that have no shorter equivalents.
If we can find those 16 optimal code fragments and find a mapping between all possible code fragments and those optimal code fragments we can use a small look up table to optimise all code fragments.
The truth table is that mapping, it tells exaclty what the code does without any influence by how it is done.
1111010011110000 B C A D not or or and not
Generating the truth table
T = (not ((((not D) or A) or C) and B))
A B C D T 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0
Generate the truth table in parallel
A 0000000011111111 B 0000111100001111 C 0011001100110011 D 0101010101010101 T 1111010011110000
Discovering the optimal code fragments
Since the search space is too large to even imagine we have to be efficient and search where it is most likely we will find the code fragments.
To find the shortest code we start the search with the shortest code fragments and make them longer and longer, that way the first one we find for a given truth table is the shortest or that there is no shorter ones.
v1 |v2 |v3 |v4 | ¬((¬v4||v1||v3)&&v2)
1 | 1 | 1 | 1 | 0 1 | 1 | 1 | 0 | 0 1 | 1 | 0 | 1 | 0 1 | 1 | 0 | 0 | 0 1 | 0 | 1 | 1 | 1 1 | 0 | 1 | 0 | 1 1 | 0 | 0 | 1 | 1 1 | 0 | 0 | 0 | 1 0 | 1 | 1 | 1 | 0 0 | 1 | 1 | 0 | 0 0 | 1 | 0 | 1 | 1 0 | 1 | 0 | 0 | 0 0 | 0 | 1 | 1 | 1 0 | 0 | 1 | 0 | 1 0 | 0 | 0 | 1 | 1 0 | 0 | 0 | 0 | 1
