IR Pass Ordering Sensitivity

Hi,

I’m trying to autotune a good sequence of IR optimization passes and I seem to run into segfaults in opt (in LLVM5) with certain pass orderings.

Is this expected behavior? If so, what would be the recommended way of determining pass dependencies so that I can encode them into the tuner?

The test program can be found here: https://gist.github.com/kavon/92d153cdd54ce9b77162af3af47d4c95

Here’s what happens:

kavon@cronus:~/m/autotune|master⚡*?
➤ /Users/kavon/msr/llvm5/bin/opt  -inline -mem2reg -inferattrs -ipconstprop -gvn -simplifycfg -bdce -sink -dse -adce -instcombine -early-cse-memssa -early-cse-memssa -dse -adce -simplifycfg -sink -ipconstprop -gvn -bdce -instcombine -jump-threading -inline -sroa ./src/apps/raytracer.bc -o ./out/raytracer_opt1043.bc
0  opt                      0x000000010ebd4498 llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 40
1  opt                      0x000000010ebd4a46 SignalHandler(int) + 342
2  libsystem_platform.dylib 0x00007fff8ce5352a _sigtramp + 26
3  opt                      0x000000010eb8ef4f llvm::StringMapImpl::FindKey(llvm::StringRef) const + 303
4  opt                      0x000000010e770235 llvm::PMDataManager::add(llvm::Pass*, bool) + 917
5  opt                      0x000000010e76d6ef llvm::PMTopLevelManager::schedulePass(llvm::Pass*) + 2367
6  opt                      0x000000010d755c9e main + 8846
7  libdyld.dylib            0x00007fff8c0c85ad start + 1
8  libdyld.dylib            0x000000000000001c start + 1945336432
Stack dump:
0.	Program arguments: /Users/kavon/msr/llvm5/bin/opt -inline -mem2reg -inferattrs -ipconstprop -gvn -simplifycfg -bdce -sink -dse -adce -instcombine -early-cse-memssa -early-cse-memssa -dse -adce -simplifycfg -sink -ipconstprop -gvn -bdce -instcombine -jump-threading -inline -sroa ./src/apps/raytracer.bc -o ./out/raytracer_opt1043.bc 
fish: “/Users/kavon/msr/llvm5/bin/opt…” terminated by signal SIGSEGV (Address boundary error)

Thanks,

Kavon

These are definitely LLVM bugs. It would be best to report reduced test cases against top of tree.

We should have some automated infrastructure for finding these too...

John

Zhendong & friends generally do that (and reported many bugs :slight_smile: I
tried that myself, but never got to automate the whole procedure.
While the problem is combinatorial in nature, evidence shows that you
don't need to enumerate all the possible combination of passes to
break LLVM. I think an `opt` option would be a good start. You can
then take the testsuite and run with that, or generate random IR with
llvm-stress and pipe that to opt. The swift folks have a slightly more
sophisticated infrastructure for doing this (you can dump the SIL
pipeline in a YAML file, and then IIRC, feed that back to `sil-opt`),
but something simpler will do, IMHO. Happy to discuss this further if
folks are in California next week :slight_smile:

Thanks,

something simpler will do, IMHO. Happy to discuss this further if
folks are in California next week :slight_smile:

Yes, I'll be in California next week, let's chat!

We could make use of the autotuner I'm currently building:

https://github.com/kavon/autotune

It tries to find an optimal sequence of IR passes, and I've run into a bunch of different bugs with it so far (e.g., it seems structurizecfg interacts poorly with 'invoke'). I'll start submitting bug reports for them soon.

~kavon

As part of the stress-suite of the LLVM obfuscator we're going to
present next Thursday, we ran into similar problems. Well, when you
s/optimization/obfuscation/ many things go wrong anyway.

I'm quite interested in the pass scheduling problem, because interaction
between optimization and obfuscation are complex, let's chat!

Hi Kavon,

JFYI, while in general any sequence of optimization passes should compose to
produce a valid optimization pipeline, there are some tradeoffs LLVM makes in
practice for backend passes. I think the current structure is more on the lines
of:

- Passes that are part of "opt -O(3|2|1|0)" should compose in any order to form
   a correct compilation pipeline that can handle any IR.

- IR passes that are only run by backends:
    * Should never silently miscompile IR
    * May fail asserts on IR they can't handle

I'd suggest restricting your autotuner on passes that are part of "opt
-O(3|2|1|0)" as a starting point.

-- Sanjoy

One may want to read an interesting paper around this

https://www.eecis.udel.edu/~cavazos/oopsla-2006.pdf