Hi Chijun,
Great, seems like you did a lot of progress and understand the issues quite well!
I have done some early sketch on the API of the new updater class.
From my current understanding, to solve the fragmentation problem of
the API, the new class first, need to maintain the DomTree and
PostDomTree class and deprecate the DefferredDominance class.
There are a couple of possibilities here. First, we can come up with a new updater class and gradually replace DefferredDominance and and the basic incremental update API with it (.applyUpdates()). During this process all the classes can coexists which should make it easier to make the transition smooth instead of risking breaking multiple places in LLVM at once. The other approach would be to modify DefferredDominance and make the transition happen in place, which should be also doable. I think that for prototyping it would be easier to clone DefferedDominance and replace one use of it at a time with the new updater class.
Second, the API should be something
looks like DT.update(updateStrategy::lazy,updateKind::delete,A,B) or
DT.applyUpdates(updateStrategy::lazy,{{ updateKind::delete,A,B }}).
Having update strategies as enums sounds very reasonable, but I’d rather we didn’t teach the DT to do it. I think the existing interface (and the header file) is already pretty large and it should make sense to have a separate class for the updates that the DT and PDT don’t know about at all. I suspect that the only thing that might be required would be to expose some additional functions from DT and PDT for update pruning, but I’m not sure about it at this point.
Third, the API can auto flush() when a query happens, which can make
the code easier to maintain. Forth, the updater class can hold an
optional PostDomTree and make its status synchronize with the
corresponding DomTree (can use lazy updates until query happens) and
use information from the DomTree to prune useless updates.
Sounds good. One issue we might hit and need to be care about is not to have both the updater class and DT in a single function somewhere in the codebase. In such cases it is possible to have some pending updates that will eventually change DT, but do .dominates() queries on the outdated tree. However, this problem exists even today to some extend (with DT and DDT) and I don’t think it’s very serious.
After I read the comments on D41302[1], in which Dave(dmgreen)
mentions there is a need to preserve the PostDomTree in the future. I
am wondering whether we need to preserve a PostDomTree all the time in
the new class?
I think that at some point we realized that preserving PDT everywhere is quite challenging with the current data structures in LLVM. The issue is that for postdominators you have to access predecessors, which requires you to track uses instead of just looking up the last instruction within a single basic block. What’s more, changes anywhere near terminator instructions in IR can cause PDT to look completely different every time you do it. To do it efficiently, you have to be very lazy about updates and have a good strategy for pruning. This project should be a huge step towards it, but I think that we have to start with optional PDT anyway.
Danny and Chandler (cc’d) should remember more about the different directions that were considered here.
Moreover, as mentioned in the open projects page[2],
the API should be able to specify which trees are actually being
updated (none, only DomTree, only PostDomTree, both), while I doubt
that if the updater initially holds both the DomTree and PostDomTree
for example, it is inappropriate to update only the PostDomTree, which
will just break the synchronization between the two trees (DomTree and
PostDomTree). Please correct me if I am wrong. 
My intention in the proposal was to say that the updater class can hold (or not) two kinds of domtrees – DT and PDT, and the updates should affect whatever is currently available. I hope this is what you are asking about. Breaking synchronization between two trees inside the updater class sounds like something we really want to avoid.
Sincerely,
Jakub