blob: 50e43769aef1fea16c374ccff08aa18b04ee1451 [file]
/-
Copyright (c) 2022 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
import Lean.Compiler.ImplementedByAttr
import Lean.Compiler.LCNF.ElimDead
import Lean.Compiler.LCNF.AlphaEqv
import Lean.Compiler.LCNF.PrettyPrinter
import Lean.Compiler.LCNF.Bind
import Lean.Compiler.LCNF.Simp.FunDeclInfo
import Lean.Compiler.LCNF.Simp.InlineCandidate
import Lean.Compiler.LCNF.Simp.InlineProj
import Lean.Compiler.LCNF.Simp.Used
import Lean.Compiler.LCNF.Simp.DefaultAlt
import Lean.Compiler.LCNF.Simp.SimpValue
import Lean.Compiler.LCNF.Simp.ConstantFold
namespace Lean.Compiler.LCNF
namespace Simp
/--
Return `true` if `c` has only one exit point.
This is a quick approximation. It does not check cases
such as: a `cases` with many but only one alternative is not reachable.
It is only used to avoid the creation of auxiliary join points, and does not need
to be precise.
-/
private partial def oneExitPointQuick (c : Code) : Bool :=
go c
where
go (c : Code) : Bool :=
match c with
| .let _ k | .fun _ k => go k
-- Approximation, the cases may have many unreachable alternatives, and only reachable.
| .cases c => c.alts.size == 1 && go c.alts[0]!.getCode
-- Approximation, we assume that any code containing join points have more than one exit point
| .jp .. | .jmp .. | .unreach .. => false
| .return .. => true
/--
Create a new local function declaration when `info.args.size < info.params.size`.
We use this function to inline/specialize a partial application of a local function.
-/
def specializePartialApp (info : InlineCandidateInfo) : SimpM FunDecl := do
let mut subst := {}
for param in info.params, arg in info.args do
subst := subst.insert param.fvarId arg.toExpr
let mut paramsNew := #[]
for param in info.params[info.args.size:] do
let type ← replaceExprFVars param.type subst (translator := true)
let paramNew ← mkAuxParam type
paramsNew := paramsNew.push paramNew
subst := subst.insert param.fvarId (.fvar paramNew.fvarId)
let code ← info.value.internalize subst
updateFunDeclInfo code
mkAuxFunDecl paramsNew code
/--
Try to inline a join point.
-/
partial def inlineJp? (fvarId : FVarId) (args : Array Arg) : SimpM (Option Code) := do
/- Remark: we don't need to use `findFunDecl'?` here. -/
let some decl ← findFunDecl? fvarId | return none
unless (← shouldInlineLocal decl) do return none
markSimplified
betaReduce decl.params decl.value args
/--
When the configuration flag `etaPoly = true`, we eta-expand
partial applications of functions that take local instances as arguments.
This kind of function is inlined or specialized, and we create new
simplification opportunities by eta-expanding them.
-/
def etaPolyApp? (letDecl : LetDecl) : OptionT SimpM FunDecl := do
guard <| (← read).config.etaPoly
let .const declName us args := letDecl.value | failure
let some info := (← getEnv).find? declName | failure
guard <| hasLocalInst info.type
guard <| !(← Meta.isInstance declName)
let some decl ← getDecl? declName | failure
guard <| decl.getArity > args.size
let params ← mkNewParams letDecl.type
let auxDecl ← mkAuxLetDecl (.const declName us (args ++ params.map (.fvar ·.fvarId)))
let funDecl ← mkAuxFunDecl params (.let auxDecl (.return auxDecl.fvarId))
addFVarSubst letDecl.fvarId funDecl.fvarId
eraseLetDecl letDecl
return funDecl
/--
Similar to `Code.isReturnOf`, but taking the current substitution into account.
-/
def isReturnOf (c : Code) (fvarId : FVarId) : SimpM Bool := do
match c with
| .return fvarId' => match (← normFVar fvarId') with
| .fvar fvarId'' => return fvarId'' == fvarId
| .erased => return false
| _ => return false
def elimVar? (value : LetValue) : SimpM (Option FVarId) := do
let .fvar fvarId #[] := value | return none
return fvarId
mutual
/--
If the value of the given let-declaration is an application that can be inlined,
inline it and simplify the result.
`k` is the "continuation" for the let declaration, if the application is inlined,
it will also be simplified.
Note: `inlineApp?` did not use to be in this mutually recursive declaration.
It used to be invoked by `simp`, and would return `Option Code` that would be
then simplified by `simp`. However, this simpler architecture produced an
exponential blowup in when processing functions such as `Lean.Elab.Deriving.Ord.mkMatch.mkAlts`.
The key problem is that when inlining a declaration we often can reduce the number
of exit points by simplified the inlined code, and then connecting the result to the
continuation `k`. However, this optimization is only possible if we simplify the
inlined code **before** we attach it to the continuation.
-/
partial def inlineApp? (letDecl : LetDecl) (k : Code) : SimpM (Option Code) := do
let some info ← inlineCandidate? letDecl.value | return none
let numArgs := info.args.size
withInlining letDecl.value info.recursive do
let fvarId := letDecl.fvarId
if numArgs < info.arity then
let funDecl ← specializePartialApp info
addFVarSubst fvarId funDecl.fvarId
markSimplified
simp (.fun funDecl k)
else
let code ← betaReduce info.params info.value info.args[:info.arity]
if k.isReturnOf fvarId && numArgs == info.arity then
/- Easy case, the continuation `k` is just returning the result of the application. -/
markSimplified
simp code
else
let code ← simp code
let simpK (result : FVarId) : SimpM Code := do
/- `result` contains the result of the inlined code -/
if numArgs > info.arity then
let decl ← mkAuxLetDecl (.fvar result info.args[info.arity:])
addFVarSubst fvarId decl.fvarId
simp (.let decl k)
else
addFVarSubst fvarId result
simp k
if oneExitPointQuick code then
-- TODO: if `k` is small, we should also inline it here
markSimplified
code.bind fun fvarId' => do
markUsedFVar fvarId'
simpK fvarId'
-- else if info.ifReduce then
-- eraseCode code
-- return none
else
markSimplified
let expectedType ← inferAppType info.fType info.args[:info.arity]
if expectedType.headBeta.isForall then
/-
If `code` returns a function, we create an auxiliary local function declaration (and eta-expand it)
instead of creating a joinpoint that takes a closure as an argument.
-/
let auxFunDecl ← mkAuxFunDecl #[] code
let auxFunDecl ← auxFunDecl.etaExpand
let k ← simpK auxFunDecl.fvarId
attachCodeDecls #[.fun auxFunDecl] k
else
let jpParam ← mkAuxParam expectedType
let jpValue ← simpK jpParam.fvarId
let jpDecl ← mkAuxJpDecl #[jpParam] jpValue
let code ← code.bind fun fvarId => return .jmp jpDecl.fvarId #[.fvar fvarId]
return Code.jp jpDecl code
/--
Simplify the given local function declaration.
-/
partial def simpFunDecl (decl : FunDecl) : SimpM FunDecl := do
let type ← normExpr decl.type
let params ← normParams decl.params
let value ← simp decl.value
decl.update type params value
/--
Try to simplify `cases` of `constructor`
-/
partial def simpCasesOnCtor? (cases : Cases) : SimpM (Option Code) := do
match (← normFVar cases.discr) with
| .erased => mkReturnErased
| .fvar discr =>
let some ctorInfo ← findCtor? discr | return none
let (alt, cases) := cases.extractAlt! ctorInfo.getName
eraseCode (.cases cases)
markSimplified
match alt with
| .default k => simp k
| .alt _ params k =>
match ctorInfo with
| .ctor ctorVal ctorArgs =>
let fields := ctorArgs[ctorVal.numParams:]
for param in params, field in fields do
addSubst param.fvarId field.toExpr
let k ← simp k
eraseParams params
return k
| .natVal 0 => simp k
| .natVal (n+1) =>
let auxDecl ← mkAuxLetDecl (.value (.natVal n))
addFVarSubst params[0]!.fvarId auxDecl.fvarId
let k ← simp k
eraseParams params
return some <| .let auxDecl k
/--
Simplify `code`
-/
partial def simp (code : Code) : SimpM Code := withIncRecDepth do
incVisited
match code with
| .let decl k =>
let baseDecl := decl
let mut decl ← normLetDecl baseDecl
if baseDecl != decl then
markSimplified
if let some value ← simpValue? decl.value then
markSimplified
decl ← decl.updateValue value
if let some decls ← ConstantFold.foldConstants decl then
markSimplified
let k ← simp k
attachCodeDecls decls k
else if let some funDecl ← etaPolyApp? decl then
simp (.fun funDecl k)
else if let some fvarId ← elimVar? decl.value then
/- Eliminate `let _x_i := _x_j;` -/
addFVarSubst decl.fvarId fvarId
eraseLetDecl decl
simp k
else if let some code ← inlineApp? decl k then
eraseLetDecl decl
return code
else if let some (decls, fvarId) ← inlineProjInst? decl.value then
addFVarSubst decl.fvarId fvarId
eraseLetDecl decl
let k ← simp k
attachCodeDecls decls k
else
let k ← simp k
if (← isUsed decl.fvarId) then
markUsedLetDecl decl
return code.updateLet! decl k
else
/- Dead variable elimination -/
eraseLetDecl decl
return k
| .fun decl k | .jp decl k =>
let mut decl := decl
let toBeInlined ← isOnceOrMustInline decl.fvarId
if toBeInlined then
/-
If the declaration will be inlined, it is wasteful to eagerly simplify it.
So, we just normalize it (i.e., apply the substitution to it).
-/
decl ← normFunDecl decl
else
/-
Note that functions in `decl` will be marked as used even if `decl` is not actually used.
They will only be deleted in the next pass. TODO: investigate whether this is a problem.
-/
if code.isFun then
if decl.isEtaExpandCandidate then
/- We must apply substitution before trying to eta-expand, otherwise `inferType` may fail. -/
decl ← normFunDecl decl
/-
We want to eta-expand **before** trying to simplify local function declaration because
eta-expansion creates many optimization opportunities.
-/
decl ← decl.etaExpand
markSimplified
decl ← simpFunDecl decl
let k ← simp k
if (← isUsed decl.fvarId) then
if toBeInlined then
/-
`decl` was supposed to be inlined, but there are still references to it.
Thus, we must all variables in `decl` as used. Recall it was not eagerly simplified.
-/
markUsedFunDecl decl
return code.updateFun! decl k
else
/- Dead function elimination -/
eraseFunDecl decl
return k
| .return fvarId =>
withNormFVarResult (← normFVar fvarId) fun fvarId => do
markUsedFVar fvarId
return code.updateReturn! fvarId
| .unreach type =>
return code.updateUnreach! (← normExpr type)
| .jmp fvarId args =>
withNormFVarResult (← normFVar fvarId) fun fvarId => do
let args ← normArgs args
if let some code ← inlineJp? fvarId args then
simp code
else
markUsedFVar fvarId
args.forM markUsedArg
return code.updateJmp! fvarId args
| .cases c =>
if let some k ← simpCasesOnCtor? c then
return k
else
withNormFVarResult (← normFVar c.discr) fun discr => do
let resultType ← normExpr c.resultType
markUsedFVar discr
let alts ← c.alts.mapMonoM fun alt => do
match alt with
| .alt ctorName ps k =>
if !(k matches .unreach ..) && (← ps.anyM fun p => isInductiveWithNoCtors p.type) then
let type ← k.inferType
eraseCode k
markSimplified
return alt.updateCode (.unreach type)
else
withDiscrCtor discr ctorName ps do
return alt.updateCode (← simp k)
| .default k => return alt.updateCode (← simp k)
let alts ← addDefaultAlt alts
if alts.size == 1 && alts[0]! matches .default .. then
return alts[0]!.getCode
else
return code.updateCases! resultType discr alts
end