blob: 3ccd4a26ae28049868a83585dbb49bfcbf797ba9 [file]
/-
Copyright (c) 2025 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.ClosedTermCache
public import Lean.Compiler.NeverExtractAttr
public import Lean.Compiler.LCNF.Internalize
public import Lean.Compiler.LCNF.ToExpr
public section
namespace Lean.Compiler.LCNF
namespace ExtractClosed
abbrev ExtractM := StateRefT (Array (CodeDecl .pure)) CompilerM
mutual
partial def extractLetValue (v : LetValue .pure) : ExtractM Unit := do
match v with
| .const _ _ args => args.forM extractArg
| .fvar fnVar args =>
extractFVar fnVar
args.forM extractArg
| .proj _ _ baseVar => extractFVar baseVar
| .lit _ | .erased => return ()
partial def extractArg (arg : Arg .pure) : ExtractM Unit := do
match arg with
| .fvar fvarId => extractFVar fvarId
| .type _ | .erased => return ()
partial def extractFVar (fvarId : FVarId) : ExtractM Unit := do
if let some letDecl ← findLetDecl? fvarId then
modify fun decls => decls.push (.let letDecl)
extractLetValue letDecl.value
end
def isIrrelevantArg (arg : Arg .pure) : Bool :=
match arg with
| .erased | .type _ => true
| .fvar _ => false
structure Context where
baseName : Name
sccDecls : Array (Decl .pure)
structure State where
decls : Array (Decl .pure) := {}
/--
Cache for `shouldExtractFVar` in order to avoid superlinear behavior.
-/
fvarDecisionCache : Std.HashMap FVarId Bool := {}
abbrev M := ReaderT Context $ StateRefT State CompilerM
mutual
partial def shouldExtractLetValue (isRoot : Bool) (v : LetValue .pure) : M Bool := do
match v with
| .lit (.str _) => return true
| .lit (.nat v) =>
-- The old compiler's implementation used the runtime's `is_scalar` function, which
-- introduces a dependency on the architecture used by the compiler.
return !isRoot || v >= Nat.pow 2 63
| .lit _ | .erased => return !isRoot
| .const name _ args =>
if (← read).sccDecls.any (·.name == name) then
return false
if hasNeverExtractAttribute (← getEnv) name then
return false
if isRoot then
if let some constInfo := (← getEnv).find? name then
let shouldExtract := match constInfo with
| .defnInfo val => val.type.isForall
| .ctorInfo _ => !(args.all isIrrelevantArg)
| _ => true
if !shouldExtract then
return false
if let some decl ← LCNF.getMonoDecl? name then
-- We don't want to extract constants as root terms
if decl.getArity == 0 then
return false
args.allM shouldExtractArg
| .fvar fnVar args => return (← shouldExtractFVar fnVar) && (← args.allM shouldExtractArg)
| .proj _ _ baseVar => shouldExtractFVar baseVar
partial def shouldExtractArg (arg : Arg .pure) : M Bool := do
match arg with
| .fvar fvarId => shouldExtractFVar fvarId
| .type _ | .erased => return true
partial def shouldExtractFVar (fvarId : FVarId) : M Bool := do
if let some result := (← get).fvarDecisionCache[fvarId]? then
return result
else
let result ← go
modify fun s => { s with fvarDecisionCache := s.fvarDecisionCache.insert fvarId result }
return result
where
go : M Bool := do
if let some letDecl ← findLetDecl? fvarId then
shouldExtractLetValue false letDecl.value
else
return false
end
mutual
partial def visitCode (code : Code .pure) : M (Code .pure) := do
match code with
| .let decl k =>
if (← shouldExtractLetValue true decl.value) then
let ⟨_, decls⟩ ← extractLetValue decl.value |>.run {}
let decls := decls.reverse.push (.let decl)
let decls ← decls.mapM Internalize.internalizeCodeDecl |>.run' {}
let closedCode := attachCodeDecls decls (.return decls.back!.fvarId)
let closedExpr := closedCode.toExpr
let env ← getEnv
let name ← if let some closedTermName := getClosedTermName? env closedExpr then
eraseCode closedCode
pure closedTermName
else
let name := (← read).baseName ++ (`_closed).appendIndexAfter (← get).decls.size
cacheClosedTermName env closedExpr name |> setEnv
let decl := { name, levelParams := [], type := decl.type, params := #[],
value := .code closedCode, inlineAttr? := some .noinline }
decl.saveMono
modify fun s => { s with decls := s.decls.push decl }
pure name
let decl ← decl.updateValue (.const name [] #[])
return code.updateLet! decl (← visitCode k)
else
return code.updateLet! decl (← visitCode k)
| .fun decl k =>
let decl ← decl.updateValue (← visitCode decl.value)
return code.updateFun! decl (← visitCode k)
| .jp decl k =>
let decl ← decl.updateValue (← visitCode decl.value)
return code.updateFun! decl (← visitCode k)
| .cases cases =>
let alts ← cases.alts.mapM (fun alt => do return alt.updateCode (← visitCode alt.getCode))
return code.updateAlts! alts
| .jmp .. | .return _ | .unreach .. => return code
end
def visitDecl (decl : Decl .pure) : M (Decl .pure) := do
let value ← decl.value.mapCodeM visitCode
return { decl with value }
end ExtractClosed
partial def Decl.extractClosed (decl : Decl .pure) (sccDecls : Array (Decl .pure)) :
CompilerM (Array (Decl .pure)) := do
let ⟨decl, s⟩ ← ExtractClosed.visitDecl decl |>.run { baseName := decl.name, sccDecls } |>.run {}
return s.decls.push decl
def extractClosed : Pass where
phase := .mono
name := `extractClosed
run := fun decls => do
if (← getConfig).extractClosed then
decls.foldlM (init := #[]) fun newDecls decl =>
return newDecls ++ (← decl.extractClosed decls)
else
return decls
builtin_initialize registerTraceClass `Compiler.extractClosed (inherited := true)
end Lean.Compiler.LCNF