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.

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