Reliable Optimizations for Idiomatic Rust

# Reliable Optimizations for Idiomatic Rust ---- ![my avatar, an inverted pink question mark on a black background](https://i.imgur.com/vPPiNW8.png) [twitter.com/oli_obk](https://twitter.com/oli_obk) [github.com/oli-obk](https://github.com/oli-obk) ---- # MIR **M**edium **I**ntermediate **R**epresentation ----  ![Graph of the representations used when going from source code to machine code, either via LLVM or via the cranelift backend. The MIR is the last representation before codegen backend specific representations.](https://i.imgur.com/EGuCqWu.png) ---- TLDR: no syntax sugar at all Note: MIR syntax is similar to Rust ---- * no macros * no loops, only `goto` * no if, match, only `switch` * no type inference or trait resolution * Every function call is `full::path::to::Type::some_function` * no autoderef * no expression chaining ---- ### Example ```rust fn main() { let x = 42.pow(3); if x < 3 { loop {} } } ``` ---- ```rust fn main() -> () { let mut _0: (); let _1: i32; // x let mut _2: bool; bb0: { _1 = core::num::<impl i32>::pow(42i32, 3u32) -> bb1 } bb1: { _2 = Lt(_1, 3i32); switchInt(_2) -> [false: bb2, otherwise: bb3]; } bb2: { return; } bb3: { goto -> bb4; } bb4: { goto -> bb4; } } ``` Note: bb* are basic blocks. All statements in a block are executed and the terminator at the end always goes to another block or returns. ----  ![This graph has no new information compared to the previous slide. It is just a 1:1 translation of the MIR code, using basic blocks as nodes and graph edges for transitions between basic blocks.](https://i.imgur.com/Wso5JmN.png) ---- ## Optimizations * make code fast * make code small * reduce runtime memory footprint Note: They also make debugging a nightmare and make UB symptoms worse. ---- Optimizations reduce compile-time ---- Optimizations reduce compile-time ![The meme with a confused person looking into the camera. There are three question marks as an overlay in the picture](https://i.imgur.com/9N3aUT1.png) Note: * more work at compile-time --> faster compile times * we optimize away code --> later opts do less work * high-impact on generic functions  ---- ### Fast Example: For loops ```rust for i in 0..n { // do stuff } ``` ---- ```rust let mut iter = (0..n).into_iter(); loop { match iter.next() { Some(i) => { /* do stuff */ }, None => break, } } ``` Note: This is a lot of noise just for running through a bunch of numbers e.g. for `for i in 0..n` ---- ### Small ```rust let millisecond = CLOCKS_PER_SECOND / 1000; ``` Note: Doing this division at runtime is a waste. The compiler does it for you and just stores the result. ---- ### Reduce memory footprint ```rust for i in 0..n { do_something(i); } ``` Note: Copy the body of `do_something` directly into the loop (inlining). * removes the cost of a function call and * can open up new optimization avenues  ---- ## Optimizations *we're digging into them for realz now* ---- ### The question mark operator ```rust fn foo(x: Result<i32, Error>) -> Result<i32, Error> { Ok(x? + 1) } ``` Note: Very commonly used operator in Rust, but LLVM has no clue how to optimize it properly. ---- ```rust fn foo(x: Result<i32, Error>) -> Result<i32, Error> { match x { Ok(a) => Ok(a + 1), Err(e) => Err(e), } } ``` Note: The previous example basically desugars to this ---- ### Ok path ```rust a = (x as Ok).0; (RETURN as Ok).0 = Add(a, 1i32); discriminant(RETURN) = 0; ``` ### Error path ```rust e = (x as Err).0; (RETURN as Err).0 = e; discriminant(RETURN) = 1; ``` ---- ```rust e = (x as Err).0; (RETURN as Err).0 = e; discriminant(RETURN) = 1; ``` gets translated to ```rust RETURN = x ``` ---- # Misconceptions ---- Thesis: Optimizations make debugging harder ---- Thesis: Optimizations make debugging harder Antithesis: No they don't Note: Optimization devs are just lazy ---- ```rust let x = 42; ``` Debugger: ``` x: <local optimized out> ``` Note: Only at `mir-opt-level=1` ---- ```rust let x = 42; ``` Debugger: ``` x: <local optimized out, value: 42> ``` ---- ```rust let x = SomeStruct { a: 42, b, c, d } let y = x.a; ``` Debugger: ``` y: <local optimized out, value stored at x.a> ``` Note: Everything with a name that gets optimized out gets metadata attached that allows the debugger to compute the value from metadata or other variables. ---- Thesis: Optimizations abuse UB for evil ---- Thesis: Optimizations abuse UB for evil ~~Antithesis~~ Nevermind, they do, **but...** ---- ## What if optimizations... ... emit warnings ... are less aggressive in unsafe code ... are configurable from the surface language Note: * simply warn the user about such things * at the MIR level we have type information and semantics are still pretty close to the Rust language's semantics * fine-tune performance or correctness without changing code ---- ## Optimizations are awesome fun accessible Note: * code machine go brrr * puzzle games, but for programmers that program programs for other programmers * good starting point for new compiler contributors ---- ## Outlook * Partial specialization * MIR inlining * Polymorphization * Value Range Analysis * NRVO * copy-propagation * de-virtualization * Hardening against UB by linting Note: high impact things-to-come * if a function argument is constant, duplicate the function replacing all uses of the argument with the constant * MIR inlining * don't duplicate a generic function for every parameter it is used with if the generic parameter has no influence on the function's behavior. E.g. `Vec::<T>::len` * if it is known that `x > 0`, `x - 1` does not need overflow checks * Named Return Value Optimization. Write directly to the return destination, eliminating intermediate copies. * replacing all uses of `a` where `a = b` is the only assignment with `b` * if the concrete type behind a trait object is known, use that * This way the user can decide to allow a lint at a site that they have reviewed thoroughly and comment on why they allowed the lint