Changes for Parallel Code Motion

[saddent]

Summary

• The Changes include using alias analysis for code motion
• The Changes include considering more instructions for code motion.

• TODO The code has a bug for getting alais analysis for a function.
• TODO Need to consider if the changes for code motion also apply for work sharing constructs.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

 //===-- IPO/OpenMPOpt.cpp - Collection of OpenMP specific optimizations ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
static CallInst *getCallIfRegularCall(
     if (CI && !CI->hasOperandBundles() &&
         (!RFI ||
          (RFI->Declaration && CI->getCalledFunction() == RFI->Declaration)))
       return CI;
     return nullptr;
   }
 
 private:
+  bool checkIsHoistable(const Instruction &I) {
+    return (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));
+  }
+
   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;
+    SmallPtrSet<Instruction *, 8> PreviousInstructions;
+    SmallPtrSet<Instruction *, 8> InvariantInstructions;
 
     auto SelectCMInst = [&](Use &U, Function &F) {
       CallInst *CI = getCallIfRegularCall(U);
       if (!CI)
         return false;
 
-      auto *Fn = dyn_cast<Function>(
+      const Function *Fn = dyn_cast<Function>(
           CI->getArgOperand(CallbackCalleeOperand)->stripPointerCasts());
 
-      for (BasicBlock &BB : Fn->getBasicBlockList()) {
-        for (Instruction &I : BB) {
+      const DominatorTree *DT =
+          OMPInfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Fn);
+
+      // TODO Need to check segfault with this call
+      AAResults *AA = OMPInfoCache.getAAResultsForFunction(*Fn);
+
+      BasicBlock *Root = DT->getRoot();
+      ReversePostOrderTraversal<BasicBlock *> RPOT(Root);
+      for (auto *BB : RPOT) {
+        for (Instruction &I : make_early_inc_range(*BB)) {
+
+          auto HasInvariantOperands = [&](Instruction &I) {
+            return all_of(I.operands(), [&](Value *V) {
+              if (const Instruction *I = dyn_cast<Instruction>(V))
+                return !(I->getFunction()->getName() == (*Fn).getName()) ||
+                       InvariantInstructions.contains(I);
+              return true;
+            });
+          };
 
-          /// 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;
-              }
+          auto checkMemoryOperationsAliased = [&](Instruction &PresI) {
+            if (!(isa<LoadInst>(PresI) || isa<StoreInst>(PresI))) {
+            for (auto PrevI : PreviousInstructions) {
+              if (LoadInst *LI = dyn_cast<LoadInst>(&PresI)) {
+                if (StoreInst *SI = dyn_cast<StoreInst>(PrevI)) {
+                  if (!(*AA).alias(LI->getPointerOperand(),
+                                   SI->getPointerOperand())) {
+                    continue;
+                  }
+                }
+              } else if (LoadInst *LI = dyn_cast<LoadInst>(PrevI)) {
+                if (StoreInst *SI = dyn_cast<StoreInst>(&PresI)) {
+                  if (!(*AA).alias(LI->getPointerOperand(),
+                                   SI->getPointerOperand())) {
+                    continue;
+                  }
+                }
               }
+              PreviousInstructions.insert(&PresI);
               return true;
+            }
+            PreviousInstructions.insert(&PresI);
+            return false;
           };
 
-          /// choosing instruction for code motion
-          if (!I.mayThrow() && !I.mayReadOrWriteMemory() &&
-              isSafeToSpeculativelyExecute(&I) && CheckConstantOperands(I)) {
-            InstructionsToBeMoved.insert(&I);
-      NumOpenMPParallelInstructionsForCodeMotion++;
+          if (checkIsHoistable(I) && !I.mayThrow() &&
+              isSafeToSpeculativelyExecute(&I) && HasInvariantOperands(I) &&
+              !checkMemoryOperationsAliased(I)) {
+            InvariantInstructions.insert(&I);
+            NumOpenMPParallelRegionsForCodeMotion++;
             continue;
           }
         }
       }
 
-      if (!InstructionsToBeMoved.empty()) {
+      if (!InvariantInstructions.empty()) {
         Changed = true;
       }
 
-      /// moves instructions before the callsite for __kmpc_fork_call
-      for (auto instruction : InstructionsToBeMoved) {
+      for (auto instruction : InvariantInstructions) {
         instruction->moveBefore(CI);
       }
       return false;
     };
 
     RFI.foreachUse(SCC, SelectCMInst);
 
-    for (auto instr : InstructionsToBeMoved) {
-      LLVM_DEBUG(dbgs() << TAG << "Instruction for CodeMotion : "
-                        << instr->dump() << "\n");
+    LLVM_DEBUG(dbgs() << TAG << "Instructions for CM : "
+                      << "\n");
+    for (auto CME : InvariantInstructions) {
+      LLVM_DEBUG(CME->dump());
     }
     return Changed;
   }
 
   /// Merge parallel regions when it is safe.
   bool mergeParallelRegions() {
     const unsigned CallbackCalleeOperand = 2;
     const unsigned CallbackFirstArgOperand = 3;