Ensure loops optimize right at the LLVM level

[Gankra]

This involves 4 steps:

1. Gather up several different loop/iterator idioms that should optimize to e.g. memset/memcopy and run it through rustc -opt-level=0 --emit=llvm-ir
2. Feed the IR from step 1 into opt -O2 -print-before-all and grab the IR from before Recognize loop idioms
3. Write a LoopIdiomRecognize pass that handles the IR in step 2
4. Write codegen tests for rustc that verify that the idioms are being optimized to the right IR

CC @pcwalton

[Gankra]

@pcwalton has said their willing to mentor anyone who wants to take a crack at this.

[pcwalton]

Also check the benchmarks game benchmarks. I've heard things about LoopIdiomRecognize badness causing problems there.

[Gankra]

A lot of the things we want to guarantee optimize right:

• Vec::extend by a vec/slice or common iterator idioms
• Vec::from_iterator by a vec/slice or common iterator idioms
• ziping two iterators, particularly those of a vec/slice should ideally reduce to something good

This is an old gist I have of some test things when I was looking at solving this with TrustedLen (which is a bad idea IMO). Not all of these benches can clearly optimize well (e.g. they aren't a memcopy/memset, but rather creating (0..n) as a vec).

https://gist.github.com/Gankro/fd2543302dade5992e0e

[jnordwick]

I'll take a crack this weekend. I'll start with Ganko's benches and add anything from benchmark games that isn't already there.

[Gankra]

I've made a repo for minimally experimenting with Vec, RawVec, and some basic benches: https://github.com/Gankro/vec-perf-test

Note that the vec! macro still uses std's Vec, but that's fine since it always optimizes anyway.

Note that not all of these benches are expected to optimize well; in particular skip-take and take-skip make [1, 2, 3, ..] which can't be turned into a memcpy or memset to my knowledge.

[jnordwick]

I'm sending my scripts/command lines I use to generate the LLVM IR to pcwalton this weekend along with the output of a run so he can make sure I'm on the right path.

One of the problems I encountered was the deep inlining required when rust monomorphized a static lambda. It make it very difficult to pull out a few things and took considerable time to hunt down all the generated functions.

If anybody knows of a way to llvm-extract that will also pull out functions that the target depends on, that would be really helpful. -func="target" will only give you exactly what you ask for. Running over the entire output just gives too much.

So, I've taken to putting a single function in main() and dumping that up then running opt with -print-before-all and looking at the before loop idiom recognition sections that are generated,

[jnordwick]

Last note on this for now. I sent pcwalton the LLVM IR opt output for one of the cases and he said that LLVM wasn't getting enough hints to do anything with the loops (e.g., it couldn't turn them into bounded loops and optimize from there). So we just need to push more hinting to LLVM, and that's the big problem. People can email me if they want to see the IR dumps and how I generated them.

[brson]

This is quite a speculative wishlist task, not updated in nearly a year. Closing. Performance improvements always welcome.