[LAA] LLE 4/6: APIs to access the dependent instructions for a dependence, NFC

[anemet]

Summary

The functions use LAI and MemoryDepChecker classes so they need to be
defined after those definitions outside of the Dependence class.

Will be used by the LoopLoadElimination pass.

[rengolin]

I'm not sure why this cannot be squashed into the next step. But LGTM, too.

[hfinkel]

LGTM.

Maybe I'm overlooking some existing commentary, but we should do a better job of documenting what the source and destination mean where there are multiple possible sources and/or destinations of the same distance. To be clear about what I mean, if I take your example from D13254:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  C[i] = A[i] * 2;
}

and I do this:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  A[i+8] = F[i] + 2;
  C[i] = A[i] * 2;
  D[i] = A[i] * 4;
}

are there multiple distance-8 dependencies, or only one for A[i] <-> A[i+8], and if only one, to which A[i+8] store does it refer (the first or the second). I realize this is a bit silly here, because one of these stores is dead, but generally speaking, we should define how this is represented.

[anemet]

In D13257#279151, @hfinkel wrote:

LGTM.

Thanks for the reviews, Hal!

Maybe I'm overlooking some existing commentary, but we should do a better job of documenting what the source and destination mean where there are multiple possible sources and/or destinations of the same distance. To be clear about what I mean, if I take your example from D13254:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  C[i] = A[i] * 2;
}

and I do this:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  A[i+8] = F[i] + 2;
  C[i] = A[i] * 2;
  D[i] = A[i] * 4;
}

are there multiple distance-8 dependencies, or only one for A[i] <-> A[i+8], and if only one, to which A[i+8] store does it refer (the first or the second). I realize this is a bit silly here, because one of these stores is dead, but generally speaking, we should define how this is represented.

There are multiple (=4) because kills are not taken into consideration. We just look at the pointers with the same underlying object, whether they are read or write and their order. So we get the full combination {S1, S2} -> {S3, S4}.

Let me add a comment about this.

[anemet]

In D13257#279151, @hfinkel wrote:

Maybe I'm overlooking some existing commentary, but we should do a better job of documenting what the source and destination mean where there are multiple possible sources and/or destinations of the same distance. To be clear about what I mean, if I take your example from D13254:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  C[i] = A[i] * 2;
}

and I do this:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  A[i+8] = F[i] + 2;
  C[i] = A[i] * 2;
  D[i] = A[i] * 4;
}

are there multiple distance-8 dependencies, or only one for A[i] <-> A[i+8], and if only one, to which A[i+8] store does it refer (the first or the second). I realize this is a bit silly here, because one of these stores is dead, but generally speaking, we should define how this is represented.

Hal, sorry for the huge delay on this but now that I got back to this and reread your question, I think I understand the disconnect. Dependence objects are between instructions and *not* between pointers/accesses. (This is one change when LAA was moved out of LV and the interface was generalized.) Thus we will have multiple distance-8 dependence here as I said in my original reply.

There is a comment before the Dependence class mentioning that this is a relation between instructions (and not pointers/accesses):

/// \brief Dependece between memory access instructions.
struct Dependence {

Let me know if that's sufficient or you want me to elaborate somehow.

Thanks,
Adam

[hfinkel]

In D13257#330229, @anemet wrote:

In D13257#279151, @hfinkel wrote:

Maybe I'm overlooking some existing commentary, but we should do a better job of documenting what the source and destination mean where there are multiple possible sources and/or destinations of the same distance. To be clear about what I mean, if I take your example from D13254:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  C[i] = A[i] * 2;
}

and I do this:

for (unsigned i = 0; i < 100; i++) {
  A[i+8] = B[i] + 2;
  A[i+8] = F[i] + 2;
  C[i] = A[i] * 2;
  D[i] = A[i] * 4;
}

are there multiple distance-8 dependencies, or only one for A[i] <-> A[i+8], and if only one, to which A[i+8] store does it refer (the first or the second). I realize this is a bit silly here, because one of these stores is dead, but generally speaking, we should define how this is represented.

Hal, sorry for the huge delay on this but now that I got back to this and reread your question, I think I understand the disconnect. Dependence objects are between instructions and *not* between pointers/accesses. (This is one change when LAA was moved out of LV and the interface was generalized.) Thus we will have multiple distance-8 dependence here as I said in my original reply.

There is a comment before the Dependence class mentioning that this is a relation between instructions (and not pointers/accesses):

/// \brief Dependece between memory access instructions.
struct Dependence {

Let me know if that's sufficient or you want me to elaborate somehow.

I think that's sufficient. Thanks for following-up.

Thanks,
Adam

include/llvm/Analysis/LoopAccessAnalysis.h

 
 namespace llvm {
 
 class Value;
 class DataLayout;
 class ScalarEvolution;
 class Loop;
 class SCEV;
+class LoopAccessInfo;
 
 /// Optimization analysis message produced during vectorization. Messages inform
 /// the user why vectorization did not occur.
 class LoopAccessReport {
   std::string Message;
   const Instruction *Instr;
 
 protected:
struct Dependence {
     /// \brief Index of the destination of the dependence in the InstMap vector.
     unsigned Destination;
     /// \brief The type of the dependence.
     DepType Type;
 
     Dependence(unsigned Source, unsigned Destination, DepType Type)
         : Source(Source), Destination(Destination), Type(Type) {}
 
+    /// \brief Return the source instruction of the dependence.
+    Instruction *getSource(const LoopAccessInfo &LAI) const;
+    /// \brief Return the destination instruction of the dependence.
+    Instruction *getDestination(const LoopAccessInfo &LAI) const;
+
     /// \brief Dependence types that don't prevent vectorization.
     static bool isSafeForVectorization(DepType Type);
 
     /// \brief Lexically backward dependence types.
     bool isPossiblyBackward() const;
 
     /// \brief Print the dependence.  \p Instr is used to map the instruction
     /// indices to instructions.
private:
 
   // The used analysis passes.
   ScalarEvolution *SE;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
 };
+
+inline Instruction *MemoryDepChecker::Dependence::getSource(
+    const LoopAccessInfo &LAI) const {
+  return LAI.getDepChecker().getMemoryInstructions()[Source];
+}
+
+inline Instruction *MemoryDepChecker::Dependence::getDestination(
+    const LoopAccessInfo &LAI) const {
+  return LAI.getDepChecker().getMemoryInstructions()[Destination];
+}
+
 } // End llvm namespace
 
 #endif