[llvm-dev] RFC: Dynamic dominators

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
Hi folks,

This summer I'm working on improving dominators during my internship at Google. Below is an RFC on switching to dynamic dominators, which you can also read as a Google Doc if you prefer so. Please let us know what you think.

~Kuba

=======================================================================

1. Context

Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the (post)dominator tree. The only way to update it is by manually setting IDoms which is not obvious in many cases and can be extremely error-prone. And because updating it manually is so difficult, programmers tend to just recompute it after changing the CFG (by not AU.addPreserved()'ing the DomTree). This causes DomTree calculation to fire very often even if only a very small portion of it gets really affected by the changes in CFG. As an example, when optimizing a Full LTO clang bitcode, DominatorTreeWrapperPass alone calls DT.recalculate over 6.5 million times, which takes 20s on my machine.
 
Using an incremental algorithm it would be much easier to keep an up-to-date DomTree without custom update logic, which will save us the time currently spent during DomTree recalculations and reduce the number of bugs caused by manual updates. It would also make it feasible to maintain postdominators and use them more broadly, which currently can be too complicated and expensive.

2. Proposal

The proposal is to make dominators use the incremental algorithm that allows to keep (post)dominator tree up to date as CFG changes. To achieve that, we would implement the dynamic depth based search algorithm (DBS) described in this paper [1] and expose 2 main new functions: insertArc(From, To) and deleteArc(From, To). The algorithm uses SemiNCA under the hood which would replace Lengauer-Tarjan implementation currently used.
 
The second part of the proposal is to gradually deprecate and remove the existing API for manually manipulating dominator tree (changeImmediateDominator, addNewBlock) and replace its use within LLVM with the new incremental API.  

3. Proof of concept

The prototype implementation can be found in my LLVM fork [2]. It comes with several layers of verification and was tested on clang, llvm test suite and a few open source libraries.
The code provides the basic functionality and tries be ‘API-equivalent’ with the current DomTree implementation. The NewDomTree is also able to convert itself to the current one for testing and verification purposes.
Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass, LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with the use of the new API.
 
The prototype also comes with a bunch of testing utilities and a simple benchmarking tool.

4. Performance

The real life performance of full dynamic DBS-based DomTree recalculation is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs than the existing SLT algorithm, which is consistent with the findings from this thesis [3]. The advantage is not that visible on debug builds, where the DBS-algorithm can be up to 8% slower. It is most like possible to speed up debug builds, but I haven’t looked into that yet.
The benchmark performed [4] loads of a (full LTO) bitcode file and builds DomTress of all functions 15 times.
 
The current DomTree updates DFS in-out numbers eagerly upon construction, while the new one postpones is until they are actually needed. To make the benchmark fair, numbers were collected for both eager and lazy strategy for the new DomTree.
 
The main advantage of the incremental algorithm comes from the fact that it allows incremental updates without rebuilding the whole tree, not from the slightly faster construction.
What’s more, the insertArc / deleteArc API doesn’t force updates to happen immediately -- they can be queued behind the scenes and happen in batches if we decide to pursue that design later.

5. Transition plan

There are several possibilities when it comes to transition. The biggest problem is that the current DomTree exposes an interface for manual updates (setIDom, changeImmediateDominator), and for manual construction (addNewBlock). Because of the additional data stored in the incremental algorithm (relative dominators, preorder parents, levels) it is not really possible to use the old API while keeping this data up-to-date. The incremental algorithm relies on this information when performing fast arc deletions; It is still able to perform them without it -- deletions are then just slower in some cases.
The most straightforward solutions are:
 
a) Keep the existing DomTree and gradually replace its uses with the new one. It is possible to convert the DBS-based dominators to the old ones.
b) Replace the existing DomTree with the new, dynamic dominators. Nuke all of the old update functions and replace their uses with the new incremental API in one commit.
c) Replace the existing DomTree with the new one, but keep the old API around and mark it as deprecated. If someone invokes one of the old update functions, mark the the additional information as invalid for dynamic deletions. Follow the pessimistic but correct dynamic deletion path if the additional information is marked as invalidated. Gradually modernize the projects to use the new API instead and then remove the old update functions.
 
Maintaining the old DT and the new one simultaneously seems like a waste of time as the DBS offers better or similar performance to the existing SLT-based implementation.
The problem with replacing the old API with the new one is that it’s used in many places (~100) across the project and I believe that doing that all at once would be tricky to get correct. Gradual update seems much easier to ensure correctness and the transitional API (invalid additional data check) is trivial to implement. Because of that, I propose to follow the option (c). 



[1] Georgiadis et al., An Experimental Study of Dynamic Dominators, https://arxiv.org/pdf/1604.02711.pdf
[2] llvm-dominators LLVM fork on Github, https://github.com/kuhar/llvm-dominators
[3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev


On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev <[hidden email]> wrote:
Hi folks,

This summer I'm working on improving dominators during my internship at Google. Below is an RFC on switching to dynamic dominators, which you can also read as a Google Doc if you prefer so. Please let us know what you think.

~Kuba

=======================================================================

1. Context

Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the (post)dominator tree. The only way to update it is by manually setting IDoms which is not obvious in many cases and can be extremely error-prone. And because updating it manually is so difficult, programmers tend to just recompute it after changing the CFG (by not AU.addPreserved()'ing the DomTree). This causes DomTree calculation to fire very often even if only a very small portion of it gets really affected by the changes in CFG. As an example, when optimizing a Full LTO clang bitcode, DominatorTreeWrapperPass alone calls DT.recalculate over 6.5 million times, which takes 20s on my machine.

Assuming an optimistic 10min clang FullLTO build time, this is about 3%, so overall this is actually a pretty perf improvement I think. 
 
Using an incremental algorithm it would be much easier to keep an up-to-date DomTree without custom update logic, which will save us the time currently spent during DomTree recalculations and reduce the number of bugs caused by manual updates.

Avoiding bugs seems really compelling. (IIRC talking with you, Davide, and DannyB at the social, there are tons of such bugs, so eliminating them by mechanically just using a new API seems awesome)
 
It would also make it feasible to maintain postdominators and use them more broadly, which currently can be too complicated and expensive.

2. Proposal

The proposal is to make dominators use the incremental algorithm that allows to keep (post)dominator tree up to date as CFG changes. To achieve that, we would implement the dynamic depth based search algorithm (DBS) described in this paper [1] and expose 2 main new functions: insertArc(From, To) and deleteArc(From, To). The algorithm uses SemiNCA under the hood which would replace Lengauer-Tarjan implementation currently used.
 
The second part of the proposal is to gradually deprecate and remove the existing API for manually manipulating dominator tree (changeImmediateDominator, addNewBlock) and replace its use within LLVM with the new incremental API.   

3. Proof of concept

The prototype implementation can be found in my LLVM fork [2]. It comes with several layers of verification and was tested on clang, llvm test suite and a few open source libraries.
The code provides the basic functionality and tries be ‘API-equivalent’ with the current DomTree implementation. The NewDomTree is also able to convert itself to the current one for testing and verification purposes.
Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass, LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with the use of the new API.
 
The prototype also comes with a bunch of testing utilities and a simple benchmarking tool.

4. Performance

The real life performance of full dynamic DBS-based DomTree recalculation is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs than the existing SLT algorithm, which is consistent with the findings from this thesis [3]. The advantage is not that visible on debug builds, where the DBS-algorithm can be up to 8% slower. It is most like possible to speed up debug builds, but I haven’t looked into that yet.
The benchmark performed [4] loads of a (full LTO) bitcode file and builds DomTress of all functions 15 times.
 
The current DomTree updates DFS in-out numbers eagerly upon construction, while the new one postpones is until they are actually needed. To make the benchmark fair, numbers were collected for both eager and lazy strategy for the new DomTree.
 
The main advantage of the incremental algorithm comes from the fact that it allows incremental updates without rebuilding the whole tree, not from the slightly faster construction.
What’s more, the insertArc / deleteArc API doesn’t force updates to happen immediately -- they can be queued behind the scenes and happen in batches if we decide to pursue that design later.

5. Transition plan

There are several possibilities when it comes to transition. The biggest problem is that the current DomTree exposes an interface for manual updates (setIDom, changeImmediateDominator), and for manual construction (addNewBlock). Because of the additional data stored in the incremental algorithm (relative dominators, preorder parents, levels) it is not really possible to use the old API while keeping this data up-to-date. The incremental algorithm relies on this information when performing fast arc deletions; It is still able to perform them without it -- deletions are then just slower in some cases.
The most straightforward solutions are:
 
a) Keep the existing DomTree and gradually replace its uses with the new one. It is possible to convert the DBS-based dominators to the old ones.
b) Replace the existing DomTree with the new, dynamic dominators. Nuke all of the old update functions and replace their uses with the new incremental API in one commit.
c) Replace the existing DomTree with the new one, but keep the old API around and mark it as deprecated. If someone invokes one of the old update functions, mark the the additional information as invalid for dynamic deletions. Follow the pessimistic but correct dynamic deletion path if the additional information is marked as invalidated. Gradually modernize the projects to use the new API instead and then remove the old update functions.
 
Maintaining the old DT and the new one simultaneously seems like a waste of time as the DBS offers better or similar performance to the existing SLT-based implementation.
The problem with replacing the old API with the new one is that it’s used in many places (~100) across the project and I believe that doing that all at once would be tricky to get correct. Gradual update seems much easier to ensure correctness and the transitional API (invalid additional data check) is trivial to implement. Because of that, I propose to follow the option (c). 

(c) sounds like the best choice to me too. That would also allow fixing dominator verification failures first, giving a nice immediate benefit to motivate and kickstart the transition.

-- Sean Silva
 



[1] Georgiadis et al., An Experimental Study of Dynamic Dominators, https://arxiv.org/pdf/1604.02711.pdf
[2] llvm-dominators LLVM fork on Github, https://github.com/kuhar/llvm-dominators
[3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev


On Mon, Jun 12, 2017 at 5:58 PM, Sean Silva <[hidden email]> wrote:


On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev <[hidden email]> wrote:
Hi folks,

This summer I'm working on improving dominators during my internship at Google. Below is an RFC on switching to dynamic dominators, which you can also read as a Google Doc if you prefer so. Please let us know what you think.

~Kuba

=======================================================================

1. Context

Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the (post)dominator tree. The only way to update it is by manually setting IDoms which is not obvious in many cases and can be extremely error-prone. And because updating it manually is so difficult, programmers tend to just recompute it after changing the CFG (by not AU.addPreserved()'ing the DomTree). This causes DomTree calculation to fire very often even if only a very small portion of it gets really affected by the changes in CFG. As an example, when optimizing a Full LTO clang bitcode, DominatorTreeWrapperPass alone calls DT.recalculate over 6.5 million times, which takes 20s on my machine.

Assuming an optimistic 10min clang FullLTO build time, this is about 3%, so overall this is actually a pretty perf improvement I think. 

s/pretty/pretty small overall/
 
 
Using an incremental algorithm it would be much easier to keep an up-to-date DomTree without custom update logic, which will save us the time currently spent during DomTree recalculations and reduce the number of bugs caused by manual updates.

Avoiding bugs seems really compelling. (IIRC talking with you, Davide, and DannyB at the social, there are tons of such bugs, so eliminating them by mechanically just using a new API seems awesome)
 
It would also make it feasible to maintain postdominators and use them more broadly, which currently can be too complicated and expensive.

2. Proposal

The proposal is to make dominators use the incremental algorithm that allows to keep (post)dominator tree up to date as CFG changes. To achieve that, we would implement the dynamic depth based search algorithm (DBS) described in this paper [1] and expose 2 main new functions: insertArc(From, To) and deleteArc(From, To). The algorithm uses SemiNCA under the hood which would replace Lengauer-Tarjan implementation currently used.
 
The second part of the proposal is to gradually deprecate and remove the existing API for manually manipulating dominator tree (changeImmediateDominator, addNewBlock) and replace its use within LLVM with the new incremental API.   

3. Proof of concept

The prototype implementation can be found in my LLVM fork [2]. It comes with several layers of verification and was tested on clang, llvm test suite and a few open source libraries.
The code provides the basic functionality and tries be ‘API-equivalent’ with the current DomTree implementation. The NewDomTree is also able to convert itself to the current one for testing and verification purposes.
Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass, LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with the use of the new API.
 
The prototype also comes with a bunch of testing utilities and a simple benchmarking tool.

4. Performance

The real life performance of full dynamic DBS-based DomTree recalculation is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs than the existing SLT algorithm, which is consistent with the findings from this thesis [3]. The advantage is not that visible on debug builds, where the DBS-algorithm can be up to 8% slower. It is most like possible to speed up debug builds, but I haven’t looked into that yet.
The benchmark performed [4] loads of a (full LTO) bitcode file and builds DomTress of all functions 15 times.
 
The current DomTree updates DFS in-out numbers eagerly upon construction, while the new one postpones is until they are actually needed. To make the benchmark fair, numbers were collected for both eager and lazy strategy for the new DomTree.
 
The main advantage of the incremental algorithm comes from the fact that it allows incremental updates without rebuilding the whole tree, not from the slightly faster construction.
What’s more, the insertArc / deleteArc API doesn’t force updates to happen immediately -- they can be queued behind the scenes and happen in batches if we decide to pursue that design later.

5. Transition plan

There are several possibilities when it comes to transition. The biggest problem is that the current DomTree exposes an interface for manual updates (setIDom, changeImmediateDominator), and for manual construction (addNewBlock). Because of the additional data stored in the incremental algorithm (relative dominators, preorder parents, levels) it is not really possible to use the old API while keeping this data up-to-date. The incremental algorithm relies on this information when performing fast arc deletions; It is still able to perform them without it -- deletions are then just slower in some cases.
The most straightforward solutions are:
 
a) Keep the existing DomTree and gradually replace its uses with the new one. It is possible to convert the DBS-based dominators to the old ones.
b) Replace the existing DomTree with the new, dynamic dominators. Nuke all of the old update functions and replace their uses with the new incremental API in one commit.
c) Replace the existing DomTree with the new one, but keep the old API around and mark it as deprecated. If someone invokes one of the old update functions, mark the the additional information as invalid for dynamic deletions. Follow the pessimistic but correct dynamic deletion path if the additional information is marked as invalidated. Gradually modernize the projects to use the new API instead and then remove the old update functions.
 
Maintaining the old DT and the new one simultaneously seems like a waste of time as the DBS offers better or similar performance to the existing SLT-based implementation.
The problem with replacing the old API with the new one is that it’s used in many places (~100) across the project and I believe that doing that all at once would be tricky to get correct. Gradual update seems much easier to ensure correctness and the transitional API (invalid additional data check) is trivial to implement. Because of that, I propose to follow the option (c). 

(c) sounds like the best choice to me too. That would also allow fixing dominator verification failures first, giving a nice immediate benefit to motivate and kickstart the transition.

-- Sean Silva
 



[1] Georgiadis et al., An Experimental Study of Dynamic Dominators, https://arxiv.org/pdf/1604.02711.pdf
[2] llvm-dominators LLVM fork on Github, https://github.com/kuhar/llvm-dominators
[3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
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?

2) I tried to use tools/dominators

I wanted to play a little bit with your work, but run in some issues:

> bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc | tee graph
p 5 5 1 1
a 1 3
a 1 5
a 2 3
a 3 2
a 3 4
e
> bin/dominators graph
Unknown file format for graph
Invalid input graph

I must do something obvious wrong. Any idea what?

Best,
Tobias

On Tue, Jun 13, 2017, at 02:12 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:

> Hi folks,
>
> This summer I'm working on improving dominators during my internship at
> Google. Below is an RFC on switching to dynamic dominators, which you can
> also read as a Google Doc
> <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing>
> if you prefer so. Please let us know what you think.
>
> ~Kuba
>
> =======================================================================
>
> *1. Context*
>
> Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the
> (post)dominator tree. The only way to update it is by manually setting
> IDoms which is not obvious in many cases and can be extremely
> error-prone.
> And because updating it manually is so difficult, programmers tend to
> just
> recompute it after changing the CFG (by not AU.addPreserved()'ing the
> DomTree). This causes DomTree calculation to fire very often even if only
> a
> very small portion of it gets really affected by the changes in CFG. As
> an
> example, when optimizing a Full LTO clang bitcode,
> DominatorTreeWrapperPass
> alone calls DT.recalculate over 6.5 million times, which takes 20s on my
> machine.
>
> Using an incremental algorithm it would be much easier to keep an
> up-to-date DomTree without custom update logic, which will save us the
> time
> currently spent during DomTree recalculations and reduce the number of
> bugs
> caused by manual updates. It would also make it feasible to maintain
> postdominators and use them more broadly, which currently can be too
> complicated and expensive.
>
> *2. Proposal*
>
> The proposal is to make dominators use the incremental algorithm that
> allows to keep (post)dominator tree up to date as CFG changes. To achieve
> that, we would implement the dynamic depth based search algorithm (DBS)
> described in this paper [1] <https://arxiv.org/pdf/1604.02711.pdf> and
> expose 2 main new functions: insertArc(From, To) and deleteArc(From, To).
> The algorithm uses SemiNCA under the hood which would replace
> Lengauer-Tarjan implementation currently used.
>
> The second part of the proposal is to gradually deprecate and remove the
> existing API for manually manipulating dominator tree
> (changeImmediateDominator, addNewBlock) and replace its use within LLVM
> with the new incremental API.
>
> *3. Proof of concept*
>
> The prototype implementation can be found in my LLVM fork [2]
> <https://github.com/kuhar/llvm-dominators>. It comes with several layers
> of
> verification and was tested on clang, llvm test suite and a few open
> source
> libraries.
> The code provides the basic functionality and tries be ‘API-equivalent’
> with the current DomTree implementation. The NewDomTree is also able to
> convert itself to the current one for testing and verification purposes.
> Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass,
> LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with
> the
> use of the new API.
>
> The prototype also comes with a bunch of testing utilities and a simple
> benchmarking tool.
>
> *4. Performance*
>
> The real life performance of full dynamic DBS-based DomTree recalculation
> is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs
> than
> the existing SLT algorithm, which is consistent with the findings from
> this
> thesis [3] <ftp://ftp.cs.princeton.edu/reports/2005/737.pdf>. The
> advantage
> is not that visible on debug builds, where the DBS-algorithm can be up to
> 8% slower. It is most like possible to speed up debug builds, but I
> haven’t
> looked into that yet.
> The benchmark performed [4]
> <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing>
> loads of a (full LTO) bitcode file and builds DomTress of all functions
> 15
> times.
>
> The current DomTree updates DFS in-out numbers eagerly upon construction,
> while the new one postpones is until they are actually needed. To make
> the
> benchmark fair, numbers were collected for both eager and lazy strategy
> for
> the new DomTree.
>
> The main advantage of the incremental algorithm comes from the fact that
> it
> allows incremental updates without rebuilding the whole tree, not from
> the
> slightly faster construction.
> What’s more, the insertArc / deleteArc API doesn’t force updates to
> happen
> immediately -- they can be queued behind the scenes and happen in batches
> if we decide to pursue that design later.
>
> *5. Transition plan*
>
> There are several possibilities when it comes to transition. The biggest
> problem is that the current DomTree exposes an interface for manual
> updates
> (setIDom, changeImmediateDominator), and for manual construction
> (addNewBlock). Because of the additional data stored in the incremental
> algorithm (relative dominators, preorder parents, levels) it is not
> really
> possible to use the old API while keeping this data up-to-date. The
> incremental algorithm relies on this information when performing fast arc
> deletions; It is still able to perform them without it -- deletions are
> then just slower in some cases.
> The most straightforward solutions are:
>
> a) Keep the existing DomTree and gradually replace its uses with the new
> one. It is possible to convert the DBS-based dominators to the old ones.
> b) Replace the existing DomTree with the new, dynamic dominators. Nuke
> all
> of the old update functions and replace their uses with the new
> incremental
> API in one commit.
> c) Replace the existing DomTree with the new one, but keep the old API
> around and mark it as deprecated. If someone invokes one of the old
> update
> functions, mark the the additional information as invalid for dynamic
> deletions. Follow the pessimistic but correct dynamic deletion path if
> the
> additional information is marked as invalidated. Gradually modernize the
> projects to use the new API instead and then remove the old update
> functions.
>
> Maintaining the old DT and the new one simultaneously seems like a waste
> of
> time as the DBS offers better or similar performance to the existing
> SLT-based implementation.
> The problem with replacing the old API with the new one is that it’s used
> in many places (~100) across the project and I believe that doing that
> all
> at once would be tricky to get correct. Gradual update seems much easier
> to
> ensure correctness and the transitional API (invalid additional data
> check)
> is trivial to implement. Because of that, I propose to follow the option
> (c).
>
>
>
> [1] Georgiadis et al., An Experimental Study of Dynamic Dominators,
> https://arxiv.org/pdf/1604.02711.pdf
> [2] llvm-dominators LLVM fork on Github,
> https://github.com/kuhar/llvm-dominators
> [3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related
> Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38
> [4] Google Doc with the performance numbers,
> https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
Hi Tobias,

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'm not sure what you exactly mean by one shot; I'll ask around tomorrow.

 I wanted to play a little bit with your work, but run in some issues:
> bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc | tee graph
p 5 5 1 1
a 1 3
a 1 5
a 2 3
a 3 2
a 3 4
e
> bin/dominators graph
Unknown file format for graph
Invalid input graph
I must do something obvious wrong. Any idea what?

You almost got it right -- 'graph' files must end with ".txt"... :P

Best,
Kuba

On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser <[hidden email]> 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?

2) I tried to use tools/dominators

I wanted to play a little bit with your work, but run in some issues:

> bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc | tee graph
p 5 5 1 1
a 1 3
a 1 5
a 2 3
a 3 2
a 3 4
e
> bin/dominators graph
Unknown file format for graph
Invalid input graph

I must do something obvious wrong. Any idea what?

Best,
Tobias

On Tue, Jun 13, 2017, at 02:12 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> Hi folks,
>
> This summer I'm working on improving dominators during my internship at
> Google. Below is an RFC on switching to dynamic dominators, which you can
> also read as a Google Doc
> <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing>
> if you prefer so. Please let us know what you think.
>
> ~Kuba
>
> =======================================================================
>
> *1. Context*
>
> Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the
> (post)dominator tree. The only way to update it is by manually setting
> IDoms which is not obvious in many cases and can be extremely
> error-prone.
> And because updating it manually is so difficult, programmers tend to
> just
> recompute it after changing the CFG (by not AU.addPreserved()'ing the
> DomTree). This causes DomTree calculation to fire very often even if only
> a
> very small portion of it gets really affected by the changes in CFG. As
> an
> example, when optimizing a Full LTO clang bitcode,
> DominatorTreeWrapperPass
> alone calls DT.recalculate over 6.5 million times, which takes 20s on my
> machine.
>
> Using an incremental algorithm it would be much easier to keep an
> up-to-date DomTree without custom update logic, which will save us the
> time
> currently spent during DomTree recalculations and reduce the number of
> bugs
> caused by manual updates. It would also make it feasible to maintain
> postdominators and use them more broadly, which currently can be too
> complicated and expensive.
>
> *2. Proposal*
>
> The proposal is to make dominators use the incremental algorithm that
> allows to keep (post)dominator tree up to date as CFG changes. To achieve
> that, we would implement the dynamic depth based search algorithm (DBS)
> described in this paper [1] <https://arxiv.org/pdf/1604.02711.pdf> and
> expose 2 main new functions: insertArc(From, To) and deleteArc(From, To).
> The algorithm uses SemiNCA under the hood which would replace
> Lengauer-Tarjan implementation currently used.
>
> The second part of the proposal is to gradually deprecate and remove the
> existing API for manually manipulating dominator tree
> (changeImmediateDominator, addNewBlock) and replace its use within LLVM
> with the new incremental API.
>
> *3. Proof of concept*
>
> The prototype implementation can be found in my LLVM fork [2]
> <https://github.com/kuhar/llvm-dominators>. It comes with several layers
> of
> verification and was tested on clang, llvm test suite and a few open
> source
> libraries.
> The code provides the basic functionality and tries be ‘API-equivalent’
> with the current DomTree implementation. The NewDomTree is also able to
> convert itself to the current one for testing and verification purposes.
> Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass,
> LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with
> the
> use of the new API.
>
> The prototype also comes with a bunch of testing utilities and a simple
> benchmarking tool.
>
> *4. Performance*
>
> The real life performance of full dynamic DBS-based DomTree recalculation
> is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs
> than
> the existing SLT algorithm, which is consistent with the findings from
> this
> thesis [3] <ftp://ftp.cs.princeton.edu/reports/2005/737.pdf>. The
> advantage
> is not that visible on debug builds, where the DBS-algorithm can be up to
> 8% slower. It is most like possible to speed up debug builds, but I
> haven’t
> looked into that yet.
> The benchmark performed [4]
> <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing>
> loads of a (full LTO) bitcode file and builds DomTress of all functions
> 15
> times.
>
> The current DomTree updates DFS in-out numbers eagerly upon construction,
> while the new one postpones is until they are actually needed. To make
> the
> benchmark fair, numbers were collected for both eager and lazy strategy
> for
> the new DomTree.
>
> The main advantage of the incremental algorithm comes from the fact that
> it
> allows incremental updates without rebuilding the whole tree, not from
> the
> slightly faster construction.
> What’s more, the insertArc / deleteArc API doesn’t force updates to
> happen
> immediately -- they can be queued behind the scenes and happen in batches
> if we decide to pursue that design later.
>
> *5. Transition plan*
>
> There are several possibilities when it comes to transition. The biggest
> problem is that the current DomTree exposes an interface for manual
> updates
> (setIDom, changeImmediateDominator), and for manual construction
> (addNewBlock). Because of the additional data stored in the incremental
> algorithm (relative dominators, preorder parents, levels) it is not
> really
> possible to use the old API while keeping this data up-to-date. The
> incremental algorithm relies on this information when performing fast arc
> deletions; It is still able to perform them without it -- deletions are
> then just slower in some cases.
> The most straightforward solutions are:
>
> a) Keep the existing DomTree and gradually replace its uses with the new
> one. It is possible to convert the DBS-based dominators to the old ones.
> b) Replace the existing DomTree with the new, dynamic dominators. Nuke
> all
> of the old update functions and replace their uses with the new
> incremental
> API in one commit.
> c) Replace the existing DomTree with the new one, but keep the old API
> around and mark it as deprecated. If someone invokes one of the old
> update
> functions, mark the the additional information as invalid for dynamic
> deletions. Follow the pessimistic but correct dynamic deletion path if
> the
> additional information is marked as invalidated. Gradually modernize the
> projects to use the new API instead and then remove the old update
> functions.
>
> Maintaining the old DT and the new one simultaneously seems like a waste
> of
> time as the DBS offers better or similar performance to the existing
> SLT-based implementation.
> The problem with replacing the old API with the new one is that it’s used
> in many places (~100) across the project and I believe that doing that
> all
> at once would be tricky to get correct. Gradual update seems much easier
> to
> ensure correctness and the transitional API (invalid additional data
> check)
> is trivial to implement. Because of that, I propose to follow the option
> (c).
>
>
>
> [1] Georgiadis et al., An Experimental Study of Dynamic Dominators,
> https://arxiv.org/pdf/1604.02711.pdf
> [2] llvm-dominators LLVM fork on Github,
> https://github.com/kuhar/llvm-dominators
> [3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related
> Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38
> [4] Google Doc with the performance numbers,
> https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



--
Jakub Kuderski

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev


On Tue, Jun 13, 2017, at 08:47 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> Hi Tobias,
>
> 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'm not sure what you exactly mean by one shot; I'll ask around tomorrow.

Not sure what algorithm Daniel had in mind, but he was talking about
some approach that basically gives post-dominance "for free" when
computing dominance. Not sure how exactly this would work.
 

>  I wanted to play a little bit with your work, but run in some issues:
> > > bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> > > bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc
> > | tee graph
> > p 5 5 1 1
> > a 1 3
> > a 1 5
> > a 2 3
> > a 3 2
> > a 3 4
> > e
> > > bin/dominators graph
> > Unknown file format for graph
> > Invalid input graph
> > I must do something obvious wrong. Any idea what?
>
>
> You almost got it right -- 'graph' files must end with ".txt"... :P

I got it. Thank you! I also realized I can directly read in .bc files.

I have a couple of immediate (but rather minor) comments:

-  It would be convenient to allow .ll files to be read.
- You do not use the BB names in the output, right? This would certainly
   improve readability!
- My output prints "New Dominator Tree" to times in a row. What is the
difference? What is the difference to Inorder Dominator Tree?
- How do I get the post-dominator tree with your tool? Do you already
have test cases? In fact, normal IR test cases would be really cool. We
do not have a lot of test coverage for all the dominance stuff.

Best,
Tobias

>
> Best,
> Kuba
>
> On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser
> <[hidden email]
> > 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?
> >
> > 2) I tried to use tools/dominators
> >
> > I wanted to play a little bit with your work, but run in some issues:
> >
> > > bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> > > bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc
> > | tee graph
> > p 5 5 1 1
> > a 1 3
> > a 1 5
> > a 2 3
> > a 3 2
> > a 3 4
> > e
> > > bin/dominators graph
> > Unknown file format for graph
> > Invalid input graph
> >
> > I must do something obvious wrong. Any idea what?
> >
> > Best,
> > Tobias
> >
> > On Tue, Jun 13, 2017, at 02:12 AM, Jakub (Kuba) Kuderski via llvm-dev
> > wrote:
> > > Hi folks,
> > >
> > > This summer I'm working on improving dominators during my internship at
> > > Google. Below is an RFC on switching to dynamic dominators, which you can
> > > also read as a Google Doc
> > > <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing>
> > > if you prefer so. Please let us know what you think.
> > >
> > > ~Kuba
> > >
> > > =======================================================================
> > >
> > > *1. Context*
> > >
> > > Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the
> > > (post)dominator tree. The only way to update it is by manually setting
> > > IDoms which is not obvious in many cases and can be extremely
> > > error-prone.
> > > And because updating it manually is so difficult, programmers tend to
> > > just
> > > recompute it after changing the CFG (by not AU.addPreserved()'ing the
> > > DomTree). This causes DomTree calculation to fire very often even if only
> > > a
> > > very small portion of it gets really affected by the changes in CFG. As
> > > an
> > > example, when optimizing a Full LTO clang bitcode,
> > > DominatorTreeWrapperPass
> > > alone calls DT.recalculate over 6.5 million times, which takes 20s on my
> > > machine.
> > >
> > > Using an incremental algorithm it would be much easier to keep an
> > > up-to-date DomTree without custom update logic, which will save us the
> > > time
> > > currently spent during DomTree recalculations and reduce the number of
> > > bugs
> > > caused by manual updates. It would also make it feasible to maintain
> > > postdominators and use them more broadly, which currently can be too
> > > complicated and expensive.
> > >
> > > *2. Proposal*
> > >
> > > The proposal is to make dominators use the incremental algorithm that
> > > allows to keep (post)dominator tree up to date as CFG changes. To achieve
> > > that, we would implement the dynamic depth based search algorithm (DBS)
> > > described in this paper [1] <https://arxiv.org/pdf/1604.02711.pdf> and
> > > expose 2 main new functions: insertArc(From, To) and deleteArc(From, To).
> > > The algorithm uses SemiNCA under the hood which would replace
> > > Lengauer-Tarjan implementation currently used.
> > >
> > > The second part of the proposal is to gradually deprecate and remove the
> > > existing API for manually manipulating dominator tree
> > > (changeImmediateDominator, addNewBlock) and replace its use within LLVM
> > > with the new incremental API.
> > >
> > > *3. Proof of concept*
> > >
> > > The prototype implementation can be found in my LLVM fork [2]
> > > <https://github.com/kuhar/llvm-dominators>. It comes with several layers
> > > of
> > > verification and was tested on clang, llvm test suite and a few open
> > > source
> > > libraries.
> > > The code provides the basic functionality and tries be ‘API-equivalent’
> > > with the current DomTree implementation. The NewDomTree is also able to
> > > convert itself to the current one for testing and verification purposes.
> > > Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass,
> > > LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with
> > > the
> > > use of the new API.
> > >
> > > The prototype also comes with a bunch of testing utilities and a simple
> > > benchmarking tool.
> > >
> > > *4. Performance*
> > >
> > > The real life performance of full dynamic DBS-based DomTree recalculation
> > > is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs
> > > than
> > > the existing SLT algorithm, which is consistent with the findings from
> > > this
> > > thesis [3] <ftp://ftp.cs.princeton.edu/reports/2005/737.pdf>. The
> > > advantage
> > > is not that visible on debug builds, where the DBS-algorithm can be up to
> > > 8% slower. It is most like possible to speed up debug builds, but I
> > > haven’t
> > > looked into that yet.
> > > The benchmark performed [4]
> > > <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing>
> > > loads of a (full LTO) bitcode file and builds DomTress of all functions
> > > 15
> > > times.
> > >
> > > The current DomTree updates DFS in-out numbers eagerly upon construction,
> > > while the new one postpones is until they are actually needed. To make
> > > the
> > > benchmark fair, numbers were collected for both eager and lazy strategy
> > > for
> > > the new DomTree.
> > >
> > > The main advantage of the incremental algorithm comes from the fact that
> > > it
> > > allows incremental updates without rebuilding the whole tree, not from
> > > the
> > > slightly faster construction.
> > > What’s more, the insertArc / deleteArc API doesn’t force updates to
> > > happen
> > > immediately -- they can be queued behind the scenes and happen in batches
> > > if we decide to pursue that design later.
> > >
> > > *5. Transition plan*
> > >
> > > There are several possibilities when it comes to transition. The biggest
> > > problem is that the current DomTree exposes an interface for manual
> > > updates
> > > (setIDom, changeImmediateDominator), and for manual construction
> > > (addNewBlock). Because of the additional data stored in the incremental
> > > algorithm (relative dominators, preorder parents, levels) it is not
> > > really
> > > possible to use the old API while keeping this data up-to-date. The
> > > incremental algorithm relies on this information when performing fast arc
> > > deletions; It is still able to perform them without it -- deletions are
> > > then just slower in some cases.
> > > The most straightforward solutions are:
> > >
> > > a) Keep the existing DomTree and gradually replace its uses with the new
> > > one. It is possible to convert the DBS-based dominators to the old ones.
> > > b) Replace the existing DomTree with the new, dynamic dominators. Nuke
> > > all
> > > of the old update functions and replace their uses with the new
> > > incremental
> > > API in one commit.
> > > c) Replace the existing DomTree with the new one, but keep the old API
> > > around and mark it as deprecated. If someone invokes one of the old
> > > update
> > > functions, mark the the additional information as invalid for dynamic
> > > deletions. Follow the pessimistic but correct dynamic deletion path if
> > > the
> > > additional information is marked as invalidated. Gradually modernize the
> > > projects to use the new API instead and then remove the old update
> > > functions.
> > >
> > > Maintaining the old DT and the new one simultaneously seems like a waste
> > > of
> > > time as the DBS offers better or similar performance to the existing
> > > SLT-based implementation.
> > > The problem with replacing the old API with the new one is that it’s used
> > > in many places (~100) across the project and I believe that doing that
> > > all
> > > at once would be tricky to get correct. Gradual update seems much easier
> > > to
> > > ensure correctness and the transitional API (invalid additional data
> > > check)
> > > is trivial to implement. Because of that, I propose to follow the option
> > > (c).
> > >
> > >
> > >
> > > [1] Georgiadis et al., An Experimental Study of Dynamic Dominators,
> > > https://arxiv.org/pdf/1604.02711.pdf
> > > [2] llvm-dominators LLVM fork on Github,
> > > https://github.com/kuhar/llvm-dominators
> > > [3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related
> > > Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38
> > > [4] Google Doc with the performance numbers,
> > > https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > [hidden email]
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
>
>
>
> --
> Jakub Kuderski
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
Tobias,

Thanks for the comments and taking a look at my fork.
 
 -  It would be convenient to allow .ll files to be read.
Sure, I can add it tomorrow.

- You do not use the BB names in the output, right? This would certainly
   improve readability!
You actually don't have to convert you bitcode files to 'graph' files (as long as they contain a single function) -- then names should be preserved, but you don't get to play with updates. The format I'm using isn't very good, but it's compatible with some other implementation by Loucas -- the author of the algorithm. Do you think that having a format like that in LLVM would make sense? Danny and I though about in the context of quickly writing and modifying tests for dominators and things like the NewGVN.

- My output prints "New Dominator Tree" to times in a row. What is the
difference? What is the difference to Inorder Dominator Tree?
 When you graph files have updates (i numFrom numTo and d numFrom numTo) then the first one is the original one and the second one is the one after applying all the updates. Inorder Dominator Tree is the existing DomTree -- I used to use it just for visual comparison.

- How do I get the post-dominator tree with your tool? Do you already
have test cases? In fact, normal IR test cases would be really cool. We
do not have a lot of test coverage for all the dominance stuff.
 I haven't really played with postdominators yet. Do you have any specific ideas on how to test it in mind? And I definitely agree, dominators need to be tested more thoroughly. I think that because of the manual updates (of questionable correctness) and frequent recalculations there must be many undiscovered bugs that we just haven't had a chance to observe yet.

Best,
Kuba    

On Tue, Jun 13, 2017 at 12:05 AM, Tobias Grosser <[hidden email]> wrote:


On Tue, Jun 13, 2017, at 08:47 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> Hi Tobias,
>
> 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'm not sure what you exactly mean by one shot; I'll ask around tomorrow.

Not sure what algorithm Daniel had in mind, but he was talking about
some approach that basically gives post-dominance "for free" when
computing dominance. Not sure how exactly this would work.

>  I wanted to play a little bit with your work, but run in some issues:
> > > bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> > > bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc
> > | tee graph
> > p 5 5 1 1
> > a 1 3
> > a 1 5
> > a 2 3
> > a 3 2
> > a 3 4
> > e
> > > bin/dominators graph
> > Unknown file format for graph
> > Invalid input graph
> > I must do something obvious wrong. Any idea what?
>
>
> You almost got it right -- 'graph' files must end with ".txt"... :P

I got it. Thank you! I also realized I can directly read in .bc files.

I have a couple of immediate (but rather minor) comments:

-  It would be convenient to allow .ll files to be read.
- You do not use the BB names in the output, right? This would certainly
   improve readability!
- My output prints "New Dominator Tree" to times in a row. What is the
difference? What is the difference to Inorder Dominator Tree?
- How do I get the post-dominator tree with your tool? Do you already
have test cases? In fact, normal IR test cases would be really cool. We
do not have a lot of test coverage for all the dominance stuff.

Best,
Tobias

>
> Best,
> Kuba
>
> On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser
> <[hidden email]
> > 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?
> >
> > 2) I tried to use tools/dominators
> >
> > I wanted to play a little bit with your work, but run in some issues:
> >
> > > bin/llvm-as ../test/Analysis/Dominators/2007-07-11-SplitBlock.ll
> > > bin/dominators -to-graph ../test/Analysis/Dominators/2007-07-11-SplitBlock.bc
> > | tee graph
> > p 5 5 1 1
> > a 1 3
> > a 1 5
> > a 2 3
> > a 3 2
> > a 3 4
> > e
> > > bin/dominators graph
> > Unknown file format for graph
> > Invalid input graph
> >
> > I must do something obvious wrong. Any idea what?
> >
> > Best,
> > Tobias
> >
> > On Tue, Jun 13, 2017, at 02:12 AM, Jakub (Kuba) Kuderski via llvm-dev
> > wrote:
> > > Hi folks,
> > >
> > > This summer I'm working on improving dominators during my internship at
> > > Google. Below is an RFC on switching to dynamic dominators, which you can
> > > also read as a Google Doc
> > > <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing>
> > > if you prefer so. Please let us know what you think.
> > >
> > > ~Kuba
> > >
> > > =======================================================================
> > >
> > > *1. Context*
> > >
> > > Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the
> > > (post)dominator tree. The only way to update it is by manually setting
> > > IDoms which is not obvious in many cases and can be extremely
> > > error-prone.
> > > And because updating it manually is so difficult, programmers tend to
> > > just
> > > recompute it after changing the CFG (by not AU.addPreserved()'ing the
> > > DomTree). This causes DomTree calculation to fire very often even if only
> > > a
> > > very small portion of it gets really affected by the changes in CFG. As
> > > an
> > > example, when optimizing a Full LTO clang bitcode,
> > > DominatorTreeWrapperPass
> > > alone calls DT.recalculate over 6.5 million times, which takes 20s on my
> > > machine.
> > >
> > > Using an incremental algorithm it would be much easier to keep an
> > > up-to-date DomTree without custom update logic, which will save us the
> > > time
> > > currently spent during DomTree recalculations and reduce the number of
> > > bugs
> > > caused by manual updates. It would also make it feasible to maintain
> > > postdominators and use them more broadly, which currently can be too
> > > complicated and expensive.
> > >
> > > *2. Proposal*
> > >
> > > The proposal is to make dominators use the incremental algorithm that
> > > allows to keep (post)dominator tree up to date as CFG changes. To achieve
> > > that, we would implement the dynamic depth based search algorithm (DBS)
> > > described in this paper [1] <https://arxiv.org/pdf/1604.02711.pdf> and
> > > expose 2 main new functions: insertArc(From, To) and deleteArc(From, To).
> > > The algorithm uses SemiNCA under the hood which would replace
> > > Lengauer-Tarjan implementation currently used.
> > >
> > > The second part of the proposal is to gradually deprecate and remove the
> > > existing API for manually manipulating dominator tree
> > > (changeImmediateDominator, addNewBlock) and replace its use within LLVM
> > > with the new incremental API.
> > >
> > > *3. Proof of concept*
> > >
> > > The prototype implementation can be found in my LLVM fork [2]
> > > <https://github.com/kuhar/llvm-dominators>. It comes with several layers
> > > of
> > > verification and was tested on clang, llvm test suite and a few open
> > > source
> > > libraries.
> > > The code provides the basic functionality and tries be ‘API-equivalent’
> > > with the current DomTree implementation. The NewDomTree is also able to
> > > convert itself to the current one for testing and verification purposes.
> > > Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass,
> > > LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with
> > > the
> > > use of the new API.
> > >
> > > The prototype also comes with a bunch of testing utilities and a simple
> > > benchmarking tool.
> > >
> > > *4. Performance*
> > >
> > > The real life performance of full dynamic DBS-based DomTree recalculation
> > > is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs
> > > than
> > > the existing SLT algorithm, which is consistent with the findings from
> > > this
> > > thesis [3] <ftp://ftp.cs.princeton.edu/reports/2005/737.pdf>. The
> > > advantage
> > > is not that visible on debug builds, where the DBS-algorithm can be up to
> > > 8% slower. It is most like possible to speed up debug builds, but I
> > > haven’t
> > > looked into that yet.
> > > The benchmark performed [4]
> > > <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing>
> > > loads of a (full LTO) bitcode file and builds DomTress of all functions
> > > 15
> > > times.
> > >
> > > The current DomTree updates DFS in-out numbers eagerly upon construction,
> > > while the new one postpones is until they are actually needed. To make
> > > the
> > > benchmark fair, numbers were collected for both eager and lazy strategy
> > > for
> > > the new DomTree.
> > >
> > > The main advantage of the incremental algorithm comes from the fact that
> > > it
> > > allows incremental updates without rebuilding the whole tree, not from
> > > the
> > > slightly faster construction.
> > > What’s more, the insertArc / deleteArc API doesn’t force updates to
> > > happen
> > > immediately -- they can be queued behind the scenes and happen in batches
> > > if we decide to pursue that design later.
> > >
> > > *5. Transition plan*
> > >
> > > There are several possibilities when it comes to transition. The biggest
> > > problem is that the current DomTree exposes an interface for manual
> > > updates
> > > (setIDom, changeImmediateDominator), and for manual construction
> > > (addNewBlock). Because of the additional data stored in the incremental
> > > algorithm (relative dominators, preorder parents, levels) it is not
> > > really
> > > possible to use the old API while keeping this data up-to-date. The
> > > incremental algorithm relies on this information when performing fast arc
> > > deletions; It is still able to perform them without it -- deletions are
> > > then just slower in some cases.
> > > The most straightforward solutions are:
> > >
> > > a) Keep the existing DomTree and gradually replace its uses with the new
> > > one. It is possible to convert the DBS-based dominators to the old ones.
> > > b) Replace the existing DomTree with the new, dynamic dominators. Nuke
> > > all
> > > of the old update functions and replace their uses with the new
> > > incremental
> > > API in one commit.
> > > c) Replace the existing DomTree with the new one, but keep the old API
> > > around and mark it as deprecated. If someone invokes one of the old
> > > update
> > > functions, mark the the additional information as invalid for dynamic
> > > deletions. Follow the pessimistic but correct dynamic deletion path if
> > > the
> > > additional information is marked as invalidated. Gradually modernize the
> > > projects to use the new API instead and then remove the old update
> > > functions.
> > >
> > > Maintaining the old DT and the new one simultaneously seems like a waste
> > > of
> > > time as the DBS offers better or similar performance to the existing
> > > SLT-based implementation.
> > > The problem with replacing the old API with the new one is that it’s used
> > > in many places (~100) across the project and I believe that doing that
> > > all
> > > at once would be tricky to get correct. Gradual update seems much easier
> > > to
> > > ensure correctness and the transitional API (invalid additional data
> > > check)
> > > is trivial to implement. Because of that, I propose to follow the option
> > > (c).
> > >
> > >
> > >
> > > [1] Georgiadis et al., An Experimental Study of Dynamic Dominators,
> > > https://arxiv.org/pdf/1604.02711.pdf
> > > [2] llvm-dominators LLVM fork on Github,
> > > https://github.com/kuhar/llvm-dominators
> > > [3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related
> > > Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38
> > > [4] Google Doc with the performance numbers,
> > > https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGId
> > yF65OTfhSMaNHQ/edit?usp=sharing
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > [hidden email]
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
>
>
>
> --
> Jakub Kuderski
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



--
Jakub Kuderski

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> Tobias,
>
> Thanks for the comments and taking a look at my fork.
>
>
> >  -  It would be convenient to allow .ll files to be read.
>
> Sure, I can add it tomorrow.

Thank you!
 
> - You do not use the BB names in the output, right? This would certainly
> >    improve readability!
>
> You actually don't have to convert you bitcode files to 'graph' files (as
> long as they contain a single function) -- then names should be
> preserved,
> but you don't get to play with updates. The format I'm using isn't very
> good, but it's compatible with some other implementation by Loucas -- the
> author of the algorithm.

I tried to use a bitcode file directly:

[grosser@greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll
define void @foo() {
entry:
  br i1 1, label %infloop, label %next

infloop:
  br label %infloop

next:
  ret void

[grosser@greina0 build]$ bin/dominators
../test/Analysis/RegionInfo/test.bc

New Dominator Tree:
  [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
    [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
      [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
      [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}

New Dominator Tree:
  [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
    [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
      [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
      [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
=============================--------------------------------
Inorder Dominator Tree:
  [1] %entry_n_1 {0,5}
    [2] %n_2 {1,2}
    [2] %n_3 {3,4}

It seems the names "inloop" and "next" are not used.

> Do you think that having a format like that in
> LLVM would make sense? Danny and I though about in the context of quickly
> writing and modifying tests for dominators and things like the NewGVN.

For from-scratch dominance computation LLVM-IR seems fine, but for all
the incremental stuff you are doing, such input indeed might make sense.
Especially if you are planning to generate many of these test cases
automatically.

> - My output prints "New Dominator Tree" to times in a row. What is the
> > difference? What is the difference to Inorder Dominator Tree?
> >
>  When you graph files have updates (i numFrom numTo and d numFrom numTo)
> then the first one is the original one and the second one is the one
> after
> applying all the updates.
> Inorder Dominator Tree is the existing DomTree

Interesting. Probably it is just a testing/debugging tool, but maybe
clarifying this in the output may avoid confusion for others who try
your changes.

> --
> I used to use it just for visual comparison.

That's what I did.
 

> - How do I get the post-dominator tree with your tool? Do you already
> > have test cases? In fact, normal IR test cases would be really cool. We
> > do not have a lot of test coverage for all the dominance stuff.
>
>  I haven't really played with postdominators yet. Do you have any
>  specific
> ideas on how to test it in mind? And I definitely agree, dominators need
> to
> be tested more thoroughly. I think that because of the manual updates (of
> questionable correctness) and frequent recalculations there must be many
> undiscovered bugs that we just haven't had a chance to observe yet.

I think we certainly should have standard LLVM-IR style test cases,
where we use -analyze to dump the domtree for a given piece of IR that
clarfies how/what dominator tree is expected for a certain piece of
input and where it is easy for others to add test cases.

Now, most of the bugs you might expect are likely in the update /
invalidation cycle. What would look very nice and readable to me, is to
write test cases as follows:

; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \
; RUN:   < %s | FileCheck %s
;
; CHECK-LABEL; delete (bb3 -> bb4)
; CHECK: <new-dom-tree>

; CHECK-LABEL; delete (bb4 -> bb5)
; CHECK: <new-dom-tree>

....

We could even have a tool that records the dom-tree modification
requests, and dumps a corresponding IR-file.

Obviously, this is just an idea.

Best,
Tobias
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
Btw, here is another interesting paper about post-dominators and control
dependence:

https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf

I think a great outcome of your internship would be some precise
documentation regarding the guarantees the LLVM dominators give --
possibly also considering classic and weak control dependence and the
difference between loop-dominance and dominance.

Please keep me up-to-date with your work. This is really work that has
long been overdue!

Best,
Tobias

On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote:

> On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev
> wrote:
> > Tobias,
> >
> > Thanks for the comments and taking a look at my fork.
> >
> >
> > >  -  It would be convenient to allow .ll files to be read.
> >
> > Sure, I can add it tomorrow.
>
> Thank you!
>  
> > - You do not use the BB names in the output, right? This would certainly
> > >    improve readability!
> >
> > You actually don't have to convert you bitcode files to 'graph' files (as
> > long as they contain a single function) -- then names should be
> > preserved,
> > but you don't get to play with updates. The format I'm using isn't very
> > good, but it's compatible with some other implementation by Loucas -- the
> > author of the algorithm.
>
> I tried to use a bitcode file directly:
>
> [grosser@greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll
> define void @foo() {
> entry:
>   br i1 1, label %infloop, label %next
>
> infloop:
>   br label %infloop
>
> next:
>   ret void
>
> [grosser@greina0 build]$ bin/dominators
> ../test/Analysis/RegionInfo/test.bc
>
> New Dominator Tree:
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
>
> New Dominator Tree:
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
> =============================--------------------------------
> Inorder Dominator Tree:
>   [1] %entry_n_1 {0,5}
>     [2] %n_2 {1,2}
>     [2] %n_3 {3,4}
>
> It seems the names "inloop" and "next" are not used.
>
> > Do you think that having a format like that in
> > LLVM would make sense? Danny and I though about in the context of quickly
> > writing and modifying tests for dominators and things like the NewGVN.
>
> For from-scratch dominance computation LLVM-IR seems fine, but for all
> the incremental stuff you are doing, such input indeed might make sense.
> Especially if you are planning to generate many of these test cases
> automatically.
>
> > - My output prints "New Dominator Tree" to times in a row. What is the
> > > difference? What is the difference to Inorder Dominator Tree?
> > >
> >  When you graph files have updates (i numFrom numTo and d numFrom numTo)
> > then the first one is the original one and the second one is the one
> > after
> > applying all the updates.
> > Inorder Dominator Tree is the existing DomTree
>
> Interesting. Probably it is just a testing/debugging tool, but maybe
> clarifying this in the output may avoid confusion for others who try
> your changes.
>
> > --
> > I used to use it just for visual comparison.
>
> That's what I did.
>  
> > - How do I get the post-dominator tree with your tool? Do you already
> > > have test cases? In fact, normal IR test cases would be really cool. We
> > > do not have a lot of test coverage for all the dominance stuff.
> >
> >  I haven't really played with postdominators yet. Do you have any
> >  specific
> > ideas on how to test it in mind? And I definitely agree, dominators need
> > to
> > be tested more thoroughly. I think that because of the manual updates (of
> > questionable correctness) and frequent recalculations there must be many
> > undiscovered bugs that we just haven't had a chance to observe yet.
>
> I think we certainly should have standard LLVM-IR style test cases,
> where we use -analyze to dump the domtree for a given piece of IR that
> clarfies how/what dominator tree is expected for a certain piece of
> input and where it is easy for others to add test cases.
>
> Now, most of the bugs you might expect are likely in the update /
> invalidation cycle. What would look very nice and readable to me, is to
> write test cases as follows:
>
> ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \
> ; RUN:   < %s | FileCheck %s
> ;
> ; CHECK-LABEL; delete (bb3 -> bb4)
> ; CHECK: <new-dom-tree>
>
> ; CHECK-LABEL; delete (bb4 -> bb5)
> ; CHECK: <new-dom-tree>
>
> ....
>
> We could even have a tool that records the dom-tree modification
> requests, and dumps a corresponding IR-file.
>
> Obviously, this is just an idea.
>
> Best,
> Tobias
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
I tried to use a bitcode file directly:

...

It seems the names "inloop" and "next" are not used.

My bad, I almost always use the tool with -view-cfg and didn't notice that BB names were different. I fixed that and now when you just run the dominators tool on a module it should work fine. It now also supports reading .ll files.

Interesting. Probably it is just a testing/debugging tool, but maybe
clarifying this in the output may avoid confusion for others who try
your changes.
Yep, I briefly mentioned that in the first line of the tool's source file, but I should probably add a note in some more visible place. Sorry for making it confusing.

We could even have a tool that records the dom-tree modification
requests, and dumps a corresponding IR-file.

Obviously, this is just an idea.
I'll think about it.

Btw, here is another interesting paper about post-dominators and control
dependence:
 https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf
Interesting, thanks for the link, I'll try to take a look at it and probably report back with some ideas and more questions.

 Best,
Kuba

On Tue, Jun 13, 2017 at 1:27 AM, Tobias Grosser <[hidden email]> wrote:
Btw, here is another interesting paper about post-dominators and control
dependence:

https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf

I think a great outcome of your internship would be some precise
documentation regarding the guarantees the LLVM dominators give --
possibly also considering classic and weak control dependence and the
difference between loop-dominance and dominance.

Please keep me up-to-date with your work. This is really work that has
long been overdue!

Best,
Tobias

On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote:
> On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev
> wrote:
> > Tobias,
> >
> > Thanks for the comments and taking a look at my fork.
> >
> >
> > >  -  It would be convenient to allow .ll files to be read.
> >
> > Sure, I can add it tomorrow.
>
> Thank you!
>
> > - You do not use the BB names in the output, right? This would certainly
> > >    improve readability!
> >
> > You actually don't have to convert you bitcode files to 'graph' files (as
> > long as they contain a single function) -- then names should be
> > preserved,
> > but you don't get to play with updates. The format I'm using isn't very
> > good, but it's compatible with some other implementation by Loucas -- the
> > author of the algorithm.
>
> I tried to use a bitcode file directly:
>
> [grosser@greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll
> define void @foo() {
> entry:
>   br i1 1, label %infloop, label %next
>
> infloop:
>   br label %infloop
>
> next:
>   ret void
>
> [grosser@greina0 build]$ bin/dominators
> ../test/Analysis/RegionInfo/test.bc
>
> New Dominator Tree:
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
>
> New Dominator Tree:
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
> =============================--------------------------------
> Inorder Dominator Tree:
>   [1] %entry_n_1 {0,5}
>     [2] %n_2 {1,2}
>     [2] %n_3 {3,4}
>
> It seems the names "inloop" and "next" are not used.
>
> > Do you think that having a format like that in
> > LLVM would make sense? Danny and I though about in the context of quickly
> > writing and modifying tests for dominators and things like the NewGVN.
>
> For from-scratch dominance computation LLVM-IR seems fine, but for all
> the incremental stuff you are doing, such input indeed might make sense.
> Especially if you are planning to generate many of these test cases
> automatically.
>
> > - My output prints "New Dominator Tree" to times in a row. What is the
> > > difference? What is the difference to Inorder Dominator Tree?
> > >
> >  When you graph files have updates (i numFrom numTo and d numFrom numTo)
> > then the first one is the original one and the second one is the one
> > after
> > applying all the updates.
> > Inorder Dominator Tree is the existing DomTree
>
> Interesting. Probably it is just a testing/debugging tool, but maybe
> clarifying this in the output may avoid confusion for others who try
> your changes.
>
> > --
> > I used to use it just for visual comparison.
>
> That's what I did.
>
> > - How do I get the post-dominator tree with your tool? Do you already
> > > have test cases? In fact, normal IR test cases would be really cool. We
> > > do not have a lot of test coverage for all the dominance stuff.
> >
> >  I haven't really played with postdominators yet. Do you have any
> >  specific
> > ideas on how to test it in mind? And I definitely agree, dominators need
> > to
> > be tested more thoroughly. I think that because of the manual updates (of
> > questionable correctness) and frequent recalculations there must be many
> > undiscovered bugs that we just haven't had a chance to observe yet.
>
> I think we certainly should have standard LLVM-IR style test cases,
> where we use -analyze to dump the domtree for a given piece of IR that
> clarfies how/what dominator tree is expected for a certain piece of
> input and where it is easy for others to add test cases.
>
> Now, most of the bugs you might expect are likely in the update /
> invalidation cycle. What would look very nice and readable to me, is to
> write test cases as follows:
>
> ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \
> ; RUN:   < %s | FileCheck %s
> ;
> ; CHECK-LABEL; delete (bb3 -> bb4)
> ; CHECK: <new-dom-tree>
>
> ; CHECK-LABEL; delete (bb4 -> bb5)
> ; CHECK: <new-dom-tree>
>
> ....
>
> We could even have a tool that records the dom-tree modification
> requests, and dumps a corresponding IR-file.
>
> Obviously, this is just an idea.
>
> Best,
> Tobias
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



--
Jakub Kuderski

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev


On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev <[hidden email]> 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.


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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev
<[hidden email]> wrote:
> 4. Performance
>
> The real life performance of full dynamic DBS-based DomTree recalculation is
> between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs than the
> existing SLT algorithm, which is consistent with the findings from this
> thesis [3]. The advantage is not that visible on debug builds, where the
> DBS-algorithm can be up to 8% slower. It is most like possible to speed up
> debug builds, but I haven’t looked into that yet.

Do you mean the algorithm is slower in debug builds of LLVM, or when
LLVM is used to do debug builds of things?

It sounds like you say the algorithm can be 8% slower for debug
builds, but also likely to speed up debug builds? I'm confused :-)
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
Do you mean the algorithm is slower in debug builds of LLVM, or when
LLVM is used to do debug builds of things?

It sounds like you say the algorithm can be 8% slower for debug
builds, but also likely to speed up debug builds? I'm confused :-)
The algorithm can be slower when LLVM is built in Debug mode instead of Release.
DomTree is only an analysis, so as long as it is correct it doesn't affect performance of compiled programs.

On Tue, Jun 13, 2017 at 11:44 AM, Hans Wennborg <[hidden email]> wrote:
On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev
<[hidden email]> wrote:
> 4. Performance
>
> The real life performance of full dynamic DBS-based DomTree recalculation is
> between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs than the
> existing SLT algorithm, which is consistent with the findings from this
> thesis [3]. The advantage is not that visible on debug builds, where the
> DBS-algorithm can be up to 8% slower. It is most like possible to speed up
> debug builds, but I haven’t looked into that yet.

Do you mean the algorithm is slower in debug builds of LLVM, or when
LLVM is used to do debug builds of things?

It sounds like you say the algorithm can be 8% slower for debug
builds, but also likely to speed up debug builds? I'm confused :-)



--
Jakub Kuderski

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
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 <
> [hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
On Tue, Jun 13, 2017, at 08:14 PM, Jakub (Kuba) Kuderski via llvm-dev
wrote:

> >
> > I tried to use a bitcode file directly:
> >
> > ...
> >
> > It seems the names "inloop" and "next" are not used.
>
>
> My bad, I almost always use the tool with -view-cfg and didn't notice
> that
> BB names were different. I fixed that and now when you just run the
> dominators tool on a module it should work fine. It now also supports
> reading .ll files.
>
> Interesting. Probably it is just a testing/debugging tool, but maybe
> > clarifying this in the output may avoid confusion for others who try
> > your changes.
>
> Yep, I briefly mentioned that in the first line of the tool's source
> file,
> but I should probably add a note in some more visible place. Sorry for
> making it confusing.

Great. It now works as expected. I still don't have an option to compute
post-dominators (I assume it is not yet implemented), but otherwise the
tools now does what I expect. Thanks for improving it!

Best,
Tobias
 

> We could even have a tool that records the dom-tree modification
> > requests, and dumps a corresponding IR-file.
> >
> > Obviously, this is just an idea.
>
> I'll think about it.
>
> Btw, here is another interesting paper about post-dominators and control
> > dependence:
> >
>  https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12
> > f1ed1e.pdf
>
> Interesting, thanks for the link, I'll try to take a look at it and
> probably report back with some ideas and more questions.
>
>  Best,
> Kuba
>
> On Tue, Jun 13, 2017 at 1:27 AM, Tobias Grosser
> <[hidden email]>
> wrote:
>
> > Btw, here is another interesting paper about post-dominators and control
> > dependence:
> >
> > https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12
> > f1ed1e.pdf
> >
> > I think a great outcome of your internship would be some precise
> > documentation regarding the guarantees the LLVM dominators give --
> > possibly also considering classic and weak control dependence and the
> > difference between loop-dominance and dominance.
> >
> > Please keep me up-to-date with your work. This is really work that has
> > long been overdue!
> >
> > Best,
> > Tobias
> >
> > On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote:
> > > On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev
> > > wrote:
> > > > Tobias,
> > > >
> > > > Thanks for the comments and taking a look at my fork.
> > > >
> > > >
> > > > >  -  It would be convenient to allow .ll files to be read.
> > > >
> > > > Sure, I can add it tomorrow.
> > >
> > > Thank you!
> > >
> > > > - You do not use the BB names in the output, right? This would
> > certainly
> > > > >    improve readability!
> > > >
> > > > You actually don't have to convert you bitcode files to 'graph' files
> > (as
> > > > long as they contain a single function) -- then names should be
> > > > preserved,
> > > > but you don't get to play with updates. The format I'm using isn't very
> > > > good, but it's compatible with some other implementation by Loucas --
> > the
> > > > author of the algorithm.
> > >
> > > I tried to use a bitcode file directly:
> > >
> > > [grosser@greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll
> > > define void @foo() {
> > > entry:
> > >   br i1 1, label %infloop, label %next
> > >
> > > infloop:
> > >   br label %infloop
> > >
> > > next:
> > >   ret void
> > >
> > > [grosser@greina0 build]$ bin/dominators
> > > ../test/Analysis/RegionInfo/test.bc
> > >
> > > New Dominator Tree:
> > >   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
> > >     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
> > >       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
> > >       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
> > >
> > > New Dominator Tree:
> > >   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}
> > >     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}
> > >       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}
> > >       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}
> > > =============================--------------------------------
> > > Inorder Dominator Tree:
> > >   [1] %entry_n_1 {0,5}
> > >     [2] %n_2 {1,2}
> > >     [2] %n_3 {3,4}
> > >
> > > It seems the names "inloop" and "next" are not used.
> > >
> > > > Do you think that having a format like that in
> > > > LLVM would make sense? Danny and I though about in the context of
> > quickly
> > > > writing and modifying tests for dominators and things like the NewGVN.
> > >
> > > For from-scratch dominance computation LLVM-IR seems fine, but for all
> > > the incremental stuff you are doing, such input indeed might make sense.
> > > Especially if you are planning to generate many of these test cases
> > > automatically.
> > >
> > > > - My output prints "New Dominator Tree" to times in a row. What is the
> > > > > difference? What is the difference to Inorder Dominator Tree?
> > > > >
> > > >  When you graph files have updates (i numFrom numTo and d numFrom
> > numTo)
> > > > then the first one is the original one and the second one is the one
> > > > after
> > > > applying all the updates.
> > > > Inorder Dominator Tree is the existing DomTree
> > >
> > > Interesting. Probably it is just a testing/debugging tool, but maybe
> > > clarifying this in the output may avoid confusion for others who try
> > > your changes.
> > >
> > > > --
> > > > I used to use it just for visual comparison.
> > >
> > > That's what I did.
> > >
> > > > - How do I get the post-dominator tree with your tool? Do you already
> > > > > have test cases? In fact, normal IR test cases would be really cool.
> > We
> > > > > do not have a lot of test coverage for all the dominance stuff.
> > > >
> > > >  I haven't really played with postdominators yet. Do you have any
> > > >  specific
> > > > ideas on how to test it in mind? And I definitely agree, dominators
> > need
> > > > to
> > > > be tested more thoroughly. I think that because of the manual updates
> > (of
> > > > questionable correctness) and frequent recalculations there must be
> > many
> > > > undiscovered bugs that we just haven't had a chance to observe yet.
> > >
> > > I think we certainly should have standard LLVM-IR style test cases,
> > > where we use -analyze to dump the domtree for a given piece of IR that
> > > clarfies how/what dominator tree is expected for a certain piece of
> > > input and where it is easy for others to add test cases.
> > >
> > > Now, most of the bugs you might expect are likely in the update /
> > > invalidation cycle. What would look very nice and readable to me, is to
> > > write test cases as follows:
> > >
> > > ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \
> > > ; RUN:   < %s | FileCheck %s
> > > ;
> > > ; CHECK-LABEL; delete (bb3 -> bb4)
> > > ; CHECK: <new-dom-tree>
> > >
> > > ; CHECK-LABEL; delete (bb4 -> bb5)
> > > ; CHECK: <new-dom-tree>
> > >
> > > ....
> > >
> > > We could even have a tool that records the dom-tree modification
> > > requests, and dumps a corresponding IR-file.
> > >
> > > Obviously, this is just an idea.
> > >
> > > Best,
> > > Tobias
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > [hidden email]
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
>
>
>
> --
> Jakub Kuderski
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev
Hi Kuba,

On Mon, Jun 12, 2017 at 7:12 PM, Jakub (Kuba) Kuderski via llvm-dev
<[hidden email]> wrote:

> Hi folks,
>
> This summer I'm working on improving dominators during my internship at
> Google. Below is an RFC on switching to dynamic dominators, which you can
> also read as a Google Doc if you prefer so. Please let us know what you
> think.
>
> ~Kuba
>
> =======================================================================
>
> 1. Context
>
> Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the
> (post)dominator tree. The only way to update it is by manually setting IDoms
> which is not obvious in many cases and can be extremely error-prone. And
> because updating it manually is so difficult, programmers tend to just
> recompute it after changing the CFG (by not AU.addPreserved()'ing the
> DomTree). This causes DomTree calculation to fire very often even if only a
> very small portion of it gets really affected by the changes in CFG. As an
> example, when optimizing a Full LTO clang bitcode, DominatorTreeWrapperPass
> alone calls DT.recalculate over 6.5 million times, which takes 20s on my
> machine.
>
> Using an incremental algorithm it would be much easier to keep an up-to-date
> DomTree without custom update logic, which will save us the time currently
> spent during DomTree recalculations and reduce the number of bugs caused by
> manual updates. It would also make it feasible to maintain postdominators
> and use them more broadly, which currently can be too complicated and
> expensive.
>

Another motivating point is that with dominators automatically updated,
the JumpThreading pass can be extended to reason about loops: i.e.,
jump-threading across back-edges of a loop is an important extension
to increase the performance of finite state automata usually implemented
with a loop and a switch stmt within.  Brian Rzycki and I have been toying
with keeping the dominators updated across the JumpThreading pass and
that seemed quite involved with the current implementation of domtree.
I'm glad to see work in this area, and we will help testing your prototype
and patches.

Thanks,
Sebastian
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via 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 <[hidden email]> 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.


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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev


On 06/12/2017 07:58 PM, Sean Silva via llvm-dev wrote:


On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev <[hidden email]> wrote:
Hi folks,
...
 
a) Keep the existing DomTree and gradually replace its uses with the new one. It is possible to convert the DBS-based dominators to the old ones.
b) Replace the existing DomTree with the new, dynamic dominators. Nuke all of the old update functions and replace their uses with the new incremental API in one commit.
c) Replace the existing DomTree with the new one, but keep the old API around and mark it as deprecated. If someone invokes one of the old update functions, mark the the additional information as invalid for dynamic deletions. Follow the pessimistic but correct dynamic deletion path if the additional information is marked as invalidated. Gradually modernize the projects to use the new API instead and then remove the old update functions.
 
Maintaining the old DT and the new one simultaneously seems like a waste of time as the DBS offers better or similar performance to the existing SLT-based implementation.
The problem with replacing the old API with the new one is that it’s used in many places (~100) across the project and I believe that doing that all at once would be tricky to get correct. Gradual update seems much easier to ensure correctness and the transitional API (invalid additional data check) is trivial to implement. Because of that, I propose to follow the option (c). 

(c) sounds like the best choice to me too. That would also allow fixing dominator verification failures first, giving a nice immediate benefit to motivate and kickstart the transition.

+1

 -Hal


-- Sean Silva
 



[1] Georgiadis et al., An Experimental Study of Dynamic Dominators, https://arxiv.org/pdf/1604.02711.pdf
[2] llvm-dominators LLVM fork on Github, https://github.com/kuhar/llvm-dominators
[3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf p. 38

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev
In reply to this post by Hal Finkel via llvm-dev


On Wed, Jun 21, 2017 at 6:00 PM, Hal Finkel <[hidden email]> 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 <[hidden email]> 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.


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.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [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 <[hidden email]> 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 <[hidden email]> 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.


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

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Loading...