[CodeMoverUtils] Added an API to check if an instruction can be safely

moved before another instruction.
Summary:Added an API to check if an instruction can be safely moved
before another instruction. In future PRs, we will like to add support
of moving instructions between blocks that are not control flow
equivalent, and add other APIs to enhance usability, e.g. moving basic
blocks, moving list of instructions...
Loop Fusion will be its first user. When there is intervening code in
between two loops, fusion is currently unable to fuse them. Loop Fusion
can use this utility to check if the intervening code can be safely
moved before or after the two loops, and move them, then it can
successfully fuse them.
Reviewer:kbarton,jdoerfert,Meinersbur,bmahjour,etiotto
Reviewed By:bmahjour
Subscribers:mgorny,hiraditya,llvm-commits
Tag:LLVM
Differential Revision:https://reviews.llvm.org/D70049

1 files changed, 23 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/PostDominators.cpp b/llvm/lib/Analysis/PostDominators.cpp
index 918c3edafa9..f01d51504d7 100644
--- a/llvm/lib/Analysis/PostDominators.cpp
+++ b/llvm/lib/Analysis/PostDominators.cpp
@@ -12,6 +12,7 @@
 
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
@@ -50,6 +51,28 @@ bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
            PAC.preservedSet<CFGAnalyses>());
 }
 
+bool PostDominatorTree::dominates(const Instruction *I1,
+                                  const Instruction *I2) const {
+  assert(I1 && I2 && "Expecting valid I1 and I2");
+
+  const BasicBlock *BB1 = I1->getParent();
+  const BasicBlock *BB2 = I2->getParent();
+
+  if (BB1 != BB2)
+    return Base::dominates(BB1, BB2);
+
+  // PHINodes in a block are unordered.
+  if (isa<PHINode>(I1) && isa<PHINode>(I2))
+    return false;
+
+  // 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;
+}
+
 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;