Cool application. I had read about FM-Indexes a little bit, I find succinct data structures fascinating. Reading up on the new BMI instructions [-1] and "interpolative coding".
I was wondering if something like, "ISDL: An Instruction Set Description Language for Retargetability" [0] would help? It would be fun to create a combinatoric instruction sequencer and then run them all in an attempt to find some sort of probabilistic heuristic about instruction costs and efficiencies. Something like FFTW, but it analyzes then entire universe of possibilities. Some of the research in synthesizing new instruction sets or operating on compressed instructions might attack the problem from the other side [1].
Stay Fresh!
[-1] https://chessprogramming.wikispaces.com/BMI1
[0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.8...
[1] http://www.well.com/~cwf/pro/vita.html#Books (look for 'compress')
One application I'm thinking about right now is how to optimize "interpolative coding", which is a very tight way of compressing inverted indexes (better than Golomb/Rice/Elias), but so far very slow. It's not immediately obvious how vectorization can make it faster, but possibly some use of the BMI instructions should help, perhaps combined with a big lookup table. It's hard even to get close enough to the right form of solution that a superoptimizer can make headway.