{"action":"created","comment":{"url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/comments/177463320","pull_request_review_id":107279757,"id":177463320,"diff_hunk":"@@ -0,0 +1,531 @@\n+// Copyright (c) 2018 Google LLC.\n+//\n+// Licensed under the Apache License, Version 2.0 (the \"License\");\n+// you may not use this file except in compliance with the License.\n+// You may obtain a copy of the License at\n+//\n+//     http://www.apache.org/licenses/LICENSE-2.0\n+//\n+// Unless required by applicable law or agreed to in writing, software\n+// distributed under the License is distributed on an \"AS IS\" BASIS,\n+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+// See the License for the specific language governing permissions and\n+// limitations under the License.\n+\n+#include \"opt/scalar_analysis.h\"\n+\n+#include <functional>\n+#include <map>\n+#include <memory>\n+#include <set>\n+#include <unordered_set>\n+#include <utility>\n+#include <vector>\n+\n+// Simplifies scalar analysis DAGs.\n+//\n+// 1. Given a node passed to SimplifyExpression we first simplify the graph by\n+// calling SimplifyPolynomial. This groups like nodes following basic arithmetic\n+// rules, so multiple adds of the same load instruction could be grouped into a\n+// single multiply of that instruction. SimplifyPolynomial will traverse the DAG\n+// and build up an accumulator buffer for each class of instruction it finds.\n+// For example take the loop:\n+// for (i=0, i<N; i++) { i+B+23+4+B+C; }\n+// In this example the expression \"i+B+23+4+B+C\" has four classes of\n+// instruction, induction variable i, the two value unknowns B and C, and the\n+// constants. The accumulator buffer is then used to rebuild the graph using\n+// the accumulation of each type. This example would then be folded into\n+// i+2*B+C+27.\n+//\n+// This new graph contains a single add node (or if only one type found then\n+// just that node) with each of the like terms (or multiplication node) as a\n+// child.\n+//\n+// 2. FoldRecurrentAddExpressions is then called on this new DAG. This will take\n+// RecurrentAddExpressions which are with respect to the same loop and fold them\n+// into a single new RecurrentAddExpression with respect to that same loop. An\n+// expression can have multiple RecurrentAddExpression's with respect to\n+// different loops in the case of nested loops. These expressions cannot be\n+// folded further. For example:\n+//\n+// for (i=0; i<N;i++) for(j=0,k=1; j<N;++j,++k)\n+//\n+// The 'j' and 'k' are RecurrentAddExpression with respect to the second loop\n+// and 'i' to the first. If 'j' and 'k' are used in an expression together then\n+// they will be folded into a new RecurrentAddExpression with respect to the\n+// second loop in that expression.\n+//\n+//\n+// 3. If the DAG now only contains a single RecurrentAddExpression we can now\n+// perform a final optimization SimplifyRecurrentAddExpression. This will\n+// transform the entire DAG into a RecurrentAddExpression. Additions to the\n+// RecurrentAddExpression are added to the offset field and multiplications to\n+// the coefficient.\n+//\n+\n+namespace spvtools {\n+namespace opt {\n+\n+// Implementation of the functions which are used to simplify the graph. Graphs\n+// of unknowns, multiplies, additions, and constants can be turned into a linear\n+// add node with each term as a child. For instance a large graph built from, X\n+// + X*2 + Y - Y*3 + 4 - 1, would become a single add expression with the\n+// children X*3, -Y*2, and the constant 3. Graphs containing a recurrent\n+// expression will be simplified to represent the entire graph around a single\n+// recurrent expression. So for an induction variable (i=0, i++) if you add 1 to\n+// i in an expression we can rewrite the graph of that expression to be a single\n+// recurrent expression of (i=1,i++).\n+class SENodeSimplifyImpl {\n+ public:\n+  SENodeSimplifyImpl(ScalarEvolutionAnalysis* analysis,\n+                     SENode* node_to_simplify)\n+      : analysis_(*analysis),\n+        node_(node_to_simplify),\n+        constant_accumulator_(0) {}\n+\n+  // Return the result of the simplification.\n+  SENode* Simplify();\n+\n+ private:\n+  // A reference the the analysis which requested the simplification.\n+  ScalarEvolutionAnalysis& analysis_;\n+\n+  // The node being simplified.\n+  SENode* node_;\n+\n+  // An accumulator of the net result of all the constant operations performed\n+  // in a graph.\n+  int64_t constant_accumulator_;\n+\n+  // An accumulator for each of the non constant terms in the graph.\n+  std::map<SENode*, int64_t> accumulators_;","path":"source/opt/scalar_analysis_simplification.cpp","position":101,"original_position":101,"commit_id":"e24e238199deab61dce80293128c2b38edd81939","original_commit_id":"8ad01d2a16cd584850566cf4121d9b18098bc4e5","user":{"login":"dnovillo","id":7295335,"avatar_url":"https://avatars1.githubusercontent.com/u/7295335?v=4","gravatar_id":"","url":"https://api.github.com/users/dnovillo","html_url":"https://github.com/dnovillo","followers_url":"https://api.github.com/users/dnovillo/followers","following_url":"https://api.github.com/users/dnovillo/following{/other_user}","gists_url":"https://api.github.com/users/dnovillo/gists{/gist_id}","starred_url":"https://api.github.com/users/dnovillo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dnovillo/subscriptions","organizations_url":"https://api.github.com/users/dnovillo/orgs","repos_url":"https://api.github.com/users/dnovillo/repos","events_url":"https://api.github.com/users/dnovillo/events{/privacy}","received_events_url":"https://api.github.com/users/dnovillo/received_events","type":"User","site_admin":false},"body":"Move data field members to the end of the class declaration, please.","created_at":"2018-03-27T15:14:46Z","updated_at":"2018-03-27T15:38:04Z","html_url":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400#discussion_r177463320","pull_request_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/comments/177463320"},"html":{"href":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400#discussion_r177463320"},"pull_request":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400"}}},"pull_request":{"url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400","id":174113083,"html_url":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400","diff_url":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400.diff","patch_url":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400.patch","issue_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/1400","number":1400,"state":"open","locked":false,"title":"Initial patch for scalar evolution analysis","user":{"login":"davors72","id":3385116,"avatar_url":"https://avatars0.githubusercontent.com/u/3385116?v=4","gravatar_id":"","url":"https://api.github.com/users/davors72","html_url":"https://github.com/davors72","followers_url":"https://api.github.com/users/davors72/followers","following_url":"https://api.github.com/users/davors72/following{/other_user}","gists_url":"https://api.github.com/users/davors72/gists{/gist_id}","starred_url":"https://api.github.com/users/davors72/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davors72/subscriptions","organizations_url":"https://api.github.com/users/davors72/orgs","repos_url":"https://api.github.com/users/davors72/repos","events_url":"https://api.github.com/users/davors72/events{/privacy}","received_events_url":"https://api.github.com/users/davors72/received_events","type":"User","site_admin":false},"body":"This patch adds support for the analysis of scalars in loops. It works\r\nby traversing the defuse chain to build a DAG of scalar operations and\r\nthen simplifies the DAG by folding constants and grouping like terms.\r\nIt represents induction variables as recurrent expressions with respect\r\nto a given loop and can simplify DAGs containing recurrent expression by\r\nrewritting the entire DAG to be a recurrent expression with respect to\r\nthe same loop.","created_at":"2018-03-09T21:29:07Z","updated_at":"2018-03-27T15:38:04Z","closed_at":null,"merged_at":null,"merge_commit_sha":"56716ce3a81c4ab4eafd19b3ba99370f6def52fa","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400/commits","review_comments_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400/comments","review_comment_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/comments{/number}","comments_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/1400/comments","statuses_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/statuses/e24e238199deab61dce80293128c2b38edd81939","head":{"label":"codeplaysoftware:scalar_analysis_release","ref":"scalar_analysis_release","sha":"e24e238199deab61dce80293128c2b38edd81939","user":{"login":"codeplaysoftware","id":7440916,"avatar_url":"https://avatars0.githubusercontent.com/u/7440916?v=4","gravatar_id":"","url":"https://api.github.com/users/codeplaysoftware","html_url":"https://github.com/codeplaysoftware","followers_url":"https://api.github.com/users/codeplaysoftware/followers","following_url":"https://api.github.com/users/codeplaysoftware/following{/other_user}","gists_url":"https://api.github.com/users/codeplaysoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/codeplaysoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/codeplaysoftware/subscriptions","organizations_url":"https://api.github.com/users/codeplaysoftware/orgs","repos_url":"https://api.github.com/users/codeplaysoftware/repos","events_url":"https://api.github.com/users/codeplaysoftware/events{/privacy}","received_events_url":"https://api.github.com/users/codeplaysoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":110717765,"name":"SPIRV-Tools","full_name":"codeplaysoftware/SPIRV-Tools","owner":{"login":"codeplaysoftware","id":7440916,"avatar_url":"https://avatars0.githubusercontent.com/u/7440916?v=4","gravatar_id":"","url":"https://api.github.com/users/codeplaysoftware","html_url":"https://github.com/codeplaysoftware","followers_url":"https://api.github.com/users/codeplaysoftware/followers","following_url":"https://api.github.com/users/codeplaysoftware/following{/other_user}","gists_url":"https://api.github.com/users/codeplaysoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/codeplaysoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/codeplaysoftware/subscriptions","organizations_url":"https://api.github.com/users/codeplaysoftware/orgs","repos_url":"https://api.github.com/users/codeplaysoftware/repos","events_url":"https://api.github.com/users/codeplaysoftware/events{/privacy}","received_events_url":"https://api.github.com/users/codeplaysoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/codeplaysoftware/SPIRV-Tools","description":null,"fork":true,"url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools","forks_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/forks","keys_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/teams","hooks_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/hooks","issue_events_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/issues/events{/number}","events_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/events","assignees_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/assignees{/user}","branches_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/branches{/branch}","tags_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/tags","blobs_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/git/refs{/sha}","trees_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/statuses/{sha}","languages_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/languages","stargazers_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/stargazers","contributors_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/contributors","subscribers_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/subscribers","subscription_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/subscription","commits_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/commits{/sha}","git_commits_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/git/commits{/sha}","comments_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/comments{/number}","issue_comment_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/issues/comments{/number}","contents_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/contents/{+path}","compare_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/merges","archive_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/downloads","issues_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/issues{/number}","pulls_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/pulls{/number}","milestones_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/milestones{/number}","notifications_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/labels{/name}","releases_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/releases{/id}","deployments_url":"https://api.github.com/repos/codeplaysoftware/SPIRV-Tools/deployments","created_at":"2017-11-14T16:45:53Z","updated_at":"2018-03-22T09:32:01Z","pushed_at":"2018-03-27T14:41:35Z","git_url":"git://github.com/codeplaysoftware/SPIRV-Tools.git","ssh_url":"git@github.com:codeplaysoftware/SPIRV-Tools.git","clone_url":"https://github.com/codeplaysoftware/SPIRV-Tools.git","svn_url":"https://github.com/codeplaysoftware/SPIRV-Tools","homepage":null,"size":8333,"stargazers_count":2,"watchers_count":2,"language":"C++","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":4,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":0,"open_issues":4,"watchers":2,"default_branch":"testing_master"}},"base":{"label":"KhronosGroup:master","ref":"master","sha":"c4dc04639904479f4418a86d2d1641514047bbff","user":{"login":"KhronosGroup","id":1608701,"avatar_url":"https://avatars3.githubusercontent.com/u/1608701?v=4","gravatar_id":"","url":"https://api.github.com/users/KhronosGroup","html_url":"https://github.com/KhronosGroup","followers_url":"https://api.github.com/users/KhronosGroup/followers","following_url":"https://api.github.com/users/KhronosGroup/following{/other_user}","gists_url":"https://api.github.com/users/KhronosGroup/gists{/gist_id}","starred_url":"https://api.github.com/users/KhronosGroup/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/KhronosGroup/subscriptions","organizations_url":"https://api.github.com/users/KhronosGroup/orgs","repos_url":"https://api.github.com/users/KhronosGroup/repos","events_url":"https://api.github.com/users/KhronosGroup/events{/privacy}","received_events_url":"https://api.github.com/users/KhronosGroup/received_events","type":"Organization","site_admin":false},"repo":{"id":45981801,"name":"SPIRV-Tools","full_name":"KhronosGroup/SPIRV-Tools","owner":{"login":"KhronosGroup","id":1608701,"avatar_url":"https://avatars3.githubusercontent.com/u/1608701?v=4","gravatar_id":"","url":"https://api.github.com/users/KhronosGroup","html_url":"https://github.com/KhronosGroup","followers_url":"https://api.github.com/users/KhronosGroup/followers","following_url":"https://api.github.com/users/KhronosGroup/following{/other_user}","gists_url":"https://api.github.com/users/KhronosGroup/gists{/gist_id}","starred_url":"https://api.github.com/users/KhronosGroup/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/KhronosGroup/subscriptions","organizations_url":"https://api.github.com/users/KhronosGroup/orgs","repos_url":"https://api.github.com/users/KhronosGroup/repos","events_url":"https://api.github.com/users/KhronosGroup/events{/privacy}","received_events_url":"https://api.github.com/users/KhronosGroup/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/KhronosGroup/SPIRV-Tools","description":null,"fork":false,"url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools","forks_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/forks","keys_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/teams","hooks_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/hooks","issue_events_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/events{/number}","events_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/events","assignees_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/assignees{/user}","branches_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/branches{/branch}","tags_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/tags","blobs_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/git/refs{/sha}","trees_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/statuses/{sha}","languages_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/languages","stargazers_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/stargazers","contributors_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/contributors","subscribers_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/subscribers","subscription_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/subscription","commits_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/commits{/sha}","git_commits_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/git/commits{/sha}","comments_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/comments{/number}","issue_comment_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/comments{/number}","contents_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/contents/{+path}","compare_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/merges","archive_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/downloads","issues_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues{/number}","pulls_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls{/number}","milestones_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/milestones{/number}","notifications_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/labels{/name}","releases_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/releases{/id}","deployments_url":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/deployments","created_at":"2015-11-11T12:56:25Z","updated_at":"2018-03-27T15:04:54Z","pushed_at":"2018-03-27T15:24:10Z","git_url":"git://github.com/KhronosGroup/SPIRV-Tools.git","ssh_url":"git@github.com:KhronosGroup/SPIRV-Tools.git","clone_url":"https://github.com/KhronosGroup/SPIRV-Tools.git","svn_url":"https://github.com/KhronosGroup/SPIRV-Tools","homepage":null,"size":7009,"stargazers_count":273,"watchers_count":273,"language":"C++","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":107,"mirror_url":null,"archived":false,"open_issues_count":174,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":107,"open_issues":174,"watchers":273,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400"},"html":{"href":"https://github.com/KhronosGroup/SPIRV-Tools/pull/1400"},"issue":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/1400"},"comments":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/issues/1400/comments"},"review_comments":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400/comments"},"review_comment":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/pulls/1400/commits"},"statuses":{"href":"https://api.github.com/repos/KhronosGroup/SPIRV-Tools/statuses/e24e238199deab61dce80293128c2b38edd81939"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"dnovillo"}}