[CodeMoverUtils][WIP] Isolate checks strictly related to the code motion candidate instruction

[RithikSharma]

Summary

Some checks in isSafeToMoveBefore are independent of insert point, this patch isolate those checks and also adds some trivial checks from LICM. This is a work in progress until we move all the conservative insert point independent checks here from LICM.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

308

These conditions are inherited from LICM, is this a generalized safe assumption? Is there any very obvious exception to this?

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

313

why do we start allowing terminators as safe candidates for code motion? Has this constraint been moved to another place that doesn't show up in this patch? The same question applies to checking for isa<PHINode>(InsertPoint) above.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

308

Not sure how this list is generated in LICM. Is it trying to exclude PHINode and terminators (e.g. BranchInst, SwitchInst, ...)? If so, then those was excluded in isSafeToMoveBefore originally.
Any test cases failed without this check?

323

This is covered in line 380.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

313

Type of instructions are limited using isSafeToMove.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

308

No failing test case yet and it does reflect the old TermInst and PHINode checks so it seems okay to me to keep this.

323

Thanks, that check is dependent on DT. I can remove this from here but I'll wait until we decide on keeping DT and PDT as optional argument as then we may end up missing this check. (I'll also look into other such checks if we decide to make DT and PDT optional).

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

323

I see that you are moving a subset of checks from LICM over here, how is this set of checks selected from LICM?

[asbirlea]

Looks like a reasonable cleanup making safety checks reusable.
Please run check-all to check the statistics you're changing are not checked for in unit tests.

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                         DominatorTree &DT, const PostDominatorTree &PDT,
                         DependenceInfo &DI);
 
+/// Return true if \p I is a safe candidate for code motion
+bool isSafeToMove(Instruction &I);
+
 /// Return true if all instructions (except the terminator) in \p BB can be
 /// safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                         DominatorTree &DT, const PostDominatorTree &PDT,
                         DependenceInfo &DI);
 
 /// Move instructions, in an order-preserving manner, from \p FromBB to the
 /// beginning of \p ToBB when proven safe.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/OrderedInstructions.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/IntrinsicInst.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "codemover-utils"
 
 STATISTIC(HasDependences,
           "Cannot move across instructions that has memory dependences");
 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
 STATISTIC(NotControlFlowEquivalent,
           "Instructions are not control flow equivalent");
 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
-STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
+STATISTIC(NotMovedDebugInfo, "Movement of DebugInfo are not supported");
+STATISTIC(NotMovedThrowCall, "Movement of Calls that throw are not supported");
+STATISTIC(NotMovedVolatileOrderedLoad,
+          "Movement of Volatile or Ordered Loads are not supported");
+STATISTIC(NotMovedVolatileOrderedStore,
+          "Movement of Volatile or Ordered Stores are not supported");
+STATISTIC(NotMovedInstruction,
+          "Movement of this Instruction type is not supported");
 
 namespace {
 /// Represent a control condition. A control condition is a condition of a
 /// terminator to decide which successors to execute. The pointer field
 /// represents the address of the condition of the terminator. The integer field
 /// is a bool, it is true when the basic block is executed when V is true. For
 /// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
 /// integer field equals to true, while %cond is a control condition of bb1 with
while (!WorkList.empty()) {
 
     if (!InBetweenInsts.insert(CurInst).second)
       continue;
 
     getNextInsts(*CurInst, WorkList);
   }
 }
 
+bool llvm::isSafeToMove(Instruction &I) {
+  if (!(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
+        isa<FenceInst>(I) || isa<CastInst>(I) || isa<UnaryOperator>(I) ||
+        isa<BinaryOperator>(I) || isa<SelectInst>(I) ||
+        isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
+        isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
+        isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
+        isa<InsertValueInst>(I) || isa<FreezeInst>(I))) {
+    return reportInvalidCandidate(I, NotMovedInstruction);
+  }
+  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
+    if (!LI->isUnordered())
+      return reportInvalidCandidate(I, NotMovedVolatileOrderedLoad);
+  } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
+    if (isa<DbgInfoIntrinsic>(I))
+      return reportInvalidCandidate(I, NotMovedDebugInfo);
+    if (CI->mayThrow())
+      return reportInvalidCandidate(I, NotMovedThrowCall);
+  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
+    if (!SI->isUnordered())
+      return reportInvalidCandidate(I, NotMovedVolatileOrderedStore);
+  }
+  return true;
+}
+
 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                               DominatorTree &DT, const PostDominatorTree &PDT,
                               DependenceInfo &DI) {
+  // check can we move Instruction
+  if (!isSafeToMove(I))
+    return false;
+
   // Cannot move itself before itself.
   if (&I == &InsertPoint)
     return false;
 
   // Not moved.
   if (I.getNextNode() == &InsertPoint)
     return true;
 
-  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
+  if (isa<PHINode>(InsertPoint))
     return reportInvalidCandidate(I, NotMovedPHINode);
 
-  if (I.isTerminator())
-    return reportInvalidCandidate(I, NotMovedTerminator);
-
   // TODO remove this limitation.
   if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
     return reportInvalidCandidate(I, NotControlFlowEquivalent);
 
   if (!DT.dominates(&InsertPoint, &I))
     for (const Use &U : I.uses())
       if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
         if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
   const bool MoveForward = OI.domTreeLevelBefore(&I, &InsertPoint);
   Instruction &StartInst = (MoveForward ? I : InsertPoint);
   Instruction &EndInst = (MoveForward ? InsertPoint : I);
   SmallPtrSet<Instruction *, 10> InstsToCheck;
   collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
   if (!MoveForward)
     InstsToCheck.insert(&InsertPoint);
 
-  // Check if there exists instructions which may throw, may synchonize, or may
-  // never return, from I to InsertPoint.
+  // Check if there exists instructions which may throw, may synchonize, or
+  // may never return, from I to InsertPoint.
   if (!isSafeToSpeculativelyExecute(&I))
     if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                     [](Instruction *I) {
                       if (I->mayThrow())
                         return true;
 
                       const CallBase *CB = dyn_cast<CallBase>(I);
                       if (!CB)