[llvm-dev] RFC: Dynamic dominators

[Daniel Berlin via llvm-dev]

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>