[PostDom] add findNearestCommonDominator for instructions

[khei4]

Summary

Implement PostDom version findNearestCommonDominator for instructions.

This seems symmetric to DominatorTree but contains some differences, e.g. returned ptr is nullable, and the use-case is only https://reviews.llvm.org/D155406. (TODO: search the use-cases).

[khei4]

TODO: it might be better to add unit test for Pdom if it's reasonable to add this method.

[nikic]

I think I would prefer to add this as a local helper to MemCpyOpt until we have a second use case.

llvm/include/llvm/Analysis/PostDominators.h

49

The "in the sense" part isn't correct for post-dominators.

llvm/lib/Analysis/PostDominators.cpp

90

I wasn't able to come up with an example where the nearest common post-dom would be an exception pad, so I think getFirstNonPHI() is fine.

[khei4]

I think I would prefer to add this as a local helper to MemCpyOpt until we have a second use case.

It seems reasonable! I'll move this to https://reviews.llvm.org/D155406 ;)

llvm/include/llvm/Analysis/PostDominators.h

49

Thanks! I'll fix it on the https://reviews.llvm.org/D155406.

llvm/include/llvm/Analysis/PostDominators.h

bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 
   // Ensure base-class overloads are visible.
   using Base::dominates;
 
   /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
   /// \p I1 if they belongs to the same basic block.
   bool dominates(const Instruction *I1, const Instruction *I2) const;
+
+  // Ensure base class overloads are visible.
+  using Base::findNearestCommonDominator;
+
+  /// Find the nearest instruction I that post-dominates both I1 and I2, in the
+  /// sense that a result produced after I will be available at both I1 and I2.
+  Instruction *findNearestCommonDominator(Instruction *I1,
+                                          Instruction *I2) const;
 };
 
 /// Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis
     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
 
   static AnalysisKey Key;

llvm/lib/Analysis/PostDominators.cpp

bool PostDominatorTree::dominates(const Instruction *I1,
   // Loop through the basic block until we find I1 or I2.
   BasicBlock::const_iterator I = BB1->begin();
   for (; &*I != I1 && &*I != I2; ++I)
     /*empty*/;
 
   return &*I == I2;
 }
 
+Instruction *
+PostDominatorTree::findNearestCommonDominator(Instruction *I1,
+                                              Instruction *I2) const {
+  BasicBlock *BB1 = I1->getParent();
+  BasicBlock *BB2 = I2->getParent();
+  if (BB1 == BB2)
+    return I1->comesBefore(I2) ? I2 : I1;
+  BasicBlock *PDomBB = findNearestCommonDominator(BB1, BB2);
+  if (!PDomBB)
+    return nullptr;
+  if (BB1 == PDomBB)
+    return I2;
+  if (BB1 == PDomBB)
+    return I1;
+  return PDomBB->getFirstNonPHI();
+}
+
 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;
 }
 
 void PostDominatorTreeWrapperPass::verifyAnalysis() const {
   if (VerifyDomInfo)
     assert(DT.verify(PostDominatorTree::VerificationLevel::Full));