On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi Jakub, > > thanks for the update. I was already eagerly waiting to hear what your > internship on dominance brings. I think the numbers are already very > encouraging and I believe moving incrementally over to the new algorithm > is exactly the right approach. > > I have a couple of questions: > > 1) Daniel and Chandler have for a long time been talking about computing > dominance and post-dominance in one shot to reduce the cost of > post-dominance and make it (freely) available everywhere. Is this > covered by your current (or planned) work? >I think chandler more than me. If me, assume I was wrong :P I believe you can prove it is not possible to do this without doing all the work of the separate passes. The main cost is the DFS walk, and you can't do an undirected DFS that will work here. I believe related things have even been proven to show the brokenness of various algorithms. See https://hal.inria.fr/hal-00761505 section 4.1 Given the difficulties and subtleties here, I would consider any such approach that tried to share work between the passes as "fraught with peril" -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170613/7e634774/attachment.html>
On Tue, Jun 13, 2017, at 08:29 PM, Daniel Berlin via llvm-dev wrote:> On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > > > Hi Jakub, > > > > thanks for the update. I was already eagerly waiting to hear what your > > internship on dominance brings. I think the numbers are already very > > encouraging and I believe moving incrementally over to the new algorithm > > is exactly the right approach. > > > > I have a couple of questions: > > > > 1) Daniel and Chandler have for a long time been talking about computing > > dominance and post-dominance in one shot to reduce the cost of > > post-dominance and make it (freely) available everywhere. Is this > > covered by your current (or planned) work? > > > > I think chandler more than me. If me, assume I was wrong :P > > > I believe you can prove it is not possible to do this without doing all > the work of the separate passes. The main cost is the DFS walk, and you > can't do an undirected DFS that will work here. > I believe related things have even been proven to show the brokenness of > various algorithms.Alright. This sounds to be more in line with what I expected. Thanks for clarifying. Best, Tobias> See https://hal.inria.fr/hal-00761505 section 4.1 > > Given the difficulties and subtleties here, I would consider any such > approach that tried to share work between the passes as "fraught with > peril" > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
On 06/13/2017 01:29 PM, Daniel Berlin via llvm-dev wrote:> > > On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev > <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > Hi Jakub, > > thanks for the update. I was already eagerly waiting to hear what your > internship on dominance brings. I think the numbers are already very > encouraging and I believe moving incrementally over to the new > algorithm > is exactly the right approach. > > I have a couple of questions: > > 1) Daniel and Chandler have for a long time been talking about > computing > dominance and post-dominance in one shot to reduce the cost of > post-dominance and make it (freely) available everywhere. Is this > covered by your current (or planned) work? > > > I think chandler more than me. If me, assume I was wrong :P > > I believe you can prove it is not possible to do this without doing > all the work of the separate passes. The main cost is the DFS walk, > and you can't do an undirected DFS that will work here. > I believe related things have even been proven to show the brokenness > of various algorithms. > > See https://hal.inria.fr/hal-00761505 section 4.1 > > Given the difficulties and subtleties here, I would consider any such > approach that tried to share work between the passes as "fraught with > peril"Is there a difference here between sharing work and sharing updates? The difficult part of using postdominance seems to be not the one-time cost of computing it, but the fact that we don't preserve it anywhere. Thus, using it would require re-computing it a lot. Even if we can't share the work of constructing a dominance and post-dominance tree, could we have an update API that could be used to keep both trees consistent? Thanks again, Hal> > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170621/6dfe4066/attachment.html>
On Wed, Jun 21, 2017 at 6:00 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > On 06/13/2017 01:29 PM, Daniel Berlin via llvm-dev wrote: > > > > On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> Hi Jakub, >> >> thanks for the update. I was already eagerly waiting to hear what your >> internship on dominance brings. I think the numbers are already very >> encouraging and I believe moving incrementally over to the new algorithm >> is exactly the right approach. >> >> I have a couple of questions: >> >> 1) Daniel and Chandler have for a long time been talking about computing >> dominance and post-dominance in one shot to reduce the cost of >> post-dominance and make it (freely) available everywhere. Is this >> covered by your current (or planned) work? >> > > I think chandler more than me. If me, assume I was wrong :P > > I believe you can prove it is not possible to do this without doing all > the work of the separate passes. The main cost is the DFS walk, and you > can't do an undirected DFS that will work here. > I believe related things have even been proven to show the brokenness of > various algorithms. > > See https://hal.inria.fr/hal-00761505 section 4.1 > > Given the difficulties and subtleties here, I would consider any such > approach that tried to share work between the passes as "fraught with peril" > > > Is there a difference here between sharing work and sharing updates? >Yes.> The difficult part of using postdominance seems to be not the one-time > cost of computing it, but the fact that we don't preserve it anywhere. > Thus, using it would require re-computing it a lot. Even if we can't share > the work of constructing a dominance and post-dominance tree, could we have > an update API that could be used to keep both trees consistent? > >This is precisely what Jakub's set of patches solves. The API for updating either dominance or post-dominance will be identical. It just needs to be informed of new edges and removed edges in the CFG. It's possible,at least in the new PM, to easily have a DominatorTreeUpdater utility that uses getAnalysisIfAvailable on both dominator and postdominator analysis, and calls through to the update API for each one. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170621/e6cb0286/attachment-0001.html>