{"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/comments/63300011","id":63300011,"diff_hunk":"@@ -0,0 +1,419 @@\n+use mir::repr as mir;\n+use mir::cfg::CFG;\n+use mir::repr::BasicBlock;\n+use rustc_data_structures::bitvec::BitVector;\n+\n+use mir::transform::lattice::Lattice;\n+\n+\n+pub trait DataflowPass<'tcx> {\n+    type Lattice: Lattice;\n+    type Rewrite: Rewrite<'tcx, Self::Lattice>;\n+    type Transfer: Transfer<'tcx, Self::Lattice>;\n+}\n+\n+pub trait Rewrite<'tcx, L: Lattice> {\n+    /// The rewrite function which given a statement optionally produces an alternative graph to be\n+    /// placed in place of the original statement.\n+    ///\n+    /// The 2nd BasicBlock *MUST NOT* have the terminator set.\n+    ///\n+    /// Correctness precondition:\n+    /// * transfer_stmt(statement, fact) == transfer_stmt(rewrite_stmt(statement, fact))\n+    /// that is, given some fact `fact` true before both the statement and relacement graph, and\n+    /// a fact `fact2` which is true after the statement, the same `fact2` must be true after the\n+    /// replacement graph too.\n+    fn stmt(&mir::Statement<'tcx>, &L, &mut CFG<'tcx>) -> StatementChange<'tcx>;","path":"src/librustc/mir/transform/dataflow.rs","position":26,"original_position":26,"commit_id":"ee4a7c39e84237756fd453356eaec0921356873f","original_commit_id":"ee4a7c39e84237756fd453356eaec0921356873f","user":{"login":"nagisa","id":679122,"avatar_url":"https://avatars.githubusercontent.com/u/679122?v=3","gravatar_id":"","url":"https://api.github.com/users/nagisa","html_url":"https://github.com/nagisa","followers_url":"https://api.github.com/users/nagisa/followers","following_url":"https://api.github.com/users/nagisa/following{/other_user}","gists_url":"https://api.github.com/users/nagisa/gists{/gist_id}","starred_url":"https://api.github.com/users/nagisa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nagisa/subscriptions","organizations_url":"https://api.github.com/users/nagisa/orgs","repos_url":"https://api.github.com/users/nagisa/repos","events_url":"https://api.github.com/users/nagisa/events{/privacy}","received_events_url":"https://api.github.com/users/nagisa/received_events","type":"User","site_admin":false},"body":"Noted.","created_at":"2016-05-15T23:26:31Z","updated_at":"2016-05-15T23:26:31Z","html_url":"https://github.com/rust-lang/rust/pull/33628#discussion_r63300011","pull_request_url":"https://api.github.com/repos/rust-lang/rust/pulls/33628","_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments/63300011"},"html":{"href":"https://github.com/rust-lang/rust/pull/33628#discussion_r63300011"},"pull_request":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/33628"}}},"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/33628","id":70076614,"html_url":"https://github.com/rust-lang/rust/pull/33628","diff_url":"https://github.com/rust-lang/rust/pull/33628.diff","patch_url":"https://github.com/rust-lang/rust/pull/33628.patch","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/33628","number":33628,"state":"open","locked":false,"title":"[WIP][MIR] Generic lattice-based DF framework","user":{"login":"nagisa","id":679122,"avatar_url":"https://avatars.githubusercontent.com/u/679122?v=3","gravatar_id":"","url":"https://api.github.com/users/nagisa","html_url":"https://github.com/nagisa","followers_url":"https://api.github.com/users/nagisa/followers","following_url":"https://api.github.com/users/nagisa/following{/other_user}","gists_url":"https://api.github.com/users/nagisa/gists{/gist_id}","starred_url":"https://api.github.com/users/nagisa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nagisa/subscriptions","organizations_url":"https://api.github.com/users/nagisa/orgs","repos_url":"https://api.github.com/users/nagisa/repos","events_url":"https://api.github.com/users/nagisa/events{/privacy}","received_events_url":"https://api.github.com/users/nagisa/received_events","type":"User","site_admin":false},"body":"This PR at its current state has only the implementation of forward dataflow analysis and a accompanying alias-constant-simplify propagation pass.\r\n\r\nThe lattice-based dataflow framework is greatly inspired by the [Hoopl](https://github.com/haskell/hoopl) and its [paper](http://research.microsoft.com/en-us/um/people/simonpj/Papers/c--/hoopl-haskell10.pdf). The framework besides just being yet another dataflow engine allows for interleaving transformations and analysis + composition of the passes. These are something the gen-kill-set-based dataflow engines aren’t quite suited for. Those features are showcased by the accompanying ACS pass and without them the ACS pass wouldn‘t be otherwise possible (at least not within 200 lines).\r\n\r\nSome notes: this is not yet complete: I expect to expand the framework to gain some more useful combinators (or at least those described in the paper) as well as some more other niceties to simplify production of dataflow-reliant passes and backwards analysis capabilities and so on and on.\r\n\r\nSome results:\r\n\r\nFor following pieces of code this MIR (with dead variables removed by yours truly) gets produced:\r\n\r\n```\r\nfn a(x: (bool, bool)) -> u32{\r\n    let z = x.0;\r\n    let v = x.1;\r\n    let y = if z || v {\r\n        10\r\n    } else {\r\n        20\r\n    };\r\n    y\r\n}\r\n```\r\n\r\n```\r\nfn a(arg0: (bool, bool)) -> u32 {\r\n    let var0: (bool, bool); // x in Scope(1) at test.rs:1:6: 1:7\r\n    let var1: bool; // z in Scope(3) at test.rs:2:9: 2:10\r\n    let var2: bool; // v in Scope(7) at test.rs:3:9: 3:10\r\n    let var3: u32; // y in Scope(11) at test.rs:4:9: 4:10\r\n    let mut tmp0: bool;\r\n    let mut tmp1: bool;\r\n    let mut tmp2: bool;\r\n    let mut tmp3: bool;\r\n    let mut tmp4: bool;\r\n    let mut tmp5: u32;\r\n\r\n    bb0: {\r\n        if((arg0.0: bool)) -> [true: bb1, false: bb3]; // Scope(14) at test.rs:4:16: 4:22\r\n    }\r\n\r\n    bb1: {\r\n        goto -> bb4; // Scope(14) at test.rs:4:16: 4:22\r\n    }\r\n\r\n    bb2: {\r\n        goto -> bb4; // Scope(14) at test.rs:4:16: 4:22\r\n    }\r\n\r\n    bb3: {\r\n        if((arg0.1: bool)) -> [true: bb1, false: bb2]; // Scope(14) at test.rs:4:16: 4:22\r\n    }\r\n\r\n    bb4: {\r\n        if(tmp2) -> [true: bb5, false: bb6]; // Scope(13) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb5: {\r\n        var3 = const 10u32; // Scope(19) at test.rs:5:9: 5:11\r\n        goto -> bb7; // Scope(13) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb6: {\r\n        var3 = const 20u32; // Scope(23) at test.rs:7:9: 7:11\r\n        goto -> bb7; // Scope(13) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb7: {\r\n        return = var3; // Scope(24) at test.rs:9:5: 9:6\r\n        goto -> bb8; // Scope(0) at test.rs:1:1: 10:2\r\n    }\r\n\r\n    bb8: {\r\n        return; // Scope(0) at test.rs:1:1: 10:2\r\n    }\r\n```\r\n\r\n```rust\r\nfn a() -> u32{\r\n    let x = false;\r\n    let z = x;\r\n    let y = if z {\r\n        10\r\n    } else {\r\n        10\r\n    };\r\n    y\r\n}\r\n```\r\n\r\n```\r\nfn a() -> u32 {\r\n    let var0: bool; // x in Scope(3) at test.rs:2:9: 2:10\r\n    let var1: bool; // z in Scope(6) at test.rs:3:9: 3:10\r\n    let var2: u32; // y in Scope(9) at test.rs:4:9: 4:10\r\n    let mut tmp0: bool;\r\n    let mut tmp1: bool;\r\n    let mut tmp2: u32;\r\n\r\n    bb0: {\r\n        goto -> bb2; // Scope(11) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb1: {\r\n        var2 = const 10u32; // Scope(14) at test.rs:5:9: 5:11\r\n        goto -> bb3; // Scope(11) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb2: {\r\n        goto -> bb3; // Scope(11) at test.rs:4:13: 8:6\r\n    }\r\n\r\n    bb3: {\r\n        return = const 10u32; // Scope(19) at test.rs:9:5: 9:6\r\n        goto -> bb4; // Scope(0) at test.rs:1:1: 10:2\r\n    }\r\n\r\n    bb4: {\r\n        return; // Scope(0) at test.rs:1:1: 10:2\r\n    }\r\n}\r\n```","created_at":"2016-05-14T00:55:48Z","updated_at":"2016-05-15T23:26:31Z","closed_at":null,"merged_at":null,"merge_commit_sha":"36db32090729e1561fdfe590ea794a03ce1968eb","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/rust-lang/rust/pulls/33628/commits","review_comments_url":"https://api.github.com/repos/rust-lang/rust/pulls/33628/comments","review_comment_url":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/33628/comments","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/ee4a7c39e84237756fd453356eaec0921356873f","head":{"label":"nagisa:mir-dflow","ref":"mir-dflow","sha":"ee4a7c39e84237756fd453356eaec0921356873f","user":{"login":"nagisa","id":679122,"avatar_url":"https://avatars.githubusercontent.com/u/679122?v=3","gravatar_id":"","url":"https://api.github.com/users/nagisa","html_url":"https://github.com/nagisa","followers_url":"https://api.github.com/users/nagisa/followers","following_url":"https://api.github.com/users/nagisa/following{/other_user}","gists_url":"https://api.github.com/users/nagisa/gists{/gist_id}","starred_url":"https://api.github.com/users/nagisa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nagisa/subscriptions","organizations_url":"https://api.github.com/users/nagisa/orgs","repos_url":"https://api.github.com/users/nagisa/repos","events_url":"https://api.github.com/users/nagisa/events{/privacy}","received_events_url":"https://api.github.com/users/nagisa/received_events","type":"User","site_admin":false},"repo":{"id":28332501,"name":"rust","full_name":"nagisa/rust","owner":{"login":"nagisa","id":679122,"avatar_url":"https://avatars.githubusercontent.com/u/679122?v=3","gravatar_id":"","url":"https://api.github.com/users/nagisa","html_url":"https://github.com/nagisa","followers_url":"https://api.github.com/users/nagisa/followers","following_url":"https://api.github.com/users/nagisa/following{/other_user}","gists_url":"https://api.github.com/users/nagisa/gists{/gist_id}","starred_url":"https://api.github.com/users/nagisa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nagisa/subscriptions","organizations_url":"https://api.github.com/users/nagisa/orgs","repos_url":"https://api.github.com/users/nagisa/repos","events_url":"https://api.github.com/users/nagisa/events{/privacy}","received_events_url":"https://api.github.com/users/nagisa/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/nagisa/rust","description":"a safe, concurrent, practical language","fork":true,"url":"https://api.github.com/repos/nagisa/rust","forks_url":"https://api.github.com/repos/nagisa/rust/forks","keys_url":"https://api.github.com/repos/nagisa/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nagisa/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nagisa/rust/teams","hooks_url":"https://api.github.com/repos/nagisa/rust/hooks","issue_events_url":"https://api.github.com/repos/nagisa/rust/issues/events{/number}","events_url":"https://api.github.com/repos/nagisa/rust/events","assignees_url":"https://api.github.com/repos/nagisa/rust/assignees{/user}","branches_url":"https://api.github.com/repos/nagisa/rust/branches{/branch}","tags_url":"https://api.github.com/repos/nagisa/rust/tags","blobs_url":"https://api.github.com/repos/nagisa/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nagisa/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nagisa/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/nagisa/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nagisa/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/nagisa/rust/languages","stargazers_url":"https://api.github.com/repos/nagisa/rust/stargazers","contributors_url":"https://api.github.com/repos/nagisa/rust/contributors","subscribers_url":"https://api.github.com/repos/nagisa/rust/subscribers","subscription_url":"https://api.github.com/repos/nagisa/rust/subscription","commits_url":"https://api.github.com/repos/nagisa/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/nagisa/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/nagisa/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/nagisa/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/nagisa/rust/contents/{+path}","compare_url":"https://api.github.com/repos/nagisa/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nagisa/rust/merges","archive_url":"https://api.github.com/repos/nagisa/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nagisa/rust/downloads","issues_url":"https://api.github.com/repos/nagisa/rust/issues{/number}","pulls_url":"https://api.github.com/repos/nagisa/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/nagisa/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/nagisa/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nagisa/rust/labels{/name}","releases_url":"https://api.github.com/repos/nagisa/rust/releases{/id}","deployments_url":"https://api.github.com/repos/nagisa/rust/deployments","created_at":"2014-12-22T09:30:51Z","updated_at":"2015-01-13T13:18:02Z","pushed_at":"2016-05-14T00:33:16Z","git_url":"git://github.com/nagisa/rust.git","ssh_url":"git@github.com:nagisa/rust.git","clone_url":"https://github.com/nagisa/rust.git","svn_url":"https://github.com/nagisa/rust","homepage":"http://www.rust-lang.org","size":291720,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":false,"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":"rust-lang:master","ref":"master","sha":"33a5c9dfd106e2f900aba7074f10b5e8e617be7b","user":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":724712,"name":"rust","full_name":"rust-lang/rust","owner":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/rust-lang/rust","description":"A safe, concurrent, practical language.","fork":false,"url":"https://api.github.com/repos/rust-lang/rust","forks_url":"https://api.github.com/repos/rust-lang/rust/forks","keys_url":"https://api.github.com/repos/rust-lang/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-lang/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-lang/rust/teams","hooks_url":"https://api.github.com/repos/rust-lang/rust/hooks","issue_events_url":"https://api.github.com/repos/rust-lang/rust/issues/events{/number}","events_url":"https://api.github.com/repos/rust-lang/rust/events","assignees_url":"https://api.github.com/repos/rust-lang/rust/assignees{/user}","branches_url":"https://api.github.com/repos/rust-lang/rust/branches{/branch}","tags_url":"https://api.github.com/repos/rust-lang/rust/tags","blobs_url":"https://api.github.com/repos/rust-lang/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-lang/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-lang/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-lang/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-lang/rust/languages","stargazers_url":"https://api.github.com/repos/rust-lang/rust/stargazers","contributors_url":"https://api.github.com/repos/rust-lang/rust/contributors","subscribers_url":"https://api.github.com/repos/rust-lang/rust/subscribers","subscription_url":"https://api.github.com/repos/rust-lang/rust/subscription","commits_url":"https://api.github.com/repos/rust-lang/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-lang/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-lang/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-lang/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/rust-lang/rust/contents/{+path}","compare_url":"https://api.github.com/repos/rust-lang/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-lang/rust/merges","archive_url":"https://api.github.com/repos/rust-lang/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-lang/rust/downloads","issues_url":"https://api.github.com/repos/rust-lang/rust/issues{/number}","pulls_url":"https://api.github.com/repos/rust-lang/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-lang/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-lang/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-lang/rust/labels{/name}","releases_url":"https://api.github.com/repos/rust-lang/rust/releases{/id}","deployments_url":"https://api.github.com/repos/rust-lang/rust/deployments","created_at":"2010-06-16T20:39:03Z","updated_at":"2016-05-15T21:50:06Z","pushed_at":"2016-05-15T23:00:22Z","git_url":"git://github.com/rust-lang/rust.git","ssh_url":"git@github.com:rust-lang/rust.git","clone_url":"https://github.com/rust-lang/rust.git","svn_url":"https://github.com/rust-lang/rust","homepage":"http://www.rust-lang.org","size":492880,"stargazers_count":16672,"watchers_count":16672,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":3183,"mirror_url":null,"open_issues_count":2513,"forks":3183,"open_issues":2513,"watchers":16672,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/33628"},"html":{"href":"https://github.com/rust-lang/rust/pull/33628"},"issue":{"href":"https://api.github.com/repos/rust-lang/rust/issues/33628"},"comments":{"href":"https://api.github.com/repos/rust-lang/rust/issues/33628/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/33628/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/33628/commits"},"statuses":{"href":"https://api.github.com/repos/rust-lang/rust/statuses/ee4a7c39e84237756fd453356eaec0921356873f"}}}}