[llvm-dev] RFC: Dynamic dominators

[Sebastian Pop via llvm-dev]

Hi Kuba,

On Mon, Jun 12, 2017 at 7:12 PM, Jakub (Kuba) Kuderski via llvm-dev
<llvm-dev at lists.llvm.org> 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