| /- | |
| 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.Runtime | |
| public import Lean.Compiler.IR.CompilerM | |
| public section | |
| namespace Lean.IR.ExplicitRC | |
| /-! | |
| Insert explicit RC instructions. So, it assumes the input code does not contain `inc` nor `dec` instructions. | |
| This transformation is applied before lower level optimizations | |
| that introduce the instructions `release` and `set` | |
| -/ | |
| structure DerivedValInfo where | |
| parent? : Option VarId | |
| children : VarIdSet | |
| deriving Inhabited | |
| abbrev DerivedValMap := Std.HashMap VarId DerivedValInfo | |
| namespace CollectDerivedValInfo | |
| structure State where | |
| varMap : DerivedValMap := {} | |
| borrowedParams : VarIdSet := {} | |
| abbrev M := StateM State | |
| private def visitParam (p : Param) : M Unit := | |
| modify fun s => { s with | |
| varMap := s.varMap.insert p.x { | |
| parent? := none | |
| children := {} | |
| } | |
| borrowedParams := | |
| if p.borrow && p.ty.isPossibleRef then | |
| s.borrowedParams.insert p.x | |
| else s.borrowedParams | |
| } | |
| private partial def addDerivedValue (parent : VarId) (child : VarId) : M Unit := do | |
| modify fun s => { s with | |
| varMap := s.varMap.modify parent fun info => | |
| { info with children := info.children.insert child } | |
| } | |
| modify fun s => { s with | |
| varMap := s.varMap.insert child { | |
| parent? := some parent | |
| children := {} | |
| } | |
| } | |
| private partial def removeFromParent (child : VarId) : M Unit := do | |
| if let some (some parent) := (← get).varMap.get? child |>.map (·.parent?) then | |
| modify fun s => { s with | |
| varMap := s.varMap.modify parent fun info => | |
| { info with children := info.children.erase child } | |
| } | |
| private partial def visitFnBody (b : FnBody) : M Unit := do | |
| match b with | |
| | .vdecl x _ e b => | |
| match e with | |
| | .proj _ parent => | |
| addDerivedValue parent x | |
| | .fap ``Array.getInternal args => | |
| if let .var parent := args[1]! then | |
| addDerivedValue parent x | |
| | .fap ``Array.get!Internal args => | |
| if let .var parent := args[2]! then | |
| addDerivedValue parent x | |
| | .reset _ x => | |
| removeFromParent x | |
| | _ => pure () | |
| visitFnBody b | |
| | .jdecl _ ps v b => | |
| ps.forM visitParam | |
| visitFnBody v | |
| visitFnBody b | |
| | .case _ _ _ alts => alts.forM (visitFnBody ·.body) | |
| | _ => if !b.isTerminal then visitFnBody b.body | |
| private partial def collectDerivedValInfo (ps : Array Param) (b : FnBody) | |
| : DerivedValMap × VarIdSet := Id.run do | |
| let ⟨_, { varMap, borrowedParams }⟩ := go |>.run { } | |
| return ⟨varMap, borrowedParams⟩ | |
| where go : M Unit := do | |
| ps.forM visitParam | |
| visitFnBody b | |
| end CollectDerivedValInfo | |
| structure VarInfo where | |
| isPossibleRef : Bool | |
| isDefiniteRef: Bool | |
| persistent : Bool | |
| deriving Inhabited | |
| abbrev VarMap := Std.TreeMap VarId VarInfo (fun x y => compare x.idx y.idx) | |
| structure LiveVars where | |
| vars : VarIdSet | |
| borrows : VarIdSet := {} | |
| deriving Inhabited | |
| @[inline] | |
| def LiveVars.merge (liveVars1 liveVars2 : LiveVars) : LiveVars := | |
| let vars := liveVars1.vars.merge liveVars2.vars | |
| let borrows := liveVars1.borrows.merge liveVars2.borrows | |
| { vars, borrows } | |
| abbrev JPLiveVarMap := Std.TreeMap JoinPointId LiveVars (fun x y => compare x.idx y.idx) | |
| structure Context where | |
| env : Environment | |
| decls : Array Decl | |
| borrowedParams : VarIdSet | |
| derivedValMap : DerivedValMap | |
| varMap : VarMap := {} | |
| jpLiveVarMap : JPLiveVarMap := {} -- map: join point => live variables | |
| localCtx : LocalContext := {} -- we use it to store the join point declarations | |
| def getDecl (ctx : Context) (fid : FunId) : Decl := | |
| findEnvDecl' ctx.env fid ctx.decls |>.get! | |
| def getVarInfo (ctx : Context) (x : VarId) : VarInfo := | |
| ctx.varMap.get! x | |
| def getJPParams (ctx : Context) (j : JoinPointId) : Array Param := | |
| ctx.localCtx.getJPParams j |>.get! | |
| @[specialize] | |
| private partial def addDescendants (ctx : Context) (x : VarId) (s : VarIdSet) | |
| (shouldAdd : VarId → Bool := fun _ => true) : VarIdSet := | |
| if let some info := ctx.derivedValMap.get? x then | |
| info.children.foldl (init := s) fun s child => | |
| let s := if shouldAdd child then s.insert child else s | |
| addDescendants ctx child s shouldAdd | |
| else s | |
| private def mkRetLiveVars (ctx : Context) : LiveVars := | |
| let borrows := ctx.borrowedParams.foldl (init := {}) fun borrows x => | |
| addDescendants ctx x (borrows.insert x) | |
| { vars := {}, borrows } | |
| def getJPLiveVars (ctx : Context) (j : JoinPointId) : LiveVars := | |
| ctx.jpLiveVarMap.get! j | |
| @[specialize] | |
| private def useVar (ctx : Context) (x : VarId) (liveVars : LiveVars) | |
| (shouldBorrow : VarId → Bool := fun _ => true) : LiveVars := Id.run do | |
| let ⟨contains, vars⟩ := liveVars.vars.containsThenInsert x | |
| let borrows := if contains then | |
| liveVars.borrows | |
| else | |
| addDescendants ctx x liveVars.borrows fun y => | |
| !liveVars.vars.contains y && shouldBorrow y | |
| return { vars, borrows } | |
| @[inline] | |
| private def bindVar (x : VarId) (liveVars : LiveVars) : LiveVars := | |
| let vars := liveVars.vars.erase x | |
| let borrows := liveVars.borrows.erase x | |
| { vars, borrows } | |
| @[inline] | |
| private def useArg (ctx : Context) (args : Array Arg) (arg : Arg) (liveVars : LiveVars) : LiveVars := | |
| match arg with | |
| | .var x => useVar ctx x liveVars fun y => | |
| args.all fun arg => | |
| match arg with | |
| | .var z => y != z | |
| | .erased => true | |
| | .erased => liveVars | |
| private def useArgs (ctx : Context) (args : Array Arg) (liveVars : LiveVars) : LiveVars := | |
| args.foldl (init := liveVars) fun liveVars arg => useArg ctx args arg liveVars | |
| private def useExpr (ctx : Context) (e : Expr) (liveVars : LiveVars) : LiveVars := | |
| match e with | |
| | .proj _ x | .uproj _ x | .sproj _ _ x | .box _ x | .unbox x | .reset _ x | .isShared x => | |
| useVar ctx x liveVars | |
| | .ctor _ ys | .fap _ ys | .pap _ ys => | |
| useArgs ctx ys liveVars | |
| | .ap x ys | .reuse x _ _ ys => | |
| let liveVars := useVar ctx x liveVars | |
| useArgs ctx ys liveVars | |
| | .lit _ => liveVars | |
| @[inline] def addInc (ctx : Context) (x : VarId) (b : FnBody) (n := 1) : FnBody := | |
| let info := getVarInfo ctx x | |
| if n == 0 then b else .inc x n (!info.isDefiniteRef) info.persistent b | |
| @[inline] def addDec (ctx : Context) (x : VarId) (b : FnBody) : FnBody := | |
| let info := getVarInfo ctx x | |
| .dec x 1 (!info.isDefiniteRef) info.persistent b | |
| private def updateRefUsingCtorInfo (ctx : Context) (x : VarId) (c : CtorInfo) : Context := | |
| let m := ctx.varMap | |
| { ctx with | |
| varMap := match m.get? x with | |
| | some info => | |
| let isPossibleRef := c.type.isPossibleRef | |
| let isDefiniteRef := c.type.isDefiniteRef | |
| m.insert x { info with isPossibleRef, isDefiniteRef } | |
| | none => m | |
| } | |
| private def addDecForAlt (ctx : Context) (caseLiveVars altLiveVars : LiveVars) (b : FnBody) : FnBody := | |
| caseLiveVars.vars.foldl (init := b) fun b x => | |
| let info := getVarInfo ctx x | |
| if !altLiveVars.vars.contains x then | |
| if info.isPossibleRef && !caseLiveVars.borrows.contains x then | |
| addDec ctx x b | |
| else b | |
| else if caseLiveVars.borrows.contains x && !altLiveVars.borrows.contains x then | |
| addInc ctx x b | |
| else b | |
| /-- `isFirstOcc xs x i = true` if `xs[i]` is the first occurrence of `xs[i]` in `xs` -/ | |
| private def isFirstOcc (xs : Array Arg) (i : Nat) : Bool := | |
| let x := xs[i]! | |
| i.all fun j _ => xs[j]! != x | |
| /-- Return true if `x` also occurs in `ys` in a position that is not consumed. | |
| That is, it is also passed as a borrow reference. -/ | |
| private def isBorrowParamAux (x : VarId) (ys : Array Arg) (consumeParamPred : Nat → Bool) : Bool := | |
| ys.size.any fun i _ => | |
| let y := ys[i] | |
| match y with | |
| | .erased => false | |
| | .var y => x == y && !consumeParamPred i | |
| private def isBorrowParam (x : VarId) (ys : Array Arg) (ps : Array Param) : Bool := | |
| isBorrowParamAux x ys fun i => ! ps[i]!.borrow | |
| /-- | |
| Return `n`, the number of times `x` is consumed. | |
| - `ys` is a sequence of instruction parameters where we search for `x`. | |
| - `consumeParamPred i = true` if parameter `i` is consumed. | |
| -/ | |
| private def getNumConsumptions (x : VarId) (ys : Array Arg) (consumeParamPred : Nat → Bool) : Nat := | |
| ys.size.fold (init := 0) fun i _ n => | |
| let y := ys[i] | |
| match y with | |
| | .erased => n | |
| | .var y => if x == y && consumeParamPred i then n+1 else n | |
| private def addIncBeforeAux (ctx : Context) (xs : Array Arg) (consumeParamPred : Nat → Bool) (b : FnBody) (liveVarsAfter : LiveVars) : FnBody := | |
| xs.size.fold (init := b) fun i _ b => | |
| let x := xs[i] | |
| match x with | |
| | .erased => b | |
| | .var x => | |
| let info := getVarInfo ctx x | |
| if !info.isPossibleRef || !isFirstOcc xs i then b | |
| else | |
| let numConsumptions := getNumConsumptions x xs consumeParamPred | |
| let numIncs := | |
| if liveVarsAfter.vars.contains x || -- `x` is live after executing instruction | |
| liveVarsAfter.borrows.contains x || | |
| isBorrowParamAux x xs consumeParamPred -- `x` is used in a position that is passed as a borrow reference | |
| then numConsumptions | |
| else numConsumptions - 1 | |
| addInc ctx x b numIncs | |
| private def addIncBefore (ctx : Context) (xs : Array Arg) (ps : Array Param) (b : FnBody) (liveVarsAfter : LiveVars) : FnBody := | |
| addIncBeforeAux ctx xs (fun i => ! ps[i]!.borrow) b liveVarsAfter | |
| /-- See `addIncBeforeAux`/`addIncBefore` for the procedure that inserts `inc` operations before an application. -/ | |
| private def addDecAfterFullApp (ctx : Context) (xs : Array Arg) (ps : Array Param) (b : FnBody) (bLiveVars : LiveVars) : FnBody := | |
| xs.size.fold (init := b) fun i _ b => | |
| match xs[i] with | |
| | .erased => b | |
| | .var x => | |
| /- We must add a `dec` if `x` must be consumed, it is alive after the application, | |
| and it has been borrowed by the application. | |
| Remark: `x` may occur multiple times in the application (e.g., `f x y x`). | |
| This is why we check whether it is the first occurrence. -/ | |
| let info := getVarInfo ctx x | |
| if info.isPossibleRef && | |
| isFirstOcc xs i && | |
| isBorrowParam x xs ps && | |
| !bLiveVars.vars.contains x && | |
| !bLiveVars.borrows.contains x then | |
| addDec ctx x b | |
| else b | |
| private def addIncBeforeConsumeAll (ctx : Context) (xs : Array Arg) (b : FnBody) (liveVarsAfter : LiveVars) : FnBody := | |
| addIncBeforeAux ctx xs (fun _ => true) b liveVarsAfter | |
| /-- Add `dec` instructions for parameters that are references, are not alive in `b`, and are not borrow. | |
| That is, we must make sure these parameters are consumed. -/ | |
| private def addDecForDeadParams (ctx : Context) (ps : Array Param) (b : FnBody) (bLiveVars : LiveVars) : FnBody × LiveVars := | |
| ps.foldl (init := ⟨b, bLiveVars⟩) fun ⟨b, bLiveVars⟩ p => | |
| let b := | |
| if !p.borrow && p.ty.isPossibleRef && !bLiveVars.vars.contains p.x then | |
| addDec ctx p.x b | |
| else b | |
| let bLiveVars := bindVar p.x bLiveVars | |
| ⟨b, bLiveVars⟩ | |
| private def isPersistent : Expr → Bool | |
| | .fap _ xs => xs.isEmpty -- all global constants are persistent objects | |
| | _ => false | |
| /-- Return true iff `v` at runtime is a scalar value stored in a tagged pointer. | |
| We do not need RC operations for this kind of value. -/ | |
| private def typeForScalarBoxedInTaggedPtr? (v : Expr) : Option IRType := | |
| match v with | |
| | .ctor c _ => | |
| some c.type | |
| | .lit (.num n) => | |
| if n ≤ maxSmallNat then | |
| some .tagged | |
| else | |
| some .tobject | |
| | _ => none | |
| private def updateVarInfo (ctx : Context) (x : VarId) (t : IRType) (v : Expr) : Context := | |
| let type := typeForScalarBoxedInTaggedPtr? v |>.getD t | |
| let isPossibleRef := type.isPossibleRef | |
| let isDefiniteRef := type.isDefiniteRef | |
| { ctx with | |
| varMap := ctx.varMap.insert x { | |
| isPossibleRef | |
| isDefiniteRef | |
| persistent := isPersistent v, | |
| } | |
| } | |
| private def addDecIfNeeded (ctx : Context) (x : VarId) (b : FnBody) (bLiveVars : LiveVars) : FnBody := | |
| let info := getVarInfo ctx x | |
| if info.isPossibleRef && | |
| !bLiveVars.vars.contains x && | |
| !bLiveVars.borrows.contains x then | |
| addDec ctx x b | |
| else b | |
| private def processVDecl (ctx : Context) (z : VarId) (t : IRType) (v : Expr) (b : FnBody) (bLiveVars : LiveVars) : FnBody × LiveVars := | |
| let b := match v with | |
| | .ctor _ ys | .reuse _ _ _ ys | .pap _ ys => | |
| addIncBeforeConsumeAll ctx ys (.vdecl z t v b) bLiveVars | |
| | .proj _ x => | |
| let b := addDecIfNeeded ctx x b bLiveVars | |
| let b := if !bLiveVars.borrows.contains z then addInc ctx z b else b | |
| .vdecl z t v b | |
| | .uproj _ x | .sproj _ _ x | .unbox x => | |
| .vdecl z t v (addDecIfNeeded ctx x b bLiveVars) | |
| | .fap f ys => | |
| let ps := (getDecl ctx f).params | |
| let b := addDecAfterFullApp ctx ys ps b bLiveVars | |
| let v := | |
| if f == ``Array.getInternal && bLiveVars.borrows.contains z then | |
| .fap ``Array.getInternalBorrowed ys | |
| else if f == ``Array.get!Internal && bLiveVars.borrows.contains z then | |
| .fap ``Array.get!InternalBorrowed ys | |
| else v | |
| let b := .vdecl z t v b | |
| addIncBefore ctx ys ps b bLiveVars | |
| | .ap x ys => | |
| let ysx := ys.push (.var x) -- TODO: avoid temporary array allocation | |
| addIncBeforeConsumeAll ctx ysx (.vdecl z t v b) bLiveVars | |
| | .lit _ | .box .. | .reset .. | .isShared _ => | |
| .vdecl z t v b | |
| let liveVars := useExpr ctx v bLiveVars | |
| let liveVars := bindVar z liveVars | |
| ⟨b, liveVars⟩ | |
| def updateVarInfoWithParams (ctx : Context) (ps : Array Param) : Context := | |
| let m := ps.foldl (init := ctx.varMap) fun m p => | |
| m.insert p.x { | |
| isPossibleRef := p.ty.isPossibleRef | |
| isDefiniteRef := p.ty.isDefiniteRef | |
| persistent := false } | |
| { ctx with varMap := m } | |
| partial def visitFnBody (b : FnBody) (ctx : Context) : FnBody × LiveVars := | |
| match b with | |
| | .vdecl x t v b => | |
| let ctx := updateVarInfo ctx x t v | |
| let ⟨b, bLiveVars⟩ := visitFnBody b ctx | |
| processVDecl ctx x t v b bLiveVars | |
| | .jdecl j xs v b => | |
| let ctxAtV := updateVarInfoWithParams ctx xs | |
| let ⟨v, vLiveVars⟩ := visitFnBody v ctxAtV | |
| let ⟨v, vLiveVars⟩ := addDecForDeadParams ctxAtV xs v vLiveVars | |
| let ctx := { ctx with | |
| localCtx := ctx.localCtx.addJP j xs v | |
| jpLiveVarMap := ctx.jpLiveVarMap.insert j vLiveVars | |
| } | |
| let ⟨b, bLiveVars⟩ := visitFnBody b ctx | |
| ⟨.jdecl j xs v b, bLiveVars⟩ | |
| | .uset x i y b => | |
| let ⟨b, s⟩ := visitFnBody b ctx | |
| -- We don't need to insert `y` since we only need to track live variables that are references at runtime | |
| let s := useVar ctx x s | |
| ⟨.uset x i y b, s⟩ | |
| | .sset x i o y t b => | |
| let ⟨b, s⟩ := visitFnBody b ctx | |
| -- We don't need to insert `y` since we only need to track live variables that are references at runtime | |
| let s := useVar ctx x s | |
| ⟨.sset x i o y t b, s⟩ | |
| | .case tid x xType alts => | |
| let alts : Array (Alt × LiveVars) := alts.map fun alt => match alt with | |
| | .ctor c b => | |
| let ctx := updateRefUsingCtorInfo ctx x c | |
| let ⟨b, altLiveVars⟩ := visitFnBody b ctx | |
| ⟨.ctor c b, altLiveVars⟩ | |
| | .default b => | |
| let ⟨b, altLiveVars⟩ := visitFnBody b ctx | |
| ⟨.default b, altLiveVars⟩ | |
| let caseLiveVars := alts.foldl (init := { vars := {}, borrows := {} }) | |
| fun liveVars ⟨_, altLiveVars⟩ => | |
| liveVars.merge altLiveVars | |
| let caseLiveVars := useVar ctx x caseLiveVars | |
| let alts := alts.map fun ⟨alt, altLiveVars⟩ => match alt with | |
| | .ctor c b => | |
| let ctx := updateRefUsingCtorInfo ctx x c | |
| let b := addDecForAlt ctx caseLiveVars altLiveVars b | |
| .ctor c b | |
| | .default b => | |
| let b := addDecForAlt ctx caseLiveVars altLiveVars b | |
| .default b | |
| ⟨.case tid x xType alts, caseLiveVars⟩ | |
| | .jmp j xs => | |
| let jLiveVars := getJPLiveVars ctx j | |
| let ps := getJPParams ctx j | |
| let b := addIncBefore ctx xs ps b jLiveVars | |
| let bLiveVars := useArgs ctx xs jLiveVars | |
| ⟨b, bLiveVars⟩ | |
| | .ret x => | |
| let liveVars := mkRetLiveVars ctx | |
| match x with | |
| | .var x => | |
| let info := ctx.varMap.get! x | |
| let liveVars := useVar ctx x liveVars | |
| let b := | |
| if info.isPossibleRef && liveVars.borrows.contains x then | |
| addInc ctx x b | |
| else b | |
| ⟨b, liveVars⟩ | |
| | .erased => ⟨b, liveVars⟩ | |
| | .unreachable => ⟨.unreachable, mkRetLiveVars ctx⟩ | |
| | .set .. | .setTag .. | .inc .. | .dec .. | .del .. => unreachable! | |
| partial def visitDecl (env : Environment) (decls : Array Decl) (d : Decl) : Decl := | |
| match d with | |
| | .fdecl (xs := xs) (body := b) .. => | |
| let ⟨derivedValMap, borrowedParams⟩ := CollectDerivedValInfo.collectDerivedValInfo xs b | |
| let ctx := updateVarInfoWithParams { env, decls, borrowedParams, derivedValMap } xs | |
| let ⟨b, bLiveVars⟩ := visitFnBody b ctx | |
| let ⟨b, _⟩ := addDecForDeadParams ctx xs b bLiveVars | |
| d.updateBody! b | |
| | other => other | |
| end ExplicitRC | |
| def explicitRC (decls : Array Decl) : CompilerM (Array Decl) := do | |
| let env ← getEnv | |
| return decls.map (ExplicitRC.visitDecl env decls) | |
| builtin_initialize registerTraceClass `compiler.ir.rc (inherited := true) | |
| end Lean.IR |