| /- | |
| Copyright (c) 2019 Microsoft Corporation. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Leonardo de Moura | |
| -/ | |
| module | |
| prelude | |
| public import Lean.Compiler.IR.CompilerM | |
| public import Lean.Compiler.IR.LiveVars | |
| public section | |
| namespace Lean.IR.ResetReuse | |
| /-! | |
| Remark: the insertResetReuse transformation is applied before we have | |
| inserted `inc/dec` instructions, and performed lower level optimizations | |
| that introduce the instructions `release` and `set`. | |
| -/ | |
| /-! | |
| Remark: the functions `S`, `D` and `R` defined here implement the | |
| corresponding functions in the paper "Counting Immutable Beans" | |
| Here are the main differences: | |
| - We use the State monad to manage the generation of fresh variable names. | |
| - Support for join points, and `uset` and `sset` instructions for unboxed data. | |
| - `D` uses the auxiliary function `Dmain`. | |
| - `Dmain` returns a pair `(b, found)` to avoid quadratic behavior when checking | |
| the last occurrence of the variable `x`. | |
| - Because we have join points in the actual implementation, a variable may be live even if it | |
| does not occur in a function body. See example at `livevars.lean`. | |
| -/ | |
| private def mayReuse (c₁ c₂ : CtorInfo) (relaxedReuse : Bool) : Bool := | |
| c₁.size == c₂.size && c₁.usize == c₂.usize && c₁.ssize == c₂.ssize && | |
| /- The following condition is a heuristic. | |
| If `relaxedReuse := false`, then we don't want to reuse cells from | |
| different constructors even when they are compatible | |
| because it produces counterintuitive behavior. -/ | |
| (relaxedReuse || c₁.name.getPrefix == c₂.name.getPrefix) | |
| /-- | |
| Replace `ctor` applications with `reuse` applications if compatible. | |
| `w` contains the "memory cell" being reused. | |
| -/ | |
| private partial def S (w : VarId) (c : CtorInfo) (relaxedReuse : Bool) (b : FnBody) : FnBody := | |
| go b | |
| where | |
| go : FnBody → FnBody | |
| | .vdecl x t v@(.ctor c' ys) b => | |
| if mayReuse c c' relaxedReuse then | |
| let updtCidx := c.cidx != c'.cidx | |
| .vdecl x t (.reuse w c' updtCidx ys) b | |
| else | |
| .vdecl x t v (go b) | |
| | .jdecl j ys v b => | |
| let v' := go v | |
| if v == v' then | |
| .jdecl j ys v (go b) | |
| else | |
| .jdecl j ys v' b | |
| | .case tid x xType alts => | |
| .case tid x xType <| alts.map fun alt => alt.modifyBody go | |
| | b => | |
| if b.isTerminal then | |
| b | |
| else | |
| let (instr, b) := b.split | |
| instr.setBody (go b) | |
| structure Context where | |
| env : Environment | |
| lctx : LocalContext := {} | |
| /-- | |
| Contains all variables in `cases` statements in the current path | |
| and variables that are already in `reset` statements when we | |
| invoke `R`. | |
| We use this information to prevent double-reset in code such as | |
| ``` | |
| case x_i : obj of | |
| Prod.mk → | |
| case x_i : obj of | |
| Prod.mk → | |
| ... | |
| ``` | |
| A variable can already be in a `reset` statement when we | |
| invoke `R` because we execute it with and without `relaxedReuse`. | |
| -/ | |
| alreadyFound : PHashSet VarId := {} | |
| /-- | |
| If `relaxedReuse := true`, then allow memory cells from different | |
| constructors to be reused. For example, we can reuse a `PSigma.mk` | |
| to allocate a `Prod.mk`. To avoid counterintuitive behavior, | |
| we first try `relaxedReuse := false`, and then `relaxedReuse := true`. | |
| -/ | |
| relaxedReuse : Bool := false | |
| /-- We use `Context` to track join points in scope. -/ | |
| abbrev M := ReaderT Context (StateT Index Id) | |
| private def mkFresh : M VarId := do | |
| let idx ← getModify fun n => n + 1 | |
| return { idx := idx } | |
| /-- | |
| Helper function for applying `S`. We only introduce a `reset` if we managed | |
| to replace a `ctor` with `reuse` in `b`. | |
| -/ | |
| private def tryS (x : VarId) (c : CtorInfo) (b : FnBody) : M FnBody := do | |
| let w ← mkFresh | |
| let b' := S w c (← read).relaxedReuse b | |
| if b == b' then | |
| return b | |
| else | |
| return .vdecl w .tobject (.reset c.size x) b' | |
| private def Dfinalize (x : VarId) (c : CtorInfo) : FnBody × Bool → M FnBody | |
| | (b, true) => return b | |
| | (b, false) => tryS x c b | |
| private def argsContainsVar (ys : Array Arg) (x : VarId) : Bool := | |
| ys.any fun arg => match arg with | |
| | .var y => x == y | |
| | _ => false | |
| private def isCtorUsing (b : FnBody) (x : VarId) : Bool := | |
| match b with | |
| | .vdecl _ _ (.ctor _ ys) _ => argsContainsVar ys x | |
| | _ => false | |
| inductive UseClassification where | |
| | ownedArg | |
| | other | |
| | none | |
| private def classifyUse (b : FnBody) (x : VarId) : M UseClassification := do | |
| match b with | |
| | .vdecl _ _ e@(.fap f args) _ => | |
| if let some decl := findEnvDecl (← read).env f then | |
| let mut result := .none | |
| for arg in args, param in decl.params do | |
| match arg with | |
| | .var y => | |
| if y == x then | |
| result := match result, param.borrow with | |
| | .ownedArg, true => .other | |
| | .ownedArg, false => .ownedArg | |
| | .other, _ => .other | |
| | .none, true => .other | |
| | .none, false => .ownedArg | |
| | .erased => pure () | |
| return result | |
| else | |
| if e.hasFreeVar x then | |
| return .ownedArg | |
| else | |
| return .none | |
| | .vdecl _ _ e@(.pap ..) _ | .vdecl _ _ e@(.ap ..) _ => | |
| if e.hasFreeVar x then | |
| return .ownedArg | |
| else | |
| return .none | |
| | _ => | |
| if b.hasFreeVar x then | |
| return .other | |
| else | |
| return .none | |
| /-- | |
| Given `Dmain b`, the resulting pair `(new_b, flag)` contains the new body `new_b`, | |
| and `flag == true` if `x` is live in `b`. | |
| Note that, in the function `D` defined in the paper, for each `let x := e; F`, | |
| `D` checks whether `x` is live in `F` or not. This is great for clarity but it | |
| is expensive: `O(n^2)` where `n` is the size of the function body. -/ | |
| private partial def Dmain (x : VarId) (c : CtorInfo) (e : FnBody) : M (FnBody × Bool) := do | |
| match e with | |
| | .case tid y yType alts => | |
| if e.hasLiveVar (← read).lctx x then | |
| /- If `x` is live in `e`, we recursively process each branch. -/ | |
| let alts ← alts.mapM fun alt => alt.modifyBodyM fun b => Dmain x c b >>= Dfinalize x c | |
| return (.case tid y yType alts, true) | |
| else | |
| return (e, false) | |
| | .jdecl j ys v b => | |
| let (b, found) ← withReader (fun ctx => { ctx with lctx := ctx.lctx.addJP j ys v }) (Dmain x c b) | |
| let (v, _ /- found' -/) ← Dmain x c v | |
| /- If `found' == true`, then `Dmain b` must also have returned `(b, true)` since | |
| we assume the IR does not have dead join points. So, if `x` is live in `j` (i.e., `v`), | |
| then it must also live in `b` since `j` is reachable from `b` with a `jmp`. | |
| On the other hand, `x` may be live in `b` but dead in `j` (i.e., `v`). -/ | |
| return (.jdecl j ys v b, found) | |
| | e => | |
| if e.isTerminal then | |
| return (e, e.hasLiveVar (← read).lctx x) | |
| else do | |
| let (instr, b) := e.split | |
| if isCtorUsing instr x then | |
| /- If the scrutinee `x` (the one that is providing memory) is being | |
| stored in a constructor, then reuse will probably not be able to reuse memory at runtime. | |
| It may work only if the new cell is consumed, but we ignore this case. -/ | |
| return (e, true) | |
| else | |
| let (b, found) ← Dmain x c b | |
| if found then | |
| return (instr.setBody b, true) | |
| else | |
| match (← classifyUse instr x) with | |
| | .ownedArg => | |
| return (instr.setBody b, true) | |
| | .other => | |
| let b ← tryS x c b | |
| return (instr.setBody b, true) | |
| | .none => | |
| return (instr.setBody b, false) | |
| private def D (x : VarId) (c : CtorInfo) (b : FnBody) : M FnBody := | |
| Dmain x c b >>= Dfinalize x c | |
| partial def R (e : FnBody) : M FnBody := do | |
| match e with | |
| | .case tid x xType alts => | |
| let alreadyFound := (← read).alreadyFound.contains x | |
| withReader (fun ctx => { ctx with alreadyFound := ctx.alreadyFound.insert x }) do | |
| let alts ← alts.mapM fun alt => do | |
| let alt ← alt.modifyBodyM R | |
| match alt with | |
| | .ctor c b => | |
| if c.isScalar || alreadyFound then | |
| -- If `alreadyFound`, then we don't try to reuse memory cell to avoid | |
| -- double reset. | |
| return alt | |
| else | |
| .ctor c <$> D x c b | |
| | .default _ => return alt | |
| return .case tid x xType alts | |
| | .jdecl j ys v b => | |
| let v ← R v | |
| let b ← withReader (fun ctx => { ctx with lctx := ctx.lctx.addJP j ys v }) (R b) | |
| return .jdecl j ys v b | |
| | e => | |
| if e.isTerminal then | |
| return e | |
| else | |
| let (instr, b) := e.split | |
| let b ← R b | |
| return instr.setBody b | |
| abbrev N := StateT (PHashSet VarId) Id | |
| partial def collectResets (e : FnBody) : N Unit := do | |
| match e with | |
| | .case _ _ _ alts => alts.forM fun alt => collectResets alt.body | |
| | .jdecl _ _ v b => collectResets v; collectResets b | |
| | .vdecl _ _ (.reset _ x) b => modify fun s => s.insert x; collectResets b | |
| | e => unless e.isTerminal do | |
| collectResets e.body | |
| end ResetReuse | |
| open ResetReuse | |
| def Decl.insertResetReuseCore (env : Environment) (d : Decl) (relaxedReuse : Bool) : Decl := | |
| match d with | |
| | .fdecl (body := b) .. => | |
| let nextIndex := d.maxIndex + 1 | |
| -- First time we execute `insertResetReuseCore`, `relaxedReuse := false`. | |
| let alreadyFound : PHashSet VarId := if relaxedReuse then (collectResets b *> get).run' {} else {} | |
| let bNew := R b { env, relaxedReuse, alreadyFound } |>.run' nextIndex | |
| d.updateBody! bNew | |
| | other => other | |
| def Decl.insertResetReuse (env : Environment) (d : Decl) : Decl := | |
| /- | |
| We execute the reset/reuse algorithm twice. The first time, we only reuse memory cells | |
| between identical constructor memory cells. That is, we do not reuse a `PSigma.mk` memory cell | |
| when allocating a `Prod.mk` memory cell, even though they have the same layout. Recall | |
| that the reset/reuse placement algorithm is a heuristic, and the first pass prevents reuses | |
| that are unlikely to be useful at runtime. Then, we run the procedure again, | |
| relaxing this restriction. If there are still opportunities for reuse, we will take advantage of them. | |
| The second pass addresses issue #4089. | |
| -/ | |
| d.insertResetReuseCore env (relaxedReuse := false) | |
| |>.insertResetReuseCore env (relaxedReuse := true) | |
| builtin_initialize registerTraceClass `compiler.ir.reset_reuse (inherited := true) | |
| end Lean.IR |