{"action":"created","comment":{"url":"https://api.github.com/repos/apple/swift/pulls/comments/203606601","pull_request_review_id":138528112,"id":203606601,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIwMzYwNjYwMQ==","diff_hunk":"@@ -405,6 +412,313 @@ bool ADContext::supportsFloatingPointDifferentiation(Type type) const {\n   return fpConf.hasValue();\n }\n \n+//===----------------------------------------------------------------------===//\n+// Control flow canonicalization\n+//===----------------------------------------------------------------------===//\n+\n+namespace {\n+class ControlFlowCanonicalization {\n+private:\n+  SILFunction &function;\n+  SILBuilder builder = SILBuilder(function);\n+  DominanceInfo &domInfo;\n+  SILLoopInfo &loopInfo;\n+\n+public:\n+  explicit ControlFlowCanonicalization(SILFunction &function,\n+                                       DominanceInfo &domInfo,\n+                                       SILLoopInfo &loopInfo)\n+    : function(function), domInfo(domInfo), loopInfo(loopInfo) {}\n+\n+  /// Run control flow canonicalization on the function.\n+  bool run();\n+};\n+}\n+\n+bool ControlFlowCanonicalization::run() {\n+  DEBUG(getDebugStream() << \"Running control flow canonicalization on function \"\n+        << function.getName() << '\\n');\n+  bool changed = false;\n+  assert(!function.isNoReturnFunction() && !function.isExternalDeclaration());\n+  assert(function.findReturnBB().getNodePtr());\n+  // Canonicalize loops.\n+  canonicalizeAllLoops(&domInfo, &loopInfo);\n+  // TODO: Handle multiple loop exits.\n+  return changed;\n+}\n+\n+//===----------------------------------------------------------------------===//\n+// Activity Analysis\n+//===----------------------------------------------------------------------===//\n+\n+/// In many real situations, the end-users of AD need only the derivatives of\n+/// some selected outputs of `P` with respect to some selected inputs of `P`.\n+/// Whatever the differentiation mode (tangent, reverse,...), these restrictions\n+/// allow the AD tool to produce a much more efficient differentiated program.\n+/// Essentially, fixing some inputs and neglecting some outputs allows AD to\n+/// just forget about several intermediate differentiated variables.\n+///\n+/// Activity analysis is the specific analysis that detects these situations,\n+/// therefore allowing for a better differentiated code. Activity analysis is\n+/// present in all transformation-based AD tools.\n+///\n+/// To begin with, the end-user specifies that only some output variables (the\n+/// “dependent”) must be differentiated with respect to only some input\n+/// variables (the “independent”). We say that variable `y` depends on `x` when\n+/// the derivative of `y` with respect to `x` is not trivially null. We say that\n+/// a variable is “varied” if it depends on at least one independent. Conversely\n+/// we say that a variable is “useful” if at least one dependent depends on it.\n+/// Finally, we say that a variable is “active” if it is at the same time varied\n+/// and useful. In the special case of the tangent mode, it is easy to check\n+/// that when variable `v` is not varied at some place in the program, then its\n+/// derivative `v̇` at this place is certainly null. Conversely when variable `v`\n+/// is not useful, then whatever the value of `v̇`, this value does not matter\n+/// for the final result. Symmetric reasoning applies for the reverse mode of\n+/// AD: observing that differentiated variables go upstream, we see that a\n+/// useless variable has a null derivative, in other words the partial\n+/// derivative of the output with respect to this variable is null. Conversely\n+/// when variable `v` is not varied, then whatever the value of `v`, this value\n+/// does not matter for the final result.\n+///\n+/// Reference:\n+/// Laurent Hascoët. Automatic Differentiation by Program Transformation. 2017.\n+\n+namespace {\n+\n+class DifferentiableActivityInfo;\n+\n+class DifferentiableActivityAnalysis\n+  : public FunctionAnalysisBase<DifferentiableActivityInfo> {\n+private:\n+  DominanceAnalysis *dominanceAnalysis = nullptr;\n+\n+public:\n+  explicit DifferentiableActivityAnalysis()\n+    : FunctionAnalysisBase(AnalysisKind::DifferentiableActivity) {}\n+\n+  static bool classof(const SILAnalysis *s) {\n+    return s->getKind() == AnalysisKind::DifferentiableActivity;\n+  }\n+\n+  virtual bool shouldInvalidate(SILAnalysis::InvalidationKind k) override {\n+    return k & InvalidationKind::Everything;\n+  }\n+\n+  virtual\n+  DifferentiableActivityInfo *newFunctionAnalysis(SILFunction *f) override;\n+\n+  virtual void initialize(SILPassManager *pm) override;\n+};\n+\n+class DifferentiableActivityInfo {","path":"lib/SILOptimizer/Mandatory/TFDifferentiation.cpp","position":139,"original_position":139,"commit_id":"f4b31b9e167a065dc07e01edcb4663365810cfd3","original_commit_id":"f4b31b9e167a065dc07e01edcb4663365810cfd3","user":{"login":"lattner","id":15152540,"node_id":"MDQ6VXNlcjE1MTUyNTQw","avatar_url":"https://avatars0.githubusercontent.com/u/15152540?v=4","gravatar_id":"","url":"https://api.github.com/users/lattner","html_url":"https://github.com/lattner","followers_url":"https://api.github.com/users/lattner/followers","following_url":"https://api.github.com/users/lattner/following{/other_user}","gists_url":"https://api.github.com/users/lattner/gists{/gist_id}","starred_url":"https://api.github.com/users/lattner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lattner/subscriptions","organizations_url":"https://api.github.com/users/lattner/orgs","repos_url":"https://api.github.com/users/lattner/repos","events_url":"https://api.github.com/users/lattner/events{/privacy}","received_events_url":"https://api.github.com/users/lattner/received_events","type":"User","site_admin":false},"body":"Please add a doc comment even if short.  Please shrink wrap the anonymous namespace around the classes, in accordance to llvm.org/docs/CodingStandards.html","created_at":"2018-07-19T05:38:43Z","updated_at":"2018-07-19T05:38:43Z","html_url":"https://github.com/apple/swift/pull/18047#discussion_r203606601","pull_request_url":"https://api.github.com/repos/apple/swift/pulls/18047","author_association":"COLLABORATOR","_links":{"self":{"href":"https://api.github.com/repos/apple/swift/pulls/comments/203606601"},"html":{"href":"https://github.com/apple/swift/pull/18047#discussion_r203606601"},"pull_request":{"href":"https://api.github.com/repos/apple/swift/pulls/18047"}}},"pull_request":{"url":"https://api.github.com/repos/apple/swift/pulls/18047","id":202346267,"node_id":"MDExOlB1bGxSZXF1ZXN0MjAyMzQ2MjY3","html_url":"https://github.com/apple/swift/pull/18047","diff_url":"https://github.com/apple/swift/pull/18047.diff","patch_url":"https://github.com/apple/swift/pull/18047.patch","issue_url":"https://api.github.com/repos/apple/swift/issues/18047","number":18047,"state":"closed","locked":false,"title":"[AutoDiff] Part 2: Add differentiable activity analysis and entry point of control flow canonicalization","user":{"login":"rxwei","id":856507,"node_id":"MDQ6VXNlcjg1NjUwNw==","avatar_url":"https://avatars0.githubusercontent.com/u/856507?v=4","gravatar_id":"","url":"https://api.github.com/users/rxwei","html_url":"https://github.com/rxwei","followers_url":"https://api.github.com/users/rxwei/followers","following_url":"https://api.github.com/users/rxwei/following{/other_user}","gists_url":"https://api.github.com/users/rxwei/gists{/gist_id}","starred_url":"https://api.github.com/users/rxwei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rxwei/subscriptions","organizations_url":"https://api.github.com/users/rxwei/orgs","repos_url":"https://api.github.com/users/rxwei/repos","events_url":"https://api.github.com/users/rxwei/events{/privacy}","received_events_url":"https://api.github.com/users/rxwei/received_events","type":"User","site_admin":false},"body":"Activity analysis helps AD figure out the result indices and parameter indices for a nested differentiation task. For example:\r\n\r\n```swift\r\nfunc bar(x: Float) {\r\n  let (a, b, c) = foo(x, 0, 1)\r\n  return b\r\n}\r\n\r\n#gradient(bar)\r\n```\r\n\r\nDuring automatic differentiation, we only need the partial derivative of dependent variable `b` with respect to independent variable `x`, that is, to reverse-differentiate `foo` from the second result with respect to the first parameter. Activity analysis is a simple data flow analysis that tells what variables (in the SIL case, SSA values) are \"varied\" with respect to independent variables, and what are \"useful\" for the output of a function.\r\n\r\nThe [relevant literature](https://www-sop.inria.fr/tropics/papers/supportCoursDA.pdf) is not using SSA form, so we twisted the definition a little bit.\r\n\r\n**Note**: This is going to produce a bunch of unused warnings, but I'm merging other bits of #17901  asap.","created_at":"2018-07-18T18:49:38Z","updated_at":"2018-07-19T05:38:43Z","closed_at":"2018-07-18T21:07:26Z","merged_at":"2018-07-18T21:07:26Z","merge_commit_sha":"0fffa5462ee4c8585fb5716b2f62583357213411","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":955546636,"node_id":"MDU6TGFiZWw5NTU1NDY2MzY=","url":"https://api.github.com/repos/apple/swift/labels/tensorflow","name":"tensorflow","color":"EF6C00","default":false}],"milestone":null,"commits_url":"https://api.github.com/repos/apple/swift/pulls/18047/commits","review_comments_url":"https://api.github.com/repos/apple/swift/pulls/18047/comments","review_comment_url":"https://api.github.com/repos/apple/swift/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apple/swift/issues/18047/comments","statuses_url":"https://api.github.com/repos/apple/swift/statuses/f4b31b9e167a065dc07e01edcb4663365810cfd3","head":{"label":"rxwei:autodiff","ref":"autodiff","sha":"f4b31b9e167a065dc07e01edcb4663365810cfd3","user":{"login":"rxwei","id":856507,"node_id":"MDQ6VXNlcjg1NjUwNw==","avatar_url":"https://avatars0.githubusercontent.com/u/856507?v=4","gravatar_id":"","url":"https://api.github.com/users/rxwei","html_url":"https://github.com/rxwei","followers_url":"https://api.github.com/users/rxwei/followers","following_url":"https://api.github.com/users/rxwei/following{/other_user}","gists_url":"https://api.github.com/users/rxwei/gists{/gist_id}","starred_url":"https://api.github.com/users/rxwei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rxwei/subscriptions","organizations_url":"https://api.github.com/users/rxwei/orgs","repos_url":"https://api.github.com/users/rxwei/repos","events_url":"https://api.github.com/users/rxwei/events{/privacy}","received_events_url":"https://api.github.com/users/rxwei/received_events","type":"User","site_admin":false},"repo":{"id":136226896,"node_id":"MDEwOlJlcG9zaXRvcnkxMzYyMjY4OTY=","name":"swift","full_name":"rxwei/swift","owner":{"login":"rxwei","id":856507,"node_id":"MDQ6VXNlcjg1NjUwNw==","avatar_url":"https://avatars0.githubusercontent.com/u/856507?v=4","gravatar_id":"","url":"https://api.github.com/users/rxwei","html_url":"https://github.com/rxwei","followers_url":"https://api.github.com/users/rxwei/followers","following_url":"https://api.github.com/users/rxwei/following{/other_user}","gists_url":"https://api.github.com/users/rxwei/gists{/gist_id}","starred_url":"https://api.github.com/users/rxwei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rxwei/subscriptions","organizations_url":"https://api.github.com/users/rxwei/orgs","repos_url":"https://api.github.com/users/rxwei/repos","events_url":"https://api.github.com/users/rxwei/events{/privacy}","received_events_url":"https://api.github.com/users/rxwei/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/rxwei/swift","description":"The Swift Programming Language","fork":true,"url":"https://api.github.com/repos/rxwei/swift","forks_url":"https://api.github.com/repos/rxwei/swift/forks","keys_url":"https://api.github.com/repos/rxwei/swift/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rxwei/swift/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rxwei/swift/teams","hooks_url":"https://api.github.com/repos/rxwei/swift/hooks","issue_events_url":"https://api.github.com/repos/rxwei/swift/issues/events{/number}","events_url":"https://api.github.com/repos/rxwei/swift/events","assignees_url":"https://api.github.com/repos/rxwei/swift/assignees{/user}","branches_url":"https://api.github.com/repos/rxwei/swift/branches{/branch}","tags_url":"https://api.github.com/repos/rxwei/swift/tags","blobs_url":"https://api.github.com/repos/rxwei/swift/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rxwei/swift/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rxwei/swift/git/refs{/sha}","trees_url":"https://api.github.com/repos/rxwei/swift/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rxwei/swift/statuses/{sha}","languages_url":"https://api.github.com/repos/rxwei/swift/languages","stargazers_url":"https://api.github.com/repos/rxwei/swift/stargazers","contributors_url":"https://api.github.com/repos/rxwei/swift/contributors","subscribers_url":"https://api.github.com/repos/rxwei/swift/subscribers","subscription_url":"https://api.github.com/repos/rxwei/swift/subscription","commits_url":"https://api.github.com/repos/rxwei/swift/commits{/sha}","git_commits_url":"https://api.github.com/repos/rxwei/swift/git/commits{/sha}","comments_url":"https://api.github.com/repos/rxwei/swift/comments{/number}","issue_comment_url":"https://api.github.com/repos/rxwei/swift/issues/comments{/number}","contents_url":"https://api.github.com/repos/rxwei/swift/contents/{+path}","compare_url":"https://api.github.com/repos/rxwei/swift/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rxwei/swift/merges","archive_url":"https://api.github.com/repos/rxwei/swift/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rxwei/swift/downloads","issues_url":"https://api.github.com/repos/rxwei/swift/issues{/number}","pulls_url":"https://api.github.com/repos/rxwei/swift/pulls{/number}","milestones_url":"https://api.github.com/repos/rxwei/swift/milestones{/number}","notifications_url":"https://api.github.com/repos/rxwei/swift/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rxwei/swift/labels{/name}","releases_url":"https://api.github.com/repos/rxwei/swift/releases{/id}","deployments_url":"https://api.github.com/repos/rxwei/swift/deployments","created_at":"2018-06-05T19:45:30Z","updated_at":"2018-06-26T07:17:36Z","pushed_at":"2018-07-19T00:32:10Z","git_url":"git://github.com/rxwei/swift.git","ssh_url":"git@github.com:rxwei/swift.git","clone_url":"https://github.com/rxwei/swift.git","svn_url":"https://github.com/rxwei/swift","homepage":"https://swift.org/","size":310781,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":0,"open_issues":0,"watchers":0,"default_branch":"tensorflow"}},"base":{"label":"apple:tensorflow","ref":"tensorflow","sha":"9842edcf191720ade2d3730e98e3c6a9b2647915","user":{"login":"apple","id":10639145,"node_id":"MDEyOk9yZ2FuaXphdGlvbjEwNjM5MTQ1","avatar_url":"https://avatars0.githubusercontent.com/u/10639145?v=4","gravatar_id":"","url":"https://api.github.com/users/apple","html_url":"https://github.com/apple","followers_url":"https://api.github.com/users/apple/followers","following_url":"https://api.github.com/users/apple/following{/other_user}","gists_url":"https://api.github.com/users/apple/gists{/gist_id}","starred_url":"https://api.github.com/users/apple/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apple/subscriptions","organizations_url":"https://api.github.com/users/apple/orgs","repos_url":"https://api.github.com/users/apple/repos","events_url":"https://api.github.com/users/apple/events{/privacy}","received_events_url":"https://api.github.com/users/apple/received_events","type":"Organization","site_admin":false},"repo":{"id":44838949,"node_id":"MDEwOlJlcG9zaXRvcnk0NDgzODk0OQ==","name":"swift","full_name":"apple/swift","owner":{"login":"apple","id":10639145,"node_id":"MDEyOk9yZ2FuaXphdGlvbjEwNjM5MTQ1","avatar_url":"https://avatars0.githubusercontent.com/u/10639145?v=4","gravatar_id":"","url":"https://api.github.com/users/apple","html_url":"https://github.com/apple","followers_url":"https://api.github.com/users/apple/followers","following_url":"https://api.github.com/users/apple/following{/other_user}","gists_url":"https://api.github.com/users/apple/gists{/gist_id}","starred_url":"https://api.github.com/users/apple/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apple/subscriptions","organizations_url":"https://api.github.com/users/apple/orgs","repos_url":"https://api.github.com/users/apple/repos","events_url":"https://api.github.com/users/apple/events{/privacy}","received_events_url":"https://api.github.com/users/apple/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apple/swift","description":"The Swift Programming Language","fork":false,"url":"https://api.github.com/repos/apple/swift","forks_url":"https://api.github.com/repos/apple/swift/forks","keys_url":"https://api.github.com/repos/apple/swift/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apple/swift/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apple/swift/teams","hooks_url":"https://api.github.com/repos/apple/swift/hooks","issue_events_url":"https://api.github.com/repos/apple/swift/issues/events{/number}","events_url":"https://api.github.com/repos/apple/swift/events","assignees_url":"https://api.github.com/repos/apple/swift/assignees{/user}","branches_url":"https://api.github.com/repos/apple/swift/branches{/branch}","tags_url":"https://api.github.com/repos/apple/swift/tags","blobs_url":"https://api.github.com/repos/apple/swift/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apple/swift/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apple/swift/git/refs{/sha}","trees_url":"https://api.github.com/repos/apple/swift/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apple/swift/statuses/{sha}","languages_url":"https://api.github.com/repos/apple/swift/languages","stargazers_url":"https://api.github.com/repos/apple/swift/stargazers","contributors_url":"https://api.github.com/repos/apple/swift/contributors","subscribers_url":"https://api.github.com/repos/apple/swift/subscribers","subscription_url":"https://api.github.com/repos/apple/swift/subscription","commits_url":"https://api.github.com/repos/apple/swift/commits{/sha}","git_commits_url":"https://api.github.com/repos/apple/swift/git/commits{/sha}","comments_url":"https://api.github.com/repos/apple/swift/comments{/number}","issue_comment_url":"https://api.github.com/repos/apple/swift/issues/comments{/number}","contents_url":"https://api.github.com/repos/apple/swift/contents/{+path}","compare_url":"https://api.github.com/repos/apple/swift/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apple/swift/merges","archive_url":"https://api.github.com/repos/apple/swift/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apple/swift/downloads","issues_url":"https://api.github.com/repos/apple/swift/issues{/number}","pulls_url":"https://api.github.com/repos/apple/swift/pulls{/number}","milestones_url":"https://api.github.com/repos/apple/swift/milestones{/number}","notifications_url":"https://api.github.com/repos/apple/swift/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apple/swift/labels{/name}","releases_url":"https://api.github.com/repos/apple/swift/releases{/id}","deployments_url":"https://api.github.com/repos/apple/swift/deployments","created_at":"2015-10-23T21:15:07Z","updated_at":"2018-07-19T04:26:18Z","pushed_at":"2018-07-19T05:35:55Z","git_url":"git://github.com/apple/swift.git","ssh_url":"git@github.com:apple/swift.git","clone_url":"https://github.com/apple/swift.git","svn_url":"https://github.com/apple/swift","homepage":"https://swift.org/","size":312488,"stargazers_count":44581,"watchers_count":44581,"language":"C++","has_issues":false,"has_projects":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":7034,"mirror_url":null,"archived":false,"open_issues_count":366,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":7034,"open_issues":366,"watchers":44581,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apple/swift/pulls/18047"},"html":{"href":"https://github.com/apple/swift/pull/18047"},"issue":{"href":"https://api.github.com/repos/apple/swift/issues/18047"},"comments":{"href":"https://api.github.com/repos/apple/swift/issues/18047/comments"},"review_comments":{"href":"https://api.github.com/repos/apple/swift/pulls/18047/comments"},"review_comment":{"href":"https://api.github.com/repos/apple/swift/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apple/swift/pulls/18047/commits"},"statuses":{"href":"https://api.github.com/repos/apple/swift/statuses/f4b31b9e167a065dc07e01edcb4663365810cfd3"}},"author_association":"COLLABORATOR"}}
{"actor":{"display_login":"lattner"}}