[llvm-dev] RFC: Dynamic dominators

[Hal Finkel via llvm-dev]

On 06/21/2017 08:49 PM, Daniel Berlin wrote:
>
>
> On Wed, Jun 21, 2017 at 6:00 PM, Hal Finkel <hfinkel at anl.gov 
> <mailto: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 <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
>>     <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.

Great!

  -Hal

-- 
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/55d6c714/attachment.html>