westleyargentum / pass-optimizer Goto Github PK

Who optimizes the optimizers?

License: MIT License

C++ 92.32% Julia 7.56% Shell 0.12%

pass-optimizer's Introduction

IR Pass Optimizer

This is an ongoing project that uses a genetic algorithm to optimize the layout of LLVM IR passes used to compile Julia code.

Quick start

git clone https://github.com/WestleyArgentum/pass-optimizer.git
cd pass-optimizer
./init.sh
julia pass-ga.jl

Design of the GA

Crossover

Many traditional methods of crossover (single and double point, uniform) assume a genome of a fixed length, or some knowledge about what the optimal length might be. Others support variable length genomes (messy ga, SAGA), but pick largely random points when splicing parent sequences together.

The algorithm employed by this GA is called "Synapsing Variable Length Crossover". It uses the longest common subsequence to identify and split parents genomes in a way that preserves the order and content of the lcs shared by both parents. The paper that formally describes SVLC is behind a paywall, but you can read some here and the code in this repository represents my attempt at an accurate reproduction.

Mutation

Because this GA relies on variable length genomes, it's important for the mutation function to sometimes insert and remove genes, in addition to simply changing them in place. Right now this is done very agressively at first (with a large number of passes being added / removed / changed), and less agressively over time until the GA has reached a predefined MAX_GENERATIONS and stops.

Areas for improvement

Please see the open issues for information about planned improvments / known problems.

pass-optimizer's People

Contributors

Stargazers

Watchers

pass-optimizer's Issues

record percent crashed

and stick in a graph

create init script that sets up a users environment

by copying codegen.cpp, the makefile, etc, into the julia folder

add validation to randomly created / changed pass configurations

Very frequently, randomly generated passes result in combinations that will not run for various reasons (loop passes won't work because they're uninitialized, etc). Right now, all of these fail and are assigned a fitness of +inf. This dramatically reduces the actual combinations that are tested.

Potentially, a better alternative could be to add a validation / patching pass that looks for common problems and attempts to fix them. Maybe this would be cheating? But it might be effective.

change crossover to split randomly when LCS is short

When entities have relatively little in common we should be trying to discover and preserve the good chunks of each. Hopefully this will help with early convergence too.

start using functions from benchmark utils in the ga

create types for use during analysis, instead of relying on method names

run_stats could produce an instance of a type and visualize_run_stats could be visualize(stats::RunStats), etc

better error handling when looking up functions

https://github.com/WestleyArgentum/pass-optimizer/blob/master/codegen/pass_setup.cpp#L100

Probably seg-faulting when the function we want doesn't exist is bad

break types out of the ga file so that they can be used during analysis

add comparison of best entities against best known pass layout to analyze script

to make it easy to really evaluate the results (in case the entity score doesn't totally work between runs)

improve corpus used to calculate fitness

Right now the micro-benchmarks that come with Julia are used to evaluate the fitness (speed) of pass layouts. This has a bunch of potential problems, and raises some interesting questions.

Should we try to find a layout that optimizes naively-written julia well?
Or should we focus on finding one that makes julia written to be performant as fast as possible?
Will the best layout be the same in both cases?

Is it possible to come up with a small, relatively quick-running set of benchmarks that would still be representative as fitness tests? Because the algorithm has to run fitness test one-by-one, this could help tremendously with speeding up the search.

tone down mutation, or scale it over time better
don't mutate entities that were passed through because of elitism