[DA] control compile-time spent by MIV tests

[bmahjour]

Summary

Function exploreDirections() in DependenceAnalysis implements a recursive algorithm for refining direction vectors. This algorithm has worst-case complexity of O(3^(n+1)) where n is the number of common loop levels. It essentially performs a search over a complete ternary tree of dependence directions. The algorithm tries to prune the search space by checking testBounds before recursing for each direction, but since the delta usually falls within the sum of lower and upper bounds the search space ends up being the full tree most of the time.

The problem can be illustrated with a deeply nested loop. For exampley DA takes more than a minute to analyze a 12 level deep loop nest containing a single load and a store (see example below and the attached IR) on a 3.1 GHz P8 machine with 600 GB of RAM.

for (int i1 = 0; i1 < n; i1++)
  for (int i2 = 0; i2 < n; i2++)
    ...
       for (int i12 = 0; i12 < n; i12++)
           A[i1 + i2 + ... + i12] = B[i1 + i2 ... + i12];

time1.simp.ll12 KBDownload

The compile-time increases exponentially as the depth of the loop nest increases.

In this patch I'm adding a threshold to control the amount of time we spend in doing MIV tests (which most of the time end up resulting in over pessimistic direction vectors anyway).

[Meinersbur]

Is it feasible tp add a test-case that reaches the threshold? If a loop depth of 12 takes a minute, would a test with depth 10 still be acceptable to run as part of the regression tests?

[bmahjour]

In D107159#2917530, @Meinersbur wrote:

Is it feasible tp add a test-case that reaches the threshold? If a loop depth of 12 takes a minute, would a test with depth 10 still be acceptable to run as part of the regression tests?

Not sure if it would be good to add a potentially long-running test (like a 10-level deep nest) to check-llvm. I tried this on a pretty powerful server...smaller systems or those under heavy load will likely take longer. However if you are interested in making sure that the DA results are still sensible when the threshold is reached, I could have a smaller, say 3-level loop nest and analyze it with da-miv-max-level-threshold=2. Would that be good?

[Meinersbur]

In D107159#2917586, @bmahjour wrote:

In D107159#2917530, @Meinersbur wrote:

Is it feasible tp add a test-case that reaches the threshold? If a loop depth of 12 takes a minute, would a test with depth 10 still be acceptable to run as part of the regression tests?

Not sure if it would be good to add a potentially long-running test (like a 10-level deep nest) to check-llvm. I tried this on a pretty powerful server...smaller systems or those under heavy load will likely take longer. However if you are interested in making sure that the DA results are still sensible when the threshold is reached, I could have a smaller, say 3-level loop nest and analyze it with da-miv-max-level-threshold=2. Would that be good?

Yes, that would be great! SCEV uses this approach as well.

[bmahjour]

Added a test and lowered the default threshold to 7.

[Meinersbur]

LGTM, thank you.

llvm/lib/Analysis/DependenceAnalysis.cpp

static cl::opt<bool> DisableDelinearizationChecks(
     "da-disable-delinearization-checks", cl::init(false), cl::Hidden,
     cl::ZeroOrMore,
     cl::desc(
         "Disable checks that try to statically verify validity of "
         "delinearized subscripts. Enabling this option may result in incorrect "
         "dependence vectors for languages that allow the subscript of one "
         "dimension to underflow or overflow into another dimension."));
 
+static cl::opt<unsigned> MIVMaxLevelThreshold(
+    "da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Maximum depth allowed for the recursive algorithm used to "
+             "explore MIV direction vectors."));
+
 //===----------------------------------------------------------------------===//
 // basics
 
 DependenceAnalysis::Result
 DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &AA = FAM.getResult<AAManager>(F);
   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
   auto &LI = FAM.getResult<LoopAnalysis>(F);

 // in the DirSet field of Bound. Returns the number of distinct
 // dependences discovered. If the dependence is disproved,
 // it will return 0.
 unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,
                                            CoefficientInfo *B, BoundInfo *Bound,
                                            const SmallBitVector &Loops,
                                            unsigned &DepthExpanded,
                                            const SCEV *Delta) const {
+  // This algorithm has worst case complexity of O(3^n), where 'n' is the number
+  // of common loop levels. To avoid excessive compile-time, pessimize all the
+  // results and immediately return when the number of common levels is beyond
+  // the given threshold.
+  if (CommonLevels > MIVMaxLevelThreshold) {
+    LLVM_DEBUG(dbgs() << "Number of common levels exceeded the threshold. MIV "
+                         "direction exploration is terminated.\n");
+    for (unsigned K = 1; K <= CommonLevels; ++K)
+      if (Loops[K])
+        Bound[K].DirSet = Dependence::DVEntry::ALL;
+    return 1;
+  }
+
   if (Level > CommonLevels) {
     // record result
     LLVM_DEBUG(dbgs() << "\t[");
     for (unsigned K = 1; K <= CommonLevels; ++K) {
       if (Loops[K]) {
         Bound[K].DirSet |= Bound[K].Direction;
 #ifndef NDEBUG
         switch (Bound[K].Direction) {

llvm/test/Analysis/DependenceAnalysis/MIVMaxLevelThreshold.ll

+; RUN: opt < %s -aa-pipeline=default -passes='print<da>' -da-miv-max-level-threshold=2
+
+;; Check to make sure when MIV tests reach a maximum depth level
+;; threshold, the resulting dependence is conservatively correct.
+
+;; for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;     for (int k = 0; k < o; k++)
+;;       A[i+j+k] = A[i-j+k] + B[i+j+k];
+
+
+; CHECK:       Src:  %2 = load float, float* %arrayidx, align 4 --> Dst:  %5 = load float, float* %arrayidx12, align 4
+; CHECK-NEXT:  da analyze - none!
+; CHECK:       Src:  %2 = load float, float* %arrayidx, align 4 --> Dst:  store float %add13, float* %arrayidx17, align 4
+; CHECK-NEXT:  da analyze - anti [* * *|<]!
+; CHECK:       Src:  %5 = load float, float* %arrayidx12, align 4 --> Dst:  store float %add13, float* %arrayidx17, align 4
+; CHECK-NEXT:  da analyze - none!
+
+define void @foo(float* noalias %A, float* noalias %B, i32 signext %m, i32 signext %n, i32 signext %o) {
+entry:
+  %cmp5 = icmp sgt i32 %n, 0
+  br i1 %cmp5, label %for.body.preheader, label %for.end23
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count21 = zext i32 %n to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.inc21
+  %indvars.iv19 = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next20, %for.inc21 ]
+  %cmp23 = icmp sgt i32 %m, 0
+  br i1 %cmp23, label %for.body4.preheader, label %for.inc21
+
+for.body4.preheader:                              ; preds = %for.body
+  %wide.trip.count17 = zext i32 %m to i64
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.body4.preheader, %for.inc18
+  %indvars.iv12 = phi i64 [ 0, %for.body4.preheader ], [ %indvars.iv.next13, %for.inc18 ]
+  %cmp61 = icmp sgt i32 %o, 0
+  br i1 %cmp61, label %for.body8.preheader, label %for.inc18
+
+for.body8.preheader:                              ; preds = %for.body4
+  %wide.trip.count = zext i32 %o to i64
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8.preheader, %for.body8
+  %indvars.iv = phi i64 [ 0, %for.body8.preheader ], [ %indvars.iv.next, %for.body8 ]
+  %0 = sub nsw i64 %indvars.iv19, %indvars.iv12
+  %1 = add nsw i64 %0, %indvars.iv
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %1
+  %2 = load float, float* %arrayidx, align 4
+  %3 = add nuw nsw i64 %indvars.iv19, %indvars.iv12
+  %4 = add nuw nsw i64 %3, %indvars.iv
+  %arrayidx12 = getelementptr inbounds float, float* %B, i64 %4
+  %5 = load float, float* %arrayidx12, align 4
+  %add13 = fadd fast float %2, %5
+  %6 = add nuw nsw i64 %indvars.iv19, %indvars.iv12
+  %7 = add nuw nsw i64 %6, %indvars.iv
+  %arrayidx17 = getelementptr inbounds float, float* %A, i64 %7
+  store float %add13, float* %arrayidx17, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.body8, label %for.inc18.loopexit
+
+for.inc18.loopexit:                               ; preds = %for.body8
+  br label %for.inc18
+
+for.inc18:                                        ; preds = %for.inc18.loopexit, %for.body4
+  %indvars.iv.next13 = add nuw nsw i64 %indvars.iv12, 1
+  %exitcond18 = icmp ne i64 %indvars.iv.next13, %wide.trip.count17
+  br i1 %exitcond18, label %for.body4, label %for.inc21.loopexit
+
+for.inc21.loopexit:                               ; preds = %for.inc18
+  br label %for.inc21
+
+for.inc21:                                        ; preds = %for.inc21.loopexit, %for.body
+  %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1
+  %exitcond22 = icmp ne i64 %indvars.iv.next20, %wide.trip.count21
+  br i1 %exitcond22, label %for.body, label %for.end23.loopexit
+
+for.end23.loopexit:                               ; preds = %for.inc21
+  br label %for.end23
+
+for.end23:                                        ; preds = %for.end23.loopexit, %entry
+  ret void
+}