{"action":"created","comment":{"url":"https://api.github.com/repos/chapel-lang/chapel/pulls/comments/87100795","pull_request_review_id":7726747,"id":87100795,"diff_hunk":"@@ -31,7 +32,7 @@ removeEmptyRecords() {\n \n   Vec<Type*> emptyRecordTypeSet;\n   int numEmptyRecordTypes = 0;\n-  Vec<Symbol*> emptyRecordSymbolSet;\n+  std::vector<Symbol*> emptyRecordSymbols;","path":"compiler/optimizations/removeEmptyRecords.cpp","position":13,"original_position":13,"commit_id":"d0387a2adeff44db5361d415a3ea4cda96fb6c3e","original_commit_id":"d0387a2adeff44db5361d415a3ea4cda96fb6c3e","user":{"login":"lydia-duncan","id":2454710,"avatar_url":"https://avatars.githubusercontent.com/u/2454710?v=3","gravatar_id":"","url":"https://api.github.com/users/lydia-duncan","html_url":"https://github.com/lydia-duncan","followers_url":"https://api.github.com/users/lydia-duncan/followers","following_url":"https://api.github.com/users/lydia-duncan/following{/other_user}","gists_url":"https://api.github.com/users/lydia-duncan/gists{/gist_id}","starred_url":"https://api.github.com/users/lydia-duncan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lydia-duncan/subscriptions","organizations_url":"https://api.github.com/users/lydia-duncan/orgs","repos_url":"https://api.github.com/users/lydia-duncan/repos","events_url":"https://api.github.com/users/lydia-duncan/events{/privacy}","received_events_url":"https://api.github.com/users/lydia-duncan/received_events","type":"User","site_admin":false},"body":":+1: ","created_at":"2016-11-08T22:41:50Z","updated_at":"2016-11-08T22:41:50Z","html_url":"https://github.com/chapel-lang/chapel/pull/4827#discussion_r87100795","pull_request_url":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827","_links":{"self":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/comments/87100795"},"html":{"href":"https://github.com/chapel-lang/chapel/pull/4827#discussion_r87100795"},"pull_request":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827"}}},"pull_request":{"url":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827","id":92854397,"html_url":"https://github.com/chapel-lang/chapel/pull/4827","diff_url":"https://github.com/chapel-lang/chapel/pull/4827.diff","patch_url":"https://github.com/chapel-lang/chapel/pull/4827.patch","issue_url":"https://api.github.com/repos/chapel-lang/chapel/issues/4827","number":4827,"state":"open","locked":false,"title":"Each Symbol keeps a list of SymExprs","user":{"login":"mppf","id":3653132,"avatar_url":"https://avatars.githubusercontent.com/u/3653132?v=3","gravatar_id":"","url":"https://api.github.com/users/mppf","html_url":"https://github.com/mppf","followers_url":"https://api.github.com/users/mppf/followers","following_url":"https://api.github.com/users/mppf/following{/other_user}","gists_url":"https://api.github.com/users/mppf/gists{/gist_id}","starred_url":"https://api.github.com/users/mppf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mppf/subscriptions","organizations_url":"https://api.github.com/users/mppf/orgs","repos_url":"https://api.github.com/users/mppf/repos","events_url":"https://api.github.com/users/mppf/events{/privacy}","received_events_url":"https://api.github.com/users/mppf/received_events","type":"User","site_admin":false},"body":"This PR enables each Symbol to have a list of SymExprs that refer to it.\r\nThese could be called \"uses\" but in compiler terminology, a \"use\" is a read of a value and a \"def\" is a write to it. The list of Symbols that refer to a SymExprs include both \"defs\" and \"uses\" as well as other ways that a Symbol might be referred to.\r\n\r\nFor example, once resolution runs, there are SymExprs that refer to:\r\n *  a called function Symbol\r\n * a particular field in an AggregateType\r\n\r\nHaving easy access to the list of SymExprs that refer to a given Symbol will simplify some code patterns.\r\n\r\nThe list of SymExprs for each Symbol is actually implemented as a doubly-linked-list. That has the best complexity. It offers O(1) performance for adding and removing and O(n) for traversal, which is pretty much the best we could hope for. Also, these list elements are implemented with intrusive list pointers. I manually re-instantiated some other doubly-linked list code we had in the compiler for alist. I think it's important to store the list pointers within the SymExprs in order to minimize allocation overhead.\r\n\r\nThis PR is best viewed as a series of commits:\r\n\r\n 1) Basic AST structure for Symbol listing SymExprs (ie add fields to Symbol and SymExpr)\r\n 2) Replace all uses of SymExpr->var with SymExpr->symbol() or SymExpr->setSymbol()\r\n 3) Wire up the list of SymExprs for each Symbol so that it updated appropriately as SymExprs are added to the tree or when setSymbol is used to update a symbol already in the tree. Also update --verify to check that this list is correct.\r\n 4) Demonstrate the usefulness of this approach by modifying 3 loops that previously went over all SymExprs (with gSymExprs).\r\n\r\n\r\nBy far the majority of changes are in part (2), so it's best to view that commit separately.\r\n\r\nPerformance Impact:\r\n\r\nI observed about 0.1 s increase in compilation time when building hello.chpl on my system before updating any passes to use the new list. Thus, the overhead is small enough that we expect performance benefit from using this approach in more of the compiler.\r\n\r\nFuture Work:\r\n\r\nIn the future, I hope that some common patterns such as finding defs and uses and finding callers of a FnSymbol will move over to the new strategy.\r\n\r\nTesting:\r\n\r\nPassed quickstart testing.\r\nPassed quickstart+gasnet testing.\r\n- [ ] verify testing\r\n- [ ] baseline testing\r\n","created_at":"2016-11-08T20:38:23Z","updated_at":"2016-11-08T22:41:50Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c5953ccf05e1e58eb2e0dddfa5b1c2c3fe6d6f28","assignee":{"login":"lydia-duncan","id":2454710,"avatar_url":"https://avatars.githubusercontent.com/u/2454710?v=3","gravatar_id":"","url":"https://api.github.com/users/lydia-duncan","html_url":"https://github.com/lydia-duncan","followers_url":"https://api.github.com/users/lydia-duncan/followers","following_url":"https://api.github.com/users/lydia-duncan/following{/other_user}","gists_url":"https://api.github.com/users/lydia-duncan/gists{/gist_id}","starred_url":"https://api.github.com/users/lydia-duncan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lydia-duncan/subscriptions","organizations_url":"https://api.github.com/users/lydia-duncan/orgs","repos_url":"https://api.github.com/users/lydia-duncan/repos","events_url":"https://api.github.com/users/lydia-duncan/events{/privacy}","received_events_url":"https://api.github.com/users/lydia-duncan/received_events","type":"User","site_admin":false},"assignees":[{"login":"lydia-duncan","id":2454710,"avatar_url":"https://avatars.githubusercontent.com/u/2454710?v=3","gravatar_id":"","url":"https://api.github.com/users/lydia-duncan","html_url":"https://github.com/lydia-duncan","followers_url":"https://api.github.com/users/lydia-duncan/followers","following_url":"https://api.github.com/users/lydia-duncan/following{/other_user}","gists_url":"https://api.github.com/users/lydia-duncan/gists{/gist_id}","starred_url":"https://api.github.com/users/lydia-duncan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lydia-duncan/subscriptions","organizations_url":"https://api.github.com/users/lydia-duncan/orgs","repos_url":"https://api.github.com/users/lydia-duncan/repos","events_url":"https://api.github.com/users/lydia-duncan/events{/privacy}","received_events_url":"https://api.github.com/users/lydia-duncan/received_events","type":"User","site_admin":false}],"milestone":null,"commits_url":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827/commits","review_comments_url":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827/comments","review_comment_url":"https://api.github.com/repos/chapel-lang/chapel/pulls/comments{/number}","comments_url":"https://api.github.com/repos/chapel-lang/chapel/issues/4827/comments","statuses_url":"https://api.github.com/repos/chapel-lang/chapel/statuses/d0387a2adeff44db5361d415a3ea4cda96fb6c3e","head":{"label":"mppf:symexprs","ref":"symexprs","sha":"d0387a2adeff44db5361d415a3ea4cda96fb6c3e","user":{"login":"mppf","id":3653132,"avatar_url":"https://avatars.githubusercontent.com/u/3653132?v=3","gravatar_id":"","url":"https://api.github.com/users/mppf","html_url":"https://github.com/mppf","followers_url":"https://api.github.com/users/mppf/followers","following_url":"https://api.github.com/users/mppf/following{/other_user}","gists_url":"https://api.github.com/users/mppf/gists{/gist_id}","starred_url":"https://api.github.com/users/mppf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mppf/subscriptions","organizations_url":"https://api.github.com/users/mppf/orgs","repos_url":"https://api.github.com/users/mppf/repos","events_url":"https://api.github.com/users/mppf/events{/privacy}","received_events_url":"https://api.github.com/users/mppf/received_events","type":"User","site_admin":false},"repo":{"id":22106313,"name":"chapel","full_name":"mppf/chapel","owner":{"login":"mppf","id":3653132,"avatar_url":"https://avatars.githubusercontent.com/u/3653132?v=3","gravatar_id":"","url":"https://api.github.com/users/mppf","html_url":"https://github.com/mppf","followers_url":"https://api.github.com/users/mppf/followers","following_url":"https://api.github.com/users/mppf/following{/other_user}","gists_url":"https://api.github.com/users/mppf/gists{/gist_id}","starred_url":"https://api.github.com/users/mppf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mppf/subscriptions","organizations_url":"https://api.github.com/users/mppf/orgs","repos_url":"https://api.github.com/users/mppf/repos","events_url":"https://api.github.com/users/mppf/events{/privacy}","received_events_url":"https://api.github.com/users/mppf/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/mppf/chapel","description":"a Productive Parallel Programming Language","fork":true,"url":"https://api.github.com/repos/mppf/chapel","forks_url":"https://api.github.com/repos/mppf/chapel/forks","keys_url":"https://api.github.com/repos/mppf/chapel/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mppf/chapel/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mppf/chapel/teams","hooks_url":"https://api.github.com/repos/mppf/chapel/hooks","issue_events_url":"https://api.github.com/repos/mppf/chapel/issues/events{/number}","events_url":"https://api.github.com/repos/mppf/chapel/events","assignees_url":"https://api.github.com/repos/mppf/chapel/assignees{/user}","branches_url":"https://api.github.com/repos/mppf/chapel/branches{/branch}","tags_url":"https://api.github.com/repos/mppf/chapel/tags","blobs_url":"https://api.github.com/repos/mppf/chapel/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mppf/chapel/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mppf/chapel/git/refs{/sha}","trees_url":"https://api.github.com/repos/mppf/chapel/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mppf/chapel/statuses/{sha}","languages_url":"https://api.github.com/repos/mppf/chapel/languages","stargazers_url":"https://api.github.com/repos/mppf/chapel/stargazers","contributors_url":"https://api.github.com/repos/mppf/chapel/contributors","subscribers_url":"https://api.github.com/repos/mppf/chapel/subscribers","subscription_url":"https://api.github.com/repos/mppf/chapel/subscription","commits_url":"https://api.github.com/repos/mppf/chapel/commits{/sha}","git_commits_url":"https://api.github.com/repos/mppf/chapel/git/commits{/sha}","comments_url":"https://api.github.com/repos/mppf/chapel/comments{/number}","issue_comment_url":"https://api.github.com/repos/mppf/chapel/issues/comments{/number}","contents_url":"https://api.github.com/repos/mppf/chapel/contents/{+path}","compare_url":"https://api.github.com/repos/mppf/chapel/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mppf/chapel/merges","archive_url":"https://api.github.com/repos/mppf/chapel/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mppf/chapel/downloads","issues_url":"https://api.github.com/repos/mppf/chapel/issues{/number}","pulls_url":"https://api.github.com/repos/mppf/chapel/pulls{/number}","milestones_url":"https://api.github.com/repos/mppf/chapel/milestones{/number}","notifications_url":"https://api.github.com/repos/mppf/chapel/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mppf/chapel/labels{/name}","releases_url":"https://api.github.com/repos/mppf/chapel/releases{/id}","deployments_url":"https://api.github.com/repos/mppf/chapel/deployments","created_at":"2014-07-22T14:05:45Z","updated_at":"2016-01-11T15:01:10Z","pushed_at":"2016-11-08T22:11:18Z","git_url":"git://github.com/mppf/chapel.git","ssh_url":"git@github.com:mppf/chapel.git","clone_url":"https://github.com/mppf/chapel.git","svn_url":"https://github.com/mppf/chapel","homepage":"http://chapel.cray.com/","size":467140,"stargazers_count":1,"watchers_count":1,"language":"Chapel","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"chapel-lang:master","ref":"master","sha":"5868ea1f8eaffe8f9a578c6c6fde10440687fa0b","user":{"login":"chapel-lang","id":7597261,"avatar_url":"https://avatars.githubusercontent.com/u/7597261?v=3","gravatar_id":"","url":"https://api.github.com/users/chapel-lang","html_url":"https://github.com/chapel-lang","followers_url":"https://api.github.com/users/chapel-lang/followers","following_url":"https://api.github.com/users/chapel-lang/following{/other_user}","gists_url":"https://api.github.com/users/chapel-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/chapel-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chapel-lang/subscriptions","organizations_url":"https://api.github.com/users/chapel-lang/orgs","repos_url":"https://api.github.com/users/chapel-lang/repos","events_url":"https://api.github.com/users/chapel-lang/events{/privacy}","received_events_url":"https://api.github.com/users/chapel-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":21663285,"name":"chapel","full_name":"chapel-lang/chapel","owner":{"login":"chapel-lang","id":7597261,"avatar_url":"https://avatars.githubusercontent.com/u/7597261?v=3","gravatar_id":"","url":"https://api.github.com/users/chapel-lang","html_url":"https://github.com/chapel-lang","followers_url":"https://api.github.com/users/chapel-lang/followers","following_url":"https://api.github.com/users/chapel-lang/following{/other_user}","gists_url":"https://api.github.com/users/chapel-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/chapel-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chapel-lang/subscriptions","organizations_url":"https://api.github.com/users/chapel-lang/orgs","repos_url":"https://api.github.com/users/chapel-lang/repos","events_url":"https://api.github.com/users/chapel-lang/events{/privacy}","received_events_url":"https://api.github.com/users/chapel-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/chapel-lang/chapel","description":"a Productive Parallel Programming Language","fork":false,"url":"https://api.github.com/repos/chapel-lang/chapel","forks_url":"https://api.github.com/repos/chapel-lang/chapel/forks","keys_url":"https://api.github.com/repos/chapel-lang/chapel/keys{/key_id}","collaborators_url":"https://api.github.com/repos/chapel-lang/chapel/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/chapel-lang/chapel/teams","hooks_url":"https://api.github.com/repos/chapel-lang/chapel/hooks","issue_events_url":"https://api.github.com/repos/chapel-lang/chapel/issues/events{/number}","events_url":"https://api.github.com/repos/chapel-lang/chapel/events","assignees_url":"https://api.github.com/repos/chapel-lang/chapel/assignees{/user}","branches_url":"https://api.github.com/repos/chapel-lang/chapel/branches{/branch}","tags_url":"https://api.github.com/repos/chapel-lang/chapel/tags","blobs_url":"https://api.github.com/repos/chapel-lang/chapel/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/chapel-lang/chapel/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/chapel-lang/chapel/git/refs{/sha}","trees_url":"https://api.github.com/repos/chapel-lang/chapel/git/trees{/sha}","statuses_url":"https://api.github.com/repos/chapel-lang/chapel/statuses/{sha}","languages_url":"https://api.github.com/repos/chapel-lang/chapel/languages","stargazers_url":"https://api.github.com/repos/chapel-lang/chapel/stargazers","contributors_url":"https://api.github.com/repos/chapel-lang/chapel/contributors","subscribers_url":"https://api.github.com/repos/chapel-lang/chapel/subscribers","subscription_url":"https://api.github.com/repos/chapel-lang/chapel/subscription","commits_url":"https://api.github.com/repos/chapel-lang/chapel/commits{/sha}","git_commits_url":"https://api.github.com/repos/chapel-lang/chapel/git/commits{/sha}","comments_url":"https://api.github.com/repos/chapel-lang/chapel/comments{/number}","issue_comment_url":"https://api.github.com/repos/chapel-lang/chapel/issues/comments{/number}","contents_url":"https://api.github.com/repos/chapel-lang/chapel/contents/{+path}","compare_url":"https://api.github.com/repos/chapel-lang/chapel/compare/{base}...{head}","merges_url":"https://api.github.com/repos/chapel-lang/chapel/merges","archive_url":"https://api.github.com/repos/chapel-lang/chapel/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/chapel-lang/chapel/downloads","issues_url":"https://api.github.com/repos/chapel-lang/chapel/issues{/number}","pulls_url":"https://api.github.com/repos/chapel-lang/chapel/pulls{/number}","milestones_url":"https://api.github.com/repos/chapel-lang/chapel/milestones{/number}","notifications_url":"https://api.github.com/repos/chapel-lang/chapel/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/chapel-lang/chapel/labels{/name}","releases_url":"https://api.github.com/repos/chapel-lang/chapel/releases{/id}","deployments_url":"https://api.github.com/repos/chapel-lang/chapel/deployments","created_at":"2014-07-09T18:15:54Z","updated_at":"2016-11-08T07:38:55Z","pushed_at":"2016-11-08T22:11:21Z","git_url":"git://github.com/chapel-lang/chapel.git","ssh_url":"git@github.com:chapel-lang/chapel.git","clone_url":"https://github.com/chapel-lang/chapel.git","svn_url":"https://github.com/chapel-lang/chapel","homepage":"http://chapel.cray.com/","size":514166,"stargazers_count":330,"watchers_count":330,"language":"Chapel","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":109,"mirror_url":null,"open_issues_count":13,"forks":109,"open_issues":13,"watchers":330,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827"},"html":{"href":"https://github.com/chapel-lang/chapel/pull/4827"},"issue":{"href":"https://api.github.com/repos/chapel-lang/chapel/issues/4827"},"comments":{"href":"https://api.github.com/repos/chapel-lang/chapel/issues/4827/comments"},"review_comments":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827/comments"},"review_comment":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/chapel-lang/chapel/pulls/4827/commits"},"statuses":{"href":"https://api.github.com/repos/chapel-lang/chapel/statuses/d0387a2adeff44db5361d415a3ea4cda96fb6c3e"}}}}
{"actor":{"display_login":"lydia-duncan"}}