Implements (extended) λPure and λRc proposed in the article "Counting Immutable Beans", Sebastian Ullrich and Leonardo de Moura.

The Lean to IR transformation produces λPure code, and this part is implemented in C++. The procedures described in the paper above are implemented in Lean.

@[reducible, inline]

abbrev Lean.IR.FunId : Type

Function identifier

@[reducible, inline]

abbrev Lean.IR.Index : Type

structure Lean.IR.VarId : Type

Variable identifier

• idx : Index

@[implicit_reducible]

instance Lean.IR.instInhabitedVarId : Inhabited VarId

def Lean.IR.instInhabitedVarId.default : VarId

@[implicit_reducible]

instance Lean.IR.instBEqVarId : BEq VarId

def Lean.IR.instBEqVarId.beq : VarId → VarId → Bool

def Lean.IR.instHashableVarId.hash : VarId → UInt64

@[implicit_reducible]

instance Lean.IR.instHashableVarId : Hashable VarId

@[implicit_reducible]

instance Lean.IR.instReprVarId : Repr VarId

def Lean.IR.instReprVarId.repr : VarId → Nat → Format

structure Lean.IR.JoinPointId : Type

Join point identifier

• idx : Index

@[implicit_reducible]

instance Lean.IR.instInhabitedJoinPointId : Inhabited JoinPointId

def Lean.IR.instInhabitedJoinPointId.default : JoinPointId

def Lean.IR.instBEqJoinPointId.beq : JoinPointId → JoinPointId → Bool

@[implicit_reducible]

instance Lean.IR.instBEqJoinPointId : BEq JoinPointId

@[implicit_reducible]

instance Lean.IR.instHashableJoinPointId : Hashable JoinPointId

def Lean.IR.instHashableJoinPointId.hash : JoinPointId → UInt64

@[implicit_reducible]

instance Lean.IR.instReprJoinPointId : Repr JoinPointId

def Lean.IR.instReprJoinPointId.repr : JoinPointId → Nat → Format

@[reducible, inline]

abbrev Lean.IR.Index.lt (a b : Index) : Bool

@[implicit_reducible]

instance Lean.IR.instToStringVarId : ToString VarId

@[implicit_reducible]

instance Lean.IR.instToStringJoinPointId : ToString JoinPointId

inductive Lean.IR.IRType : Type

Low Level IR types. Most are self explanatory.

• usize represents the C++ size_t Type. We have it here because it is 32-bit in 32-bit machines, and 64-bit in 64-bit machines, and we want the C++ backend for our Compiler to generate platform independent code.

• erased for Lean types, propositions and proofs.

• object a pointer to a value in the heap.

• tagged a tagged pointer (i.e., the least significant bit is 1) storing a scalar value.

• tobject an object or a tagged pointer

• void is used to identify uses of the state token from BaseIO which do no longer need to be passed around etc. at this point in the pipeline.

• struct and union are used to return small values (e.g., Option, Prod, Except) on the stack.

Remark: the RC operations for tobject are slightly more expensive because we first need to test whether the tobject is really a pointer or not.

Remark: the Lean runtime assumes that sizeof(void*) == sizeof(sizeT). Lean cannot be compiled on old platforms where this is not True.

Since values of type struct and union are only used to return values, We assume they must be used/consumed "linearly". We use the term "linear" here to mean "exactly once" in each execution. That is, given x : S, where S is a struct, then one of the following must hold in each (execution) branch. 1- x occurs only at a single ret x instruction. That is, it is being consumed by being returned. 2- x occurs only at a single ctor. That is, it is being "consumed" by being stored into another struct/union. 3- We extract (aka project) every single field of x exactly once. That is, we are consuming x by consuming each of one of its components. Minor refinement: we don't need to consume scalar fields or struct/union fields that do not contain object fields.

• float : IRType
• uint8 : IRType
• uint16 : IRType
• uint32 : IRType
• uint64 : IRType
• usize : IRType
• erased : IRType
• object : IRType
• tobject : IRType
• float32 : IRType
• struct (leanTypeName : Option Name) (types : Array IRType) : IRType
• union (leanTypeName : Name) (types : Array IRType) : IRType
• tagged : IRType
• void : IRType

@[implicit_reducible]

instance Lean.IR.instInhabitedIRType : Inhabited IRType

def Lean.IR.instInhabitedIRType.default : IRType

partial def Lean.IR.instBEqIRType.beq : IRType → IRType → Bool

@[implicit_reducible]

instance Lean.IR.instBEqIRType : BEq IRType

partial def Lean.IR.instReprIRType.repr : IRType → Nat → Format

@[implicit_reducible]

instance Lean.IR.instReprIRType : Repr IRType

def Lean.IR.IRType.isScalar : IRType → Bool

def Lean.IR.IRType.isObj : IRType → Bool

def Lean.IR.IRType.isPossibleRef : IRType → Bool

def Lean.IR.IRType.isDefiniteRef : IRType → Bool

def Lean.IR.IRType.isErased : IRType → Bool

def Lean.IR.IRType.isVoid : IRType → Bool

def Lean.IR.IRType.boxed : IRType → IRType

inductive Lean.IR.Arg : Type

Arguments to applications, constructors, etc. We use erased for Lean types, propositions and proofs that have been erased. Recall that for a Function f, we also generate f._rarg which does not take erased arguments. However, f._rarg is only safe to be used in full applications.

• var (id : VarId) : Arg
• erased : Arg

@[implicit_reducible]

instance Lean.IR.instInhabitedArg : Inhabited Arg

def Lean.IR.instInhabitedArg.default : Arg

def Lean.IR.instBEqArg.beq : Arg → Arg → Bool

@[implicit_reducible]

instance Lean.IR.instBEqArg : BEq Arg

@[implicit_reducible]

instance Lean.IR.instReprArg : Repr Arg

def Lean.IR.instReprArg.repr : Arg → Nat → Format

def Lean.IR.Arg.beq : Arg → Arg → Bool

inductive Lean.IR.LitVal : Type

• num (v : Nat) : LitVal
• str (v : String) : LitVal

@[implicit_reducible]

instance Lean.IR.instInhabitedLitVal : Inhabited LitVal

def Lean.IR.instInhabitedLitVal.default : LitVal

@[implicit_reducible]

instance Lean.IR.instBEqLitVal : BEq LitVal

def Lean.IR.instBEqLitVal.beq : LitVal → LitVal → Bool

structure Lean.IR.CtorInfo : Type

Constructor information.

• name is the Name of the Constructor in Lean.
• cidx is the Constructor index (aka tag).
• size is the number of arguments of type object/tobject.
• usize is the number of arguments of type usize.
• ssize is the number of bytes used to store scalar values.

Recall that a Constructor object contains a header, then a sequence of pointers to other Lean objects, a sequence of USize (i.e., size_t) scalar values, and a sequence of other scalar values.

• name : Name
• cidx : Nat
• size : Nat
• usize : Nat
• ssize : Nat

@[implicit_reducible]

instance Lean.IR.instInhabitedCtorInfo : Inhabited CtorInfo

def Lean.IR.instInhabitedCtorInfo.default : CtorInfo

@[implicit_reducible]

instance Lean.IR.instBEqCtorInfo : BEq CtorInfo

def Lean.IR.instBEqCtorInfo.beq : CtorInfo → CtorInfo → Bool

@[implicit_reducible]

instance Lean.IR.instReprCtorInfo : Repr CtorInfo

def Lean.IR.instReprCtorInfo.repr : CtorInfo → Nat → Format

def Lean.IR.CtorInfo.isRef (info : CtorInfo) : Bool

def Lean.IR.CtorInfo.isScalar (info : CtorInfo) : Bool

def Lean.IR.CtorInfo.type (info : CtorInfo) : IRType

inductive Lean.IR.Expr : Type

• ctor (i : CtorInfo) (ys : Array Arg) : Expr

  We use ctor mainly for constructing Lean object/tobject values lean_ctor_object in the runtime. This instruction is also used to creat struct and union return values. For union, only i.cidx is relevant. For struct, i is irrelevant.

• reset (n : Nat) (x : VarId) : Expr
• reuse (x : VarId) (i : CtorInfo) (updtHeader : Bool) (ys : Array Arg) : Expr

  reuse x in ctor_i ys instruction in the paper.

• proj (i : Nat) (x : VarId) : Expr

  Extract the tobject value at Position sizeof(void*)*i from x. We also use proj for extracting fields from struct return values, and casting union return values.

• uproj (i : Nat) (x : VarId) : Expr

  Extract the Usize value at Position sizeof(void*)*i from x.

• sproj (n offset : Nat) (x : VarId) : Expr

  Extract the scalar value at Position sizeof(void*)*n + offset from x.

• fap (c : FunId) (ys : Array Arg) : Expr

  Full application.

• pap (c : FunId) (ys : Array Arg) : Expr

  Partial application that creates a pap value (aka closure in our nonstandard terminology).

• ap (x : VarId) (ys : Array Arg) : Expr

  Application. x must be a pap value.

• box (ty : IRType) (x : VarId) : Expr

  Given x : ty where ty is a scalar type, this operation returns a value of Type tobject. For small scalar values, the Result is a tagged pointer, and no memory allocation is performed.

• unbox (x : VarId) : Expr

  Given x : [t]object, obtain the scalar value.

• lit (v : LitVal) : Expr
• isShared (x : VarId) : Expr

  Return 1 : uint8 Iff RC(x) > 1

@[implicit_reducible]

instance Lean.IR.instInhabitedExpr : Inhabited Expr

def Lean.IR.instInhabitedExpr.default : Expr

structure Lean.IR.Param : Type

• x : VarId
• borrow : Bool
• ty : IRType

@[implicit_reducible]

instance Lean.IR.instInhabitedParam : Inhabited Param

def Lean.IR.instInhabitedParam.default : Param

def Lean.IR.instReprParam.repr : Param → Nat → Format

@[implicit_reducible]

instance Lean.IR.instReprParam : Repr Param

inductive Lean.IR.Alt : Type

• ctor (info : CtorInfo) (b : FnBody) : Alt
• default (b : FnBody) : Alt

inductive Lean.IR.FnBody : Type

• vdecl (x : VarId) (ty : IRType) (e : Expr) (b : FnBody) : FnBody

  let x : ty := e; b

• jdecl (j : JoinPointId) (xs : Array Param) (v b : FnBody) : FnBody

  Join point Declaration block_j (xs) := e; b

• set (x : VarId) (i : Nat) (y : Arg) (b : FnBody) : FnBody

  Store y at Position sizeof(void*)*i in x. x must be a Constructor object and RC(x) must be 1. This operation is not part of λPure is only used during optimization.

• setTag (x : VarId) (cidx : Nat) (b : FnBody) : FnBody
• uset (x : VarId) (i : Nat) (y : VarId) (b : FnBody) : FnBody

  Store y : Usize at Position sizeof(void*)*i in x. x must be a Constructor object and RC(x) must be 1.

• sset (x : VarId) (i offset : Nat) (y : VarId) (ty : IRType) (b : FnBody) : FnBody

  Store y : ty at Position sizeof(void*)*i + offset in x. x must be a Constructor object and RC(x) must be 1. ty must not be object, tobject, erased nor Usize.

• inc (x : VarId) (n : Nat) (c persistent : Bool) (b : FnBody) : FnBody

  RC increment for object. If c == true, then inc must check whether x is a tagged pointer or not. If persistent == true then x is statically known to be a persistent object.

• dec (x : VarId) (n : Nat) (c persistent : Bool) (b : FnBody) : FnBody

  RC decrement for object. If c == true, then inc must check whether x is a tagged pointer or not. If persistent == true then x is statically known to be a persistent object.

• del (x : VarId) (b : FnBody) : FnBody
• case (tid : Name) (x : VarId) (xType : IRType) (cs : Array Alt) : FnBody
• ret (x : Arg) : FnBody
• jmp (j : JoinPointId) (ys : Array Arg) : FnBody

  Jump to join point j

• unreachable : FnBody

def Lean.IR.instInhabitedFnBody.default_1 : FnBody

@[implicit_reducible]

instance Lean.IR.instInhabitedFnBody : Inhabited FnBody

def Lean.IR.instInhabitedAlt.default_1 : Alt

@[implicit_reducible]

instance Lean.IR.instInhabitedAlt : Inhabited Alt

@[reducible, inline]

abbrev Lean.IR.FnBody.nil : FnBody

def Lean.IR.FnBody.isTerminal : FnBody → Bool

def Lean.IR.FnBody.body : FnBody → FnBody

def Lean.IR.FnBody.setBody : FnBody → FnBody → FnBody

@[inline]

def Lean.IR.FnBody.resetBody (b : FnBody) : FnBody

@[inline]

def Lean.IR.FnBody.split (b : FnBody) : FnBody × FnBody

If b is a non terminal, then return a pair (c, b') s.t. b == c <;> b', and c.body == FnBody.nil

def Lean.IR.Alt.body : Alt → FnBody

def Lean.IR.Alt.setBody : Alt → FnBody → Alt

@[inline]

def Lean.IR.Alt.modifyBody (f : FnBody → FnBody) : Alt → Alt

@[inline]

def Lean.IR.Alt.modifyBodyM {m : Type → Type} [Monad m] (f : FnBody → m FnBody) : Alt → m Alt

def Lean.IR.Alt.isDefault : Alt → Bool

def Lean.IR.push (bs : Array FnBody) (b : FnBody) : Array FnBody

partial def Lean.IR.flattenAux (b : FnBody) (r : Array FnBody) : Array FnBody × FnBody

def Lean.IR.FnBody.flatten (b : FnBody) : Array FnBody × FnBody

partial def Lean.IR.reshapeAux (a : Array FnBody) (i : Nat) (b : FnBody) : FnBody

def Lean.IR.reshape (bs : Array FnBody) (term : FnBody) : FnBody

@[inline]

def Lean.IR.modifyJPs (bs : Array FnBody) (f : FnBody → FnBody) : Array FnBody

@[inline]

def Lean.IR.modifyJPsM {m : Type → Type} [Monad m] (bs : Array FnBody) (f : FnBody → m FnBody) : m (Array FnBody)

structure Lean.IR.DeclInfo : Type

Extra information associated with a declaration.

• sorryDep? : Option Name

  If some <blame>, then declaration depends on <blame> which uses a sorry axiom.

inductive Lean.IR.Decl : Type

• fdecl (f : FunId) (xs : Array Param) (type : IRType) (body : FnBody) (info : DeclInfo) : Decl
• extern (f : FunId) (xs : Array Param) (type : IRType) (ext : ExternAttrData) : Decl

@[implicit_reducible]

instance Lean.IR.instInhabitedDecl : Inhabited Decl

def Lean.IR.instInhabitedDecl.default : Decl

def Lean.IR.Decl.name : Decl → FunId

def Lean.IR.Decl.params : Decl → Array Param

def Lean.IR.Decl.resultType : Decl → IRType

def Lean.IR.Decl.isExtern : Decl → Bool

def Lean.IR.Decl.getInfo : Decl → DeclInfo

def Lean.IR.Decl.updateBody! (d : Decl) (bNew : FnBody) : Decl

def Lean.IR.mkDummyExternDecl (f : FunId) (xs : Array Param) (ty : IRType) : Decl

@[reducible, inline]

abbrev Lean.IR.IndexSet : Type

Set of variable and join point names

def Lean.IR.mkIndexSet (idx : Index) : IndexSet

inductive Lean.IR.LocalContextEntry : Type

• param : IRType → LocalContextEntry
• localVar : IRType → Expr → LocalContextEntry
• joinPoint : Array Param → FnBody → LocalContextEntry

@[reducible, inline]

abbrev Lean.IR.LocalContext : Type

def Lean.IR.LocalContext.addLocal (ctx : LocalContext) (x : VarId) (t : IRType) (v : Expr) : LocalContext

def Lean.IR.LocalContext.addJP (ctx : LocalContext) (j : JoinPointId) (xs : Array Param) (b : FnBody) : LocalContext

def Lean.IR.LocalContext.addParam (ctx : LocalContext) (p : Param) : LocalContext

def Lean.IR.LocalContext.addParams (ctx : LocalContext) (ps : Array Param) : LocalContext

def Lean.IR.LocalContext.isJP (ctx : LocalContext) (idx : Index) : Bool

def Lean.IR.LocalContext.getJPBody (ctx : LocalContext) (j : JoinPointId) : Option FnBody

def Lean.IR.LocalContext.getJPParams (ctx : LocalContext) (j : JoinPointId) : Option (Array Param)

def Lean.IR.LocalContext.isParam (ctx : LocalContext) (idx : Index) : Bool

def Lean.IR.LocalContext.isLocalVar (ctx : LocalContext) (idx : Index) : Bool

def Lean.IR.LocalContext.contains (ctx : LocalContext) (idx : Index) : Bool

def Lean.IR.LocalContext.eraseJoinPointDecl (ctx : LocalContext) (j : JoinPointId) : LocalContext

def Lean.IR.LocalContext.getType (ctx : LocalContext) (x : VarId) : Option IRType

def Lean.IR.LocalContext.getValue (ctx : LocalContext) (x : VarId) : Option Expr

@[reducible, inline]

abbrev Lean.IR.IndexRenaming : Type

class Lean.IR.AlphaEqv (α : Type) : Type

• aeqv : IndexRenaming → α → α → Bool

def Lean.IR.VarId.alphaEqv (ρ : IndexRenaming) (v₁ v₂ : VarId) : Bool

@[implicit_reducible]

instance Lean.IR.instAlphaEqvVarId : AlphaEqv VarId

def Lean.IR.Arg.alphaEqv (ρ : IndexRenaming) : Arg → Arg → Bool

@[implicit_reducible]

instance Lean.IR.instAlphaEqvArg : AlphaEqv Arg

def Lean.IR.args.alphaEqv (ρ : IndexRenaming) (args₁ args₂ : Array Arg) : Bool

@[implicit_reducible]

instance Lean.IR.instAlphaEqvArrayArg : AlphaEqv (Array Arg)

def Lean.IR.Expr.alphaEqv (ρ : IndexRenaming) : Expr → Expr → Bool

@[implicit_reducible]

instance Lean.IR.instAlphaEqvExpr : AlphaEqv Expr

def Lean.IR.addVarRename (ρ : IndexRenaming) (x₁ x₂ : Nat) : IndexRenaming

def Lean.IR.addParamRename (ρ : IndexRenaming) (p₁ p₂ : Param) : Option IndexRenaming

def Lean.IR.addParamsRename (ρ : IndexRenaming) (ps₁ ps₂ : Array Param) : Option IndexRenaming

partial def Lean.IR.FnBody.alphaEqv : IndexRenaming → FnBody → FnBody → Bool

def Lean.IR.FnBody.beq (b₁ b₂ : FnBody) : Bool

@[implicit_reducible]

instance Lean.IR.instBEqFnBody : BEq FnBody

@[reducible, inline]

abbrev Lean.IR.VarIdSet : Type

def Lean.IR.mkIf (x : VarId) (t e : FnBody) : FnBody

def Lean.IR.getUnboxOpName (t : IRType) : String