LocalOpt

Optimizations within a single method. Certain optimizations enable others, for example removing unreachable code can render a try block empty and enable removeEmptyExceptionHandlers. The latter in turn enables more unreachable code to be eliminated (the catch block), so there is a cyclic dependency. Optimizations that depend on each other are therefore executed in a loop until reaching a fixpoint.

The optimizations marked UPSTREAM enable optimizations that were already executed, so they cause another iteration in the fixpoint loop.

nullness optimizations: rewrite null-checking branches to GOTO if nullness is known

• enables downstream
  • unreachable code (null / non-null branch becomes unreachable)
  • box-unbox elimination (may render an escaping consumer of a box unreachable)
  • stale stores (aload x is replaced by aconst_null if it's known null)
  • simplify jumps (replaces conditional jumps by goto, so may enable goto chains)

unreachable code / DCE (removes instructions of basic blocks to which there is no branch)

• enables downstream:
  • stale stores (loads may be eliminated, removing consumers of a store)
  • empty handlers (try blocks may become empty)
  • simplify jumps (goto l; [dead code]; l: ...) => remove goto
  • stale local variable descriptors
  • (not box-unbox, which is implemented using prod-cons, so it doesn't consider dead code)

note that eliminating empty handlers and stale local variable descriptors is required for correctness, see the comment in the body of methodOptimizations.

box-unbox elimination (eliminates box-unbox pairs within the same method)

• enables UPSTREAM:
  • nullness optimizations (a box extraction operation (unknown nullness) may be rewritten to a read of a non-null local. example in doc comment of box-unbox implementation)
  • further box-unbox elimination (e.g. an Integer stored in a Tuple; eliminating the tuple may enable eliminating the Integer)
• enables downstream:
  • copy propagation (new locals are introduced, may be aliases of existing)
  • stale stores (multi-value boxes where not all values are used)
  • redundant casts (("a", "b")._1: the generic _1 method returns Object, a cast to String is added. The cast is redundant after eliminating the tuple.)
  • empty local variable descriptors (local variables that were holding the box may become unused)

• push-pop (due to artifacts of eliminating runtime type tests on primitives)

copy propagation (replaces LOAD n to the LOAD m for the smallest m that is an alias of n)

• enables downstream:
  • stale stores (a stored value may not be loaded anymore)
  • store-load pairs (a load n may now be right after a store n)

stale stores (replace STORE by POP), rewrites ClassTag(x).newArray, inlines array_apply/update

• enables UPSTREAM:
  • nullness optimizations (newArray rewrite or inlining may turn things non-null)
• enables downstream:
  • push-pop (the new pop may be the single consumer for an instruction)
  • redundant casts (because rewrites newArray, the array type gets more precise)

redundant casts and rewrite some intrinsics: eliminates casts that are statically known to succeed (uses type propagation), rewrites instanceof checks, rewrites intrinsics.

• enables UPSTREAM:
  • box-unbox elimination (a removed checkcast may be a box consumer)
  • copy propagation (a removed checkcast may turn an upcasted local variable into an alias)
• enables downstream:
  • push-pop for closure allocation elimination (every indyLambda is followed by a checkcast, see scala/bug#9540)
  • redundant casts (changing an instanceof to true/false removes branches and can make types of other values more precise)

push-pop (when a POP is the only consumer of a value, remove the POP and its producer)

• enables UPSTREAM:
  • stale stores (if a LOAD is removed, a corresponding STORE may become stale)
  • box-unbox elimination (push-pop may eliminate a closure allocation, rendering a captured box non-escaping)
  • redundant casts (Int.unbox(x) is replaced by x.asInstanceOf[Integer]; pop)
  • nullness (x.intValue is replaced by if (x == null) throw null)
• enables downstream:
  • store-load pairs (a variable may become non-live)
  • stale handlers (push-pop removes code)
  • simplify jumps (push-pop removes code)

store-load pairs (remove STORE x; LOAD x if x is otherwise not used in the method)

• enables downstream:
  • empty handlers (code is removes, a try block may become empty)
  • simplify jumps (code is removed, a goto may become redundant for example)
  • stale local variable descriptors

empty handlers (removes exception handlers whose try block is empty)

• enables UPSTREAM:
  • unreachable code (catch block becomes unreachable)
  • box-unbox (a box may be escape in an operation in a dead handler)
• enables downstream:
  • simplify jumps

simplify jumps (various, like GOTO l; l: ..., see doc comments of individual optimizations)

• enables UPSTREAM
  • unreachable code (GOTO a; a: GOTO b; b: ..., the first jump is changed to GOTO b, the second becomes unreachable)
  • store-load pairs (a GOTO l; l: ... is removed between store and load)
  • push-pop (IFNULL l; l: ... is replaced by POP)

The following cleanup optimizations don't enable any upstream optimizations, so they can be executed once at the end, when the above optimizations reach a fixpoint.

empty local variable descriptors (removes unused variables from the local variable table)

empty line numbers (eliminates line number nodes that describe no executable instructions)

At this point, we used to filter out redundant label nodes (sequences of labels without any executable instructions in between). However, this operation is relatively expensive, and unnecessary: labels don't exist in the classfile, they are lowered to bytecode offsets, so redundant labels disappear by design.

Note on a method's maxLocals / maxStack: the backend only uses those values for running Analyzers. The values can be conservative approximations: if an optimization removes code and the maximal stack size is now smaller, the larger maxStack value will still work fine for running an Analyzer (just that frames allocate more space than required). The correct max values written to the bytecode are re-computed during classfile serialization. To keep things simpler, we don't update the max values in every optimization:

• we do it in removeUnreachableCodeImpl, because it's quite straightforward
• maxLocals is updated in compactLocalVariables, which runs at the end of method optimizations

Note on updating the call graph: whenever an optimization eliminates a callsite or a closure instantiation, we eliminate the corresponding entry from the call graph.