[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.

www/trunk/OpenProjects.html

<li>
         <li><a href="#codegen_testing2018">Improve code generation testing</a></li>
       </ul>
       <ul>
         <li><a href="#llvm_optimized_debugging">Improve debugging of optimized code</a></li>
       </ul>
       <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>
       <li><a href="#lldb-data-formatters">Implement a DSL for LLDB data formatters</a>
       </li>
 
       <li><a href="#lldb-reimplement-lldb-mi">Reimplement lldb-mi on top of the
           LLDB public API</a>

 <div class="www_text">
   <p><b>Description of the project:</b> The llvm project has a lot of tools that can be used to inspect binaries, just as any other toolchain project does. However, many people are accustomed to existing tools and so having a command line compatible shell and we'd like to make that easy for them. Bonus points for producing similar output so that automated tools can continue to work reliably.
   <p><b>Expected Results:</b>This project has one goal - produce binary tools that are drop in compatible with GNU binutils. The student will be expected to focus on a single tool at a time so that we can count each one as "done" as much as possible.
 
   <p><b>Confirmed Mentor:</b> Eric Christopher and Sterling Augustine</p>
   <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> Dominance relation is used widely in many compiler analyses and optimizations. 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>
 </div>
 <!-- *********************************************************************** -->
 
 <!-- *********************************************************************** -->