Locally optimal optimisation of code fragments

The problem with optimal optimisation of code

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:

2³²⁴ * 2³² * 2³² = 6 277 101 735 386 680 763 835 789 423 207 666 416 102 355 444 464 034 512 896

possible combinations of code and data. This number is so large that there is no hope in using brute force to test all possible combinations or to verify that two different code fragments give the same result for all possible input.

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:

2³²⁴ * 2¹ * 2¹ = 1 361 129 467 683 753 853 853 498 429 727 072 845 824

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 2² = 4 possible input combinations.

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

Since the truth column T only contaqins 4 bits we have exactly 2⁴ = 16 possible boolean functions with two inputs. So out of all those trillions of code fragments there are only 16 unique ones and from that it follows that it must exist 16 code fragments that that have no shorter equivalent.

We assume 32 bit per variable All bits are completely independent from each other, that means we only have to consider the least significant bit. All other bits will behave the same.

Out of 14 190 004 558 696 programs generated only 64 974 were unique. That means that there must be 64 974 shortest code fragments, one for each function. If we can find a mapping between

1111010011110000 B C A D not or or and not (not ((((not D) or A) or C) and B))

Generate the truth table

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
 

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