{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/51813","repository_url":"https://api.github.com/repos/rust-lang/rust","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/51813/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/51813/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/51813/events","html_url":"https://github.com/rust-lang/rust/issues/51813","id":335857738,"node_id":"MDU6SXNzdWUzMzU4NTc3Mzg=","number":51813,"title":"[nll] introduce dirty list to dataflow and liveness propagation","user":{"login":"nikomatsakis","id":155238,"node_id":"MDQ6VXNlcjE1NTIzOA==","avatar_url":"https://avatars0.githubusercontent.com/u/155238?v=4","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"labels":[{"id":867466241,"node_id":"MDU6TGFiZWw4Njc0NjYyNDE=","url":"https://api.github.com/repos/rust-lang/rust/labels/NLL-performant","name":"NLL-performant","color":"f799ea","default":false},{"id":211668100,"node_id":"MDU6TGFiZWwyMTE2NjgxMDA=","url":"https://api.github.com/repos/rust-lang/rust/labels/T-compiler","name":"T-compiler","color":"bfd4f2","default":false},{"id":693557751,"node_id":"MDU6TGFiZWw2OTM1NTc3NTE=","url":"https://api.github.com/repos/rust-lang/rust/labels/WG-compiler-nll","name":"WG-compiler-nll","color":"c2e0c6","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-06-26T14:50:35Z","updated_at":"2018-06-26T15:00:53Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"I've been examining profiling results of the clap-rs test case (I am profiling the https://github.com/rust-lang/rust/pull/51538 branch, more specifically). One clear hot spot is the `do_dataflow` and `liveness_of_locals`, which account for 18% and 9% of MIR borrow check respectively. Both of them are fairly naive \"fixed point\" iterations that propagate bits around. Both could (probably) be improved by introducing a \"dirty list\" to avoid processing basic blocks whose contents have not changed.\r\n"},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/400341990","html_url":"https://github.com/rust-lang/rust/issues/51813#issuecomment-400341990","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/51813","id":400341990,"node_id":"MDEyOklzc3VlQ29tbWVudDQwMDM0MTk5MA==","user":{"login":"nikomatsakis","id":155238,"node_id":"MDQ6VXNlcjE1NTIzOA==","avatar_url":"https://avatars0.githubusercontent.com/u/155238?v=4","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"created_at":"2018-06-26T15:00:53Z","updated_at":"2018-06-26T15:00:53Z","author_association":"CONTRIBUTOR","body":"A few tips into the code to get you started. `do_dataflow` is here:\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L123-L136\r\n\r\nIt invokes [`run`](https://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L140-L145) which then [invokes `dataflow`](https://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L171):\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L77-L81\r\n\r\nThis in turn invokes `propagate`:\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L184-L194\r\n\r\nwhich calls `walk_cfg` repeatedly:\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L238\r\n\r\n`walk_cfg` just iterates over **all the basic blocks**:\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L240\r\n\r\nfor each one, it takes the current \"start point\" and applies the gen-kill sets:\r\n\r\nhttps://github.com/rust-lang/rust/blob/764232cb2a8407c72b9fea68835e686240e30ef3/src/librustc_mir/dataflow/mod.rs#L243-L247\r\n\r\nLikely, it would be more efficient to keep some kind of \"dirty bits\" indicating which basic blocks may need to be processed at all."}}
{"actor":{"display_login":"nikomatsakis"}}