blob: 96556e059650525b408c685ff970f7d853215c44 [file]
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Henrik Böving
-/
module
prelude
public import Lean.Compiler.IR.CompilerM
import Init.While
/-!
This module contains logic for detecting simple ground expressions that can be extracted into
statically initializable variables. To do this it attempts to compile declarations into
a simple language of expressions, `SimpleGroundExpr`. If this attempt succeeds it stores the result
in an environment extension, accessible through `getSimpleGroundExpr`. Later on the code emission
step can reference this environment extension to generate static initializers for the respective
declaration.
-/
namespace Lean
namespace IR
/--
An argument to a `SimpleGroundExpr`. They get compiled to `lean_object*` in various ways.
-/
public inductive SimpleGroundArg where
/--
A simple tagged literal.
-/
| tagged (val : Nat)
/--
A reference to another declaration that was marked as a simple ground expression. This gets
compiled to a reference to the mangled version of the name.
-/
| reference (n : Name)
/--
A reference directly to a raw C name. This gets compiled to a reference to the name directly.
-/
| rawReference (s : String)
deriving Inhabited
/--
A simple ground expression that can be turned into a static initializer.
-/
public inductive SimpleGroundExpr where
/--
Represents a `lean_ctor_object`. Crucially the `scalarArgs` array must have a size that is a
multiple of 8.
-/
| ctor (cidx : Nat) (objArgs : Array SimpleGroundArg) (usizeArgs : Array USize) (scalarArgs : Array UInt8)
/--
A string literal, represented by a `lean_string_object`.
-/
| string (data : String)
/--
A partial application, represented by a `lean_closure_object`.
-/
| pap (func : FunId) (args : Array SimpleGroundArg)
/--
An application of `Lean.Name.mkStrX`. This expression is represented separately to ensure that
long name literals get extracted into statically initializable constants. The arguments contain
both the name of the string literal it references as well as the hash of the name up to that
point. This is done to make emitting the literal as simple as possible.
-/
| nameMkStr (args : Array (Name × UInt64))
/--
A reference to another declaration that was marked as a simple ground expression. This gets
compiled to a reference to the mangled version of the name.
-/
| reference (n : Name)
deriving Inhabited
public structure SimpleGroundExtState where
constNames : PHashMap Name SimpleGroundExpr := {}
revNames : List Name := []
deriving Inhabited
builtin_initialize simpleGroundDeclExt : EnvExtension SimpleGroundExtState ←
registerEnvExtension (pure {}) (asyncMode := .sync)
(replay? := some fun oldState newState _ s =>
let newNames := newState.revNames.take (newState.revNames.length - oldState.revNames.length)
newNames.foldl (init := s) fun s n =>
let g := newState.constNames.find! n
{ s with constNames := s.constNames.insert n g, revNames := n :: s.revNames }
)
/--
Record `declName` as mapping to the simple ground expr `expr`.
-/
public def addSimpleGroundDecl (env : Environment) (declName : Name) (expr : SimpleGroundExpr) :
Environment :=
simpleGroundDeclExt.modifyState env fun s =>
{ s with constNames := s.constNames.insert declName expr, revNames := declName :: s.revNames }
/--
Attempt to fetch a `SimpleGroundExpr` associated with `declName` if it exists.
-/
public def getSimpleGroundExpr (env : Environment) (declName : Name) : Option SimpleGroundExpr :=
(simpleGroundDeclExt.getState env).constNames.find? declName
/--
Like `getSimpleGroundExpr` but recursively traverses `reference` exprs to get to actual ground
values.
-/
public def getSimpleGroundExprWithResolvedRefs (env : Environment) (declName : Name) :
Option SimpleGroundExpr := Id.run do
let mut declName := declName
while true do
let val := getSimpleGroundExpr env declName
match val with
| some (.reference ref) => declName := ref
| other => return other
return none
/--
Check if `declName` is recorded as being a `SimpleGroundExpr`.
-/
public def isSimpleGroundDecl (env : Environment) (declName : Name) : Bool :=
(simpleGroundDeclExt.getState env).constNames.contains declName
public def uint64ToByteArrayLE (n : UInt64) : Array UInt8 :=
#[
n.toUInt8,
(n >>> 0x08).toUInt8,
(n >>> 0x10).toUInt8,
(n >>> 0x18).toUInt8,
(n >>> 0x20).toUInt8,
(n >>> 0x28).toUInt8,
(n >>> 0x30).toUInt8,
(n >>> 0x38).toUInt8,
]
inductive SimpleGroundValue where
| arg (arg : SimpleGroundArg)
| uint8 (val : UInt8)
| uint16 (val : UInt16)
| uint32 (val : UInt32)
| uint64 (val : UInt64)
| usize (val : USize)
deriving Inhabited
structure State where
groundMap : Std.HashMap VarId SimpleGroundValue := {}
abbrev M := StateRefT State $ OptionT CompilerM
/--
Attempt to compile `b` into a `SimpleGroundExpr`. If `b` is not compileable return `none`.
The compiler currently supports the following patterns:
- String literals
- Partial applications with other simple expressions
- Constructor calls with other simple expressions
- `Name.mkStrX`, `Name.str._override`, and `Name.num._override`
- references to other declarations marked as simple ground expressions
-/
partial def compileToSimpleGroundExpr (b : FnBody) : CompilerM (Option SimpleGroundExpr) :=
compileFnBody b |>.run' {} |>.run
where
compileFnBody (b : FnBody) : M SimpleGroundExpr := do
match b with
| .vdecl id _ expr (.ret (.var id')) =>
guard <| id == id'
compileFinalExpr expr
| .vdecl id ty expr b => compileNonFinalExpr id ty expr b
| _ => failure
@[inline]
record (id : VarId) (val : SimpleGroundValue) : M Unit :=
modify fun s => { s with groundMap := s.groundMap.insert id val }
compileNonFinalExpr (id : VarId) (ty : IRType) (expr : Expr) (b : FnBody) : M SimpleGroundExpr := do
match expr with
| .fap c #[] =>
guard <| isSimpleGroundDecl (← getEnv) c
record id (.arg (.reference c))
compileFnBody b
| .lit v =>
match v with
| .num v =>
match ty with
| .tagged =>
guard <| v < 2^31
record id (.arg (.tagged v))
| .uint8 => record id (.uint8 (.ofNat v))
| .uint16 => record id (.uint16 (.ofNat v))
| .uint32 => record id (.uint32 (.ofNat v))
| .uint64 => record id (.uint64 (.ofNat v))
| .usize => record id (.usize (.ofNat v))
| _ => failure
compileFnBody b
| .str .. => failure
| .ctor i objArgs =>
if i.isScalar then
record id (.arg (.tagged i.cidx))
compileFnBody b
else
let objArgs ← compileArgs objArgs
let usizeArgs := Array.replicate i.usize 0
-- Align to 8 bytes for alignment with lean_object*
let align (v a : Nat) : Nat :=
(v / a) * a + a * (if v % a != 0 then 1 else 0)
let alignedSsize := align i.ssize 8
let ssizeArgs := Array.replicate alignedSsize 0
compileSetChain id i objArgs usizeArgs ssizeArgs b
| _ => failure
compileSetChain (id : VarId) (info : CtorInfo) (objArgs : Array SimpleGroundArg) (usizeArgs : Array USize)
(scalarArgs : Array UInt8) (b : FnBody) : M SimpleGroundExpr := do
match b with
| .ret (.var id') =>
guard <| id == id'
return .ctor info.cidx objArgs usizeArgs scalarArgs
| .sset id' i offset y _ b =>
guard <| id == id'
let i := i - objArgs.size - usizeArgs.size
let offset := i * 8 + offset
let scalarArgs ←
match (← get).groundMap[y]! with
| .uint8 v =>
let scalarArgs := scalarArgs.set! offset v
pure scalarArgs
| .uint16 v =>
let scalarArgs := scalarArgs.set! offset v.toUInt8
let scalarArgs := scalarArgs.set! (offset + 1) (v >>> 0x08).toUInt8
pure scalarArgs
| .uint32 v =>
let scalarArgs := scalarArgs.set! offset v.toUInt8
let scalarArgs := scalarArgs.set! (offset + 1) (v >>> 0x08).toUInt8
let scalarArgs := scalarArgs.set! (offset + 2) (v >>> 0x10).toUInt8
let scalarArgs := scalarArgs.set! (offset + 3) (v >>> 0x18).toUInt8
pure scalarArgs
| .uint64 v =>
let scalarArgs := scalarArgs.set! offset v.toUInt8
let scalarArgs := scalarArgs.set! (offset + 1) (v >>> 0x08).toUInt8
let scalarArgs := scalarArgs.set! (offset + 2) (v >>> 0x10).toUInt8
let scalarArgs := scalarArgs.set! (offset + 3) (v >>> 0x18).toUInt8
let scalarArgs := scalarArgs.set! (offset + 4) (v >>> 0x20).toUInt8
let scalarArgs := scalarArgs.set! (offset + 5) (v >>> 0x28).toUInt8
let scalarArgs := scalarArgs.set! (offset + 6) (v >>> 0x30).toUInt8
let scalarArgs := scalarArgs.set! (offset + 7) (v >>> 0x38).toUInt8
pure scalarArgs
| _ => failure
compileSetChain id info objArgs usizeArgs scalarArgs b
| .uset id' i y b =>
guard <| id == id'
let i := i - objArgs.size
let .usize v := (← get).groundMap[y]! | failure
let usizeArgs := usizeArgs.set! i v
compileSetChain id info objArgs usizeArgs scalarArgs b
| _ => failure
compileFinalExpr (e : Expr) : M SimpleGroundExpr := do
match e with
| .lit v =>
match v with
| .str v => return .string v
| .num .. => failure
| .ctor i args =>
guard <| i.usize == 0 && i.ssize == 0 && !args.isEmpty
return .ctor i.cidx (← compileArgs args) #[] #[]
| .fap ``Name.num._override args =>
let pre ← compileArg args[0]!
let .tagged i ← compileArg args[1]! | failure
let name := Name.num (← interpNameLiteral pre) i
let hash := name.hash
return .ctor 2 #[pre, .tagged i] #[] (uint64ToByteArrayLE hash)
| .fap ``Name.str._override args =>
let pre ← compileArg args[0]!
let (ref, str) ← compileStrArg args[1]!
let name := Name.str (← interpNameLiteral pre) str
let hash := name.hash
return .ctor 1 #[pre, .reference ref] #[] (uint64ToByteArrayLE hash)
| .fap ``Name.mkStr1 args
| .fap ``Name.mkStr2 args
| .fap ``Name.mkStr3 args
| .fap ``Name.mkStr4 args
| .fap ``Name.mkStr5 args
| .fap ``Name.mkStr6 args
| .fap ``Name.mkStr7 args
| .fap ``Name.mkStr8 args =>
let mut nameAcc := Name.anonymous
let mut processedArgs := Array.emptyWithCapacity args.size
for arg in args do
let (ref, str) ← compileStrArg arg
nameAcc := .str nameAcc str
processedArgs := processedArgs.push (ref, nameAcc.hash)
return .nameMkStr processedArgs
| .pap c ys => return .pap c (← compileArgs ys)
| .fap c #[] =>
guard <| isSimpleGroundDecl (← getEnv) c
return .reference c
| _ => failure
compileArg (arg : Arg) : M SimpleGroundArg := do
match arg with
| .var var =>
let .arg arg := (← get).groundMap[var]! | failure
return arg
| .erased => return .tagged 0
compileArgs (args : Array Arg) : M (Array SimpleGroundArg) := do
args.mapM compileArg
compileStrArg (arg : Arg) : M (Name × String) := do
let .var var := arg | failure
let (.arg (.reference ref)) := (← get).groundMap[var]! | failure
let some (.string val) := getSimpleGroundExprWithResolvedRefs (← getEnv) ref | failure
return (ref, val)
interpStringLiteral (arg : SimpleGroundArg) : M String := do
let .reference ref := arg | failure
let some (.string val) := getSimpleGroundExprWithResolvedRefs (← getEnv) ref | failure
return val
interpNameLiteral (arg : SimpleGroundArg) : M Name := do
match arg with
| .tagged 0 => return .anonymous
| .reference ref =>
match getSimpleGroundExprWithResolvedRefs (← getEnv) ref with
| some (.ctor 1 #[pre, .reference ref] _ _) =>
let pre ← interpNameLiteral pre
let str ← interpStringLiteral (.reference ref)
return .str pre str
| some (.ctor 2 #[pre, .tagged i] _ _) =>
let pre ← interpNameLiteral pre
return .num pre i
| some (.nameMkStr args) =>
args.foldlM (init := .anonymous) fun acc (ref, _) => do
let part ← interpStringLiteral (.reference ref)
return .str acc part
| _ => failure
| _ => failure
/--
Detect whether `d` can be compiled to a `SimpleGroundExpr`. If it can record the associated
`SimpleGroundExpr` into the environment for later processing by code emission.
-/
public def Decl.detectSimpleGround (d : Decl) : CompilerM Unit := do
let .fdecl (body := body) (xs := params) (type := type) .. := d | return ()
if type.isPossibleRef && params.isEmpty then
if let some groundExpr ← compileToSimpleGroundExpr body then
trace[compiler.ir.simple_ground] m!"Marked {d.name} as simple ground expr"
modifyEnv fun env => addSimpleGroundDecl env d.name groundExpr
builtin_initialize registerTraceClass `compiler.ir.simple_ground (inherited := true)
end IR
end Lean