{"action":"created","issue":{"url":"https://api.github.com/repos/0x7CFE/llst/issues/92","repository_url":"https://api.github.com/repos/0x7CFE/llst","labels_url":"https://api.github.com/repos/0x7CFE/llst/issues/92/labels{/name}","comments_url":"https://api.github.com/repos/0x7CFE/llst/issues/92/comments","events_url":"https://api.github.com/repos/0x7CFE/llst/issues/92/events","html_url":"https://github.com/0x7CFE/llst/pull/92","id":161022248,"number":92,"title":"Type inference prototype based on static analysis","user":{"login":"0x7CFE","id":3784017,"avatar_url":"https://avatars.githubusercontent.com/u/3784017?v=3","gravatar_id":"","url":"https://api.github.com/users/0x7CFE","html_url":"https://github.com/0x7CFE","followers_url":"https://api.github.com/users/0x7CFE/followers","following_url":"https://api.github.com/users/0x7CFE/following{/other_user}","gists_url":"https://api.github.com/users/0x7CFE/gists{/gist_id}","starred_url":"https://api.github.com/users/0x7CFE/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/0x7CFE/subscriptions","organizations_url":"https://api.github.com/users/0x7CFE/orgs","repos_url":"https://api.github.com/users/0x7CFE/repos","events_url":"https://api.github.com/users/0x7CFE/events{/privacy}","received_events_url":"https://api.github.com/users/0x7CFE/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/0x7CFE/llst/labels/feature","name":"feature","color":"84b6eb"},{"url":"https://api.github.com/repos/0x7CFE/llst/labels/research","name":"research","color":"0052cc"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":22,"created_at":"2016-06-18T12:35:26Z","updated_at":"2016-07-21T17:23:12Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/0x7CFE/llst/pulls/92","html_url":"https://github.com/0x7CFE/llst/pull/92","diff_url":"https://github.com/0x7CFE/llst/pull/92.diff","patch_url":"https://github.com/0x7CFE/llst/pull/92.patch"},"body":"This PR is my first rather independent (or naïve?) attempt to realize how type inference may be used to aid JIT VM. Underlying concept is not based on any well-known theory like [Hindley-Milner type system](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system) or [Martin Löf's Intuitionistic type theory](https://en.wikipedia.org/wiki/Intuitionistic_type_theory). It's the result of a pure meditation on Smalltalk bytecodes.\r\n\r\nSurprisingly enough, Smalltalk being fully dynamic in it's nature is still very regular in terms of it's memory access and control flow. This really helps when we try to perform static analysis.\r\n\r\nCurrent implementation concentrates on the method temporaries and gives up completely when it faces object fields. However, I believe that in local context it is still possible to infer the object's fields to fully unlock further analysis and optimizations, like stack allocation, GC root elimination, and of course [TBAA](https://en.wikipedia.org/wiki/Alias_analysis#Type-based_alias_analysis).\r\n\r\nCurrent implementation is powerful enough to infer self assigning temporaries within a loop and even in complex closure contexts. \r\n\r\nFor example, the following method is inferred completely:\r\n```Smalltalk\r\ntestInference |sum|\r\n    sum <- 0.\r\n    1 to: 100 do:\r\n        [ :x | sum <- sum + x ].\r\n    ^sum\r\n```\r\nHere analyzer _proves_ that `sum` variable will have `SmallInt` type in it's scope which spans across the follwing methods: `Undefined>>testInference`, `Number>>to:do:`, `Block>>value:` and finally, the block `Undefined>>testInference@8`. Integer overflow is currently undefined.\r\n\r\nThis allows IR generator to encode operations on `sum` directly as `i32` without any worries about GC or dynamic dispatch.\r\n\r\nCurrent inference scheme highly uses method monomorphisation and specialization, which helps to perform calculations at compile time. \r\n\r\nFor example, this code is reduced to a single literal value (the result) at compile time:\r\n```Smalltalk\r\nfibonacci: n\r\n    n < 3 ifTrue: [ ^1 ].\r\n    ^ (self fibonacci: n - 2) + (self fibonacci: n - 1)\r\n```\r\n\r\nType inference works even in case of recurring contexts and correctly solves [chicken or egg problem](https://en.wikipedia.org/wiki/Chicken_or_the_egg). Consider the listing of the `Collection>>sort:`\r\n```Smalltalk\r\nsort: criteria | left right mediane |\r\n    (self size < 2) ifTrue: [^self].\r\n\r\n    mediane <- self popFirst.\r\n\r\n    left  <- List new.\r\n    right <- List new.\r\n    self do: [ :x |\r\n        (criteria value: x value: mediane)\r\n            ifTrue:  [ left  add: x ]\r\n            ifFalse: [ right add: x ] ].\r\n\r\n    left  <- left  sort: criteria.\r\n    right <- right sort: criteria.\r\n\r\n    right add: mediane.\r\n    ^ left appendList: right\r\n```\r\n\r\nThis is suboptimal implementation of the [Quicksort algorithm](https://en.wikipedia.org/wiki/Quicksort) used here only for testing purposes. It performs two recursive calls to `Collection>>sort:` when sorting `left` and `right` sublists. The main difficulty here is to infer the return value of the `Collection>>sort:`. For example, analysis of the `left` refers to the outer context which at that point is not inferred completely, hence no return type available.\r\n\r\nHowever, current implementation correctly solves the problem using a fact, that every recursion has it's base which should be evaluated prior to the next recursive call. By propagating the base return type from the outer context to the inner one we succeed in the whole process. See [the log](https://gist.github.com/0x7CFE/19d695e804f5c2eeccea36a7aa92dc7d) for an example of such inference. You may also see the resulting call graph as [rendered svg](https://gist.github.com/0x7CFE/689d40589797332ef46a0d692fc7eaa6) or [graphviz source](https://gist.github.com/0x7CFE/85fa09eaedd12c02b57e216b99a10d8d).\r\n\r\nStatic analysis along with runtime statistics and polymorphic method cacheing provides enough information for effective dispatch of the Smalltalk code.\r\n\r\nSee also: #56, #58.\r\n\r\nThe implementation is not complete yet, there are a lot of things to do:\r\n- [x] Implement inference of non-literal recursive messages, such as `Collection>>sort:`\r\n- [ ] Implement inference of composite types one per entry\r\n- [ ] Detect block escaping and avoid inference of the captured variables\r\n- [ ] Detect situations where inference will produce invalid results\r\n- [ ] Detect correct number of passes for guaranteed inference\r\n- [ ] Detect when method specialization is redundant and unnecessary\r\n- [ ] Solve the situation when phi incoming maps to a node from a dead path\r\n- [x] Type inference walker should use breadth-first traverse\r\n- [ ] Analysis for block invocation kind in closure sites\r\n- [ ] Inference across phi nodes\r\n- [x] Memory management, block inference caches, …\r\n- [ ] Implement inference of the remaining primitives \r\n- [x] Use inferred types in actual code generation\r\n- [ ] Take care of non-static objects\r\n"},"comment":{"url":"https://api.github.com/repos/0x7CFE/llst/issues/comments/234323199","html_url":"https://github.com/0x7CFE/llst/pull/92#issuecomment-234323199","issue_url":"https://api.github.com/repos/0x7CFE/llst/issues/92","id":234323199,"user":{"login":"coveralls","id":2354108,"avatar_url":"https://avatars.githubusercontent.com/u/2354108?v=3","gravatar_id":"","url":"https://api.github.com/users/coveralls","html_url":"https://github.com/coveralls","followers_url":"https://api.github.com/users/coveralls/followers","following_url":"https://api.github.com/users/coveralls/following{/other_user}","gists_url":"https://api.github.com/users/coveralls/gists{/gist_id}","starred_url":"https://api.github.com/users/coveralls/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/coveralls/subscriptions","organizations_url":"https://api.github.com/users/coveralls/orgs","repos_url":"https://api.github.com/users/coveralls/repos","events_url":"https://api.github.com/users/coveralls/events{/privacy}","received_events_url":"https://api.github.com/users/coveralls/received_events","type":"User","site_admin":false},"created_at":"2016-07-21T17:23:12Z","updated_at":"2016-07-21T17:23:12Z","body":"\n[![Coverage Status](https://coveralls.io/builds/7106694/badge)](https://coveralls.io/builds/7106694)\n\nCoverage decreased (-13.6%) to 47.667% when pulling **9741b4653f0743847682538156e8cb2787840f35 on feature/17/type_inference** into **ff4d76d30584adaa20a309ca2487122cb51479c6 on develop**.\n"}}
{"actor":{"display_login":"coveralls"}}