Re: BFK - My brainf**k compiler
Posted: Mon Aug 08, 2011 12:18 pm
The way I planned to go about that particular optimization at the time was a quite general method. First of all I would find all innermost loops. For each one I'd check whether the number of < matches the number of >. If that is the case you can then simulate 1 iteration of the loop. For the loop to be optimizable it should decrease the square with index 0 by exactly 1. You can then use the result of that 1 iteration to determine what happens to all the other squares.
For example take the code.
Find all inner loops:
Count number of < and > and compare
Determine that the numbers match.
Simulating one iteration then gives:
Generate the actual code:
Hope that that gives the general idea.
For example take the code
Code: Select all
++++[->>+>++<<<]Find all inner loops:
Code: Select all
[->>+>++<<<]Code: Select all
[->>+>++<<<] >:3 <:3Simulating one iteration then gives:
Code: Select all
d[0] = -1;
d[1] = 0;
d[2] = 1;
d[3] = 2;
Code: Select all
d[1] += 0*d[0]; // Could be optimized away
d[2] += 1*d[0];
d[3] += 2*d[0];
d[0] = 0;