Would it be possible to add a verifyAnalysis function to MLI and check if a freshly calculated one matches the 'preserved' one?

Looks good to me.

@arsenm @hiraditya
Are you fine with committing the patch as-is and exploring using the incremental updater later?

Fix a typo

I'd like to commit this simple fix as-is, make sure no buildbots complain, and then introduce a proper incremental updating in a later revision.

In D68154#1687316, @kuhar wrote:

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

Thanks for the comments, @arsenm and @hiraditya.

The changes to verifier caught a MDT bug on AArch64:

test/CodeGen/AArch64/tailmerging_in_mbp.ll -mtriple=aarch64-eabi -verify-machine-dom-info 
DominatorTree is different than a freshly computed one!
	Current:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 25 slow queries.
  [1] %bb.0 {4294967295,4294967295} [0]
    [2] %bb.1 {4294967295,4294967295} [1]
      [3] %bb.2 {4294967295,4294967295} [2]
        [4] %bb.3 {4294967295,4294967295} [3]
          [5] %bb.7 {4294967295,4294967295} [4]
          [5] %bb.4 {4294967295,4294967295} [4]
            [6] %bb.5 {4294967295,4294967295} [5]
              [7] %bb.6 {4294967295,4294967295} [6]
    [2] %bb.8 {4294967295,4294967295} [1]
Roots: %bb.0

Seems fine to me. Thanks for the fixes.
Please wait some time and see if others are OK with this change too.

Fix a typo.

Small cleanup.

Looks good. Thanks!

The non-static-analyzer bits look good to me, I added a few nits.

Looks good now. I added a few nits inline.

@Szelethus

That wasn't going to happen, since the GraphDiff object has to be used in the getChildren function. I made llvm::IDFCalculator::getChildren virtual, is this okay?

I also have a local branch on which I used std::function (had to be used in order to pass a lambda with a non-empty capture list) and kept everything non-virtual, but I read somewhere that std::function is heavy-weight. Which solution is better, if any?

I'd expect the getChildren to be potentially performance-sensitive and am worried about switching it into a virtual call or another indirection through std::function. Do you have some evidence that this does not affect performance?

In D63389#1546196, @Szelethus wrote:

Thanks!

In D63389#1546185, @kuhar wrote:

Looks great, I'm only not sure about the GraphDiff removal.

Practically revert D50675. This was done because GraphDiff is only specialized for BasicBlock, and wouldn't be used for clang::CFGBlcok. Interestingly, it wasn't even used at all: In D45299, it was used at a certain point (https://reviews.llvm.org/D45299?id=160698) but was ultimately removed. Is this okay?

@asbirlea?

If having a virtual function isn't too painful, it'd be easy to reimplement it.

Looks great, I'm only not sure about the GraphDiff removal.

You can easily get CD by calculating the PostDominanceFrontier. LLVM implements a templated IDF (Iterated Dominance Frontier) construction.
A native implementation for llvm ir for reference, if you need:

• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc

Thanks, I think this is a much better solution than directly hacking on DomTreeBuilder.

Like I mentioned in another thread, I really dislike this approach. The single source of truth about graph traversal in dominators is the ChildGetter structure that internally uses children and inverse_children, and expects them to only return pointers to actual successors/predecessors. It's very weird that children and inverse_children return nullptrs -- they are not valid graph nodes, and I don't see why this would be desired, despite how unreachable regions are represented in the CFG.

In D61055#1481983, @dmgreen wrote:

I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXPENSIVE_CHECKS or opt-in with Fast.

Do you mean removing the default entirely? To makes it explicit.

Whatever we do in the long run needn't be done here, and making this Fast and behind expensive checks is a definite improvement. (I think Full is still more expensive than necessary, even for an expensive checks build).

Yes, I think expensive checks are sufficient. If you think there's a strong need to assert in debug builds, maybe try the Fast level for now and remove it after a few weeks, once you gain confidence in the code or someone complains the check is too slow?

In D61055#1481841, @dmgreen wrote:

But I was not aware that Fast used to be the default, and was still quite slow. I was under the impression that the problems in the past were to do with it using Full under expensive checks, and that Fast was fairly quick (quick enough for an asserts build).

It of course depends on exactly location, but we found that Fast is generally not quick enough to be run during a typical loop pass (on large files, or loopy code from non-clang frontends). I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXEPNSIVE_CHECKS or opt-in with Fast.

In D61055#1481740, @yrouban wrote:

In D61055#1481627, @dmgreen wrote:

Hello. I think it's fine to always use DominatorTree::VerificationLevel::Fast, the others are more about checking that the DomTree construction code was correct. Fast will compare against a new tree, so for updates will check the the tree is correct.

may be we have to set Fast by default instead of Full?

bool DominatorTreeBase<>::verify(VerificationLevel VL = VerificationLevel::Full) const {

IMO you could introduce df_iterator_tree_storage by a slight modification to the default one:

// df_iterator_storage - A private class which is used to figure out where to
// store the visited set.
template<class SetType, bool External>   // Non-external set
class df_iterator_storage {
public:
  SetType Visited;
};

OK, I can see that this is exactly what you want to avoid in the related revision. In this case, isn't it possible to provide a dummy storage to DepthFirstIterator and use it to efficiently traverse trees?

Would it make sense to use one of the llvm graph iterators and have descendants_begin() and descendants_end() functions instead?

If you think you there's enough evidence that is_permutation can cause a problems here, go ahead with the current patch.

In D58373#1406843, @MaskRay wrote:

In D58373#1402235, @kuhar wrote:

Roots.size() is only > 1 for the PostDominatorTree, and I'd expect it to be small (< 100) on virtually all functions. is_permulation was used in the original code because it doesn't allocate and should be cheaper for small trees.

Do you have some statistics on the size of Roots? At what size does SmallPtrSet start to outperform is_permuatation?

Thanks for the empirical data (<100). I find SmallPtrSet<void *, 4> starts to outperform std::is_permutation when there are about 16 elements on my machine. It may be 2x slower (should be larger, but I put it in a loop and the loop itself has some costs) when there is only one root. So the benefit to use a SmallPtrSet here is just to filter out some unlikely cases (>1000 roots) and to clear up my doubts when I see that verifyRoots claims to be O(N)...

It seems it would be best to create a small helper function that does permutation check using std::is_permuatation for small arrays and uses SmallPtrSet for the rest.

In D58170#1404458, @NutshellySima wrote:

In D58170#1404415, @kuhar wrote:

I think the default for applyUpdates should be the strict mode; any code that relies on imprecise information about updates should make it clear by using some longer name, like applyUpdatesRelaxed.

I'm fine with making applyUpdates default to strict mode to make it consistent to other parts of the codebase and encourage people to use the strict one which does not have extra overhead on scanning the CFG.

But if the user follows the rules on using applyUpdatesRelaxed/Checked, DTU is also guaranteed to have precise information on updates.

I think the default should be the strict mode; any code that relies on imprecise information about updates should make it clear by using some longer name, like applyUpdatesRelaxed.

In D58327#1403532, @MaskRay wrote:

And how can I benchmark dynamic dominator tree? CalculateFromScratch is easy to benchmark as I can just repeatedly run the function analysis domtree and discard the result but I don't know how for the dynamic case...

The best method I came up with is to instrument the updater primitives (applyUpdates, insertEdge, deleteEdge, recalculate, etc.), and measure time within the running optimizer. It should be best to get some big bitcode file and run opt with O3 on it. clang is reasonably sized in this configuration, you should also have luck with webassembly and rippled. If you are with google, you can try some bigger internal targets (there is a script to compile a given target to bitcode).

Great, thanks for putting effort into this and the related patches