blob: 830a62e9d3e63d4f845cdf4deaffea0d70cf00fb [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, Cameron Zwarich
-/
module
prelude
import Lean.Compiler.LCNF.ToImpureType
public import Lean.Compiler.LCNF.PassManager
import Lean.Compiler.LCNF.PhaseExt
import Init.Data.Format.Macro
namespace Lean.Compiler.LCNF
open ImpureType
/--
Marks an extern definition to be guaranteed to always return tagged values.
This information is used to optimize reference counting in the compiler.
-/
@[builtin_doc]
builtin_initialize taggedReturnAttr : TagAttribute ←
registerTagAttribute `tagged_return "mark extern definition to always return tagged values"
structure BuilderState where
/--
We keep around a substitution here because we run a second trivial structure elimination when
converting to impure. This elimination is aware of the fact that `Void` is irrelevant while the first
one in isn't because we are still pure. However, impure does not allow us to have bindings of
the form `let x := y` which might occur when for example projecting out of a trivial structure
where previously a binding would've been `let x := proj y i` and now becomes `let x := y`.
For this reason we carry around these kinds of bindings in this substitution and apply it whenever
we access an fvar in the conversion.
-/
subst : LCNF.FVarSubst .pure := {}
abbrev ToImpureM := StateRefT BuilderState CompilerM
instance : MonadFVarSubst ToImpureM .pure true where
getSubst := return (← get).subst
instance : MonadFVarSubstState ToImpureM .pure where
modifySubst f := modify fun s => { s with subst := f s.subst }
def Param.toImpure (p : Param .pure) : ToImpureM (Param .impure) := do
let type ← toImpureType p.type
if type.isVoid || type.isErased then
addSubst p.fvarId .erased
let p := { p with type }
modifyLCtx fun lctx => lctx.addParam p
return p
def lowerProj (base : FVarId) (ctorInfo : CtorInfo) (field : CtorFieldInfo) :
LetValue .impure × Expr :=
match field with
| .object i irType => ⟨.oproj i base, irType⟩
| .usize i => ⟨.uproj i base, ImpureType.usize⟩
| .scalar _ offset irType => ⟨.sproj (ctorInfo.size + ctorInfo.usize) offset base, irType⟩
| .erased => ⟨.erased, ImpureType.erased⟩
| .void => ⟨.erased, ImpureType.void⟩
def Arg.toImpure (arg : Arg .pure) : ToImpureM (Arg .impure) := do
let arg ← normArg arg
match arg with
| .fvar fvarId => return .fvar fvarId
| .erased | .type .. => return .erased
public def lowerResultType (type : Expr) (arity : Nat) : CoreM Expr :=
toImpureType (resultTypeForArity type arity)
where resultTypeForArity (type : Lean.Expr) (arity : Nat) : Expr :=
if arity == 0 then
type
else
match type with
| .forallE _ _ b _ => resultTypeForArity b (arity - 1)
| .const ``lcErased _ => mkConst ``lcErased
| _ => panic! "invalid arity"
def litValueImpureType (v : LCNF.LitValue) : Expr :=
match v with
| .nat n =>
if n < UInt32.size then ImpureType.tagged else ImpureType.tobject
| .str .. => ImpureType.object
| .uint8 .. => ImpureType.uint8
| .uint16 .. => ImpureType.uint16
| .uint32 .. => ImpureType.uint32
| .uint64 .. => ImpureType.uint64
| .usize .. => ImpureType.usize
mutual
partial def lowerLet (decl : LetDecl .pure) (k : Code .pure) : ToImpureM (Code .impure) := do
let value ← normLetValue decl.value
match value with
| .lit litValue =>
let type := litValueImpureType litValue
let decl := ⟨decl.fvarId, decl.binderName, type, .lit litValue⟩
continueLet decl
| .proj typeName i fvarId =>
if let some info ← hasTrivialImpureStructure? typeName then
if info.fieldIdx == i then
addSubst decl.fvarId (.fvar fvarId)
else
addSubst decl.fvarId .erased
k.toImpure
else
match (← normFVar fvarId) with
| .fvar fvarId =>
let some (.inductInfo { ctors := [ctorName], .. }) := (← Lean.getEnv).find? typeName
| panic! "projection of non-structure type"
let ⟨ctorInfo, fields⟩ ← getCtorLayout ctorName
let ⟨result, type⟩ := lowerProj fvarId ctorInfo fields[i]!
match result with
| .erased => continueErased decl.fvarId
| _ => continueLet ⟨decl.fvarId, decl.binderName, type, result⟩
| .erased =>
addSubst decl.fvarId .erased
k.toImpure
| .const name _ args =>
let irArgs ← args.mapM (·.toImpure)
if let some sig ← getImpureSignature? name then
return (← mkApplication name sig.params.size irArgs)
if let some decl ← getMonoDecl? name then
return (← mkApplication name decl.params.size irArgs)
let env ← Lean.getEnv
match env.find? name with
| some (.ctorInfo ctorVal) =>
if let some info ← hasTrivialImpureStructure? ctorVal.induct then
let arg := args[info.numParams + info.fieldIdx]!
LCNF.addSubst decl.fvarId arg
k.toImpure
else
let type ← nameToImpureType ctorVal.induct
if type.isScalar then
let decl := ⟨decl.fvarId, decl.binderName, type, .lit (.impureTypeScalarNumLit type ctorVal.cidx)⟩
let res ← continueLet decl
return res
let ⟨ctorInfo, fields⟩ ← getCtorLayout name
let irArgs := irArgs.extract (start := ctorVal.numParams)
if irArgs.size != fields.size then
-- An overapplied constructor arises from compiler
-- transformations on unreachable code
return .unreach (ImpureType.tobject) -- TODO: need a more precise type for this
let objArgs : Array (Arg .impure) ← do
let mut result : Array (Arg .impure) := #[]
for h : i in *...fields.size do
match fields[i] with
| .object .. =>
result := result.push irArgs[i]!
| .usize .. | .scalar .. | .erased | .void => pure ()
pure result
let rec lowerNonObjectFields : ToImpureM (Code .impure) :=
let rec loop (i : Nat) : ToImpureM (Code .impure) := do
match irArgs[i]? with
| some (.fvar fvarId) =>
match fields[i]! with
| .usize usizeIdx =>
let k ← loop (i + 1)
return .uset decl.fvarId usizeIdx fvarId k
| .scalar _ offset argType =>
let k ← loop (i + 1)
return .sset decl.fvarId (ctorInfo.size + ctorInfo.usize) offset fvarId argType k
| .object .. | .erased | .void => loop (i + 1)
| some .erased => loop (i + 1)
| none => k.toImpure
loop 0
let decl := ⟨decl.fvarId, decl.binderName, ctorInfo.type, .ctor ctorInfo objArgs⟩
modifyLCtx fun lctx => lctx.addLetDecl decl
return .let decl (← lowerNonObjectFields)
| some (.defnInfo ..) | some (.opaqueInfo ..) => mkFap name irArgs
| some (.axiomInfo ..) | .some (.quotInfo ..) | .some (.inductInfo ..) | .some (.thmInfo ..) =>
-- Should have been caught by `ToLCNF`
throwError f!"ToImpure: unexpected use of noncomputable declaration `{name}`; please report this issue"
| some (.recInfo ..) =>
throwError f!"code generator does not support recursor `{name}` yet, consider using 'match ... with' and/or structural recursion"
| none => panic! "reference to unbound name"
| .fvar fvarId irArgs =>
let irArgs ← irArgs.mapM (·.toImpure)
let type := (← toImpureType decl.type).boxed
let decl := ⟨decl.fvarId, decl.binderName, type, .fvar fvarId irArgs⟩
continueLet decl
| .erased =>
continueErased decl.fvarId
where
continueLet (decl : LetDecl .impure) : ToImpureM (Code .impure) := do
modifyLCtx fun lctx => lctx.addLetDecl decl
let k ← k.toImpure
return .let decl k
continueErased (fvarId : FVarId) : ToImpureM (Code .impure) := do
addSubst fvarId .erased
k.toImpure
mkFap (name : Name) (args : Array (Arg .impure)) : ToImpureM (Code .impure) := do
continueLet ⟨decl.fvarId, decl.binderName, ← toImpureType decl.type, .fap name args⟩
mkPap (name : Name) (args : Array (Arg .impure)) : ToImpureM (Code .impure) := do
continueLet ⟨decl.fvarId, decl.binderName, ImpureType.object, .pap name args⟩
mkOverApplication (name : Name) (numParams : Nat) (args : Array (Arg .impure)) :
ToImpureM (Code .impure) := do
let type := (← toImpureType decl.type).boxed
let firstArgs := args.extract 0 numParams
let restArgs := args.extract numParams args.size
let auxDecl ← mkLetDecl (.str decl.binderName "overap") ImpureType.object (.fap name firstArgs)
let resDecl := ⟨decl.fvarId, decl.binderName, type, .fvar auxDecl.fvarId restArgs⟩
modifyLCtx fun lctx => lctx.addLetDecl resDecl
return .let auxDecl (.let resDecl (← k.toImpure))
mkApplication (name : Name) (numParams : Nat) (args : Array (Arg .impure)) :
ToImpureM (Code .impure) := do
let numArgs := args.size
if numArgs < numParams then
mkPap name args
else if numArgs == numParams then
mkFap name args
else
mkOverApplication name numParams args
partial def Code.toImpure (c : Code .pure) : ToImpureM (Code .impure) := do
match c with
| .let decl k => lowerLet decl k
| .jp decl k =>
let params ← decl.params.mapM (·.toImpure)
let value ← decl.value.toImpure
let k ← k.toImpure
let type ← lowerResultType decl.type params.size
let decl := ⟨decl.fvarId, decl.binderName, params, type, value⟩
modifyLCtx fun lctx => lctx.addFunDecl decl
return .jp decl k
| .jmp fvarId args => return .jmp fvarId (← args.mapM (·.toImpure))
| .cases c =>
if let some info ← hasTrivialImpureStructure? c.typeName then
assert! c.alts.size == 1
let .alt ctorName ps k := c.alts[0]! | unreachable!
assert! ctorName == info.ctorName
assert! info.fieldIdx < ps.size
for idx in 0...ps.size do
let p := ps[idx]!
if idx == info.fieldIdx then
addSubst p.fvarId (.fvar c.discr)
else
addSubst p.fvarId .erased
k.toImpure
else
-- `casesOn` for inductive predicates should have already been expanded.
withNormFVarResult (← normFVar c.discr) fun discr => do
let resultType ← toImpureType c.resultType
let alts ← c.alts.mapM (·.toImpure discr)
return .cases ⟨(← nameToImpureType c.typeName).getAppFn.constName!, resultType, discr, alts⟩
| .return fvarId =>
withNormFVarResult (← normFVar fvarId) fun fvarId => do
return .return fvarId
| .unreach type => return .unreach (← toImpureType type)
| .fun .. => panic! "all local functions should be λ-lifted"
partial def Alt.toImpure (discr : FVarId) (alt : Alt .pure) : ToImpureM (Alt .impure) := do
match alt with
| .alt ctorName params k =>
let ⟨ctorInfo, fields⟩ ← getCtorLayout ctorName
let lowerParams (params : Array (LCNF.Param .pure)) (fields : Array CtorFieldInfo) :
ToImpureM (Code .impure) := do
let rec loop (i : Nat) : ToImpureM (Code .impure) := do
match params[i]?, fields[i]? with
| some param, some field =>
let ⟨result, type⟩ := lowerProj discr ctorInfo field
match result with
| .erased =>
addSubst param.fvarId .erased
loop (i + 1)
| _ =>
let decl := ⟨param.fvarId, param.binderName, type, result⟩
modifyLCtx fun lctx => lctx.addLetDecl decl
return .let decl (← loop (i + 1))
| none, none => k.toImpure
| _, _ => panic! "mismatched fields and params"
loop 0
let body ← lowerParams params fields
return .ctorAlt ctorInfo body
| .default k => return .default (← k.toImpure)
end
def Decl.toImpure (decl : Decl .pure) : CompilerM (Decl .impure) := do
go |>.run' {}
where
go : ToImpureM (Decl .impure) := do
let decl ← lowerDecl
decl.saveImpure
return decl
lowerDecl : ToImpureM (Decl .impure) := do
let params ← decl.params.mapM (·.toImpure)
let mut resultType ← lowerResultType decl.type decl.params.size
let taggedReturn := taggedReturnAttr.hasTag (← getEnv) decl.name
match decl.value with
| .code code =>
if taggedReturn then
throwError m!"Error while compiling function '{decl.name}': @[tagged_return] is only valid for extern declarations"
let value ← code.toImpure
return { decl with type := resultType, params, value := .code value }
| .extern externAttrData =>
if taggedReturn then
if resultType.isScalar then
throwError m!"@[tagged_return] on function '{decl.name}' with scalar return type {resultType}"
else
resultType := ImpureType.tagged
return { decl with type := resultType, params, value := .extern externAttrData }
public def toImpure : Pass where
name := `toImpure
run := (·.mapM (·.toImpure))
phase := .mono
phaseOut := .impure
shouldAlwaysRunCheck := true
builtin_initialize
registerTraceClass `Compiler.toImpure (inherited := true)
end Lean.Compiler.LCNF