blob: 67d5ebfa7cb4acd0055c07d93b31c226f5f8822a [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Cameron Zwarich
-/
module
prelude
public import Lean.Compiler.LCNF.Basic
public import Lean.Compiler.LCNF.CompilerM
public import Lean.Compiler.LCNF.PhaseExt
public import Lean.Compiler.IR.Basic
public import Lean.Compiler.IR.CompilerM
public import Lean.Compiler.IR.ToIRType
public import Lean.CoreM
public import Lean.Environment
public section
namespace Lean.IR
open Lean.Compiler (LCNF.Alt LCNF.Arg LCNF.Code LCNF.Decl LCNF.DeclValue LCNF.LCtx LCNF.LetDecl
LCNF.LetValue LCNF.LitValue LCNF.Param LCNF.getMonoDecl?)
namespace ToIR
structure BuilderState where
vars : Std.HashMap FVarId Arg := {}
joinPoints : Std.HashMap FVarId JoinPointId := {}
nextId : Nat := 1
abbrev M := StateRefT BuilderState CoreM
def M.run (x : M α) : CoreM α := do
x.run' {}
def getFVarValue (fvarId : FVarId) : M Arg := do
return (← get).vars.get! fvarId
def getJoinPointValue (fvarId : FVarId) : M JoinPointId := do
return (← get).joinPoints.get! fvarId
def bindVar (fvarId : FVarId) : M VarId := do
modifyGet fun s =>
let varId := { idx := s.nextId }
⟨varId, { s with vars := s.vars.insertIfNew fvarId (.var varId),
nextId := s.nextId + 1 }⟩
def bindVarToVarId (fvarId : FVarId) (varId : VarId) : M Unit := do
modify fun s => { s with vars := s.vars.insertIfNew fvarId (.var varId) }
def newVar : M VarId := do
modifyGet fun s =>
let varId := { idx := s.nextId }
⟨varId, { s with nextId := s.nextId + 1 }⟩
def bindJoinPoint (fvarId : FVarId) : M JoinPointId := do
modifyGet fun s =>
let joinPointId := { idx := s.nextId }
⟨joinPointId, { s with joinPoints := s.joinPoints.insertIfNew fvarId joinPointId,
nextId := s.nextId + 1 }⟩
def bindErased (fvarId : FVarId) : M Unit := do
modify fun s => { s with vars := s.vars.insertIfNew fvarId .erased }
def findDecl (n : Name) : M (Option Decl) :=
return findEnvDecl (← Lean.getEnv) n
def addDecl (d : Decl) : M Unit :=
Lean.modifyEnv fun env => declMapExt.addEntry env d
def lowerLitValue (v : LCNF.LitValue) : LitVal × IRType :=
match v with
| .nat n =>
let type := if n < UInt32.size then .tagged else .tobject
⟨.num n, type⟩
| .str s => ⟨.str s, .object⟩
| .uint8 v => ⟨.num (UInt8.toNat v), .uint8⟩
| .uint16 v => ⟨.num (UInt16.toNat v), .uint16⟩
| .uint32 v => ⟨.num (UInt32.toNat v), .uint32⟩
| .uint64 v => ⟨.num (UInt64.toNat v), .uint64⟩
| .usize v => ⟨.num (UInt64.toNat v), .usize⟩
def lowerArg (a : LCNF.Arg) : M Arg := do
match a with
| .fvar fvarId => getFVarValue fvarId
| .erased | .type .. => return .erased
inductive TranslatedProj where
| expr (e : Expr)
| erased
deriving Inhabited
def lowerProj (base : VarId) (ctorInfo : CtorInfo) (field : CtorFieldInfo)
: TranslatedProj × IRType :=
match field with
| .object i irType => ⟨.expr (.proj i base), irType⟩
| .usize i => ⟨.expr (.uproj i base), .usize⟩
| .scalar _ offset irType => ⟨.expr (.sproj (ctorInfo.size + ctorInfo.usize) offset base), irType⟩
| .erased => ⟨.erased, .erased⟩
def lowerParam (p : LCNF.Param) : M Param := do
let x ← bindVar p.fvarId
let ty ← toIRType p.type
return { x, borrow := p.borrow, ty }
mutual
partial def lowerCode (c : LCNF.Code) : M FnBody := do
match c with
| .let decl k => lowerLet decl k
| .jp decl k =>
let joinPoint ← bindJoinPoint decl.fvarId
let params ← decl.params.mapM lowerParam
let body ← lowerCode decl.value
return .jdecl joinPoint params body (← lowerCode k)
| .jmp fvarId args =>
let joinPointId ← getJoinPointValue fvarId
return .jmp joinPointId (← args.mapM lowerArg)
| .cases cases =>
-- `casesOn` for inductive predicates should have already been expanded.
let .var varId := (← getFVarValue cases.discr) | unreachable!
return .case cases.typeName
varId
(← nameToIRType cases.typeName)
(← cases.alts.mapM (lowerAlt varId))
| .return fvarId =>
return .ret (← getFVarValue fvarId)
| .unreach .. => return .unreachable
| .fun .. => panic! "all local functions should be λ-lifted"
partial def lowerLet (decl : LCNF.LetDecl) (k : LCNF.Code) : M FnBody := do
match decl.value with
| .lit litValue =>
let var ← bindVar decl.fvarId
let ⟨litValue, type⟩ := lowerLitValue litValue
return .vdecl var type (.lit litValue) (← lowerCode k)
| .proj typeName i fvarId =>
match (← getFVarValue fvarId) with
| .var varId =>
let some (.inductInfo { ctors := [ctorName], .. }) := (← Lean.getEnv).find? typeName
| panic! "projection of non-structure type"
let ⟨ctorInfo, fields⟩ ← getCtorLayout ctorName
let ⟨result, type⟩ := lowerProj varId ctorInfo fields[i]!
match result with
| .expr e =>
let var ← bindVar decl.fvarId
return .vdecl var type e (← lowerCode k)
| .erased =>
bindErased decl.fvarId
lowerCode k
| .erased =>
bindErased decl.fvarId
lowerCode k
| .const name _ args =>
let irArgs ← args.mapM lowerArg
if let some decl ← findDecl name then
return (← mkApplication name decl.params.size irArgs)
if let some decl ← LCNF.getMonoDecl? name then
return (← mkApplication name decl.params.size irArgs)
let env ← Lean.getEnv
match env.find? name with
| some (.ctorInfo ctorVal) =>
let type ← nameToIRType ctorVal.induct
if type.isScalar then
let var ← bindVar decl.fvarId
return .vdecl var type (.lit (.num ctorVal.cidx)) (← lowerCode k)
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 .unreachable
let objArgs : Array Arg ← do
let mut result : Array Arg := #[]
for h : i in *...fields.size do
match fields[i] with
| .object .. =>
result := result.push irArgs[i]!
| .usize .. | .scalar .. | .erased => pure ()
pure result
let objVar ← bindVar decl.fvarId
let rec lowerNonObjectFields (_ : Unit) : M FnBody :=
let rec loop (i : Nat) : M FnBody := do
match irArgs[i]? with
| some (.var varId) =>
match fields[i]! with
| .usize usizeIdx =>
let k ← loop (i + 1)
return .uset objVar usizeIdx varId k
| .scalar _ offset argType =>
let k ← loop (i + 1)
return .sset objVar (ctorInfo.size + ctorInfo.usize) offset varId argType k
| .object .. | .erased => loop (i + 1)
| some .erased => loop (i + 1)
| none => lowerCode k
loop 0
return .vdecl objVar ctorInfo.type (.ctor ctorInfo objArgs) (← lowerNonObjectFields ())
| some (.defnInfo ..) | some (.opaqueInfo ..) =>
mkFap name irArgs
| some (.axiomInfo ..) | .some (.quotInfo ..) | .some (.inductInfo ..) | .some (.thmInfo ..) =>
throwNamedError lean.dependsOnNoncomputable f!"`{name}` not supported by code generator; consider marking definition as `noncomputable`"
| 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 args =>
match (← getFVarValue fvarId) with
| .var id =>
let irArgs ← args.mapM lowerArg
mkAp id irArgs
| .erased => mkErased ()
| .erased => mkErased ()
where
mkVar (v : VarId) : M FnBody := do
bindVarToVarId decl.fvarId v
lowerCode k
mkErased (_ : Unit) : M FnBody := do
bindErased decl.fvarId
lowerCode k
mkFap (name : Name) (args : Array Arg) : M FnBody := do
let var ← bindVar decl.fvarId
let type ← toIRType decl.type
return .vdecl var type (.fap name args) (← lowerCode k)
mkPap (name : Name) (args : Array Arg) : M FnBody := do
let var ← bindVar decl.fvarId
return .vdecl var .object (.pap name args) (← lowerCode k)
mkAp (fnVar : VarId) (args : Array Arg) : M FnBody := do
let var ← bindVar decl.fvarId
let type := (← toIRType decl.type).boxed
return .vdecl var type (.ap fnVar args) (← lowerCode k)
mkOverApplication (name : Name) (numParams : Nat) (args : Array Arg) : M FnBody := do
let var ← bindVar decl.fvarId
let type := (← toIRType decl.type).boxed
let tmpVar ← newVar
let firstArgs := args.extract 0 numParams
let restArgs := args.extract numParams args.size
return .vdecl tmpVar .object (.fap name firstArgs) <|
.vdecl var type (.ap tmpVar restArgs) (← lowerCode k)
mkApplication (name : Name) (numParams : Nat) (args : Array Arg) : M FnBody := 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 lowerAlt (discr : VarId) (a : LCNF.Alt) : M Alt := do
match a with
| .alt ctorName params code =>
let ⟨ctorInfo, fields⟩ ← getCtorLayout ctorName
let lowerParams (params : Array LCNF.Param) (fields : Array CtorFieldInfo) : M FnBody := do
let rec loop (i : Nat) : M FnBody := do
match params[i]?, fields[i]? with
| some param, some field =>
let ⟨result, type⟩ := lowerProj discr ctorInfo field
match result with
| .expr e =>
return .vdecl (← bindVar param.fvarId)
type
e
(← loop (i + 1))
| .erased =>
bindErased param.fvarId
loop (i + 1)
| none, none => lowerCode code
| _, _ => panic! "mismatched fields and params"
loop 0
let body ← lowerParams params fields
return .ctor ctorInfo body
| .default code =>
return .default (← lowerCode code)
end
def lowerResultType (type : Lean.Expr) (arity : Nat) : M IRType :=
toIRType (resultTypeForArity type arity)
where resultTypeForArity (type : Lean.Expr) (arity : Nat) : Lean.Expr :=
if arity == 0 then
type
else
match type with
| .forallE _ _ b _ => resultTypeForArity b (arity - 1)
| .const ``lcErased _ => mkConst ``lcErased
| _ => panic! "invalid arity"
def lowerDecl (d : LCNF.Decl) : M (Option Decl) := do
let params ← d.params.mapM lowerParam
let resultType ← lowerResultType d.type d.params.size
match d.value with
| .code code =>
let body ← lowerCode code
pure <| some <| .fdecl d.name params resultType body {}
| .extern externAttrData =>
if externAttrData.entries.isEmpty then
-- TODO: This matches the behavior of the old compiler, but we should
-- find a better way to handle this.
addDecl (mkDummyExternDecl d.name params resultType)
pure <| none
else
pure <| some <| .extern d.name params resultType externAttrData
end ToIR
def toIR (decls: Array LCNF.Decl) : CoreM (Array Decl) := do
let mut irDecls := #[]
for decl in decls do
if let some irDecl ← ToIR.lowerDecl decl |>.run then
irDecls := irDecls.push irDecl
return irDecls
end Lean.IR