Research the possibilities of statistically assisted type inference #17

0x7CFE · 2013-09-16T17:04:34Z

In statically typed environments Hindley-Milner algorithm may be used to infer the types of expression depending on it's parts. The question is, may this idea be applied to the Smalltalk's pure dynamic environment?

In case of JIT VM we have statistics of which call site affect what classes and potentionally object of what class is returned. Gathering this information we may find a places (call sites and methods) with classes tightly bound to one or more variables. If particular variable appeared to have only one class during the whole runtime, we may then perform an optimization that assumes that current variable always have this class. Thus, specializing the method. Inside, we may treat class as a statically assigned type. This allows us to apply type infering where it is possible.

Issue: #17

It allows to compare any two types, store them in STL container such as std::set, use them as a key in std::map and use composition operators during type inference procedure. Operator | is a disjunction-like operator used to get sum of several possible types within a type. For example: 2 | 2 -> 2 2 | 3 -> (2, 3) 2 | * -> (2, *) (Object) | (SmallInt) -> ((Object), (SmallInt)) This operator may be used to aggregate possible types within a linear sequence where several type outcomes are possible: x <- y isNil ifTrue: [ nil ] ifFalse: [ 42 ]. In this case x will have composite type (nil, 42). On the other hand, when dealing with loops we need some kind of a reduction operator that will act as a conjunction: 2 & 2 -> 2 2 & 3 -> (SmallInt) 2 & (SmallInt) -> (SmallInt) <any type> & * -> * (SmallInt) & (Object) -> * This operator is used during induction run of the type analyzer to prove that variable does not leave it's local type domain, i.e it's type is not reduced to a *. Issue: #17

Meta info is very useful during type analysis. It helps to make decisions based on graph structure. In future, more flags will be added. Issue: #17

Issue: #17

It allows to compare any two types, store them in STL container such as std::set, use them as a key in std::map and use composition operators during type inference procedure. Operator | is a disjunction-like operator used to get sum of several possible types within a type. For example: 2 | 2 -> 2 2 | 3 -> (2, 3) 2 | * -> (2, *) (Object) | (SmallInt) -> ((Object), (SmallInt)) This operator may be used to aggregate possible types within a linear sequence where several type outcomes are possible: x <- y isNil ifTrue: [ nil ] ifFalse: [ 42 ]. In this case x will have composite type (nil, 42). On the other hand, when dealing with loops we need some kind of a reduction operator that will act as a conjunction: 2 & 2 -> 2 2 & 3 -> (SmallInt) 2 & (SmallInt) -> (SmallInt) <any type> & * -> * (SmallInt) & (Object) -> * This operator is used during induction run of the type analyzer to prove that variable does not leave it's local type domain, i.e it's type is not reduced to a *. Issue: #17

Meta info is very useful during type analysis. It helps to make decisions based on graph structure. In future, more flags will be added. Issue: #17

Issue: #17

This code need to be refactored properly. In case if both operands are literal, then result may be defined as literal too. Otherwise primitive should "fail" by allowing control flow to pass further. For literal calculation it is best to use existing code for software VM. Issue: #17

Issue: #17

This information is very useful during type inference. It may be gathered on-demand, but that would require additional pass. It is very cheap to collect meta info on the fly, so why not? Issue: #17

Issue: #17

For correct inference of the parallel paths in a graph it is critical to perform traverse breadth-first. Otherwise, phi nodes may have their incomings undefined. Issue: #17 Issue: #92

Some methods like Object>>error: do not return a value in a usual way. In that case control flow is interrupted and all call chain aborts. Type analyzer uses an empty composite type () to mark such special case. Please note that () is not equal to * or ? types that still return a value. Issue: #17 Issue: #92

Issue: #17 Issue: #92

…Graph() Issue: #17 Issue: #92

Issue: #17 Issue: #92

Previously if one includes inference.h and uses namespace type, then it will result in a name collision if LLVM is in scope. Issue: #17 Issue: #92

Issue: #17 Issue: #92

…erence Issue: #17 Issue: #92

Issue: #17 Issue: #92

…d args Issue: #17 Issue: #92

Issue: #17 Issue: #92

Unlike statically inferred block, dynamic ones need to create and carry their closure environment. Two blocks with the same set of argument types may have different closure types even if their closure context is the same. We add closure types to a dynamic block's cache key and to block function name to disambiguate calls. Issue: #17 Issue: #92

Issue: #17 Issue: #92

0x7CFE added the research label Apr 22, 2014

0x7CFE added a commit that referenced this issue May 21, 2016

Adds basic logic of type analyzer and inference API

1f0da05

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds Type::toString()

8294226

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds CallContext::operator[index]

00ea340

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds const cast for BranchNode

91fc4e2

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Fixes analyzer and context, adds handling of conditional branches

739729d

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds meta information to control graph

479fb29

Meta info is very useful during type analysis. It helps to make decisions based on graph structure. In future, more flags will be added. Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds core inference logic to TypeAnalyzer

7caca94

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds basic logic of type analyzer and inference API

1789190

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds Type::toString()

eeebbbf

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds CallContext::operator[index]

7f43e3f

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds const cast for BranchNode

aa97c11

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Fixes analyzer and context, adds handling of conditional branches

55e65b4

Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds meta information to control graph

b53b712

Meta info is very useful during type analysis. It helps to make decisions based on graph structure. In future, more flags will be added. Issue: #17

0x7CFE added a commit that referenced this issue May 21, 2016

Adds core inference logic to TypeAnalyzer

50aa7eb

Issue: #17

0x7CFE added a commit that referenced this issue May 23, 2016

Adds inference for instantiation and get class primitives

c50da97

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Adds function to print block type

2f7a417

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Renames CallContext to InferContext, analyzeCall to inferMessage

4b2e1a8

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Removes findCallContext()

719e6ec

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Adds stub for block inference

feddc12

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Adds logic to infer messages to literal classes

b0d8b87

Issue: #17

0x7CFE added a commit that referenced this issue May 25, 2016

Adds inference for block invocation arguments

bdeb3c0

Issue: #17

0x7CFE added a commit that referenced this issue May 26, 2016

Fixes subtypes in array context

e189b20

Issue: #17

0x7CFE added a commit that referenced this issue Jun 18, 2016

Disambiguates subtype fill functions

3f80561

Issue: #17

0x7CFE added a commit that referenced this issue Jun 18, 2016

Adds more small int primitives (still temporary solution)

3367adc

Issue: #17

0x7CFE added a commit that referenced this issue Jun 18, 2016

Fixes prototype of TypeSystem::inferBlock()

e08da8d

Issue: #17

0x7CFE added a commit that referenced this issue Jul 5, 2016

Adds Type::fold(), refactors getSingleReturnType()

ce9f0b7

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 5, 2016

Adds caching for block graphs, renames getControlGraph() to getMethod…

d74c752

…Graph() Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 5, 2016

Folds arguments of SmallInt primitives

31ff87f

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 9, 2016

Adds helper functions Type::is*() and getQualifiedName()

63aacb2

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 9, 2016

Refactors inference.h by namespaces by adding explicit st:: prefix

eb8eeb9

Previously if one includes inference.h and uses namespace type, then it will result in a name collision if LLVM is in scope. Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 9, 2016

Adds initial inference logic to the MethodCompiler and JitRuntime

40eb706

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 10, 2016

Context and tempos are now stack allocated, SendBinary uses inference

9fc2dfc

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 10, 2016

Context and tempo are now stack allocated, SendBinary partly uses inf…

c6385ad

…erence Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 10, 2016

Fixes shouldProtectProducer(), variable names and comments

9c8d492

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Fixes shouldProtectProducer(), variable names and comments

3fc7659

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

ControlGraph::TMetaInfo::readsArguments now stores indices of accesse…

cc2e736

…d args Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Adds Type::isBlock()

f2c78e3

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Refactors JIT caches to support method/block specialization

cf7d822

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Adds support for direct calls of inferred blocks

9d39182

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Adds nounwind specifier to core helper functions

5263fe0

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Adds MethodCompiler::insertTrace() for JIT code trace injection

c9af814

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Fixes Type::toString()

15a7e2a

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 17, 2016

Fixes compiler and runtime related to dynamic block dispatch

3daecdb

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 21, 2016

Various fixes of method compiler, control graph and type analyzer

f17ef79

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 21, 2016

Adds TypeSystem::findBlockContext()

a532ac0

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 21, 2016

Fixes sendToSuper

9741b46

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 21, 2016

Refactors JITRuntime::printStat()

206db1c

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 25, 2016

Folds argument types of SendBinary instruction

33f4452

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Jul 25, 2016

Fixes primitives inference

fc6d1dd

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Aug 2, 2016

Fixes PushBlock in nested block context

878db08

Issue: #17 Issue: #92

0x7CFE added a commit that referenced this issue Aug 6, 2016

Adds closure mask for dynamic blocks created in soft VM

6a1167e

Issue: #17 Issue: #92

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Research the possibilities of statistically assisted type inference #17

Research the possibilities of statistically assisted type inference #17

0x7CFE commented Sep 16, 2013

Research the possibilities of statistically assisted type inference #17

Research the possibilities of statistically assisted type inference #17

Comments

0x7CFE commented Sep 16, 2013