{"action":"created","issue":{"url":"https://api.github.com/repos/WebAssembly/binaryen/issues/507","repository_url":"https://api.github.com/repos/WebAssembly/binaryen","labels_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/507/labels{/name}","comments_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/507/comments","events_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/507/events","html_url":"https://github.com/WebAssembly/binaryen/pull/507","id":154945236,"number":507,"title":"Coalesce locals","user":{"login":"kripken","id":173661,"avatar_url":"https://avatars.githubusercontent.com/u/173661?v=3","gravatar_id":"","url":"https://api.github.com/users/kripken","html_url":"https://github.com/kripken","followers_url":"https://api.github.com/users/kripken/followers","following_url":"https://api.github.com/users/kripken/following{/other_user}","gists_url":"https://api.github.com/users/kripken/gists{/gist_id}","starred_url":"https://api.github.com/users/kripken/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kripken/subscriptions","organizations_url":"https://api.github.com/users/kripken/orgs","repos_url":"https://api.github.com/users/kripken/repos","events_url":"https://api.github.com/users/kripken/events{/privacy}","received_events_url":"https://api.github.com/users/kripken/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":10,"created_at":"2016-05-16T01:30:32Z","updated_at":"2016-05-17T18:49:35Z","closed_at":"2016-05-16T18:03:11Z","pull_request":{"url":"https://api.github.com/repos/WebAssembly/binaryen/pulls/507","html_url":"https://github.com/WebAssembly/binaryen/pull/507","diff_url":"https://github.com/WebAssembly/binaryen/pull/507.diff","patch_url":"https://github.com/WebAssembly/binaryen/pull/507.patch"},"body":"This generates a CFG from the AST, finds live ranges, and does local coloring.\r\n\r\nCurrently it does simple greedy coloring, which obviously should be improved on. However it currently removes 2% of local definitions on BananaBread from asm2wasm and 1% from wasm-backend, so it's already useful. Further work can also focus on stuff like the distribution of locals (gzip would do better on 99 accesses of 0 and 1 of 1, as opposed to 50 of each, even though the total number of locals is the same, etc.).\r\n\r\nThis is the slowest optimization pass we have so far. I didn't do much tuning yet. Currently it uses sorted vectors for the sets of live locals, which is good for functions with many locals but short average lists. Suggestions are very welcome."},"comment":{"url":"https://api.github.com/repos/WebAssembly/binaryen/issues/comments/219816240","html_url":"https://github.com/WebAssembly/binaryen/pull/507#issuecomment-219816240","issue_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/507","id":219816240,"user":{"login":"kripken","id":173661,"avatar_url":"https://avatars.githubusercontent.com/u/173661?v=3","gravatar_id":"","url":"https://api.github.com/users/kripken","html_url":"https://github.com/kripken","followers_url":"https://api.github.com/users/kripken/followers","following_url":"https://api.github.com/users/kripken/following{/other_user}","gists_url":"https://api.github.com/users/kripken/gists{/gist_id}","starred_url":"https://api.github.com/users/kripken/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kripken/subscriptions","organizations_url":"https://api.github.com/users/kripken/orgs","repos_url":"https://api.github.com/users/kripken/repos","events_url":"https://api.github.com/users/kripken/events{/privacy}","received_events_url":"https://api.github.com/users/kripken/received_events","type":"User","site_admin":false},"created_at":"2016-05-17T18:49:35Z","updated_at":"2016-05-17T18:49:35Z","body":"Ok, I see how you generate the list of live vars using that algorithm (indeed nicer on SSA...). Do you then use that to generate an interference graph? That's where the iteration over variables would happen. Or do you do some other register allocation method?"}}