[GSoC] Dominators project proposal

[kuhar]

Summary

The GSoC project proposal I came up with -- to implement a single updater class for performing incremental dominator tree updates. The main goal is to make the use of the updater easier and to simplify existing APIs. The secondary goal is to perform cheaper PDT updates when having and already updated DT available.

I want to make sure that the proposal and the way it's written is reasonable before going forward with it.

[grosser]

Very nice! I like the proposal!

[davide]

lg, thanks for taking care of this.

[brzycki]

+1 from me. I'd love to see a single interface for all Dominator-related analysis or updates. This idea reminds me (a bit) of a comment @dberlin made in D43173 about an interface similar to getBestSimplifyQuery to reduce the number of functions that need explicit pointers to a DT, DDT, PDT or other analysis object. I don't quite understand how this would work but I wanted to bring it up in case the work could be done in a way to anticipate such an interface to reduce re-work.

OpenProjects.html

       <ul>
   <li><a href="#replace_binary_utilities">Command line replacements for GNU Binutils</a></li>
       </ul>
+      <ul>
+        <li><a href="#llvm_domtree_updater">Implement a single updater class for Dominators</a></li>
+      </ul>
     </li>
     <li>
     <a href="http://lldb.llvm.org/"><b>LLDB</b></a><ul>

   <p><b>Desirable skills:</b> Intermediate knowledge of C++.</p>
 </div>
 
+<!-- *********************************************************************** -->
+<div class="www_subsubsection">
+  <a name="llvm_domtree_updater">Implement a single updater class for Dominators</a>
+</div>
+<!-- *********************************************************************** -->
 
+<div class="www_text">
+  <p><b>Description of the project:</b> LLVM provides an implementation of the (Semi-NCA) Depth Based Search algorithm to incrementally update Dominator and PostDominator Trees. It it possible to use it directly or through a lazy updater object -- DeferredDominance. The current API is fragmented and different analyzes, transforms, and utilities (e.g. Local.cpp, LoopUnroll.cpp) have to decide how to perform incremental updates.
+  </p>
+  <p>The fix would be to design and implement a new class for abstracting away how tree updates are performed (eagerly or lazily) and which trees are actually being updated (none, only DomTree, only PostDomTree, both). With this, performing faster incremental updates will become possible by first updating DomTree, and then using the result to prune unnecessary updates to PostDomTree.</p>
+
+  <p>Expected Results:
+    <ul><li>Create a new class that will store Dominator Trees to update and allow to specify update policy.</li></ul>
+    <ul><li>Convert existing API to use the new updater object instead of working directly with DomTree/DeferredDominance.</li></ul>
+    <ul><li>Design and implement a new algorithm to prune unnecessary PostDomTree updates based on updated DomTree.</li></ul>
+    <ul><li>(Optional) Explore more strategies for performing lazy updates (e.g. by exposing .dominates() and performing updates when called).</li></ul>
+  </p>
+  <p><b>Confirmed Mentor:</b> Jakub Kuderski, Tobias Grosser (?)</p>
+  <p><b>Desirable skills:</b> Intermediate knowledge of C++. Familiarity with basic tree/graph algorithms and data structures.</p>
+</div>
+
 <!-- *********************************************************************** -->
 <div class="www_subsection">
   <a>Others</a>