In D56284#1348747, @anna wrote:

I've got a naive question about the DTU: Does the automatic updater handle the ImmediateDominator "automatically" for the remaining nodes in the dom tree once identify that one of the nodes in the DT has a change in IDom?

Exactly. Given a set of CFG updates, if figures out how to change the DomTree and PostDomTree such that they match the CFG.

In D56284#1348681, @anna wrote:

the same bug can happen with:

1. latch exit
2. non-immediate successors of latchexit/otherexit.
   
   I have simplified test cases for each of these and we need a more general fix. Working on this.

In D56284#1345811, @anna wrote:

In D56284#1345766, @kuhar wrote:

@anna Can this be rewritten to use the DomTreeUpdater utility?

@kuhar, I have not looked at the DTU uttility yet, but I'd think it can be rewritten (unless there are some limitations for the DomTreeUpdater utility). However, that would be a large enough change and I think it's better to do it as a separate change at a later point rather than as part of fixing this bug. Also, there are enough DT updates through out this code that it will take a while to get through the whole process of porting over for runtime unrolling.

@anna Can this be rewritten to use the DomTreeUpdater utility? We have large number of examples in the codebase already, so the question is whether this affects the performance in this case. Historically, we had tons of bugs in manual DomTree updates and I'd rather we replaces as much as possible using the incremental updater.

In D54730#1304696, @efriedma wrote:

Fundamentally, does this have to be an expensive operation? It seems like there should be some way to keep a "local" operation like this from propagating across the entire tree.

In D54730#1304463, @NutshellySima wrote:

Though I don't have bitcode samples to reproduce your findings, I guess three times faster is caused by the DomTree is consuming a lot of time in DeleteUnreachable().

Maybe we can put some high level APIs that have these best practices inside DTU such as something like updateAfterSpliceBlocks and updateAfterChangePredecessorTo or just add a sort after running updates legalization. :)

We experimented with different ordering of updates before, including scheduling deletions before insertions, but didn't discover any promising strategies. Because of that, updates are performed in the exact order they were scheduled (except optimizing out trivially redundant ones).

Looks good to me now, thanks for the fixes! You may want for somebody else to take a look at it, though.

In D53245#1276939, @NutshellySima wrote:

Since bug 37929 is a regression in version 7.0, should we backport this patch into branch 7.0.1 later (maybe November) if there isn't anyone reporting issues on this patch?

LGTM. Thanks for looking into this!

In D53245#1274293, @kuhar wrote:

In D53245#1274287, @brzycki wrote:

I'd still like to see the constant as a hidden command line argument cl::opt(). Otherwise I think this is an excellent patch with considerable compile-time speedups. Nice work @NutshellySima .

The issue I find with cl::opt here is that this is a generic class that may not necessarily have a corresponding cpp file -- there can be multiple clients to GenericDomTreeConstruction, each with different requirements. Because of that, it's not clear to me in which translation unit one would put cl::opt for the constant in.
Is that a solved problem somewhere else in LLVM? I'm not familiar with using cl::opt in header files.

In D53245#1274287, @brzycki wrote:

I'd still like to see the constant as a hidden command line argument cl::opt(). Otherwise I think this is an excellent patch with considerable compile-time speedups. Nice work @NutshellySima .

In D53245#1266421, @NutshellySima wrote:

@kuhar , here is the statistics for k*α>n:

Awesome, thanks for the numbers. It's much easier to reason about it this way. But I'm a bit confused by why you measured it like this. Can we have statistics with respect to nodes visited during DFS? That should be highly correlated and give us more confidence in the measured times.

I think maybe "40" is a better choice?

30 seems best to me :)

In D53245#1265481, @NutshellySima wrote:

Do you think for the unittests of the incremental updater, the updater should directly apply updates on a small k (don't do recalculation with few updates) or n (don't do recalculation on a small graph)?

I think that for small n it shouldn't recalculate when k < n.

In D53245#1265454, @NutshellySima wrote:

I have tested heuristic k>n/α with α=10/40/65/70/75/80/100/300/1000 on clang.bcs. (But I didn't save them to a file :\) 10/1000 produce very bad result. ("10" is better than the current implementation). 300 produces better result than 1000. 40/100 produce better ones than 10/300/1000. And 65-80 don't make much difference and produce the best results among all αs I selected.

I'd be very interested to see the numbers for these constants.

In D53245#1265405, @NutshellySima wrote:

For k>n you mentioned, I think you mean k>n/α (α is a constant) because for the reproducer in 37929, the minimum value of α to make the time consumed by clang acceptable is about 3 (α should definitely be larger than 3). But selecting a higher value like "75" can also boost other inputs more (about 2x~4.5x on clang*.bcs).

OK, makes sense if that the case in the bug report.

In D53245#1265080, @NutshellySima wrote:

In D53245#1264864, @dmgreen wrote:

Interesting. Nice improvements. What about small trees? It would seem that any tree less that 75 nodes would always be recalculated. Do the timings you ran include things to show that this is better? Or was that just looking at larger trees at the time?

I haven't conducted dedicated tests on graphs with the number of vertices less than 75, but among all the domtrees recalculated in the two clang-*.bc I mentioned above, there are approximately 63% of them has an n smaller than 75.

I'd be much more comfortable if this change didn't always recalculate for graphs smaller than 75. I think there is a lot of value in making sure the incremental updater is behaving correctly on small examples (e.g., existing unit tests, most regression tests, etc.). If for some reason it stops working, it will be much easier to detect and fix it on these small examples.

In D53245#1264506, @NutshellySima wrote:

In D53245#1264493, @kuhar wrote:

• For the constant "650", I used the 2nd reproducer in bug PR37929 and collected some statistics on the size of the updates after legalization and the time used by applying updates. The statistics shows that the time complexity is about Θ(k^2.4) (let k be the size of the update vector after legalization) [I have just checked the original paper, it is O(m min{n, k} + kn), so about Ω(k*(k+n)) in the case of the reproducer] and it seems that at least for a CFG size no larger than the one in PR37929, "650" is a reasonable value that the time used by recalculating is sure to be less than applying updates directly. (I think there sure should be some better heuristics deciding this.)

Thanks for the detailed explanation. This is what I expected. I don't it's enough to use 650 in the code without any explanation or justification -- even if it works in practise, I think it deserves a comment.

• It is definitely better to get it related to the tree size but I'm lack of inputs with different CFG sizes to experiment on.

You can take intermediate bitcode files when doing full-LTO built using lld. I think the command that does the trick is --save-temps=DIR or similar.

• I acknowledged this as an issue of the incremental updater not handling a huge update vector correctly; It definitely should fallback to recalculating if it is much faster. I believe this constant is related to the size of updates after legalization so I put it in the incremental updater. [Currently, there is a similar functionality in DTU which is Ω(n^2) and I believe it is slow and (redundant if JT submits updates normally) so I am considering removing it from DTU, then it is impossible to know the size of the legalized update vector]. Besides, it can also benefit other places not using the DomTreeUpdater.

I see. If we expect to see many redundant updates, then it makes sense to check that after legalization.

Thanks for looking into this. A couple of high-level questions:

• how was the constant "650" picked? Is it just playing with different values and choosing something that seemed reasonable?
• why is the threshold independent of the tree size? Intuitively the policy could be to recalculate if the number of updates is greater than some multiple of size. Maybe we can refer to the average-case complexity from Lucuas' paper?
• why do we want to put it in the incremental updater instead of the DomTreeUpdater class?

Thank you for the comments, Richard!

In D51200#1223752, @rsmith wrote:

+rjmccall for CodeGen changes

Rename missed CallInlineKind parameters to CIK

Fix naming and add more tests.

One extra question: do you think this deserves a separate RFC?

Disclaimer: I'm a Clang newbie and I'm not sure if that's a good way to implement these intrinsics. I'm not sure about the following things:

• The new enum CallInlineKind may not be in the right place
• Not sure if adding the extra parameter to EmitSomething methods is the cleanest thing possible -- some functions have it now, some don't, and it makes argument lists longer
• Not sure if just adding an extra attribute at each callsite is enough -- I'm not sure what is supposed to happen when there are conflicting inline attributes at call sites and function declarations (e.g. __builtin_always_inline and __attribute__ ((always_inline)))
• I don't know how to handle constexpr functions
• I don't know how to implement it for constructor calls

Seems fine

In D50717#1199288, @dmgreen wrote:

I'm no expert, but I thought that SmallPtrSet->erase(BB) would treat BB as an opaque value that it removes from it's set, not accessing it's content in any way. You may be right about the eraseFromParent invalidating things though.

It's certainly much better this new way :)

In D50717#1199198, @dmgreen wrote:

I guess because it's only erasing it from a SmallPtrSet, it's not actually _using_ it, but this looks like a very sensible change.

Looks fine.

LGTM

Thanks for the changes. LGTM.

In D50479#1194111, @asbirlea wrote:

I agree that long term this can and should be reused in DomTree, so I'm trying to make it have the right functionality.
Another possibly related issue, is that I'm not reversing the children, as in DomTree, not sure the reason behind that one.

Sure. The children are being reversed to preserve the successor order in DFS, which uses stack and reverses them (again) internally. But this reverse can be moved somewhere else and you don't have to worry about it.

In D50479#1194111, @asbirlea wrote:

Another issue with the above traits: is there a way to avoid some of the code duplication, since the only differences are the bool arguments to GraphDiff and succ/pred iterators?

One thing that is not clear to me is how you decide whether to apply the updates on top of the current CFG or to reverse-apply them. DomTreeConstruction needs the latter, but I don't know what makes sense in your use-case.

Thanks for the changes!

Looks good, thanks for the patch!

Nit: It's removal and not deprecation.
Looks good otherwise.

Looks fine except for the test IR.

@chandlerc OK, now I finally understand why it's possible to get confused here. I put a patch with modified documentation here: D49944.

@chandlerc FYI, all existing uses of the 'raw' api (DT.insert/deleteEdge, DT.applyUpdates) are going to be replaced with the new unified API after branching to 8.0. @NutshellySima is working on this.
The plan is also to hide insert/deleteEdge completely, so that we won't have bugs like this in the future.

This case requires batch updater. It's always surprising that these kinds of bugs can stay undetected for months.

Thanks for the changes, Chijun!

Thanks for the comment!
LGTM.

LGTM, but please wait to see if @brzycki has some comments before submitting the patch

Looks like a nice improvement!

A general high-level question/suggestion: would it be possible to split this patch such that we don't change all of the uses of DDT and plain updates at once? I'm afraid this can subtly break in many places, and the patch will have to be reverted a couple of times before you get them right. If you do it with more granularity, then it should be easier to land each part and test it in isolation.
Is it possible, or do you have a dependency on the utility functions from Local.cpp and other helper files?

Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.

Perhaps it would make sense to expose a similar function for the Eager strategy?
And I would make it sorter, so just isLazy and isEager -- shouldn't make anything more ambiguous IMO.

One thing that is not clear to me is whether it's work to replace plain updates (DT->insert/deleteEdge, DT->applyUpdates) with DTU when it's clear that both are going to be functionally the same. The overhead of constructing DTU is probably negligible, but it's more verbose and I'm not sure what benefit it brings.

LGTM. Should make life easier.

Looks good to me now. Thanks for making all the fixes!

Looks almost ready to me. Found just a couple of nits.

In D48383#1145727, @brzycki wrote:

2. Add insertEdgeRelaxed() and deleteEdgeRelaxed() to cover the behavior of the original DeferredDominance's insertEdge()/deleteEdge().

Maybe it'd be better to have a default boolean third variable?
deleteEdge(BasicBlock *From, BasicBlock *To, bool Relaxed = false) { ...