[OpenMPOpt][SplitMemTransfer][WIP] Detect issue

[hamax97]

Summary

Detecting where the "issue" of the memory transfer will be moved.

• Problem when getting aliasing results of a call instruction. Returns MayAlias even if the offload region has the noalias modifier.

[hamax97]

• Fix code style issue.
• Problem with getModRefInfo, it always returns that a value V may be modified, even when running opt with -aa-pipeline=basic-aa.

llvm/include/llvm/Transforms/IPO/OpenMPOpt.h

struct OMPInformationCache : public InformationCache {
   /// ...)
   struct MemoryTransfer {
 
     /// Used to map the values physically (in the IR) stored in an offload
     /// array, to a vector in memory.
     struct OffloadArray {
       AllocaInst &Array; /// Physical array (in the IR).
       SmallVector<Value *, 8> StoredValues; /// Mapped values.
+      SmallVector<StoreInst *, 8> LastAccesses;
       InformationCache &InfoCache;
 
       /// Factory function for creating and initializing the OffloadArray with
       /// the values stored in \p Array before the instruction \p Before is
       /// reached.
       /// This MUST be used instead of the constructor.
       static std::unique_ptr<OffloadArray> initialize(
           AllocaInst &Array,
           Instruction &Before,
           InformationCache &InfoCache);
 
       /// Use the factory function initialize(...) instead.
       OffloadArray(AllocaInst &Array, InformationCache &InfoCache)
           : Array(Array), InfoCache(InfoCache) {}
 
     private:
       /// Traverses the BasicBlocks collecting the stores made to
-      /// OffloadArray::Array, leaving OffloadArray::StoredValues with the
-      /// values stored before the instruction \p Before is reached.
+      /// Array, leaving StoredValues with the values stored before
+      /// the instruction \p Before is reached.
       bool getValues(Instruction &Before);
 
-      /// Returns the index of OffloadArray::Array where the store is being
+      /// Returns the index of Array where the store is being
       /// made. Returns -1 if the index can't be deduced.
       int32_t getAccessedIdx(StoreInst &S);
 
-      /// Returns true all values in \p V are not nullptrs.
-      static bool isFilled(const SmallVectorImpl<Value *> &V);
+      /// Returns true if all values in StoredValues and
+      /// LastAccesses are not nullptrs.
+      bool isFilled();
     };
 
     CallBase *RuntimeCall; /// Call that involves a memotry transfer.
     InformationCache &InfoCache;
 
     /// These help mapping the values in offload_baseptrs, offload_ptrs, and
     /// offload_sizes, respectively.
-    std::unique_ptr<OffloadArray> BasePtrs;
-    std::unique_ptr<OffloadArray> Ptrs;
-    std::unique_ptr<OffloadArray> Sizes;
+    std::unique_ptr<OffloadArray> BasePtrs = nullptr;
+    std::unique_ptr<OffloadArray> Ptrs = nullptr;
+    std::unique_ptr<OffloadArray> Sizes = nullptr;
+
+    /// Set of instructions that compose the argument setup for the call
+    /// RuntimeCall.
+    SetVector<Instruction *> Issue;
 
     MemoryTransfer(CallBase *RuntimeCall, InformationCache &InfoCache) :
         RuntimeCall{RuntimeCall}, InfoCache{InfoCache}
     {}
 
     /// Maps the values physically (the IR) stored in the offload arrays
     /// offload_baseptrs, offload_ptrs, offload_sizes to their corresponding
-    /// members, MemoryTransfer::BasePtrs, MemoryTransfer::Ptrs,
-    /// MemoryTransfer::Sizes.
+    /// members, BasePtrs, Ptrs, Sizes.
     /// Returns false if one of the arrays couldn't be processed or some of the
     /// values couldn't be found.
     bool getValuesInOffloadArrays();
+
+    /// Groups the instructions that compose the argument setup for the call
+    /// RuntimeCall.
+    bool detectIssue();
+
+    /// Returns true if \p I might modify some of the values in the
+    /// offload arrays.
+    bool mayBeModifiedBy(Instruction *I);
+
+  private:
+    /// Gets the setup instructions for each of the values in \p OA. These
+    /// instructions are stored into Issue.
+    bool getSetupInstructions(std::unique_ptr<OffloadArray> &OA);
+    /// Gets the setup instructions for the pointer operand of \p S.
+    bool getPointerSetupInstructions(StoreInst *S);
+    /// Gets the setup instructions for the value operand of \p S.
+    bool getValueSetupInstructions(StoreInst *S);
+
+    /// Returns true if \p I may modify one of the values in \p Values.
+    bool mayModify(Instruction *I, SmallVectorImpl<Value *> &Values);
   };
 
   /// The slice of the module we are allowed to look at.
   SmallPtrSetImpl<Function *> &ModuleSlice;
 
   /// An OpenMP-IR-Builder instance
   OpenMPIRBuilder OMPBuilder;
 
private:
   /// Tries to hide the latency of runtime calls that involve host to
   /// device memory transfers by splitting them into their "issue" and "wait".
   /// versions. The "issue" is moved upwards as much as possible. The "wait" is
   /// moved downards as much as possible. The "issue" issues the memory transfer
   /// asynchronously, returning a handle. The "wait" waits in the returned
   /// handle for the memory transfer to finish.
   bool hideMemTransfersLatency();
 
+  /// Returns a pointer to the instruction where the "issue" of \p MT can be
+  /// moved. Returns nullptr if the movement is not possible, or not worth it.
+  Instruction *canBeMovedUpwards(MemoryTransfer &MT);
+
   static Value *combinedIdentStruct(Value *CurrentIdent, Value *NextIdent,
                                     bool GlobalOnly, bool &SingleChoice);
 
   /// Return an `struct ident_t*` value that represents the ones used in the
   /// calls of \p RFI inside of \p F. If \p GlobalOnly is true, we will not
   /// return a local `struct ident_t*`. For now, if we cannot find a suitable
   /// return value we create one from scratch. We also do not yet combine
   /// information, e.g., the source locations, see combinedIdentStruct.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

 #include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 
 using namespace llvm;
 using namespace omp;
 using namespace types;
 
 #define DEBUG_TYPE "openmp-opt"
 
 static cl::opt<bool> DisableOpenMPOptimizations(
if (!Sizes) {
                         << RuntimeCall->getCaller()->getName() << "\n");
       return false;
     }
   }
 
   return true;
 }
 
+bool MemoryTransfer::detectIssue() {
+  assert(BasePtrs && Ptrs && "No offload arrays to look at!");
+  if (BasePtrs) {
+    bool Success = getSetupInstructions(BasePtrs);
+    if (!Success) {
+      LLVM_DEBUG(dbgs() << TAG << "Couldn't get setup instructions of "
+                        << "offload_baseptrs. In call to "
+                        << RuntimeCall->getName() << " in function "
+                        << RuntimeCall->getCaller()->getName() << "\n");
+      return false;
+    }
+  }
+
+  if (Ptrs) {
+    bool Success = getSetupInstructions(Ptrs);
+    if (!Success) {
+      LLVM_DEBUG(dbgs() << TAG << "Couldn't get setup instructions of "
+                        << "offload_ptrs. In call to "
+                        << RuntimeCall->getName() << " in function "
+                        << RuntimeCall->getCaller()->getName() << "\n");
+      return false;
+    }
+  }
+
+  if (Sizes) {
+    bool Success = getSetupInstructions(Sizes);
+    if (!Success) {
+      LLVM_DEBUG(dbgs() << TAG << "Couldn't get setup instructions of "
+                        << "offload_sizes. In call to "
+                        << RuntimeCall->getName() << " in function "
+                        << RuntimeCall->getCaller()->getName() << "\n");
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool MemoryTransfer::getSetupInstructions(std::unique_ptr<OffloadArray> &OA) {
+  for (auto *S : OA->LastAccesses) {
+    if (!getValueSetupInstructions(S))
+      return false;
+
+    if (!getPointerSetupInstructions(S))
+      return false;
+
+    Issue.insert(S);
+  }
+  return true;
+}
+
+bool MemoryTransfer::getPointerSetupInstructions(StoreInst *S) {
+  auto *P = S->getPointerOperand();
+
+  // TODO: P might be a global value. Make it general.
+  if (!isa<Instruction>(P))
+    return false;
+
+  auto *DstInst = cast<Instruction>(P);
+  if (isa<GetElementPtrInst>(DstInst)) {
+    Issue.insert(DstInst);
+
+  } else if (DstInst->isCast()) {
+    auto *Casted = DstInst->getOperand(0);
+
+    // TODO: Casted might be a global value. Make it general.
+    if (!isa<Instruction>(Casted))
+      return false;
+
+    if (auto *GEP = dyn_cast<GetElementPtrInst>(Casted))
+      Issue.insert(GEP);
+
+    Issue.insert(DstInst);
+  }
+
+  return true;
+}
+
+bool MemoryTransfer::getValueSetupInstructions(StoreInst *S) {
+  auto *V = S->getValueOperand();
+  // Auxiliary storage to later insert the found instructions in the order
+  // needed.
+  SmallVector<Instruction *, 8> TempStorage;
+  bool Success = false;
+  unsigned MaxLookup = 6;
+  for (unsigned I = 0; I < MaxLookup; ++I) {
+    if (isa<AllocaInst>(V) || isa<Argument>(V) || isa<GlobalValue>(V) ||
+        isa<Constant>(V)) {
+      Success = true;
+      break;
+    }
+
+    if (!isa<Instruction>(V)) {
+      Success = false;
+      break;
+    }
+
+    auto *Inst = cast<Instruction>(V);
+    TempStorage.push_back(Inst);
+
+    // FIXME: Inst might depend on more instructions through its second operand.
+    V = Inst->getOperand(0);
+  }
+
+  if (Success)
+    while (!TempStorage.empty())
+      Issue.insert(TempStorage.pop_back_val());
+
+  return Success;
+}
+
+bool MemoryTransfer::mayBeModifiedBy(Instruction *I) {
+  assert(BasePtrs && Ptrs && "No offload addresses to analyze!");
+  if (Issue.count(I))
+    return false;
+
+  if (mayModify(I, BasePtrs->StoredValues))
+    return true;
+  if (mayModify(I, Ptrs->StoredValues))
+    return true;
+  if (Sizes) {
+    if (mayModify(I, Sizes->StoredValues))
+      return true;
+  }
+
+  return false;
+}
+
+bool MemoryTransfer::mayModify(Instruction *I,
+                               SmallVectorImpl<Value *> &Values) {
+  assert(I && "Can't analyze nullptr!");
+  auto *AAResults = InfoCache.getAnalysisResultForFunction<AAManager>(
+      *RuntimeCall->getCaller());
+  if (!AAResults) {
+    LLVM_DEBUG(dbgs() << TAG << "Couldn't get AAManager in function "
+                      << RuntimeCall->getCaller()->getName() << "\n");
+    return true;
+  }
+
+  const DataLayout &DL = InfoCache.getDL();
+  bool IsStoreInst = isa<StoreInst>(I);
+
+  for (auto *V : Values) {
+    auto AARes = AAResults->alias(I, V);
+    if (AARes >= AliasResult::MayAlias)
+      return true;
+
+    // If \p I is a StoreInst to an offloaded value.
+    if (IsStoreInst &&
+        GetUnderlyingObject(I->getOperand(1), DL) == V)
+      return true;
+  }
+  return false;
+}
+
 std::unique_ptr<OffloadArray> OffloadArray::initialize(
     AllocaInst &Array, Instruction &Before, InformationCache &InfoCache) {
   if (!Array.getAllocatedType()->isArrayTy()) {
     LLVM_DEBUG(dbgs() << TAG << "Allocated type is not array.\n");
     return nullptr;
   }
 
   auto OA = std::make_unique<OffloadArray>(Array, InfoCache);
   bool Success = OA->getValues(Before);
   if (!Success) {
     LLVM_DEBUG(dbgs() << TAG << "Error getting values in offload array.\n");
     return nullptr;
   }
 
   return OA;
 }
 
 bool OffloadArray::getValues(Instruction &Before) {
   // Initialize container.
   const uint64_t NumValues =
       Array.getAllocatedType()->getArrayNumElements();
   StoredValues.assign(NumValues, nullptr);
+  LastAccesses.assign(NumValues, nullptr);
 
   // TODO: This assumes the instruction \p Before is in the same BasicBlock
   //       as OffloadArray::Array. Make it general, for any control flow graph.
   auto *BB = Array.getParent();
   if (BB != Before.getParent()) {
     LLVM_DEBUG(dbgs() << TAG << "The lower limit instruction is in a"
                       << " different BasicBlock.\n");
     return false;
   }
 
   const DataLayout &DL = InfoCache.getDL();
   for (auto &I : *BB) {
     if (&I == &Before) break;
 
-    if (isa<StoreInst>(&I)) {
-      auto *Dst = GetUnderlyingObject(I.getOperand(1), DL);
+    if (auto *S = dyn_cast<StoreInst>(&I)) {
+      auto *Dst = GetUnderlyingObject(S->getPointerOperand(), DL);
 
       if (Dst == &Array) {
-        int32_t AccessedIdx = getAccessedIdx(*cast<StoreInst>(&I));
-        if (AccessedIdx < 0) {
+        int32_t Idx = getAccessedIdx(*S);
+        if (Idx < 0) {
           LLVM_DEBUG(dbgs() << TAG << "Unexpected StoreInst\n");
           return false;
         }
 
-        StoredValues[AccessedIdx] = GetUnderlyingObject(I.getOperand(0), DL);
+        StoredValues[Idx] = GetUnderlyingObject(S->getValueOperand(), DL);
+        LastAccesses[Idx] = S;
       }
     }
   }
 
-  return isFilled(StoredValues);
+  return isFilled();
 }
 
 int32_t OffloadArray::getAccessedIdx(StoreInst &S) {
   auto *Dst = S.getOperand(1);
   if (!isa<Instruction>(Dst)) {
     LLVM_DEBUG(dbgs() << TAG << "Unrecognized store pattern.\n");
     return -1;
   }
int32_t OffloadArray::getAccessedIdx(StoreInst &S) {
   if (ArrayIdx == GEPInst->idx_end()) {
     LLVM_DEBUG(dbgs() << TAG << "Unrecognized store pattern.\n");
     return -1;
   }
 
   return OpenMPOpt::getIntLiteral(ArrayIdx->get());
 }
 
-bool OffloadArray::isFilled(const SmallVectorImpl<Value *> &V) {
-  for (auto *E : V)
-    if (!E)
+bool OffloadArray::isFilled() {
+  const unsigned NumValues = StoredValues.size();
+  for (unsigned I = 0; I < NumValues; ++I) {
+    if (!StoredValues[I] || !LastAccesses[I])
       return false;
+  }
 
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // Declarations and definitions of AAICVTracker.
 //===----------------------------------------------------------------------===//
 namespace {
auto SplitDataTransfer = [&] (Use &U, Function &Decl) {
     MemoryTransfer MT(RTCall, OMPInfoCache);
     bool Success = MT.getValuesInOffloadArrays();
     if (!Success) {
       LLVM_DEBUG(dbgs() << TAG << "Couldn't get offload arrays in call to "
                         << MT.RuntimeCall->getName() << " in function "
                         << MT.RuntimeCall->getCaller()->getName() << "\n");
       return false;
     }
+
+    Success = MT.detectIssue();
+    if (!Success) {
+      LLVM_DEBUG(dbgs() << TAG << "Couldn't detect issue in call to "
+                        << MT.RuntimeCall->getName() << " in function "
+                        << MT.RuntimeCall->getCaller()->getName() << "\n");
+      return false;
+    }
+
+    if (auto *I = canBeMovedUpwards(MT)) {
+      // TODO: Split call and move "issue" below I.
+    }
     return false;
   };
 
   RFI.foreachUse(SplitDataTransfer);
   return Changed;
 }
 
+Instruction *OpenMPOpt::canBeMovedUpwards(MemoryTransfer &MT) {
+  assert(MT.Issue.size() > 0 && "There's not set of instructions to be moved!");
+
+  CallBase *RC = MT.RuntimeCall;
+  auto *MSSAResult =
+      OMPInfoCache.getAnalysisResultForFunction<MemorySSAAnalysis>(
+          *RC->getCaller());
+  if (!MSSAResult) {
+    LLVM_DEBUG(dbgs() << TAG << "Couldn't get MemorySSAAnalysis in function "
+                      << RC->getCaller()->getName() << "\n");
+    return nullptr;
+  }
+
+  auto &MSSA = MSSAResult->getMSSA();
+  auto *MSSAWalker = MSSA.getWalker();
+  const auto *LiveOnEntry = MSSA.getLiveOnEntryDef();
+  auto *MemAccess = MSSAWalker->getClobberingMemoryAccess(RC);
+
+  while (MemAccess != LiveOnEntry) {
+    if (!isa<MemoryDef>(MemAccess))
+      continue;
+
+    auto *MemInst = (cast<MemoryDef>(MemAccess))->getMemoryInst();
+    if (MT.mayBeModifiedBy(MemInst))
+      return MemInst;
+
+    MemAccess = MSSAWalker->getClobberingMemoryAccess(MemAccess);
+  }
+
+  return nullptr;
+}
+
 Value *OpenMPOpt::combinedIdentStruct(Value *CurrentIdent, Value *NextIdent,
     bool GlobalOnly, bool &SingleChoice) {
   if (CurrentIdent == NextIdent)
     return CurrentIdent;
 
   // TODO: Figure out how to actually combine multiple debug locations. For
   //       now we just keep an existing one if there is a single choice.
   if (!GlobalOnly || isa<GlobalValue>(NextIdent)) {