[RFC] improve string functions with evolutionary algorithms.

[OndÅej BÃlka <neleai at seznam dot cz>]

Hi,

I got idea from pipeline analysis discussion to use evolutionary
algorithm to improve performance. 

I wrote a simple optimizer that tries does randomly permutes instruction
sequence to determine best scheduling. It does relatively good job in
that, sometimes we gain %1 over existing implementation. 

There are two benefits of evolver, first is that without scheduling
constraints we can write code that is easier to review and then apply
evolver which keeps code semantics. (I could supply sequence of swaps of
adjacent instructions which do not interact and produce second
implementaion from first one.)

Second benefit is that we can do separate scheduling for each
architecture with nearly zero additional effort which could also give us
bit of performance.


What I do is relatively simple so there is room for improvement. Main
problem is that I do not know what is best representation. Instructions
for partial order and it should be somewhat better to work on it and
encode choices by inequalities that complete it to linear order but I do
not know how.

Second is limited knowledge of assembly we do not support control flow
and do not know how determine if instruction flags affect control flow.

Now I use EVOLVE_START EVOLVE_END blocks to mark basic blocks without
control flow instructions in them.

Second is that something could be gained by renaming registers but for
this I would need to analyze what registers are available in given basic
block.

Next problem is that I determined parameters by trial and error. I want
to add meta level that will also vary evolution parameters to get better results.

What also is not entirely clear is that I use evolver to optimize some
benchmark so we need to check if optimizations generalizes beyond that
benchmark.


An evolver is attached, I will send patches with optimizations if to 
see how successfull they will be.

Attachment: evolver.tar.bz2
Description: Binary data