blob: 25c7d97a6e95a5c5ff771fb171f413d94c193578 [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.LCNF.CompilerM
import Lean.Compiler.LCNF.ToExpr
import Lean.Compiler.LCNF.PassManager
namespace Lean.Compiler.LCNF
/-! Common Sub-expression Elimination -/
namespace CSE
structure State where
map : PHashMap Expr FVarId := {}
subst : FVarSubst := {}
abbrev M := StateRefT State CompilerM
instance : MonadFVarSubst M false where
getSubst := return (← get).subst
instance : MonadFVarSubstState M where
modifySubst f := modify fun s => { s with subst := f s.subst }
@[inline] def getSubst : M FVarSubst :=
return (← get).subst
@[inline] def addEntry (value : Expr) (fvarId : FVarId) : M Unit :=
modify fun s => { s with map := s.map.insert value fvarId }
@[inline] def withNewScope (x : M α) : M α := do
let map := (← get).map
try x finally modify fun s => { s with map }
def replaceLet (decl : LetDecl) (fvarId : FVarId) : M Unit := do
eraseLetDecl decl
addFVarSubst decl.fvarId fvarId
def replaceFun (decl : FunDecl) (fvarId : FVarId) : M Unit := do
eraseFunDecl decl
addFVarSubst decl.fvarId fvarId
partial def _root_.Lean.Compiler.LCNF.Code.cse (code : Code) : CompilerM Code :=
go code |>.run' {}
where
goFunDecl (decl : FunDecl) : M FunDecl := do
let type ← normExpr decl.type
let params ← normParams decl.params
let value ← withNewScope do go decl.value
decl.update type params value
go (code : Code) : M Code := do
match code with
| .let decl k =>
let decl ← normLetDecl decl
-- We only apply CSE to pure code
let key := decl.value.toExpr
match (← get).map.find? key with
| some fvarId =>
replaceLet decl fvarId
go k
| none =>
addEntry key decl.fvarId
return code.updateLet! decl (← go k)
| .fun decl k =>
let decl ← goFunDecl decl
let value := decl.toExpr
match (← get).map.find? value with
| some fvarId' =>
replaceFun decl fvarId'
go k
| none =>
addEntry value decl.fvarId
return code.updateFun! decl (← go k)
| .jp decl k =>
let decl ← goFunDecl decl
/-
We currently don't eliminate common join points because we want to prevent
jumps to out-of-scope join points.
-/
return code.updateFun! decl (← go k)
| .cases c =>
withNormFVarResult (← normFVar c.discr) fun discr => do
let resultType ← normExpr c.resultType
let alts ← c.alts.mapMonoM fun alt => do
match alt with
| .alt _ ps k => withNewScope do
return alt.updateAlt! (← normParams ps) (← go k)
| .default k => withNewScope do return alt.updateCode (← go k)
return code.updateCases! resultType discr alts
| .return fvarId => withNormFVarResult (← normFVar fvarId) fun fvarId => return code.updateReturn! fvarId
| .jmp fvarId args => withNormFVarResult (← normFVar fvarId) fun fvarId => return code.updateJmp! fvarId (← normArgs args)
| .unreach .. => return code
end CSE
/--
Common sub-expression elimination
-/
def Decl.cse (decl : Decl) : CompilerM Decl := do
let value ← decl.value.cse
return { decl with value }
def cse (phase : Phase := .base) (occurrence := 0) : Pass :=
.mkPerDeclaration `cse Decl.cse phase occurrence
builtin_initialize
registerTraceClass `Compiler.cse (inherited := true)
end Lean.Compiler.LCNF