docs
API
Generated with
docs/scalus/scalus.sir/scalus.sir.lowering/scalus.sir.lowering.simple/LetFloating

LetFloating

scalus.sir.lowering.simple.LetFloating
object LetFloating

Let-floating transformation that moves lazy let bindings closer to their usage points.

This transformation implements "floating inward" as described in: Simon Peyton Jones, Will Partain, and André Santos. 1996. Let-floating: moving bindings to give faster programs.

The algorithm works in three phases:

  1. Enrichment pass (down-traversal): Build enriched SIR with node indices, track variable usage, lambda context, and dependencies
  2. Analysis pass: Find dominating nodes for each lazy let binding using tracked usage information and transitive dependency propagation
  3. Output generation pass (down-traversal): Reconstruct SIR, moving lazy lets to their computed dominating nodes

Lambda barrier: Non-effortless bindings (computations) are prevented from crossing lambda boundaries to avoid duplicating work when the lambda is called multiple times. Effortless bindings (constants, variables, lambdas) can cross freely.

TODO: optimization can introduce expressions like App((lambda x, x),y) which can be eliminated. Maybe add a beta-reduction pass after let-floating, or just handle it here.

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Type members

Classlikes

case class NodeInfo(index: Int, childIndices: List[Int], usedVars: Set[VarRef], definedVars: Map[String, VarDef], parent: Option[Int] = ..., nearestEnclosingLambda: Option[Int] = ...)

Node information tracked during traversal

Node information tracked during traversal

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class TrackedVarInfo(var minDirectUsageNode: Option[Int] = ..., reverseDependencies: Set[VarRef] = ..., var minMultipleChildrenNode: Option[Int] = ...)

Tracked information about a variable during let-floating transformation

Tracked information about a variable during let-floating transformation

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class VarDef(name: String, binding: Binding, definingNode: Int, isLazy: Boolean, dependencies: Set[VarRef])

Variable definition with dependencies

Variable definition with dependencies

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class VarRef(name: String, definingNode: Int)

Variable reference: name and defining node index

Variable reference: name and defining node index

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all

Value members

Concrete methods

def apply(sir: SIR): SIR

Apply let-floating transformation to SIR

Apply let-floating transformation to SIR

Attributes

Generated with