[DTU] Refine the document of mutation APIs [NFC] (PR40528)

[NutshellySima]

Summary

It was pointed out in Bug 40528 that it is not clear whether insert/deleteEdge can be used to perform multiple updates and a comment in D57316 reveals that the difference between several ways to update the DominatorTree is confusing.

This patch tries to address issues above.

[NutshellySima]

Fix a typo.

[kuhar]

Nice, thanks for working on this!

As a general direction, I think we should try to minimize the amount of documentation about DT updates -- the number of different ways and all their preconditions are confusing.

I'd like to first go forward with this patch, after minor corrections, and then mark insertEdge/deleteEdge as deprecated, migrate their uses to applyUpdates, and later remove it entirely. The, we can note put a note in GenericDomTree saying that for the llvm trees, DTU should be used instead.

llvm/include/llvm/Analysis/DomTreeUpdater.h

93

I'd add some indentation.

94

Instead of referring to the DT incremental updater, I'd say that it performs updates immediately.

101

Instead of listing this as another method, I'd mention that even though GenericDomTree provides these update primitives, it is recommended to use DTU with llvm::DomTree and llvm::PostdomTree. I think the less text here the better.

106

I'd completely omit the mention of the 'manual' update API -- there are very few legitimate reasons to use it now

109

I think this is fine with the eager strategy.

138

update that the DomTreeUpdater or the DominatorTree already acknowledged.

update that has already been applied.

144

like above

200

under the

[brzycki]

In D57881#1388903, @kuhar wrote:

Nice, thanks for working on this!

Agreed, thank you!

I'd like to first go forward with this patch, after minor corrections, and then mark insertEdge/deleteEdge as deprecated, migrate their uses to applyUpdates, and later remove it entirely. Then we can note put a note in GenericDomTree saying that for the llvm trees, DTU should be used instead.

+1
The insertEdge() and deleteEdge() direct calls require so much manual fix-up at the call-sites I'd really prefer to see them go away. It also provides a cleaner interface to DTU as a whole, opening up opportunities to alter the underlying class without changing call semantics.

[mkazantsev]

llvm/include/llvm/Analysis/DomTreeUpdater.h

128

That looks *highly* fishy. Between which two points we should have exactly one update?

For example, if we use eager strategy and we need to delete 10 edges and insert 10 other edges, is that guaranteed to work if we consecutively make 1 CFG update followed by 1 DT update, and do so for every edge? Can we interpret it as making exactly one update 20 times over?

Is that exactly one update between two flushes for lazy strategy?

[brzycki]

Hello @mkazantsev.

That looks *highly* fishy. Between which two points [of insertEdge()] we should have exactly one update?

If you are using the Eager strategy these updates will be immediately applied to the DT and PDT internal to the DTU class. As the comment states there are internal checks of the CFG to determine if the insertion is valid. Because DT, PDT, and CFG are three distinct and separate structures we have to treat the CFG as the canonical shape of the IR. In Lazy strategy mode the update is simply queued until the next flush event.

For example, if we use eager strategy and we need to delete 10 edges and insert 10 other edges, is that guaranteed to work if we consecutively make 1 CFG update followed by 1 DT update, and do so for every edge? Can we interpret it as making exactly one update 20 times over?

Yes, if and only if the state of the CFG is considered valid after each single deletion and insertion event (see number 3 below). For most cases it's recommended to use the applyUpdates() method in this case for several reasons:

1. There may be updates that cancel each other out {Insert, A, B} ... {Delete, A, B}. It is much more efficient to detect these before altering the DT and PDT as a no-op.
2. It's often the case at the call-site the code iterates over dozens of edges and needs to alter several of them in the CFG. Because the DTU class requires a stable CFG state to check valid insertions and deletions it's often better to send the updates to DTU after all the changes are done.
3. There are cases when it's impossible to make the CFG correct for a single edge change. There are often cases where 2-4 edges have to be altered before the CFG is considered valid. In this case you'll actually cause a DTU assert if you attempt to perform insertEdge() for every edge because it will fail when attempting to check the insertion in the CFG.
4. Single calls to insertEdge() and deleteEdge() incur function call overhead and multiple checks that are aggregated in the case of a single call to applyUpdates().

There are valid reasons to use insertEdge() and deleteEdge(). The primary reason is the caller needs to only make exactly one change to DTU. The call to applyUpdates() has a bit of extra overhead to sanitize the update list and only makes sense if there are 2 or more updates.

Is that exactly one update between two flushes for lazy strategy?

I'm not sure how to answer this question. The idea of exactly one update for Lazy strategy is much more difficult to determine. The update may be a no-op. It may also be enqueued only to be removed by a later update before a flush event as a new no-op pair. The update might be invalid but DTU was called through one of the *Relaxed() methods.

I will say that if you do the following:

DTU->flush();
// Alter CFG to add a new edge A -> B
DTU->insertEdge(A, B);
DTU->flush();

Will perform exactly one update at the DTU level. This may cause two sub-updates if both DT and PDT are not nullPtr. Each of these sub-updates may incur dozens of edge changes in their respective DominatorTree graphs.

[NutshellySima]

llvm/include/llvm/Analysis/DomTreeUpdater.h

109

Considering updating DT/PDT under Eager mode is an idempotent action, I think it is applicable to delay the update validity scanning under Lazy mode to the time submitting updates to DT/PDT to avoid some fishy problems involved in JT before and also make applyUpdates() under Lazy mode also idempotent without using "point-based updates" which can have potential performance issues.

128

When using DTU Eager UpdateStrategy or using DT/PDT directly, updating a DominatorTree doesn't follow associative law of conjunction because the internal updating logic of DomTree will do a graph search on the corresponding CFG each time you call the mutation APIs.
For example,

// Don't make any change to CFG
// Considering Eager DomTree updates is idempotent
DT.insertEdge(Foo, Bar); // Assert here if there is no Foo->Bar in the original CFG
DT.deleteEdge(Foo, Bar); // Assert here if there is Foo->Bar in the original CFG

Considering insertEdge/deleteEdge can bring confusion to devs, I'll consider remove those 2 APIs but

// Don't make any change to CFG
// Considering Eager DomTree updates is idempotent
DT.applyUpdates({Insert,Foo, Bar}); // Assert here if there is no Foo->Bar in the original CFG
DT.applyUpdates({Delete,Foo, Bar}); // Assert here if there is Foo->Bar in the original CFG

is also not OK overall.

[mkazantsev]

llvm/include/llvm/Analysis/DomTreeUpdater.h

128

I mean the following scenario:

1. Delete A->B in control flow
2. DTU.deleteEdge(A, B)
3. Delete B->C in control flow
4. DTU.deleteEdge(B, C) ...

I can have two different interpretations of that:
a) It is not supposed to work under any strategy because I have more than 1 deletion.
b) It is only supposed to work under Eager strategy because at every point I make exactly one CFG update followed by DT update, and it is not supposed to work under Lazy strategy because I have more than 1 deletion.

From this comment, I cannot figure out which interpretation is correct (if any).

[NutshellySima]

llvm/include/llvm/Analysis/DomTreeUpdater.h

128

DTU can work in the scenario you mentioned.
The precondition you call any mutation API (insertEdge/deleteEdge/applyUpdates) is that the current CFG is the same as (the CFG which DTU is in sync+updates submitted).
So,

// CFG state a), DTU is now in sync with CFG state a)
1. Delete A->B in control flow // CFG state b)
2. DTU.deleteEdge(A, B) // `CFG state b)` matches `CFG state a)-Edge(A, B)`, so it's legal. DTU is now in sync with CFG state b)
3. Delete B->C in control flow // CFG state c)
4. DTU.deleteEdge(B, C) // `CFG state c)` matches `CFG state b)-Edge(B, C)`, so it's legal. DTU is now in sync with CFG state c).

The above scenario works under both Eager and Lazy modes.

You can also submit updates under *only* Lazy mode like:

1. Delete A->B in control flow
2. Delete B->C in control flow
3. DTU.deleteEdge(A, B)
4. DTU.deleteEdge(B, C)

But I don't think it's valuable to document this difference between Eager and Lazy mode because it will only cause confusion to others. I believe the aim of the document of DTU is to make a uniform rule to use both Eager and Lazy modes to encourage us to write code that is fully compatible under both modes, i.e. hiding the difference between them.

[mkazantsev]

llvm/include/llvm/Analysis/DomTreeUpdater.h

128

This precondition you've mentioned should be met at *different* points under Lazy and Eager strategy. We DO NOT need this precondition after each insert/deleteEdge under Lazy strategy, we only need it when we flush. We DO need this precondition after each insert/deleteEdge under Eager strategy.

If I understand you correctly, there are actually two rules:

1. Under the Eager strategy, flush is done after every insert/deleteEdge. Under the Lazy strategy, it should be called explicitly.
2. By the moment when we make flush, the current CFG is the same as (the CFG which DTU is in sync+updates submitted).

This difference is important, and lack of it in documentation was the motivation for PR40528. I think it should be documented.

[NutshellySima]

1. Add documents on flush APIs and clarify the precondition when flush APIs are called.
2. Add information on recalculate().
3. Add information on the invalid updates removal feature. (applyUpates())
4. Remove documents on internal details which API users don't need to know about.
5. Mark insertEdge*()/deleteEdge*() as deprecated.
6. Address other comments.

[NutshellySima]

llvm/include/llvm/Analysis/DomTreeUpdater.h

109

I did an experiment on submitting updates already applied to DT, but I observed 1 assertion and 2 crashes running check-llvm. I guess it's because of this piece of code. And it is also helpful to make DTU deduplicate reliably (see D58170). So I keep this note.

[kuhar]

Looks better now, found just a couple of nits.

llvm/include/llvm/Analysis/DomTreeUpdater.h

88

nit: s/APIs/API

91

DominatorTree and PostDominatorTree?

95

s/call flush APIS/call the flush function

102

s/Though/Although

122

s/i.e./i.e.,

138

Please mark the method with: LLVM_ATTRIBUTE_DEPRECATED
This can happen in a separate patch.

148

I thought that we still need the relaxed version in order to make JumpThreading code happy? Should it be deprecated?

157

Use LLVM_ATTRIBUTE_DEPRECATED

167

like above

[NutshellySima]

llvm/include/llvm/Analysis/DomTreeUpdater.h

148

I think it is not needed to preserve the relaxed version because JT also submits invalid updates when calling applyUpdates(). And I believe D58170 can solve most of the problems in JT by making use of the extra information inferred from the fact that JT only submits updates that didn't happen but never submits updates that are already applied.

[brzycki]

llvm/include/llvm/Analysis/DomTreeUpdater.h

148

I hope you are correct @NutshellySima . I never wanted to add the *relaxed() methods but there are situations in JumpThreading where we run for a very long time before calling flush(). For some F I was unable to detect all invalid cases.

It's probably worth testing to do so, although it's been quite a long time for me to recall exactly which testcases caused problems.

[mkazantsev]

LGTM. Thakns a lot for doing this!

[NutshellySima]

Address comments.

llvm/include/llvm/Analysis/DomTreeUpdater.h

public:
   /// Returns true if there are DominatorTree updates queued.
   /// Returns false under Eager UpdateStrategy or DT is nullptr.
   bool hasPendingDomTreeUpdates() const;
 
   /// Returns true if there are PostDominatorTree updates queued.
   /// Returns false under Eager UpdateStrategy or PDT is nullptr.
   bool hasPendingPostDomTreeUpdates() const;
 
-  /// Apply updates on all available trees. Under Eager UpdateStrategy with
+  ///@{
+  /// \name Mutation API
+  ///
+  /// These methods provide APIs for submitting updates to the DominatorTree and
+  /// the PostDominatorTree.
+  ///
+  /// Note: There are two strategies to update the DominatorTree:
+  /// 1. Eager UpdateStrategy: Updates are submitted and then flushed
+  /// immediately.
+  /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you
+  /// explicitly call flush APIs. It is recommended to use this update strategy
+  /// when you submit a bunch of updates multiple times which can then
+  /// add up to a large number of updates between two queries on the
+  /// DominatorTree. The incremental updater can reschedule the updates or
+  /// decide to recalculate the dominator tree in order to speedup the updating
+  /// process depending on the number of updates.
+  ///
+  /// Though GenericDomTree provides several update primitives,
+  /// it is not encouraged to use these APIs directly.
+
+  /// Submit updates to all available trees. Under Eager UpdateStrategy with
   /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
-  /// discard duplicated updates and self-dominance updates. If both DT and PDT
-  /// are nullptrs, this function discards all updates. The Eager Strategy
-  /// applies the updates immediately while the Lazy Strategy queues the
-  /// updates. It is required for the state of the LLVM IR to be updated
-  /// *before* applying the Updates because the internal update routine will
-  /// analyze the current state of the relationship between a pair of (From, To)
-  /// BasicBlocks to determine whether a single update needs to be discarded.
+  /// 1. discard duplicated updates,
+  /// 2. remove invalid updates. (Invalid updates means deletion of an edge that
+  /// still exists or insertion of an edge that does not exist.)
+  /// The Eager Strategy flushes updates immediately while the Lazy Strategy
+  /// queues the updates.
+  ///
+  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
+  /// in sync with + all updates before that single update.
+  ///
+  /// CAUTION!
+  /// 1. It is required for the state of the LLVM IR to be updated
+  /// *before* submitting the updates because the internal update routine will
+  /// analyze the current state of the CFG to determine whether an update
+  /// is valid.
+  /// 2. It is illegal to submit any update that has already been submitted,
+  /// i.e. you are supposed not to insert an existent edge or delete a
+  /// nonexistent edge.
   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
                     bool ForceRemoveDuplicates = false);
 
-  /// Notify all available trees on an edge insertion. If both DT and PDT are
-  /// nullptrs, this function discards the update. Under either Strategy,
-  /// self-dominance update will be removed. The Eager Strategy applies
-  /// the update immediately while the Lazy Strategy queues the update.
-  /// It is recommended to only use this method when you have exactly one
-  /// insertion (and no deletions). It is recommended to use applyUpdates() in
-  /// all other cases. This function has to be called *after* making the update
-  /// on the actual CFG. An internal functions checks if the edge exists in the
-  /// CFG in DEBUG mode.
+  /// Notify DTU that the entry block was replaced.
+  /// Recalculate all available trees and flush all BasicBlocks
+  /// awaiting deletion immediately.
+  void recalculate(Function &F);
+
+  /// \deprecated { Submit an edge insertion to all available trees. The Eager
+  /// Strategy flushes this update immediately while the Lazy Strategy queues
+  /// the update. An internal function checks if the edge exists in the CFG in
+  /// DEBUG mode. CAUTION! This function has to be called *after* making the
+  /// update on the actual CFG. It is illegal to submit any update that has
+  /// already been applied. }
   void insertEdge(BasicBlock *From, BasicBlock *To);
 
-  /// Notify all available trees on an edge insertion.
-  /// Under either Strategy, the following updates will be discard silently
-  /// 1. Invalid - Inserting an edge that does not exist in the CFG.
-  /// 2. Self-dominance update.
-  /// 3. Both DT and PDT are nullptrs.
-  /// The Eager Strategy applies the update immediately while the Lazy Strategy
-  /// queues the update. It is recommended to only use this method when you have
-  /// exactly one insertion (and no deletions) and want to discard an invalid
-  /// update.
+  /// \deprecated {Submit an edge insertion to all available trees.
+  /// Under either Strategy, an invalid update will be discard silently.
+  /// Invalid update means inserting an edge that does not exist in the CFG.
+  /// The Eager Strategy flushes this update immediately while the Lazy Strategy
+  /// queues the update. It is only recommended to use this method when you
+  /// want to discard an invalid update.
+  /// CAUTION! It is illegal to submit any update that has already been
+  /// submitted. }
   void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 
-  /// Notify all available trees on an edge deletion. If both DT and PDT are
-  /// nullptrs, this function discards the update. Under either Strategy,
-  /// self-dominance update will be removed. The Eager Strategy applies
-  /// the update immediately while the Lazy Strategy queues the update.
-  /// It is recommended to only use this method when you have exactly one
-  /// deletion (and no insertions). It is recommended to use applyUpdates() in
-  /// all other cases. This function has to be called *after* making the update
-  /// on the actual CFG. An internal functions checks if the edge doesn't exist
-  /// in the CFG in DEBUG mode.
+  /// \deprecated { Submit an edge deletion to all available trees. The Eager
+  /// Strategy flushes this update immediately while the Lazy Strategy queues
+  /// the update. An internal function checks if the edge doesn't exist in the
+  /// CFG in DEBUG mode.
+  /// CAUTION! This function has to be called *after* making the update on the
+  /// actual CFG. It is illegal to submit any update that has already been
+  /// submitted. }
   void deleteEdge(BasicBlock *From, BasicBlock *To);
 
-  /// Notify all available trees on an edge deletion.
-  /// Under either Strategy, the following updates will be discard silently
-  /// 1. Invalid - Deleting an edge that still exists in the CFG.
-  /// 2. Self-dominance update.
-  /// 3. Both DT and PDT are nullptrs.
-  /// The Eager Strategy applies the update immediately while the Lazy Strategy
-  /// queues the update. It is recommended to only use this method when you have
-  /// exactly one deletion (and no insertions) and want to discard an invalid
-  /// update.
+  /// \deprecated { Submit an edge deletion to all available trees.
+  /// Under either Strategy, an invalid update will be discard silently.
+  /// Invalid update means deleting an edge that exists in the CFG.
+  /// The Eager Strategy flushes this update immediately while the Lazy Strategy
+  /// queues the update. It is only recommended to use this method when you
+  /// want to discard an invalid update.
+  /// CAUTION! It is illegal to submit any update that has already been
+  /// submitted. }
   void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists and finally get deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date. Assert if any instruction of DelBB is
   /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
   /// will be queued until flush() is called.
   void deleteBB(BasicBlock *DelBB);
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists. Then the callback will
   /// be called. Finally, DelBB will be deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date. Assert if any instruction of DelBB is
   /// modified while awaiting deletion. Multiple callbacks can be queued for one
   /// DelBB under Lazy UpdateStrategy.
   void callbackDeleteBB(BasicBlock *DelBB,
                         std::function<void(BasicBlock *)> Callback);
 
-  /// Recalculate all available trees and flush all BasicBlocks
-  /// awaiting deletion immediately.
-  void recalculate(Function &F);
+  ///@}
+
+  ///@{
+  /// \name Flush API
+  ///
+  /// CAUTION! By the moment these flush APIs are called, the current CFG needs
+  /// to be the same as the CFG which DTU is in sync with + all updates
+  /// submitted.
 
   /// Flush DomTree updates and return DomTree.
-  /// It also flush out of date updates applied by all available trees
-  /// and flush Deleted BBs if both trees are up-to-date.
+  /// It flushes Deleted BBs if both trees are up-to-date.
   /// It must only be called when it has a DomTree.
   DominatorTree &getDomTree();
 
   /// Flush PostDomTree updates and return PostDomTree.
-  /// It also flush out of date updates applied by all available trees
-  /// and flush Deleted BBs if both trees are up-to-date.
+  /// It flushes Deleted BBs if both trees are up-to-date.
   /// It must only be called when it has a PostDomTree.
   PostDominatorTree &getPostDomTree();
 
   /// Apply all pending updates to available trees and flush all BasicBlocks
   /// awaiting deletion.
-  /// Does nothing under Eager UpdateStrategy.
+
   void flush();
 
+  ///@}
+
   /// Debug method to help view the internal state of this class.
   LLVM_DUMP_METHOD void dump() const;
 
 private:
   class CallBackOnDeletion final : public CallbackVH {
   public:
     CallBackOnDeletion(BasicBlock *V,
                        std::function<void(BasicBlock *)> Callback)