inductive Lean.Compiler.LCNF.UnreachableBranches.Value : Type

The abstract domain of the interpreter. Representing sets of values of a certain type.

• bot : Value

  Undefined, could be anything we have no information.

• top : Value

  All values are possible.

• ctor (i : Name) (vs : Array Value) : Value

  A certain constructor with a certain sets of parameters is possible.

• choice (vs : List Value) : Value

  A set of values are possible.

Instances For

• Lean.Compiler.LCNF.UnreachableBranches.Value.instBEq
• Lean.Compiler.LCNF.UnreachableBranches.instInhabitedValue
• Lean.Compiler.LCNF.UnreachableBranches.instReprValue

instance Lean.Compiler.LCNF.UnreachableBranches.instInhabitedValue : Inhabited Value

Equations

• Lean.Compiler.LCNF.UnreachableBranches.instInhabitedValue = { default := Lean.Compiler.LCNF.UnreachableBranches.Value.bot }

instance Lean.Compiler.LCNF.UnreachableBranches.instReprValue : Repr Value

Equations

• Lean.Compiler.LCNF.UnreachableBranches.instReprValue = { reprPrec := Lean.Compiler.LCNF.UnreachableBranches.reprValue✝ }

def Lean.Compiler.LCNF.UnreachableBranches.Value.maxValueDepth : Nat

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Value.maxValueDepth = 8

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.beq : Value → Value → Bool

instance Lean.Compiler.LCNF.UnreachableBranches.Value.instBEq : BEq Value

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Value.instBEq = { beq := Lean.Compiler.LCNF.UnreachableBranches.Value.beq }

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.addChoice (vs : List Value) (v : Value) : List Value

Fuse v into vs. That is do not only append but if we see that v is a constructor that is already contained within vs try to detect the difference between these values and merge them accordingly into a choice node further down the tree.

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.merge (v1 v2 : Value) : Value

Merge two values into one. bot is the neutral element, top the annihilator.

def Lean.Compiler.LCNF.UnreachableBranches.Value.truncate (env : Environment) (v : Value) : Value

Make sure constructors of recursive inductive datatypes can only occur once in each path. Values at depth > maxValueDepth are also approximated at top. We use this function to implement a simple widening operation for our abstract interpreter. Recall the widening functions is used to ensure termination in abstract interpreters.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Value.truncate env v = Lean.Compiler.LCNF.UnreachableBranches.Value.truncate.go env v ∅ Lean.Compiler.LCNF.UnreachableBranches.Value.maxValueDepth

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.truncate.go (env : Environment) (v : Value) (forbiddenTypes : NameSet) (remainingDepth : Nat) : Value

def Lean.Compiler.LCNF.UnreachableBranches.Value.widening (env : Environment) (v1 v2 : Value) : Value

Widening operator that guarantees termination in our abstract interpreter.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Value.widening env v1 v2 = Lean.Compiler.LCNF.UnreachableBranches.Value.truncate env (v1.merge v2)

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.containsCtor : Value → Name → Bool

Check whether a certain constructor is part of a Value by name. Note that both top and bot will always true here. For bot this is because we have no information about the Value so just to be sure we don't claim the absence of a certain constructor.

def Lean.Compiler.LCNF.UnreachableBranches.Value.getCtorArgs : Value → Name → Option (Array Value)

Obtain the arguments of a certain constructor within the Value.

Equations

• One or more equations did not get rendered due to their size.
• (Lean.Compiler.LCNF.UnreachableBranches.Value.ctor i args).getCtorArgs x✝ = if (i == x✝) = true then some args else none
• x✝¹.getCtorArgs x✝ = none

def Lean.Compiler.LCNF.UnreachableBranches.Value.ofNat (n : Nat) : Value

Equations

• One or more equations did not get rendered due to their size.

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.ofNat.goBig (orig curr : Nat) : Value

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.ofNat.goSmall : Nat → Value

def Lean.Compiler.LCNF.UnreachableBranches.Value.ofLCNFLit : LitValue → Value

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Value.ofLCNFLit (Lean.Compiler.LCNF.LitValue.natVal n) = Lean.Compiler.LCNF.UnreachableBranches.Value.ofNat n
• Lean.Compiler.LCNF.UnreachableBranches.Value.ofLCNFLit (Lean.Compiler.LCNF.LitValue.strVal val) = Lean.Compiler.LCNF.UnreachableBranches.Value.top

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.proj : Value → Nat → Value

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.isLiteral : Value → Bool

We say that a Value is a literal iff it is only a tree of Value.ctor nodes.

def Lean.Compiler.LCNF.UnreachableBranches.Value.getLiteral (v : Value) : CompilerM (Option (Array CodeDecl × FVarId))

Attempt to turn a Value that is representing a literal into a set of auxiliary declarations + the final FVarId of the declaration that contains the actual literal. If it is not a literal return none.

Equations

• v.getLiteral = if v.isLiteral = true then do let literal ← Lean.Compiler.LCNF.UnreachableBranches.Value.getLiteral.go v pure (some literal) else pure none

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.getLiteral.go : Value → CompilerM (Array CodeDecl × FVarId)

partial def Lean.Compiler.LCNF.UnreachableBranches.Value.getLiteral.getNatConstant : Value → Nat

@[reducible, inline]

abbrev Lean.Compiler.LCNF.UnreachableBranches.FunctionSummaries : Type

A map from function names to the Value that the abstract interpreter produced for them.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.FunctionSummaries = Lean.PHashMap Lean.Name Lean.Compiler.LCNF.UnreachableBranches.Value

opaque Lean.Compiler.LCNF.UnreachableBranches.functionSummariesExt : SimplePersistentEnvExtension (Name × Value) FunctionSummaries

Storing FunctionSummaries for all functions in a .olean.

def Lean.Compiler.LCNF.UnreachableBranches.addFunctionSummary (env : Environment) (fid : Name) (v : Value) : Environment

Add a Value for a function name.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.getFunctionSummary? (env : Environment) (fid : Name) : Option Value

Obtain the Value for a function name if possible.

Equations

• One or more equations did not get rendered due to their size.

@[reducible, inline]

abbrev Lean.Compiler.LCNF.UnreachableBranches.Assignment : Type

A map from variable identifiers to the Value produced by the abstract interpreter for them.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.Assignment = Std.HashMap Lean.FVarId Lean.Compiler.LCNF.UnreachableBranches.Value

structure Lean.Compiler.LCNF.UnreachableBranches.InterpContext : Type

The context of InterpM.

• decls : Array Decl

  The list of Decls we are operating on in InterpM. This can be a single declaration or a mutual block of declarations where their analysis might influence each other as we approach the fixpoint.

• currFnIdx : Nat

  The index of the function we are currently operating on in decls.

structure Lean.Compiler.LCNF.UnreachableBranches.InterpState : Type

• assignments : Array Assignment

  Assignments of functions in the InterpContext.

• funVals : PArray Value

  Values of functions in the InterpContext use during computation of the fixpoint. Afterwards they are stored into the Environment.

@[reducible, inline]

abbrev Lean.Compiler.LCNF.UnreachableBranches.InterpM (α : Type) : Type

The monad which powers the abstract interpreter.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.getAssignment : InterpM Assignment

Get the variable Assignment of the current function.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.getAssignment = do let __do_lift ← get let __do_lift_1 ← read pure __do_lift.assignments[__do_lift_1.currFnIdx]!

def Lean.Compiler.LCNF.UnreachableBranches.getFunVal (funIdx : Nat) : InterpM Value

Get the Value of a certain function in the current block by index.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.getFunVal funIdx = do let __do_lift ← get pure __do_lift.funVals[funIdx]!

def Lean.Compiler.LCNF.UnreachableBranches.findFunVal? (declName : Name) : InterpM (Option Value)

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.modifyAssignment (f : Assignment → Assignment) : InterpM Unit

Run f on the variable Assignment of the current function.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.findVarValue (var : FVarId) : InterpM Value

Obtain the Value associated with var from the context of InterpM. If none is available return Value.bot.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.findArgValue (arg : Arg) : InterpM Value

Find the value of arg using the logic of findVarValue.

Equations

• Lean.Compiler.LCNF.UnreachableBranches.findArgValue (Lean.Compiler.LCNF.Arg.fvar fvarId) = Lean.Compiler.LCNF.UnreachableBranches.findVarValue fvarId
• Lean.Compiler.LCNF.UnreachableBranches.findArgValue arg = pure Lean.Compiler.LCNF.UnreachableBranches.Value.top

def Lean.Compiler.LCNF.UnreachableBranches.updateVarAssignment (var : FVarId) (newVal : Value) : InterpM Unit

Update the assignment of var by merging the current value with newVal.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.resetVarAssignment (var : FVarId) : InterpM Unit

Set the value of var to bot.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.updateCurrFnSummary (v : Value) : InterpM Unit

Widen the value of the current function by v.

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.UnreachableBranches.updateFunDeclParamsAssignment (params : Array Param) (args : Array Arg) : InterpM Bool

Return true if the assignment of at least one parameter has been updated. Furthermore if we see that params.size != args.size we know that this is a partial application and set the values of the remaining parameters to top since it is impossible to track what will happen with them from here on.

Equations

• One or more equations did not get rendered due to their size.

partial def Lean.Compiler.LCNF.UnreachableBranches.interpCode : Code → InterpM Unit

The actual abstract interpreter on a block of Code.

partial def Lean.Compiler.LCNF.UnreachableBranches.interpCode.interpLetValue (letVal : LetValue) : InterpM Value

The abstract interpreter on a LetValue.

partial def Lean.Compiler.LCNF.UnreachableBranches.interpCode.handleFunArg (arg : Arg) : InterpM Unit

partial def Lean.Compiler.LCNF.UnreachableBranches.interpCode.handleFunVar (var : FVarId) : InterpM Unit

If we see a function being passed as an argument to a higher order function we cannot know what arguments it will be passed further down the line. Hence we set all of its arguments to top since anything is possible.

partial def Lean.Compiler.LCNF.UnreachableBranches.interpCode.interpFunCall (funDecl : FunDecl) (args : Array Arg) : InterpM Unit

def Lean.Compiler.LCNF.UnreachableBranches.inferStep : InterpM Bool

Rerun the abstract interpreter on all declarations except of the unsafe ones. Return whether any Value got updated in the process.

Equations

• One or more equations did not get rendered due to their size.

partial def Lean.Compiler.LCNF.UnreachableBranches.inferMain : InterpM Unit

Run inferStep until it reaches a fix point.

def Lean.Compiler.LCNF.UnreachableBranches.elimDead (assignment : Assignment) (decl : Decl) : CompilerM Decl

Use the information produced by the abstract interpreter to:

• Eliminate branches that we know cannot be hit
• Eliminate values that we know have to be constants.

Equations

• One or more equations did not get rendered due to their size.

partial def Lean.Compiler.LCNF.UnreachableBranches.elimDead.go (assignment : Assignment) (code : Code) : CompilerM Code

def Lean.Compiler.LCNF.Decl.elimDeadBranches (decls : Array Decl) : CompilerM (Array Decl)

Equations

• One or more equations did not get rendered due to their size.

def Lean.Compiler.LCNF.elimDeadBranches : Pass

Equations

• One or more equations did not get rendered due to their size.