Changes for Parallel Code Motion

[saddent]

Summary

The changes host the implementation for parallel code motion
of OpenMp based parallel programs.

[saddent]

Updating D132065: Changes for Parallel Code Motion

Applied clang-format to the changes

[wsmoses]

.gitignore

73

Please remove this

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

176

Change the comment to number of instructions for parallel code motion?

.gitignore

 .cache
 # static analyzer regression testing project files
 /clang/utils/analyzer/projects/*/CachedSource
 /clang/utils/analyzer/projects/*/PatchedSource
 /clang/utils/analyzer/projects/*/ScanBuildResults
 /clang/utils/analyzer/projects/*/RefScanBuildResults
 # automodapi puts generated documentation files here.
 /lldb/docs/python_api/
+/clang_build/*

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

static cl::opt<bool> DisableOpenMPOptStateMachineRewrite(
     cl::desc("Disable OpenMP optimizations that replace the state machine."),
     cl::Hidden, cl::init(false));
 
 static cl::opt<bool> DisableOpenMPOptBarrierElimination(
     "openmp-opt-disable-barrier-elimination",
     cl::desc("Disable OpenMP optimizations that eliminate barriers."),
     cl::Hidden, cl::init(false));
 
+static cl::opt<bool> DisableOpenMPOptParallelCodeMotion(
+    "openmp-opt-disable-code-motion", cl::ZeroOrMore,
+    cl::desc("Disable OpenMP optimizations that perform code motion."),
+    cl::Hidden, cl::init(false));
+
 static cl::opt<bool> PrintModuleAfterOptimizations(
     "openmp-opt-print-module-after",
     cl::desc("Print the current module after OpenMP optimizations."),
     cl::Hidden, cl::init(false));
 
 static cl::opt<bool> PrintModuleBeforeOptimizations(
     "openmp-opt-print-module-before",
     cl::desc("Print the current module before OpenMP optimizations."),

 STATISTIC(
     NumOpenMPParallelRegionsReplacedInGPUStateMachine,
     "Number of OpenMP parallel regions replaced with ID in GPU state machines");
 STATISTIC(NumOpenMPParallelRegionsMerged,
           "Number of OpenMP parallel regions merged");
 STATISTIC(NumBytesMovedToSharedMemory,
           "Amount of memory pushed to shared memory");
 STATISTIC(NumBarriersEliminated, "Number of redundant barriers eliminated");
+STATISTIC(NumOpenMPParallelRegionsForCodeMotion,
+          "Number of OpenMP parallel regions for Code Motion");
 
 #if !defined(NDEBUG)
 static constexpr auto TAG = "[" DEBUG_TYPE "]";
 #endif
 
 namespace {
 
 struct AAHeapToShared;
if (IsModulePass) {
       if (EnableParallelRegionMerging) {
         if (mergeParallelRegions()) {
           deduplicateRuntimeCalls();
           Changed = true;
         }
       }
 
       Changed |= eliminateBarriers();
+      Changed |= parallelCodeMotion();
     }
 
     return Changed;
   }
 
   /// Print initial ICV values for testing.
   /// FIXME: This should be done from the Attributor once it is added.
   void printICVs() const {
static CallInst *getCallIfRegularCall(
     if (CI && !CI->hasOperandBundles() &&
         (!RFI ||
          (RFI->Declaration && CI->getCalledFunction() == RFI->Declaration)))
       return CI;
     return nullptr;
   }
 
 private:
+  bool parallelCodeMotion() {
+    bool Changed = false;
+    const unsigned CallbackCalleeOperand = 2;
+
+    if (DisableOpenMPOptParallelCodeMotion)
+      return false;
+
+    OMPInformationCache::RuntimeFunctionInfo &RFI =
+        OMPInfoCache.RFIs[OMPRTL___kmpc_fork_call];
+
+    if (!RFI.Declaration)
+      return false;
+
+    SmallDenseMap<BasicBlock *, SmallPtrSet<Instruction *, 4>> BB2PRMap;
+    SmallPtrSet<Instruction *, 8> InstructionsToBeMoved;
+
+    auto SelectCMInst = [&](Use &U, Function &F) {
+      CallInst *CI = getCallIfRegularCall(U);
+      if (!CI)
+        return false;
+
+      auto *Fn = dyn_cast<Function>(
+          CI->getArgOperand(CallbackCalleeOperand)->stripPointerCasts());
+
+      for (BasicBlock &BB : Fn->getBasicBlockList()) {
+        for (Instruction &I : BB) {
+
+          /// check for constant operand operations
+          auto CheckConstantOperands = [&](Instruction &I) {
+            int operandCount = I.getNumOperands();
+            for (int i = 0; i < operandCount; i++) {
+              if (!dyn_cast<ConstantInt>(I.getOperand(i))) {
+                return false;
+              }
+            }
+            return true;
+          };
+
+          /// choosing instruction for code motion
+          if (!I.mayThrow() && !I.mayReadOrWriteMemory() &&
+              isSafeToSpeculativelyExecute(&I) && CheckConstantOperands(I)) {
+            InstructionsToBeMoved.insert(&I);
+            continue;
+          }
+        }
+      }
+
+      if (!InstructionsToBeMoved.empty()) {
+        Changed = true;
+        NumOpenMPParallelRegionsForCodeMotion++;
+      }
+
+      /// moves instructions before the callsite for __kmpc_fork_call
+      for (auto instruction : InstructionsToBeMoved) {
+        instruction->moveBefore(CI);
+      }
+      return false;
+    };
+
+    RFI.foreachUse(SCC, SelectCMInst);
+
+    for (auto instr : InstructionsToBeMoved) {
+      LLVM_DEBUG(dbgs() << TAG << "Instruction for CodeMotion : "
+                        << instr->dump() << "\n");
+    }
+    return Changed;
+  }
+
   /// Merge parallel regions when it is safe.
   bool mergeParallelRegions() {
     const unsigned CallbackCalleeOperand = 2;
     const unsigned CallbackFirstArgOperand = 3;
     using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 
     // Check if there are any __kmpc_fork_call calls to merge.
     OMPInformationCache::RuntimeFunctionInfo &RFI =