Add support for annotated minimum dependence distance

[ArchDRobison]

Summary

This patch enables producers of LLVM IR to tell the LoopVectorizer (and other tools) that there is a minimum dependence distance, such as with the OpenMP 4.0 "safelen" clause. See email chain http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-August/075701.html for discussion. The updates to LangRef explain the final design.

[ArchDRobison]

Can I enlist one of you to review this patch? I've updated to adjust for Renato's recent updates to hint processing..

[hfinkel]

Generally speaking, I think this is fine. You definitely need to run this through clang-format (which you can do directly on the patch file, IIRC), or manually fix the formatting to comply with the LLVM coding conventions.

However, if the main use case for this is dealing with OpenMP's safelen (and possibly other similar user-provided safety assertions), then I would like to get a resolution on the lexical dependency question (i.e. whether we really also need some ordering construct here).

Also, for future reference, please upload full-context diffs (see http://llvm.org/docs/Phabricator.html for instructions).

[ArchDRobison]

Update adjusts patch for this morning's LLVM trunk, and was cleaned up with clang-format-diff.py.

[rengolin]

Any progress in this? If not, can we close this review?

[hfinkel]

I believe that we had discussed this in a different thread, and decided that we needed to record a partial ordering in this metadata. It looks like a new patch has not yet been developed.

[ArchDRobison]

I believe that support for forward lexical dependences was the item that required partial ordering support, but was orthogonal to this patch, which addresses minimum dependence distance.

• Arch

[hfinkel]

In D5123#137651, @ArchDRobison wrote:

I believe that support for forward lexical dependences was the item that required partial ordering support, but was orthogonal to this patch, which addresses minimum dependence distance.

I was not under the impression that it is orthogonal (or it is a prerequisite). Right now, we only have a way to specify that a loop is completely data parallel (no loop carried dependencies at all), so it does not really matter. It does matter, however, if we have a minimum dependency distance, because that distance can have a validity dependence on lexical dependencies (forward and backward) that are sensitive to potential reordering.

Also, as a separate matter, the unroller, when it does partial unrolling, needs to update this metadata (to divide the distances by the unrolling factor).

[ArchDRobison]

Thanks for the reminder about the reordering issue. I'll abandon this patch.

docs/LangRef.rst

 
    !0 = metadata !{ metadata !"llvm.loop.unroll.full" }
 
+'``llvm.loop.minimum_dependence_distance``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+This metadata specifies a minimum dependence distance for accesses marked
+with ``llvm.mem.parallel_loop_access``. The first operand is the string
+``llvm.loop.minimum_dependence_distance`` and the second operand is a
+positive integer specifying the minimum distance.
+For example:
+
+.. code-block:: llvm
+
+   !0 = metadata !{metadata !"llvm.loop.minimum_dependence_distance", i32 4}
+
+specifies that parallel accesses have a minimum dependence distance of 4.
+
 '``llvm.mem``'
 ^^^^^^^^^^^^^^^
 

 The ``llvm.mem.parallel_loop_access`` metadata refers to a loop identifier, 
 or metadata containing a list of loop identifiers for nested loops. 
 The metadata is attached to memory accessing instructions and denotes that 
-no loop carried memory dependence exist between it and other instructions denoted 
-with the same loop identifier.
+any loop carried memory dependence between it and other instructions denoted 
+with the same loop identifier have a minimum dependence distance of ``k``,
+where ``k`` is specified by ``llvm.mem.minimum_dependence_distance`` metadata
+on the loop.  If ``k`` is not specified by such metadata, it is positive 
+infinity.
 
 Precisely, given two instructions ``m1`` and ``m2`` that both have the 
 ``llvm.mem.parallel_loop_access`` metadata, with ``L1`` and ``L2`` being the 
 set of loops associated with that metadata, respectively, then there is no loop 
-carried dependence between ``m1`` and ``m2`` for loops in both ``L1`` and 
-``L2``.
+carried dependence with distance less than ``k1`` and ``k2`` between 
+``m1`` and ``m2`` for loops in both ``L1`` and ``L2``, where ``k1`` and ``k2``
+are the minimum distancesd specified by ``llvm.loop.minimum_dependence_distance``
+on ``L1`` and ``L2`` respectively (or the default of infinity if not specified).  
 
 As a special case, if all memory accessing instructions in a loop have 
-``llvm.mem.parallel_loop_access`` metadata that refers to that loop, then the 
-loop has no loop carried memory dependences and is considered to be a parallel 
-loop.  
+``llvm.mem.parallel_loop_access`` metadata that refers to that loop and
+``llvm.loop.minimum_dependence_distance`` is not specified for the loop,
+then the loop has no loop carried memory dependences and is considered to 
+be a parallel loop.  
 
 Note that if not all memory access instructions have such metadata referring to 
 the loop, then the loop is considered not being trivially parallel. Additional 

include/llvm/Analysis/LoopInfo.h

   /// isSafeToClone - Return true if the loop body is safe to clone in practice.
   bool isSafeToClone() const;
 
-  /// Returns true if the loop is annotated parallel.
+  /// Returns true if the loop is annotated parallel *without* distance restrictions.
   ///
   /// A parallel loop can be assumed to not contain any dependencies between
   /// iterations by the compiler. That is, any loop-carried dependency checking

   /// iterations is not guaranteed, thus, the end result might or might not
   /// implement actual concurrent execution of instructions across multiple
   /// iterations.
-  bool isAnnotatedParallel() const;
+  bool isAnnotatedParallel() const {
+    return getAnnotatedRestrictedParallel().second==0;
+  };
 
+  /// Determine if the loop is annotated parallel, possibly with distance restrictions.
+  ///
+  /// Let (p,k) denote the returned pair.
+  /// If p==false, no assumptions can be made.  k is always 1 in this case.
+  /// If p==true && k==0, then the loop can be assumed to have no 
+  /// dependencies between iterations, i.e. isAnnotatedParallel()==true.  
+  /// If p==true && k>0, the loop can be assumed to have no dependencies
+  /// with distance less than k between iterations.
+  std::pair<bool,unsigned> getAnnotatedRestrictedParallel() const;
+
   /// Return the llvm.loop loop id metadata node for this loop if it is present.
   ///
   /// If this loop contains the same llvm.loop metadata on each branch to the

lib/Analysis/LoopInfo.cpp

   }
 }
 
-bool Loop::isAnnotatedParallel() const {
+std::pair<bool,unsigned> Loop::getAnnotatedRestrictedParallel() const {
   MDNode *desiredLoopIdMetadata = getLoopID();
 
   if (!desiredLoopIdMetadata)
-      return false;
+      return std::make_pair(false,1u);
 
   // The loop branch contains the parallel loop metadata. In order to ensure
   // that any parallel-loop-unaware optimization pass hasn't added loop-carried

       MDNode *loopIdMD = II->getMetadata("llvm.mem.parallel_loop_access");
 
       if (!loopIdMD)
-        return false;
+          return std::make_pair(false,1u);
 
       bool loopIdMDFound = false;
       for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) {

       }
 
       if (!loopIdMDFound)
-        return false;
+        return std::make_pair(false,1);
     }
   }
-  return true;
+
+  // Check for restriction to distance d.  If present, it appears as a non-first 
+  // operand of the loopId with the form 
+  //   'metadata !"llvm.loop.minimum_dependence_distance", i32 d'
+  for (unsigned i = 1, ie = desiredLoopIdMetadata->getNumOperands(); i < ie; ++i)
+    if (const MDNode *MD = dyn_cast<MDNode>(desiredLoopIdMetadata->getOperand(i)))
+      if (MD->getNumOperands() == 2)
+        if (MDString *s = dyn_cast<MDString>(MD->getOperand(0)))
+          if (s->getString() == "llvm.loop.minimum_dependence_distance") 
+            return std::make_pair(true,
+              dyn_cast<ConstantInt>(MD->getOperand(1))->getZExtValue());
+
+  // Zero is convention for unrestricted.
+  return std::make_pair(true,0);
 }
 
 

lib/Transforms/Vectorize/LoopVectorize.cpp

                             AliasAnalysis *AA, Function *F)
       : NumLoads(0), NumStores(0), NumPredStores(0), TheLoop(L), SE(SE), DL(DL),
         DT(DT), TLI(TLI), AA(AA), TheFunction(F), Induction(nullptr),
-        WidestIndTy(nullptr), HasFunNoNaNAttr(false), MaxSafeDepDistBytes(-1U) {
+        WidestIndTy(nullptr), HasFunNoNaNAttr(false), MaxSafeDepDistBytes(-1U), 
+        AnnotatedMinDepDist(1) {
   }
 
   /// This enum represents the kinds of reductions that we support.

 
   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
 
+  void adjustForAnnotatedMinDepDist( unsigned WidestTypeBytes ) {
+     if( AnnotatedMinDepDist!=1 ) 
+        MaxSafeDepDistBytes = AnnotatedMinDepDist < -1u/WidestTypeBytes 
+                              ? AnnotatedMinDepDist*WidestTypeBytes
+                              : -1u;
+  }
+
   bool hasStride(Value *V) { return StrideSet.count(V); }
   bool mustCheckStrides() { return !StrideSet.empty(); }
   SmallPtrSet<Value *, 8>::iterator strides_begin() {

   bool HasFunNoNaNAttr;
 
   unsigned MaxSafeDepDistBytes;
+  unsigned AnnotatedMinDepDist;
 
   ValueToValueMap Strides;
   SmallPtrSet<Value *, 8> StrideSet;

       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i)
         Vals.push_back(LoopID->getOperand(i));
 
-    Vals.push_back(
-        createHint(Context, Twine(Prefix(), "vectorize.width").str(), Width));
-    Vals.push_back(
-        createHint(Context, Twine(Prefix(), "interleave.count").str(), 1));
+    Vals.push_back(createHint(Context, Twine(Prefix(), "vectorize.width").str(), Width));
+    Vals.push_back(createHint(Context, Twine(Prefix(), "interleave.count").str(), 1));
+    updateHintIfPresent(Context, Vals, Twine(Prefix(), "minimum_dependence_distance").str(), 1);
 
     MDNode *NewLoopID = MDNode::get(Context, Vals);
     // Set operand 0 to refer to the loop id itself.

     }
   }
 
+  // If Vals has hint with given name, update it with similar hint with value V.
+  template <typename Vec>
+  void updateHintIfPresent(LLVMContext &Context, Vec& Vals, StringRef Name, unsigned V) {
+    // Look for hint with same string, and if it exists, update it in place.
+    for (auto &U : Vals)
+      if (U)
+        if (MDNode *MD = dyn_cast<MDNode>(U))
+          if (MD->getNumOperands()>0 )
+            if (MDString *S = dyn_cast<MDString>(MD->getOperand(0)))
+              if (S->getString().equals(Name)) {
+                U = createHint(Context, Name, V);
+                break;
+              }
+  }
+
   /// Vectorization width.
   unsigned Width;
   /// Vectorization unroll factor.

   PtrRtCheck.Pointers.clear();
   PtrRtCheck.Need = false;
 
-  const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
+  const auto Annotations = TheLoop->getAnnotatedRestrictedParallel();
+  // Logic below handles fully parallel loops by treating them
+  // as having a very large dependence distance.
+  AnnotatedMinDepDist = Annotations.second ? Annotations.second : -1u;
+
+  const bool NeedDepCheck = AnnotatedMinDepDist==1;
   MemoryDepChecker DepChecker(SE, DL, TheLoop);
 
   // For each block.

           continue;
 
         LoadInst *Ld = dyn_cast<LoadInst>(it);
-        if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
+        if (!Ld || (!Ld->isSimple() && NeedDepCheck)) {
           emitAnalysis(Report(Ld)
                        << "read with atomic ordering or volatile read");
           DEBUG(dbgs() << "LV: Found a non-simple load.\n");

           emitAnalysis(Report(it) << "instruction cannot be vectorized");
           return false;
         }
-        if (!St->isSimple() && !IsAnnotatedParallel) {
+        if (!St->isSimple() && NeedDepCheck) {
           emitAnalysis(Report(St)
                        << "write with atomic ordering or volatile write");
           DEBUG(dbgs() << "LV: Found a non-simple store.\n");

     }
   }
 
-  if (IsAnnotatedParallel) {
+  if (!NeedDepCheck) {
     DEBUG(dbgs()
-          << "LV: A loop annotated parallel, ignore memory dependency "
-          << "checks.\n");
+          << "LV: A loop annotated with min dependence distance " 
+          << AnnotatedMinDepDist << ", ignore memory dependency checks.\n");
     return true;
   }
 

   unsigned WidestType = getWidestType();
   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
   unsigned MaxSafeDepDist = -1U;
+  Legal->adjustForAnnotatedMinDepDist(WidestType / 8);
   if (Legal->getMaxSafeDepDistBytes() != -1U)
     MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
   WidestRegister = ((WidestRegister < MaxSafeDepDist) ?

test/Transforms/LoopVectorize/X86/min-dep-dist.ll

+; RUN: opt < %s  -loop-vectorize -mcpu=corei7-avx -S | FileCheck %s
+; CHECK-NOT: memcheck
+; CHECK-NOT: <8 x float
+; CHECK-NOT: <4 x float
+; CHECK: <2 x float
+; CHECK-NOT: minimum_dependence_distance", i32 2}
+ 
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Simple routine that would be vectorized wider than 2
+; if llvm.loop.minimum_dependence_distance were not present.
+define void @foo(float* %a, float* %b) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %i = getelementptr inbounds float* %a, i64 %indvars.iv
+  %t = load float* %i, align 4, !llvm.mem.parallel_loop_access !0
+  %mul = fmul float %t, %t
+  %j = getelementptr inbounds float* %b, i64 %indvars.iv
+  store float %mul, float* %j, align 4, !llvm.mem.parallel_loop_access !0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0
+
+for.end:
+  ret void
+}
+
+!0 = metadata !{metadata !0, metadata !1}
+!1 = metadata !{metadata !"llvm.loop.minimum_dependence_distance", i32 2}