Locally optimal optimisation of code fragments

A 32 bit CPU

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 computation of 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 impossobly large.

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