blob: d0553efe669e591de7dafcb2a6a0e035b2e4a1d2 [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.Specialize
import Lean.Compiler.LCNF.FixedParams
import Lean.Compiler.LCNF.InferType
namespace Lean.Compiler.LCNF
/--
Each parameter is associated with a `SpecParamInfo`. This information is used by `LCNF/Specialize.lean`.
-/
inductive SpecParamInfo where
/--
A parameter that is an type class instance (or an arrow that produces a type class instance),
and is fixed in recursive declarations. By default, Lean always specializes this kind of argument.
-/
| fixedInst
/--
A parameter that is a function and is fixed in recursive declarations. If the user tags a declaration
with `@[specialize]` without specifying which arguments should be specialized, Lean will specialize
`.fixedHO` arguments in addition to `.fixedInst`.
-/
| fixedHO
/--
Computationally irrelevant parameters that are fixed in recursive declarations,
*and* there is a `fixedInst`, `fixedHO`, or `user` param that depends on it.
-/
| fixedNeutral
/--
An argument that has been specified in the `@[specialize]` attribute. Lean specializes it even if it is
not fixed in recursive declarations. Non-termination can happen, and Lean interrupts it with an error message
based on the stack depth.
-/
| user
/--
Parameter is not going to be specialized.
-/
| other
deriving Inhabited, Repr
instance : ToMessageData SpecParamInfo where
toMessageData
| .fixedInst => "I"
| .fixedHO => "H"
| .fixedNeutral => "N"
| .user => "U"
| .other => "O"
structure SpecState where
specInfo : PHashMap Name (Array SpecParamInfo) := {}
deriving Inhabited
structure SpecEntry where
declName : Name
paramsInfo : Array SpecParamInfo
deriving Inhabited
namespace SpecState
def addEntry (s : SpecState) (e : SpecEntry) : SpecState :=
match s with
| { specInfo } => { specInfo := specInfo.insert e.declName e.paramsInfo }
end SpecState
private abbrev declLt (a b : SpecEntry) :=
Name.quickLt a.declName b.declName
private abbrev sortEntries (entries : Array SpecEntry) : Array SpecEntry :=
entries.qsort declLt
private abbrev findAtSorted? (entries : Array SpecEntry) (declName : Name) : Option SpecEntry :=
entries.binSearch { declName, paramsInfo := #[] } declLt
/--
Extension for storing `SpecParamInfo` for declarations being compiled.
Remark: we only store information for declarations that will be specialized.
-/
builtin_initialize specExtension : SimplePersistentEnvExtension SpecEntry SpecState ←
registerSimplePersistentEnvExtension {
addEntryFn := SpecState.addEntry
addImportedFn := fun _ => {}
toArrayFn := fun s => sortEntries s.toArray
}
/--
Return `true` if `type` is a type tagged with `@[nospecialize]` or an arrow that produces this kind of type.
For example, this function returns true for `Inhabited Nat`, and `Nat → Inhabited Nat`.
-/
private def isNoSpecType (env : Environment) (type : Expr) : Bool :=
match type with
| .forallE _ _ b _ => isNoSpecType env b
| _ =>
if let .const declName _ := type.getAppFn then
hasNospecializeAttribute env declName
else
false
/-!
*Note*: `fixedNeutral` must have forward dependencies.
The code specializer consider a `fixedNeutral` parameter during code specialization
only if it contains forward dependecies that are tagged as `.user`, `.fixedHO`, or `.fixedInst`.
The motivation is to minimize the number of code specializations that have little or no impact on
performance. For example, let's consider the function.
```
def liftMacroM
{α : Type} {m : Type → Type}
[Monad m] [MonadMacroAdapter m] [MonadEnv m] [MonadRecDepth m] [MonadError m]
[MonadResolveName m] [MonadTrace m] [MonadOptions m] [AddMessageContext m] [MonadLiftT IO m] (x : MacroM α) : m α := do
```
The parameter `α` does not occur in any local instance, and `x` is marked as `.other` since the function
is not tagged as `[specialize]`. There is little value in considering `α` during code specialization,
but if we do many copies of this function will be generated.
Recall users may still force the code specializer to take `α` into account by using `[specialize α]` (`α` has `.user` info),
or `[specialize x]` (`α` has `.fixedNeutral` since `x` is a forward dependency tagged as `.user`),
or `[specialize]` (`α` has `.fixedNeutral` since `x` is a forward dependency tagged as `.fixedHO`).
-/
/--
Return `true` if parameter `j` of the given declaration has a forward dependency at parameter `k`,
and `k` is tagged as `.user`, `.fixedHO`, or `.fixedInst`.
See comment at `.fixedNeutral`.
-/
private def hasFwdDeps (decl : Decl) (paramsInfo : Array SpecParamInfo) (j : Nat) : Bool := Id.run do
let param := decl.params[j]!
for k in [j+1 : decl.params.size] do
if paramsInfo[k]! matches .user | .fixedHO | .fixedInst then
let param' := decl.params[k]!
if param'.type.containsFVar param.fvarId then
return true
return false
/--
Save parameter information for `decls`.
Remark: this function, similarly to `mkFixedArgMap`,
assumes that if a function `f` was declared in a mutual block, then `decls`
contains all (computationally relevant) functions in the mutual block.
-/
def saveSpecParamInfo (decls : Array Decl) : CompilerM Unit := do
let mut declsInfo := #[]
for decl in decls do
if hasNospecializeAttribute (← getEnv) decl.name then
declsInfo := declsInfo.push (mkArray decl.params.size .other)
else
let specArgs? := getSpecializationArgs? (← getEnv) decl.name
let contains (i : Nat) : Bool := specArgs?.getD #[] |>.contains i
let mut paramsInfo : Array SpecParamInfo := #[]
for i in [:decl.params.size] do
let param := decl.params[i]!
let info ←
if contains i then
pure .user
/-
If the user tagged class (e.g., `Inhabited`) with the `@[nospecialize]` attribute,
then parameters of this type should not be considered for specialization.
-/
else if isNoSpecType (← getEnv) param.type then
pure .other
else if isTypeFormerType param.type then
pure .fixedNeutral
else if (← isArrowClass? param.type).isSome then
pure .fixedInst
/-
Recall that if `specArgs? == some #[]`, then user annotated function with `@[specialize]`, but did not
specify which arguments must be specialized besides instances. In this case, we try to specialize
any "fixed higher-order argument"
-/
else if specArgs? == some #[] && param.type matches .forallE .. then
pure .fixedHO
else
pure .other
paramsInfo := paramsInfo.push info
pure ()
declsInfo := declsInfo.push paramsInfo
if declsInfo.any fun paramsInfo => paramsInfo.any (· matches .user | .fixedInst | .fixedHO) then
let m := mkFixedParamsMap decls
for i in [:decls.size] do
let decl := decls[i]!
let mut paramsInfo := declsInfo[i]!
let some mask := m.find? decl.name | unreachable!
trace[Compiler.specialize.info] "{decl.name} {mask}"
paramsInfo := paramsInfo.zipWith mask fun info fixed => if fixed || info matches .user then info else .other
for j in [:paramsInfo.size] do
let mut info := paramsInfo[j]!
if info matches .fixedNeutral && !hasFwdDeps decl paramsInfo j then
paramsInfo := paramsInfo.set! j .other
if paramsInfo.any fun info => info matches .fixedInst | .fixedHO | .user then
trace[Compiler.specialize.info] "{decl.name} {paramsInfo}"
modifyEnv fun env => specExtension.addEntry env { declName := decl.name, paramsInfo }
def getSpecParamInfoCore? (env : Environment) (declName : Name) : Option (Array SpecParamInfo) :=
match env.getModuleIdxFor? declName with
| some modIdx =>
if let some entry := findAtSorted? (specExtension.getModuleEntries env modIdx) declName then
some entry.paramsInfo
else
none
| none => (specExtension.getState env).specInfo.find? declName
def getSpecParamInfo? [Monad m] [MonadEnv m] (declName : Name) : m (Option (Array SpecParamInfo)) :=
return getSpecParamInfoCore? (← getEnv) declName
def isSpecCandidate [Monad m] [MonadEnv m] (declName : Name) : m Bool := do
return getSpecParamInfoCore? (← getEnv) declName |>.isSome
builtin_initialize
registerTraceClass `Compiler.specialize.info
end Lean.Compiler.LCNF