Difference between revisions of "Locally optimal optimisation of code fragments"
(→The problem with optimal optimisation of code) |
|||
| Line 1: | Line 1: | ||
| + | A 32 bit CPU | ||
| + | |||
| + | |||
| + | |||
==The problem with optimal optimisation of code== | ==The problem with optimal optimisation of code== | ||
| − | For a CPU with an 8 bit instruction word there are 2<sup>8</sup> = 256 different instructions, a code fragment of 8 instructions | + | For a CPU with an 8 bit instruction word there are 2<sup>8</sup> = 256 different instructions, a code fragment of 8 instructions has 256<sup>8</sup> = 18 446 744 073 709 551 616 different combinations. A typical instruction has two 32 bit input registers so the total number of combinations code fragments and data is 256<sup>8</sup> * 2<sup>32</sup> * 2<sup>32</sup> = 340 282 366 920 938 463 463 374 607 431 768 211 456 |
Revision as of 06:00, 6 September 2013
A 32 bit CPU
The problem with optimal optimisation of code
For a CPU with an 8 bit instruction word there are 28 = 256 different instructions, a code fragment of 8 instructions has 2568 = 18 446 744 073 709 551 616 different combinations. A typical instruction has two 32 bit input registers so the total number of combinations code fragments and data is 2568 * 232 * 232 = 340 282 366 920 938 463 463 374 607 431 768 211 456
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
