blob: 86d0978813d7cb4cf7d5987716d55b9d28b874b1 [file]
/-
Copyright (c) 2022 Henrik Böving. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Henrik Böving
-/
import Lean.Compiler.LCNF.CompilerM
import Lean.Compiler.LCNF.InferType
import Lean.Compiler.LCNF.PassManager
namespace Lean.Compiler.LCNF.Simp
namespace ConstantFold
/--
A constant folding monad, the additional state stores auxiliary declarations
required to build the new constant.
-/
abbrev FolderM := StateRefT (Array CodeDecl) CompilerM
/--
A constant folder for a specific function, takes all the arguments of a
certain function and produces a new `Expr` + auxiliary declarations in
the `FolderM` monad on success. If the folding fails it returns `none`.
-/
abbrev Folder := Array Arg → FolderM (Option LetValue)
/--
A typeclass for detecting and producing literals of arbitrary types
inside of LCNF.
-/
class Literal (α : Type) where
/--
Attempt to turn the provided `Expr` into a value of type `α` if
it is whatever concept of a literal `α` has. Note that this function
does assume that the provided `Expr` does indeed have type `α`.
-/
getLit : FVarId → CompilerM (Option α)
/--
Turn a value of type `α` into a series of auxiliary `LetDecl`s + a
final `Expr` putting them all together into a literal of type `α`,
where again the idea of what a literal is depends on `α`.
-/
mkLit : α → FolderM LetValue
export Literal (getLit mkLit)
/--
A wrapper around `LCNF.mkAuxLetDecl` that will automatically store the
`LetDecl` in the state of `FolderM`.
-/
def mkAuxLetDecl (e : LetValue) (prefixName := `_x) : FolderM FVarId := do
let decl ← LCNF.mkAuxLetDecl e prefixName
modify fun s => s.push <| .let decl
return decl.fvarId
section Literals
/--
A wrapper around `mkAuxLetDecl` that also calls `mkLit`.
-/
def mkAuxLit [Literal α] (x : α) (prefixName := `_x) : FolderM FVarId := do
let lit ← mkLit x
mkAuxLetDecl lit prefixName
partial def getNatLit (fvarId : FVarId) : CompilerM (Option Nat) := do
let some (.value (.natVal n)) ← findLetValue? fvarId | return none
return n
def mkNatLit (n : Nat) : FolderM LetValue :=
return .value (.natVal n)
instance : Literal Nat where
getLit := getNatLit
mkLit := mkNatLit
def getStringLit (fvarId : FVarId) : CompilerM (Option String) := do
let some (.value (.strVal s)) ← findLetValue? fvarId | return none
return s
def mkStringLit (n : String) : FolderM LetValue :=
return .value (.strVal n)
instance : Literal String where
getLit := getStringLit
mkLit := mkStringLit
def getBoolLit (fvarId : FVarId) : CompilerM (Option Bool) := do
let some (.const ctor [] #[]) ← findLetValue? fvarId | return none
return ctor == ``Bool.true
def mkBoolLit (b : Bool) : FolderM LetValue :=
let ctor := if b then ``Bool.true else ``Bool.false
return .const ctor [] #[]
instance : Literal Bool where
getLit := getBoolLit
mkLit := mkBoolLit
private partial def getLitAux [Inhabited α] (fvarId : FVarId) (ofNat : Nat → α) (ofNatName : Name) : CompilerM (Option α) := do
let some (.const declName _ #[.fvar fvarId]) ← findLetValue? fvarId | return none
unless declName == ofNatName do return none
let some natLit ← getLit fvarId | return none
return ofNat natLit
def mkNatWrapperInstance [Inhabited α] (ofNat : Nat → α) (ofNatName : Name) (toNat : α → Nat) : Literal α where
getLit := (getLitAux · ofNat ofNatName)
mkLit x := do
let helperId ← mkAuxLit <| toNat x
return .const ofNatName [] #[.fvar helperId]
instance : Literal UInt8 := mkNatWrapperInstance UInt8.ofNat ``UInt8.ofNat UInt8.toNat
instance : Literal UInt16 := mkNatWrapperInstance UInt16.ofNat ``UInt16.ofNat UInt16.toNat
instance : Literal UInt32 := mkNatWrapperInstance UInt32.ofNat ``UInt32.ofNat UInt32.toNat
instance : Literal UInt64 := mkNatWrapperInstance UInt64.ofNat ``UInt64.ofNat UInt64.toNat
instance : Literal Char := mkNatWrapperInstance Char.ofNat ``Char.ofNat Char.toNat
end Literals
/--
Turns an expression chain of the form
```
let _x.1 := @List.nil _
let _x.2 := @List.cons _ a _x.1
let _x.3 := @List.cons _ b _x.2
let _x.4 := @List.cons _ c _x.3
let _x.5 := @List.cons _ d _x.4
let _x.6 := @List.cons _ e _x.5
```
into: `[a, b, c, d ,e]` + The type contained in the list
-/
partial def getPseudoListLiteral (fvarId : FVarId) : CompilerM (Option (List FVarId × Expr × Level)) := do
go fvarId []
where
go (fvarId : FVarId) (fvarIds : List FVarId) : CompilerM (Option (List FVarId × Expr × Level)) := do
let some e ← findLetValue? fvarId | return none
match e with
| .const ``List.nil [u] #[.type α] =>
return some (fvarIds.reverse, α, u)
| .const ``List.cons _ #[_, .fvar h, .fvar t] =>
go t (h :: fvarIds)
| _ => return none
/--
Turn an `#[a, b, c]` into:
```
let _x.12 := 3
let _x.8 := @Array.mkEmpty _ _x.12
let _x.22 := @Array.push _ _x.8 x
let _x.24 := @Array.push _ _x.22 y
let _x.26 := @Array.push _ _x.24 z
_x.26
```
-/
def mkPseudoArrayLiteral (elements : Array FVarId) (typ : Expr) (typLevel : Level) : FolderM LetValue := do
let sizeLit ← mkAuxLit elements.size
let mut literal ← mkAuxLetDecl <| .const ``Array.mkEmpty [typLevel] #[.type typ, .fvar sizeLit]
for element in elements do
literal ← mkAuxLetDecl <| .const ``Array.push [typLevel] #[.type typ, .fvar literal, .fvar element]
return .fvar literal #[]
/--
Evaluate array literals at compile time, that is turn:
```
let _x.1 := @List.nil _
let _x.2 := @List.cons _ z _x.1
let _x.3 := @List.cons _ y _x.2
let _x.4 := @List.cons _ x _x.3
let _x.5 := @List.toArray _ _x.4
```
To its array form:
```
let _x.12 := 3
let _x.8 := @Array.mkEmpty _ _x.12
let _x.22 := @Array.push _ _x.8 x
let _x.24 := @Array.push _ _x.22 y
let _x.26 := @Array.push _ _x.24 z
```
-/
def foldArrayLiteral : Folder := fun args => do
let #[_, .fvar fvarId] := args | return none
let some (list, typ, level) ← getPseudoListLiteral fvarId | return none
let arr := Array.mk list
let lit ← mkPseudoArrayLiteral arr typ level
return some lit
/--
Turn a unary function such as `Nat.succ` into a constant folder.
-/
def Folder.mkUnary [Literal α] [Literal β] (folder : α → β) : Folder := fun args => do
let #[.fvar fvarId] := args | return none
let some arg1 ← getLit fvarId | return none
let res := folder arg1
mkLit res
/--
Turn a binary function such as `Nat.add` into a constant folder.
-/
def Folder.mkBinary [Literal α] [Literal β] [Literal γ] (folder : α → β → γ) : Folder := fun args => do
let #[.fvar fvarId₁, .fvar fvarId₂] := args | return none
let some arg₁ ← getLit fvarId₁ | return none
let some arg₂ ← getLit fvarId₂ | return none
mkLit <| folder arg₁ arg₂
def Folder.mkBinaryDecisionProcedure [Literal α] [Literal β] {r : α → β → Prop} (folder : (a : α) → (b : β) → Decidable (r a b)) : Folder := fun args => do
if (← getPhase) < .mono then
return none
let #[.fvar fvarId₁, .fvar fvarId₂] := args | return none
let some arg₁ ← getLit fvarId₁ | return none
let some arg₂ ← getLit fvarId₂ | return none
let boolLit := folder arg₁ arg₂ |>.decide
mkLit boolLit
/--
Provide a folder for an operation with a left neutral element.
-/
def Folder.leftNeutral [Literal α] [BEq α] (neutral : α) : Folder := fun args => do
let #[.fvar fvarId₁, .fvar fvarId₂] := args | return none
let some arg₁ ← getLit fvarId₁ | return none
unless arg₁ == neutral do return none
return some <| .fvar fvarId₂ #[]
/--
Provide a folder for an operation with a right neutral element.
-/
def Folder.rightNeutral [Literal α] [BEq α] (neutral : α) : Folder := fun args => do
let #[.fvar fvarId₁, .fvar fvarId₂] := args | return none
let some arg₂ ← getLit fvarId₂ | return none
unless arg₂ == neutral do return none
return some <| .fvar fvarId₁ #[]
/--
Provide a folder for an operation with a left annihilator.
-/
def Folder.leftAnnihilator [Literal α] [BEq α] (annihilator : α) (zero : α) : Folder := fun args => do
let #[.fvar fvarId, _] := args | return none
let some arg ← getLit fvarId | return none
unless arg == annihilator do return none
mkLit zero
/--
Provide a folder for an operation with a right annihilator.
-/
def Folder.rightAnnihilator [Literal α] [BEq α] (annihilator : α) (zero : α) : Folder := fun args => do
let #[_, .fvar fvarId] := args | return none
let some arg ← getLit fvarId | return none
unless arg == annihilator do return none
mkLit zero
def Folder.divShift [Literal α] [BEq α] (shiftRight : Name) (pow2 : α → α) (log2 : α → α) : Folder := fun args => do
unless (← getEnv).contains shiftRight do return none
let #[lhs, .fvar fvarId] := args | return none
let some rhs ← getLit fvarId | return none
let exponent := log2 rhs
unless pow2 exponent == rhs do return none
let shiftLit ← mkAuxLit exponent
return some <| .const shiftRight [] #[lhs, .fvar shiftLit]
def Folder.mulRhsShift [Literal α] [BEq α] (shiftLeft : Name) (pow2 : α → α) (log2 : α → α) : Folder := fun args => do
unless (← getEnv).contains shiftLeft do return none
let #[lhs, .fvar fvarId] := args | return none
let some rhs ← getLit fvarId | return none
let exponent := log2 rhs
unless pow2 exponent == rhs do return none
let shiftLit ← mkAuxLit exponent
return some <| .const shiftLeft [] #[lhs, .fvar shiftLit]
def Folder.mulLhsShift [Literal α] [BEq α] (shiftLeft : Name) (pow2 : α → α) (log2 : α → α) : Folder := fun args => do
unless (← getEnv).contains shiftLeft do return none
let #[.fvar fvarId, rhs] := args | return none
let some lhs ← getLit fvarId | return none
let exponent := log2 lhs
unless pow2 exponent == lhs do return none
let shiftLit ← mkAuxLit exponent
return some <| .const shiftLeft [] #[rhs, .fvar shiftLit]
/--
Pick the first folder out of `folders` that succeeds.
-/
def Folder.first (folders : Array Folder) : Folder := fun exprs => do
let backup ← get
for folder in folders do
if let some res ← folder exprs then
return res
else
set backup
return none
/--
Provide a folder for an operation that has the same left and right neutral element.
-/
def Folder.leftRightNeutral [Literal α] [BEq α] (neutral : α) : Folder :=
Folder.first #[Folder.leftNeutral neutral, Folder.rightNeutral neutral]
/--
Provide a folder for an operation that has the same left and right annihilator.
-/
def Folder.leftRightAnnihilator [Literal α] [BEq α] (annihilator : α) (zero : α) : Folder :=
Folder.first #[Folder.leftAnnihilator annihilator zero, Folder.rightAnnihilator annihilator zero]
/--
Literal folders for higher order datastructures.
-/
def higherOrderLiteralFolders : List (Name × Folder) := [
(``List.toArray, foldArrayLiteral)
]
def Folder.mulShift [Literal α] [BEq α] (shiftLeft : Name) (pow2 : α → α) (log2 : α → α) : Folder :=
Folder.first #[Folder.mulLhsShift shiftLeft pow2 log2, Folder.mulRhsShift shiftLeft pow2 log2]
/--
All arithmetic folders.
-/
def arithmeticFolders : List (Name × Folder) := [
(``Nat.succ, Folder.mkUnary Nat.succ),
(``Nat.add, Folder.first #[Folder.mkBinary Nat.add, Folder.leftRightNeutral 0]),
(``UInt8.add, Folder.first #[Folder.mkBinary UInt8.add, Folder.leftRightNeutral (0 : UInt8)]),
(``UInt16.add, Folder.first #[Folder.mkBinary UInt16.add, Folder.leftRightNeutral (0 : UInt16)]),
(``UInt32.add, Folder.first #[Folder.mkBinary UInt32.add, Folder.leftRightNeutral (0 : UInt32)]),
(``UInt64.add, Folder.first #[Folder.mkBinary UInt64.add, Folder.leftRightNeutral (0 : UInt64)]),
(``Nat.sub, Folder.first #[Folder.mkBinary Nat.sub, Folder.leftRightNeutral 0]),
(``UInt8.sub, Folder.first #[Folder.mkBinary UInt8.sub, Folder.leftRightNeutral (0 : UInt8)]),
(``UInt16.sub, Folder.first #[Folder.mkBinary UInt16.sub, Folder.leftRightNeutral (0 : UInt16)]),
(``UInt32.sub, Folder.first #[Folder.mkBinary UInt32.sub, Folder.leftRightNeutral (0 : UInt32)]),
(``UInt64.sub, Folder.first #[Folder.mkBinary UInt64.sub, Folder.leftRightNeutral (0 : UInt64)]),
(``Nat.mul, Folder.first #[Folder.mkBinary Nat.mul, Folder.leftRightNeutral 1, Folder.leftRightAnnihilator 0 0, Folder.mulShift ``Nat.shiftLeft (Nat.pow 2) Nat.log2]),
(``UInt8.mul, Folder.first #[Folder.mkBinary UInt8.mul, Folder.leftRightNeutral (1 : UInt8), Folder.leftRightAnnihilator (0 : UInt8) 0, Folder.mulShift ``UInt8.shiftLeft (UInt8.shiftLeft 1 ·) UInt8.log2]),
(``UInt16.mul, Folder.first #[Folder.mkBinary UInt16.mul, Folder.leftRightNeutral (1 : UInt16), Folder.leftRightAnnihilator (0 : UInt16) 0, Folder.mulShift ``UInt16.shiftLeft (UInt16.shiftLeft 1 ·) UInt16.log2]),
(``UInt32.mul, Folder.first #[Folder.mkBinary UInt32.mul, Folder.leftRightNeutral (1 : UInt32), Folder.leftRightAnnihilator (0 : UInt32) 0, Folder.mulShift ``UInt32.shiftLeft (UInt32.shiftLeft 1 ·) UInt32.log2]),
(``UInt64.mul, Folder.first #[Folder.mkBinary UInt64.mul, Folder.leftRightNeutral (1 : UInt64), Folder.leftRightAnnihilator (0 : UInt64) 0, Folder.mulShift ``UInt64.shiftLeft (UInt64.shiftLeft 1 ·) UInt64.log2]),
(``Nat.div, Folder.first #[Folder.mkBinary Nat.div, Folder.rightNeutral 1, Folder.divShift ``Nat.shiftRight (Nat.pow 2) Nat.log2]),
(``UInt8.div, Folder.first #[Folder.mkBinary UInt8.div, Folder.rightNeutral (1 : UInt8), Folder.divShift ``UInt8.shiftRight (UInt8.shiftLeft 1 ·) UInt8.log2]),
(``UInt16.div, Folder.first #[Folder.mkBinary UInt16.div, Folder.rightNeutral (1 : UInt16), Folder.divShift ``UInt16.shiftRight (UInt16.shiftLeft 1 ·) UInt16.log2]),
(``UInt32.div, Folder.first #[Folder.mkBinary UInt32.div, Folder.rightNeutral (1 : UInt32), Folder.divShift ``UInt32.shiftRight (UInt32.shiftLeft 1 ·) UInt32.log2]),
(``UInt64.div, Folder.first #[Folder.mkBinary UInt64.div, Folder.rightNeutral (1 : UInt64), Folder.divShift ``UInt64.shiftRight (UInt64.shiftLeft 1 ·) UInt64.log2])
]
def relationFolders : List (Name × Folder) := [
(``Nat.decEq, Folder.mkBinaryDecisionProcedure Nat.decEq),
(``Nat.decLt, Folder.mkBinaryDecisionProcedure Nat.decLt),
(``Nat.decLe, Folder.mkBinaryDecisionProcedure Nat.decLe),
(``UInt8.decEq, Folder.mkBinaryDecisionProcedure UInt8.decEq),
(``UInt8.decLt, Folder.mkBinaryDecisionProcedure UInt8.decLt),
(``UInt8.decLe, Folder.mkBinaryDecisionProcedure UInt8.decLe),
(``UInt16.decEq, Folder.mkBinaryDecisionProcedure UInt16.decEq),
(``UInt16.decLt, Folder.mkBinaryDecisionProcedure UInt16.decLt),
(``UInt16.decLe, Folder.mkBinaryDecisionProcedure UInt16.decLe),
(``UInt32.decEq, Folder.mkBinaryDecisionProcedure UInt32.decEq),
(``UInt32.decLt, Folder.mkBinaryDecisionProcedure UInt32.decLt),
(``UInt32.decLe, Folder.mkBinaryDecisionProcedure UInt32.decLe),
(``UInt64.decEq, Folder.mkBinaryDecisionProcedure UInt64.decEq),
(``UInt64.decLt, Folder.mkBinaryDecisionProcedure UInt64.decLt),
(``UInt64.decLe, Folder.mkBinaryDecisionProcedure UInt64.decLe),
(``Bool.decEq, Folder.mkBinaryDecisionProcedure Bool.decEq),
(``Bool.decEq, Folder.mkBinaryDecisionProcedure String.decEq)
]
/--
All string folders.
-/
def stringFolders : List (Name × Folder) := [
(``String.append, Folder.first #[Folder.mkBinary String.append, Folder.leftRightNeutral ""]),
(``String.length, Folder.mkUnary String.length),
(``String.push, Folder.mkBinary String.push)
]
/--
Apply all known folders to `decl`.
-/
def applyFolders (decl : LetDecl) (folders : SMap Name Folder) : CompilerM (Option (Array CodeDecl)) := do
match decl.value with
| .const name _ args =>
if let some folder := folders.find? name then
if let (some res, aux) ← folder args |>.run #[] then
let decl ← decl.updateValue res
return some <| aux.push (.let decl)
return none
| _ => return none
private unsafe def getFolderCoreUnsafe (env : Environment) (opts : Options) (declName : Name) : ExceptT String Id Folder :=
env.evalConstCheck Folder opts ``Folder declName
@[implemented_by getFolderCoreUnsafe]
private opaque getFolderCore (env : Environment) (opts : Options) (declName : Name) : ExceptT String Id Folder
private def getFolder (declName : Name) : CoreM Folder := do
ofExcept <| getFolderCore (← getEnv) (← getOptions) declName
def builtinFolders : SMap Name Folder :=
(arithmeticFolders ++ relationFolders ++ higherOrderLiteralFolders ++ stringFolders).foldl (init := {}) fun s (declName, folder) =>
s.insert declName folder
structure FolderOleanEntry where
declName : Name
folderDeclName : Name
structure FolderEntry extends FolderOleanEntry where
folder : Folder
builtin_initialize folderExt : PersistentEnvExtension FolderOleanEntry FolderEntry (List FolderOleanEntry × SMap Name Folder) ←
registerPersistentEnvExtension {
mkInitial := return ([], builtinFolders)
addImportedFn := fun entriesArray => do
let ctx ← read
let mut folders := builtinFolders
for entries in entriesArray do
for { declName, folderDeclName } in entries do
let folder ← IO.ofExcept <| getFolderCore ctx.env ctx.opts folderDeclName
folders := folders.insert declName folder
return ([], folders.switch)
addEntryFn := fun (entries, map) entry => (entry.toFolderOleanEntry :: entries, map.insert entry.declName entry.folder)
exportEntriesFn := fun (entries, _) => entries.reverse.toArray
}
def registerFolder (declName : Name) (folderDeclName : Name) : CoreM Unit := do
let folder ← getFolder folderDeclName
modifyEnv fun env => folderExt.addEntry env { declName, folderDeclName, folder }
def getFolders : CoreM (SMap Name Folder) :=
return folderExt.getState (← getEnv) |>.2
/--
Apply a list of default folders to `decl`
-/
def foldConstants (decl : LetDecl) : CompilerM (Option (Array CodeDecl)) := do
applyFolders decl (← getFolders)
end ConstantFold
end Lean.Compiler.LCNF.Simp