{"action":"created","comment":{"url":"https://api.github.com/repos/dotnet/coreclr/pulls/comments/72914807","id":72914807,"diff_hunk":"@@ -3179,9 +3522,38 @@ LinearScan::buildRefPositionsForNode(GenTree *tree,\n     int internalCount = buildInternalRegisterDefsForNode(tree, currentLoc, internalRefs);\n \n     // pop all ref'd tree temps\n-    for (int useIndex=0; useIndex < consume; useIndex++)\n+    GenTreeOperandIterator iterator = tree->OperandsBegin(true);\n+    LocationInfoList operandDefs;\n+    LocationInfoListNode* operandDefsIterator = operandDefs.End();\n+    for (int useIndex = 0; useIndex < consume; useIndex++)\n     {\n-        LocationInfo locInfo = stack->Pop();\n+        if (operandDefsIterator == operandDefs.End())\n+        {\n+            GenTree* operand;\n+            do\n+            {\n+                assert(iterator != tree->OperandsEnd());\n+                operand = *iterator;\n+\n+                ++iterator;\n+            } while (!operand->gtLsraInfo.contributesSources);","path":"src/jit/lsra.cpp","position":498,"original_position":498,"commit_id":"6d8c82c765835947885e2f7227bf13b52d97d28d","original_commit_id":"6d8c82c765835947885e2f7227bf13b52d97d28d","user":{"login":"CarolEidt","id":2973870,"avatar_url":"https://avatars.githubusercontent.com/u/2973870?v=3","gravatar_id":"","url":"https://api.github.com/users/CarolEidt","html_url":"https://github.com/CarolEidt","followers_url":"https://api.github.com/users/CarolEidt/followers","following_url":"https://api.github.com/users/CarolEidt/following{/other_user}","gists_url":"https://api.github.com/users/CarolEidt/gists{/gist_id}","starred_url":"https://api.github.com/users/CarolEidt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CarolEidt/subscriptions","organizations_url":"https://api.github.com/users/CarolEidt/orgs","repos_url":"https://api.github.com/users/CarolEidt/repos","events_url":"https://api.github.com/users/CarolEidt/events{/privacy}","received_events_url":"https://api.github.com/users/CarolEidt/received_events","type":"User","site_admin":false},"body":">contributesSources [](start = 42, length = 18)\r\n\r\nThis code could use some comments. In particular:\r\n- It would be good to elucidate here that the first piece of code is getting the register info for (possibly multiple) registers that are defined by a single operand.\r\n- It is not immediately obvious that, once I have captured `operandDefs`, that I can then free those nodes from the map.\r\n- There is often confusion between uses and defs. It would be good to explicitly remind the reader that these `operandDefs` become the uses of the current node, and that if a node `contributesSources` those are actually its defs. It's a bit confusing, so you might redefine `contributesSources` as something like `definesRegs` - since that's more consistent with the `operandDefs` naming.","created_at":"2016-08-01T00:47:31Z","updated_at":"2016-08-01T00:47:31Z","html_url":"https://github.com/dotnet/coreclr/pull/6533#discussion_r72914807","pull_request_url":"https://api.github.com/repos/dotnet/coreclr/pulls/6533","_links":{"self":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/comments/72914807"},"html":{"href":"https://github.com/dotnet/coreclr/pull/6533#discussion_r72914807"},"pull_request":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/6533"}}},"pull_request":{"url":"https://api.github.com/repos/dotnet/coreclr/pulls/6533","id":79432920,"html_url":"https://github.com/dotnet/coreclr/pull/6533","diff_url":"https://github.com/dotnet/coreclr/pull/6533.diff","patch_url":"https://github.com/dotnet/coreclr/pull/6533.patch","issue_url":"https://api.github.com/repos/dotnet/coreclr/issues/6533","number":6533,"state":"open","locked":false,"title":"Replace the LSRA stack with a hash table.","user":{"login":"pgavlin","id":1224093,"avatar_url":"https://avatars.githubusercontent.com/u/1224093?v=3","gravatar_id":"","url":"https://api.github.com/users/pgavlin","html_url":"https://github.com/pgavlin","followers_url":"https://api.github.com/users/pgavlin/followers","following_url":"https://api.github.com/users/pgavlin/following{/other_user}","gists_url":"https://api.github.com/users/pgavlin/gists{/gist_id}","starred_url":"https://api.github.com/users/pgavlin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pgavlin/subscriptions","organizations_url":"https://api.github.com/users/pgavlin/orgs","repos_url":"https://api.github.com/users/pgavlin/repos","events_url":"https://api.github.com/users/pgavlin/events{/privacy}","received_events_url":"https://api.github.com/users/pgavlin/received_events","type":"User","site_admin":false},"body":"LSRA currently uses a stack to find the `LocationInfo` for each register consumed\r\nby a node. The changes in this stack's contents given a particular node are\r\ngoverned by three factors:\r\n- The number of registers the node consumes (`gtLsraInfo.srcCount`)\r\n- The number of registers the node produces (`gtLstaInfo.dstCount`)\r\n- Whether or not the node produces an unused value (`gtLsraInfo.isLocalDefUse`)\r\n\r\nIn all cases, `gtLsraInfo.srcCount` values are popped off of the stack in the\r\norder in which they were pushed (i.e. in FIFO rather than LIFO order). If the\r\nnode produces a value that will be used, `gtLsraInfo.dstCount` values are\r\nthen pushed onto the stack. If the node produces an unused value, nothing is\r\npushed onto the stack.\r\n\r\nNaively, it would appear that the number of registers a node consumes would be\r\nat least the count of the node's non-leaf operands (to put it differently, one\r\nmight assume that any non-leaf operator that produces a value would define at\r\nleast one register). However, contained nodes complicate the situation: because\r\na contained node's execution is subsumed by its user, the contained node's\r\nsources become sources for its user and the contained node does not define any\r\nregisters. As a result, both the number of registers consumed and the number of\r\nregisters produced by a contained node are 0. Thus, contained nodes do not\r\nupdate the stack, and the node's parent (if it is not also contained) will\r\npop the values produced by the contained node's operands. Logically speaking,\r\nit is as if a contained node defines the transitive closure of the registers\r\ndefined by its own non-contained operands.\r\n\r\nThe use of the stack relies on the property that even in linear order the\r\nJIT's IR is still tree ordered. That is to say, given an operator and its\r\noperands, any nodes that execute between any two operands do not produce\r\nSDSU temps that are consumed after the second operand. IR with such a\r\nshape would unbalance the stack.\r\n\r\nThe planned move to the LIR design given in #6366 removes the tree order\r\nconstraint in order to simplify understanding and manipulating the IR in the\r\nbackend. Because LIR may not be tree ordered, LSRA may no longer use a stack\r\nto find the `LocationInfo` for a node's operands. This change replaces the\r\nstack with a map from nodes to lists of `LocationInfo` values, each of\r\nwhich describes a register that is logically defined (if not physically\r\ndefined) by that node. Only contained nodes logically define registers that\r\nthey do not physically define: contained nodes map to the list of\r\n`LocationInfo` values logically defined by their operands. All non-contained\r\nnodes map to the list of `LocationInfo` values that they physically define.\r\nNon-contained nodes that do not define any registers are not inserted into\r\nthe map.","created_at":"2016-07-29T22:20:24Z","updated_at":"2016-08-01T00:47:31Z","closed_at":null,"merged_at":null,"merge_commit_sha":"675cad6f245d82557f5d05d8c4a87ea6597451b4","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/dotnet/coreclr/pulls/6533/commits","review_comments_url":"https://api.github.com/repos/dotnet/coreclr/pulls/6533/comments","review_comment_url":"https://api.github.com/repos/dotnet/coreclr/pulls/comments{/number}","comments_url":"https://api.github.com/repos/dotnet/coreclr/issues/6533/comments","statuses_url":"https://api.github.com/repos/dotnet/coreclr/statuses/6d8c82c765835947885e2f7227bf13b52d97d28d","head":{"label":"pgavlin:LSRA","ref":"LSRA","sha":"6d8c82c765835947885e2f7227bf13b52d97d28d","user":{"login":"pgavlin","id":1224093,"avatar_url":"https://avatars.githubusercontent.com/u/1224093?v=3","gravatar_id":"","url":"https://api.github.com/users/pgavlin","html_url":"https://github.com/pgavlin","followers_url":"https://api.github.com/users/pgavlin/followers","following_url":"https://api.github.com/users/pgavlin/following{/other_user}","gists_url":"https://api.github.com/users/pgavlin/gists{/gist_id}","starred_url":"https://api.github.com/users/pgavlin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pgavlin/subscriptions","organizations_url":"https://api.github.com/users/pgavlin/orgs","repos_url":"https://api.github.com/users/pgavlin/repos","events_url":"https://api.github.com/users/pgavlin/events{/privacy}","received_events_url":"https://api.github.com/users/pgavlin/received_events","type":"User","site_admin":false},"repo":{"id":30321049,"name":"coreclr","full_name":"pgavlin/coreclr","owner":{"login":"pgavlin","id":1224093,"avatar_url":"https://avatars.githubusercontent.com/u/1224093?v=3","gravatar_id":"","url":"https://api.github.com/users/pgavlin","html_url":"https://github.com/pgavlin","followers_url":"https://api.github.com/users/pgavlin/followers","following_url":"https://api.github.com/users/pgavlin/following{/other_user}","gists_url":"https://api.github.com/users/pgavlin/gists{/gist_id}","starred_url":"https://api.github.com/users/pgavlin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pgavlin/subscriptions","organizations_url":"https://api.github.com/users/pgavlin/orgs","repos_url":"https://api.github.com/users/pgavlin/repos","events_url":"https://api.github.com/users/pgavlin/events{/privacy}","received_events_url":"https://api.github.com/users/pgavlin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/pgavlin/coreclr","description":"This repo contains the .NET Core runtime, called CoreCLR. It is an execution engine for .NET apps, performing functions such as IL byte code loading, compilation to machine code and garbage collection. The repo contains the complete up-to-date CoreCLR codebase.","fork":true,"url":"https://api.github.com/repos/pgavlin/coreclr","forks_url":"https://api.github.com/repos/pgavlin/coreclr/forks","keys_url":"https://api.github.com/repos/pgavlin/coreclr/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pgavlin/coreclr/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pgavlin/coreclr/teams","hooks_url":"https://api.github.com/repos/pgavlin/coreclr/hooks","issue_events_url":"https://api.github.com/repos/pgavlin/coreclr/issues/events{/number}","events_url":"https://api.github.com/repos/pgavlin/coreclr/events","assignees_url":"https://api.github.com/repos/pgavlin/coreclr/assignees{/user}","branches_url":"https://api.github.com/repos/pgavlin/coreclr/branches{/branch}","tags_url":"https://api.github.com/repos/pgavlin/coreclr/tags","blobs_url":"https://api.github.com/repos/pgavlin/coreclr/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pgavlin/coreclr/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pgavlin/coreclr/git/refs{/sha}","trees_url":"https://api.github.com/repos/pgavlin/coreclr/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pgavlin/coreclr/statuses/{sha}","languages_url":"https://api.github.com/repos/pgavlin/coreclr/languages","stargazers_url":"https://api.github.com/repos/pgavlin/coreclr/stargazers","contributors_url":"https://api.github.com/repos/pgavlin/coreclr/contributors","subscribers_url":"https://api.github.com/repos/pgavlin/coreclr/subscribers","subscription_url":"https://api.github.com/repos/pgavlin/coreclr/subscription","commits_url":"https://api.github.com/repos/pgavlin/coreclr/commits{/sha}","git_commits_url":"https://api.github.com/repos/pgavlin/coreclr/git/commits{/sha}","comments_url":"https://api.github.com/repos/pgavlin/coreclr/comments{/number}","issue_comment_url":"https://api.github.com/repos/pgavlin/coreclr/issues/comments{/number}","contents_url":"https://api.github.com/repos/pgavlin/coreclr/contents/{+path}","compare_url":"https://api.github.com/repos/pgavlin/coreclr/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pgavlin/coreclr/merges","archive_url":"https://api.github.com/repos/pgavlin/coreclr/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pgavlin/coreclr/downloads","issues_url":"https://api.github.com/repos/pgavlin/coreclr/issues{/number}","pulls_url":"https://api.github.com/repos/pgavlin/coreclr/pulls{/number}","milestones_url":"https://api.github.com/repos/pgavlin/coreclr/milestones{/number}","notifications_url":"https://api.github.com/repos/pgavlin/coreclr/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pgavlin/coreclr/labels{/name}","releases_url":"https://api.github.com/repos/pgavlin/coreclr/releases{/id}","deployments_url":"https://api.github.com/repos/pgavlin/coreclr/deployments","created_at":"2015-02-04T21:04:39Z","updated_at":"2016-02-26T17:14:54Z","pushed_at":"2016-08-01T00:04:48Z","git_url":"git://github.com/pgavlin/coreclr.git","ssh_url":"git@github.com:pgavlin/coreclr.git","clone_url":"https://github.com/pgavlin/coreclr.git","svn_url":"https://github.com/pgavlin/coreclr","homepage":"","size":95317,"stargazers_count":0,"watchers_count":0,"language":"C#","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"dotnet:master","ref":"master","sha":"b49116c0f940760c49b2af9b7593e38a11921694","user":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"repo":{"id":30092893,"name":"coreclr","full_name":"dotnet/coreclr","owner":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/dotnet/coreclr","description":"This repo contains the .NET Core runtime, called CoreCLR, and the base library, called mscorlib. It includes the garbage collector, JIT compiler, base .NET data types and many low-level classes.","fork":false,"url":"https://api.github.com/repos/dotnet/coreclr","forks_url":"https://api.github.com/repos/dotnet/coreclr/forks","keys_url":"https://api.github.com/repos/dotnet/coreclr/keys{/key_id}","collaborators_url":"https://api.github.com/repos/dotnet/coreclr/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/dotnet/coreclr/teams","hooks_url":"https://api.github.com/repos/dotnet/coreclr/hooks","issue_events_url":"https://api.github.com/repos/dotnet/coreclr/issues/events{/number}","events_url":"https://api.github.com/repos/dotnet/coreclr/events","assignees_url":"https://api.github.com/repos/dotnet/coreclr/assignees{/user}","branches_url":"https://api.github.com/repos/dotnet/coreclr/branches{/branch}","tags_url":"https://api.github.com/repos/dotnet/coreclr/tags","blobs_url":"https://api.github.com/repos/dotnet/coreclr/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/dotnet/coreclr/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/dotnet/coreclr/git/refs{/sha}","trees_url":"https://api.github.com/repos/dotnet/coreclr/git/trees{/sha}","statuses_url":"https://api.github.com/repos/dotnet/coreclr/statuses/{sha}","languages_url":"https://api.github.com/repos/dotnet/coreclr/languages","stargazers_url":"https://api.github.com/repos/dotnet/coreclr/stargazers","contributors_url":"https://api.github.com/repos/dotnet/coreclr/contributors","subscribers_url":"https://api.github.com/repos/dotnet/coreclr/subscribers","subscription_url":"https://api.github.com/repos/dotnet/coreclr/subscription","commits_url":"https://api.github.com/repos/dotnet/coreclr/commits{/sha}","git_commits_url":"https://api.github.com/repos/dotnet/coreclr/git/commits{/sha}","comments_url":"https://api.github.com/repos/dotnet/coreclr/comments{/number}","issue_comment_url":"https://api.github.com/repos/dotnet/coreclr/issues/comments{/number}","contents_url":"https://api.github.com/repos/dotnet/coreclr/contents/{+path}","compare_url":"https://api.github.com/repos/dotnet/coreclr/compare/{base}...{head}","merges_url":"https://api.github.com/repos/dotnet/coreclr/merges","archive_url":"https://api.github.com/repos/dotnet/coreclr/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/dotnet/coreclr/downloads","issues_url":"https://api.github.com/repos/dotnet/coreclr/issues{/number}","pulls_url":"https://api.github.com/repos/dotnet/coreclr/pulls{/number}","milestones_url":"https://api.github.com/repos/dotnet/coreclr/milestones{/number}","notifications_url":"https://api.github.com/repos/dotnet/coreclr/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/dotnet/coreclr/labels{/name}","releases_url":"https://api.github.com/repos/dotnet/coreclr/releases{/id}","deployments_url":"https://api.github.com/repos/dotnet/coreclr/deployments","created_at":"2015-01-30T22:10:02Z","updated_at":"2016-07-31T17:56:59Z","pushed_at":"2016-08-01T00:04:49Z","git_url":"git://github.com/dotnet/coreclr.git","ssh_url":"git@github.com:dotnet/coreclr.git","clone_url":"https://github.com/dotnet/coreclr.git","svn_url":"https://github.com/dotnet/coreclr","homepage":"https://docs.microsoft.com/dotnet/","size":105049,"stargazers_count":6737,"watchers_count":6737,"language":"C#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1579,"mirror_url":null,"open_issues_count":921,"forks":1579,"open_issues":921,"watchers":6737,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/6533"},"html":{"href":"https://github.com/dotnet/coreclr/pull/6533"},"issue":{"href":"https://api.github.com/repos/dotnet/coreclr/issues/6533"},"comments":{"href":"https://api.github.com/repos/dotnet/coreclr/issues/6533/comments"},"review_comments":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/6533/comments"},"review_comment":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/dotnet/coreclr/pulls/6533/commits"},"statuses":{"href":"https://api.github.com/repos/dotnet/coreclr/statuses/6d8c82c765835947885e2f7227bf13b52d97d28d"}}}}
{"actor":{"display_login":"CarolEidt"}}