Optimization epic

[jeaye]

General

• Constant propagation (substituting constants in where possible)
• Constant folding (compile-time eval of pure expressions with literals)
  • Requires tracking pure fns
• Share closure contexts by having common value ordering across mutually recursive functions
• Guaranteed named recursion TCO
• AST-level function inlining (requires interop to be a big win)
  • Clojure uses this to inline RT.get, Numbers.multiply, etc
  • Don't duplicate body in inline meta; just use :inline true
    • Then we need to deal with merging fn bodies; use an implicit let to create the params by name
  • Use a recursive count on the fn body to do cost analysis

Function attribute tracking

• Pure (doesn't modify any global memory) - https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-pure-function-attribute
• Const (doesn't read or modify any global memory) - https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-const-function-attribute
• Captures a parameter (note which params are captured)
• Can throw

Vars

• If a var has :jank/static? true meta, deref + store it in the module's global ctor and never deref it again (superseded by direct linking)
  • Also, in each function, only load it once

Dead code elimination

• Dead branches
• Pure statements

Boxing

• Arithmetic unboxing for numeric locals
• Unboxed numeric function parameters (requires either hinting or monomorphization)
• Unboxing for non-numeric locals (strings, maps, etc -- a la Project Valhalla)
  • If the local is never returned or closed over, it can be on the stack
  • Requires tracking capturing fns
    • https://llvm.org/docs/LangRef.html#pointercapture
  • C# does some of this: https://em-tg.github.io/csborrow/
• If a local function is not captured, it can be monomorphized for each call

Startup

• Group all fns into a single module to load
• Box globals in static memory, not with the GC
• Add CLI option to elide meta (see Clojure's elide-meta)
• Two phase jank compilation which bakes in core libs during the second phase (i.e. instant startup)

Form rewriting

• Auto-transient
• Auto-transducer
• Zero-cost map destructuring (see here)
• General loop unrolling
• Specific loop unrolling (i.e. get-in)
• Faster str usage (a la stringer)
• Replace first and second on known countable types with nth
• Change recursion into loop/recur
• Auto record creation, for map literals

IR-specific

• Don't require boxing strings for reading globals #301
• Don't put meta into globals
• Optimize the passes we run and offer different levels
• Put this into closure context for named recursion
  • Can also work by forcing normal functions into closures if they're named recursive

Interop

• Avoid repeated trait conversions for the same value

AOT-only

• Direct linking (dynamic call)
• Direct linking (direct call)
• Unused var removal (includes defns)
• Flag to elide var meta
• Remove unused args from fns
• Unity build (i.e. one object file for all namespaces)
• Automatic inlining
  • Given that we have inlining based on meta, defined above, if we're compiling with direct linking we can automatically inline any fn which passes cost analysis

Runtime

• Use immer to merge maps

References

• LLVM front-end tips: https://llvm.org/docs/Frontend/PerformanceTips.html
• Optimizing compiler: https://en.wikipedia.org/wiki/Optimizing_compiler
• Clojure optimization discussion: https://clojureverse.org/t/do-clojure-still-have-rooms-to-improve-at-compiler-level/7802
• Orbit, optimizing Scheme compiler: https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/orbit.pdf
• Lisp compiler optimizations: https://healeycodes.com/lisp-compiler-optimizations

[frenchy64]

Idea: if you're likely to call an (immutable) function more than once with a known arity, unbox it until you know its calling convention. If possible, then use f->call(...) directly instead of dynamic_call. Saves a visit on each call, and the more arguments passed, the more work is saved each call (as dynamic_call is more expensive for higher arities).

Applicable to things like: (let [f ..] (loop [..] (f a b))) or (let [f ..] (reduce (fn [..] (f a b)) ..))

Not sure if you could go even further and extract the raw function pointers, and also manually pass the context of closures. I'm not sure if that would force you to use std::function or if you could call them directly. Would additionally save the virtual method call.

Similar things could be done to avoid apply. If we know the arities of a function at compile time like (let [opaque [{} []]] (apply select-keys opaque)) we could skip apply_to and compile the equivalent of:

(if (= 2 (count opaque))
  (select-keys (nth opaque 0) (nth opaque 1))
  (throw (ex-info "wrong arguments to select-keys" {}))

[jeaye]

It's impossible to get the type of an unknown object, which could be anything, without a visit. We cannot store that type outside of the visitor. This is more of a physics problem with static type systems and type erasure.

The only way to do this optimization is to know the type ahead of time. Now, once we have seamless interop, and then we add type tracking for known values, we can actually know the full type of a local function and generate a call to ->call accordingly. This is what we had with C++ codegen and then lost when everything went to LLVM IR. We can get more of it back once we have support for interop, since the compiler and do implicit interop as part of its codegen, not just for explicit interop forms. Until we have that type info ahead of time, though, this is impossible.