[DA] Enable -da-delinearize by default

[dmgreen]

Summary

We already use this flag for the tests we run. This should make it safe to use by
checking that the subscript we use are within bounds of the array dimensions
we compute, preventing subscripts from wrapping into the next dimension.

Enabling it by default can help increase the power of DA for multi dimensional
array accesses.

[fhahn]

Thanks Dave! This should be helpful for LoopInterchange after D35430. Did you measure any the compile-time impact of this?

[dmgreen]

Re add a missing 'a'

[dmgreen]

Ah, yes. I will try to get some compile time numbers. I expect it is in the noise for all the rest that DA is doing (but may be being optimistic). I will check.

[javed.absar]

AFAIU this change would affect other targets. Probably best to add more reviewers (owners for other targets).

[grosser]

We probably need to also add code that ensures that the arrays that result from delinearization remain within bounds. Without this code, the resulting checks are likely incorrect.

[hfinkel]

In D45872#1073553, @grosser wrote:

We probably need to also add code that ensures that the arrays that result from delinearization remain within bounds. Without this code, the resulting checks are likely incorrect.

I agree. To be clear, I think that this means addressing the FIXME in the code:

// The delinearization transforms a single-subscript MIV dependence test into
// a multi-subscript SIV dependence test that is easier to compute. So we
// resize Pair to contain as many pairs of subscripts as the delinearization
// has found, and then initialize the pairs following the delinearization.
Pair.resize(size);
for (int i = 0; i < size; ++i) {
  Pair[i].Src = SrcSubscripts[i];
  Pair[i].Dst = DstSubscripts[i];
  unifySubscriptType(&Pair[i]);

  // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
  // delinearization has found, and add these constraints to the dependence
  // check to avoid memory accesses overflow from one dimension into another.
  // This is related to the problem of determining the existence of data
  // dependences in array accesses using a different number of subscripts: in
  // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
}

I'd assumed that is why delinearization is disabled by default.

[grosser]

Exactly. The reason this was not done before is that we did not really had a user. Historically the LLVM's DA was implemented without users, then we added delinearization with Polly being the first (and only) user. The classical loop transformation passes came only later.

[dmgreen]

Ah, I see. Thanks for the information. I had tried some example loops, but apparently hadn't tried the right thing. I'll hopefully look into it.

[dmgreen]

This attempts to statically prove that the subscripts found by delinearization will always be within bounds of the array dimensions calculated. It does not feel super powerful, and the idea of storing the bounds and using them in later calculations may be better. It also doesn't attempt to do anything like runtime-checks. It will hopefully make da-delin correct though.

[fhahn]

lib/Analysis/DependenceAnalysis.cpp

3266

How about using SCEVAddRecExpr::evaluateAtIteration here?

[dmgreen]

Thanks for the suggestion. You learn something new every day.

This adds some type checking that is needed. During the testing I found this delinearization doesn't work as well on 64bit systems due to all the extra extends being added. Presumably polly has a better way of dealing with this.

[dmgreen]

Rebase

[philip.pfaffe]

Some inline nits. What worries me slightly is that the test oracle changed in GCD.ll. Why is that? Where the tests plainly wrong before?

lib/Analysis/DependenceAnalysis.cpp

3257

I'd prefer a continue over a structured block here.

3258

tryDeliniarize is a 300LOC function. Instead of the lambda, why not make this a static function?

3283

Double 'using'.

[dmgreen]

Thanks for the comments. I've moved things around as a result of your suggestions.

I managed to create https://rise4fun.com/Z3/oCi2 for the change in GCD.ll, which seems to be able come up with valid solutions for both < and > in i (Providing N < 0 is valid). The ones in SymbolicSIV.ll seem wrong too.

[dmgreen]

Ping.

https://rise4fun.com/Z3/hP6p is a slightly cleaner version of the proof for the change in GCD.ll.

[bcahoon]

Hi,

This patch looks good to me. I applied it to our code and ran some of our internal correctness and performance tests (for Hexagon), and the results came back clean.

This new delinearization code misses some cases that the old version caught. For example, something like the following, which cannot be delinearized because of the isKnownNonNegative check, so the dependence distance is not computed exactly.

unsigned foo(unsigned *restrict a, unsigned *restrict b, unsigned h, unsigned w, unsigned ss, unsigned ds) {
  unsigned sum = 0;
  for ( unsigned y = 1; y < h - 1; ++y) {
    for ( unsigned x = 1; x < w - 1; ++x ) {
      unsigned char sum = 0;
      sum += a[x + ss];
      sum += a[x + ss + 1];
      b[x] = sum;
    }
    a += ss;
    b += ds;
  }
  return sum;
}

Thanks,
Brendon

[dmgreen]

Hello. Thanks for running the tests. I did not know that there were uses outside of loop interchange and now unroll and jam. That's good to know it will get some more use.

By the old delinearise code, do you mean the one that was based on geps, or this one without these extra checks in it? I believe unfortunately that both could produce wrong dependencies in some cases.

For your example, what would you expect the dependency between the two loads to be? I think it is difficult to prove anything other than [* *] (Because ss could be 0, or a value lower than w). Delinearizing using scevs seems to be a tricky business, and there may be cases that are tough to prove. I think this is better than what is in tree at the moment though, and brings the code in line with what we test, which I think is important.

[bcahoon]

Hi David,

We have a (loop) scalar replacement implementation that uses the dependence analysis information. We don't really need/use it much anymore for various reasons, including that there are other LLVM passes that get much of the same benefits.

You're correct about the problems with delinearizing. I think it was Sebastian who added a patch a while back that removed some of the delinearization code in DA that was incorrect (using the GEPs). My example was a bad one, though. Sorry about that. I was trying to show an example where we could possibly delinearize correctly but still doesn't work with your patch. I still think your patch is good as-is, and enabling the DA with delinearization is great, but I'm not sure if/what other opportunities it's still missing.

Thanks,
Brendon

[dmgreen]

Yes, I agree. There are hopefully multiple improvements we can make in the future. I remember seeing one patch recently (40369) that should help delinearise when sext's are involved (which I think happens a lot on 64bit machines). One thing that would probably be good to add somehow would be versioning based on needs of the loop. For example in your case it could check that ss is more than w, or in a more general case check that arrays do not alias. I know polly is very good at that, but it's not something we have for DA yet.

Hopefully we can improve things as we go.

[sebpop]

lgtm thanks!

[dmgreen]

Thanks!

lib/Analysis/DependenceAnalysis.cpp

 STATISTIC(GCDapplications, "GCD applications");
 STATISTIC(GCDsuccesses, "GCD successes");
 STATISTIC(GCDindependence, "GCD independence");
 STATISTIC(BanerjeeApplications, "Banerjee applications");
 STATISTIC(BanerjeeIndependence, "Banerjee independence");
 STATISTIC(BanerjeeSuccesses, "Banerjee successes");
 
 static cl::opt<bool>
-Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
+    Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore,
                 cl::desc("Try to delinearize array references."));
 
 //===----------------------------------------------------------------------===//
 // basics
 
 DependenceAnalysis::Result
 DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &AA = FAM.getResult<AAManager>(F);
   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
 
   // Fail when there is only a subscript: that's a linearized access function.
   if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
       SrcSubscripts.size() != DstSubscripts.size())
     return false;
 
   int size = SrcSubscripts.size();
 
+  // Statically check that the array bounds are in-range
+  // FIXME: It may be better to record these sizes and add them as constraints
+  // to the dependency checks.
+  for (int i = 0; i < size; ++i) {
+    if (i != 0) {
+      auto isKnownLessThan = [=](const SCEV *S, const SCEV *Size) {
+        // First unify to the same type
+        auto *SType = dyn_cast<IntegerType>(S->getType());
+        auto *SizeType = dyn_cast<IntegerType>(Size->getType());
+        if (!SType || !SizeType)
+          return false;
+        Type *MaxType = (SType->getBitWidth() >= SizeType->getBitWidth())
+                            ? SType
+                            : SizeType;
+        S = SE->getTruncateOrZeroExtend(S, MaxType);
+        Size = SE->getTruncateOrZeroExtend(Size, MaxType);
+
+        // Special check for addrecs using BE taken count
+        const SCEV *Bound = SE->getMinusSCEV(S, Size);
+        if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
+          if (AddRec->isAffine()) {
+            const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop());
+            if (!isa<SCEVCouldNotCompute>(BECount)) {
+              const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE);
+              if (SE->isKnownNegative(Limit))
+                return true;
+            }
+          }
+        }
+
+        // Check using using normal isKnownNegative
+        const SCEV *LimitedBound = SE->getMinusSCEV(
+            S, SE->getSMaxExpr(Size, SE->getOne(Size->getType())));
+        return SE->isKnownNegative(LimitedBound);
+      };
+
+      if (!SE->isKnownNonNegative(SrcSubscripts[i]))
+        return false;
+
+      if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
+        return false;
+
+      if (!SE->isKnownNonNegative(DstSubscripts[i]))
+        return false;
+
+      if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
+        return false;
+    }
+  }
+
   DEBUG({
       dbgs() << "\nSrcSubscripts: ";
     for (int i = 0; i < size; i++)
       dbgs() << *SrcSubscripts[i];
     dbgs() << "\nDstSubscripts: ";
     for (int i = 0; i < size; i++)
       dbgs() << *DstSubscripts[i];
     });
 
   // The delinearization transforms a single-subscript MIV dependence test into
   // a multi-subscript SIV dependence test that is easier to compute. So we
   // resize Pair to contain as many pairs of subscripts as the delinearization
   // has found, and then initialize the pairs following the delinearization.
   Pair.resize(size);
   for (int i = 0; i < size; ++i) {
     Pair[i].Src = SrcSubscripts[i];
     Pair[i].Dst = DstSubscripts[i];
     unifySubscriptType(&Pair[i]);
-
-    // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
-    // delinearization has found, and add these constraints to the dependence
-    // check to avoid memory accesses overflow from one dimension into another.
-    // This is related to the problem of determining the existence of data
-    // dependences in array accesses using a different number of subscripts: in
-    // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
   }
 
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG

test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll

-; RUN: opt -basicaa -da -analyze -da-delinearize < %s
+; RUN: opt -basicaa -da -analyze < %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, double *A) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)

test/Analysis/DependenceAnalysis/Banerjee.ll

 ; RUN: opt < %s -analyze -basicaa -da -da-delinearize=false | FileCheck %s
-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s -check-prefix=DELIN
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s -check-prefix=DELIN
 
-; ModuleID = 'Banerjee.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 1; i <= 10; i++)
 ;;    for (long int j = 1; j <= 10; j++) {
 ;;      A[10*i + j] = 0;
 ;;      *B++ = A[10*i + j - 1];

test/Analysis/DependenceAnalysis/Coupled.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'Coupled.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 0; i < 50; i++) {
 ;;    A[i][i] = i;
 ;;    *B++ = A[i + 10][i + 9];
 

test/Analysis/DependenceAnalysis/DADelin.ll

+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv8m.main-arm-none-eabi"
+
+; CHECK-LABEL: t1
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k] =
+define void @t1(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - consistent anti [0 0 0|<]!
+; CHECK: da analyze - none!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  store i32 %add12, i32* %arrayidx, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t2
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k + 1] =
+define void @t2(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [* * *|<]!
+; CHECK: da analyze - output [* * *]!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %add111 = add nsw i32 %add11, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t3
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k - 1] =
+define void @t3(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [* * *|<]!
+; CHECK: da analyze - output [* * *]!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %add111 = sub nsw i32 %add11, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t4
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k + o] =
+define void @t4(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [* * *|<]!
+; CHECK: da analyze - output [* * *]!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %add111 = add nsw i32 %add11, %o
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t5
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k - o] =
+define void @t5(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [* * *|<]!
+; CHECK: da analyze - output [* * *]!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %add111 = sub nsw i32 %add11, %o
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t6
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k + m*o] =
+define void @t6(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - consistent anti [-1 0 0]!
+; CHECK: da analyze - none!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %mo = mul i32 %m, %o
+  %add111 = add nsw i32 %add11, %mo
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t7
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 0; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k - m*o] =
+define void @t7(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - consistent anti [1 0 0]!
+; CHECK: da analyze - none!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 0, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %mo = mul i32 %m, %o
+  %add111 = sub nsw i32 %add11, %mo
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+; CHECK-LABEL: t8
+;;  for (int i = 0; i < n; i++)
+;;   for (int j = 0; j < m; j++)
+;;    for (int k = 1; k < o; k++)
+;;      = A[i*m*o + j*o + k]
+;;     A[i*m*o + j*o + k - 1] =
+define void @t8(i32 %n, i32 %m, i32 %o, i32* nocapture %A) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - consistent anti [0 0 1]!
+; CHECK: da analyze - none!
+entry:
+  %cmp49 = icmp sgt i32 %n, 0
+  br i1 %cmp49, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %cmp247 = icmp sgt i32 %m, 0
+  %cmp645 = icmp sgt i32 %o, 0
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %i.050 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc23, %for.cond.cleanup3 ]
+  br i1 %cmp247, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup3
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond1.preheader
+  %mul = mul nsw i32 %i.050, %m
+  br label %for.cond5.preheader
+
+for.cond5.preheader:                              ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %j.048 = phi i32 [ 0, %for.cond5.preheader.lr.ph ], [ %inc20, %for.cond.cleanup7 ]
+  br i1 %cmp645, label %for.body8.lr.ph, label %for.cond.cleanup7
+
+for.body8.lr.ph:                                  ; preds = %for.cond5.preheader
+  %mul944 = add i32 %j.048, %mul
+  %add = mul i32 %mul944, %o
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %k.046 = phi i32 [ 1, %for.body8.lr.ph ], [ %inc, %for.body8 ]
+  %add11 = add nsw i32 %k.046, %add
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add11
+  %0 = load i32, i32* %arrayidx, align 4
+  %add12 = add nsw i32 %0, 1
+  %add111 = sub nsw i32 %add11, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add111
+  store i32 %add12, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i32 %k.046, 1
+  %exitcond = icmp eq i32 %inc, %o
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+
+for.cond.cleanup7:                                ; preds = %for.body8, %for.cond5.preheader
+  %inc20 = add nuw nsw i32 %j.048, 1
+  %exitcond51 = icmp eq i32 %inc20, %m
+  br i1 %exitcond51, label %for.cond.cleanup3, label %for.cond5.preheader
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7, %for.cond1.preheader
+  %inc23 = add nuw nsw i32 %i.050, 1
+  %exitcond52 = icmp eq i32 %inc23, %n
+  br i1 %exitcond52, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+}
+
+
+; CHECK-LABEL: test_sizes
+define double @test_sizes(i16 %h, i16 %N, i16* nocapture %array) {
+; CHECK: da analyze - consistent input [0 S]!
+; CHECK: da analyze - anti [* *|<]!
+; CHECK: da analyze - output [* *]!
+entry:
+  %cmp28 = icmp sgt i16 %N, 1
+  br i1 %cmp28, label %for.body.lr.ph, label %for.end12
+
+for.body.lr.ph:                                   ; preds = %entry
+  %cmp425 = icmp slt i16 %h, 0
+  %0 = add i16 %h, 1
+  %wide.trip.count = zext i16 %N to i32
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc10, %for.body.lr.ph
+  %indvars.iv32 = phi i32 [ 1, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc10 ]
+  %indvars.iv = phi i16 [ 2, %for.body.lr.ph ], [ %indvars.iv.next, %for.inc10 ]
+  br i1 %cmp425, label %for.inc10, label %for.body5.lr.ph
+
+for.body5.lr.ph:                                  ; preds = %for.body
+  %1 = sext i16 %indvars.iv to i32
+  %arrayidx = getelementptr inbounds i16, i16* %array, i32 %indvars.iv32
+  br label %for.body5
+
+for.body5:                                        ; preds = %for.body5, %for.body5.lr.ph
+  %indvars.iv30 = phi i32 [ %indvars.iv.next31, %for.body5 ], [ %1, %for.body5.lr.ph ]
+  %j.027 = phi i16 [ %inc, %for.body5 ], [ 0, %for.body5.lr.ph ]
+  %2 = load i16, i16* %arrayidx, align 4
+  %add6 = add nsw i16 %2, %j.027
+  %arrayidx8 = getelementptr inbounds i16, i16* %array, i32 %indvars.iv30
+  store i16 %add6, i16* %arrayidx8, align 4
+  %inc = add nuw nsw i16 %j.027, 1
+  %indvars.iv.next31 = add nsw i32 %indvars.iv30, 1
+  %exitcond = icmp eq i16 %inc, %0
+  br i1 %exitcond, label %for.inc10, label %for.body5
+
+for.inc10:                                        ; preds = %for.body5, %for.body
+  %indvars.iv.next33 = add nuw nsw i32 %indvars.iv32, 1
+  %indvars.iv.next = add i16 %indvars.iv, %0
+  %exitcond34 = icmp eq i32 %indvars.iv.next33, %wide.trip.count
+  br i1 %exitcond34, label %for.end12, label %for.body
+
+for.end12:                                        ; preds = %for.inc10, %entry
+  ret double undef
+}
 No newline at end of file

test/Analysis/DependenceAnalysis/ExactSIV.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'ExactSIV.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long unsigned i = 0; i < 10; i++) {
 ;;    A[i + 10] = i;
 ;;    *B++ = A[2*i + 1];
 

test/Analysis/DependenceAnalysis/GCD.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s -check-prefix=DELIN
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s -check-prefix=DELIN
 
-; ModuleID = 'GCD.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 0; i < 100; i++)
 ;;    for (long int j = 0; j < 100; j++) {
 ;;      A[2*i - 4*j] = i;
 ;;      *B++ = A[6*i + 8*j];

 ;;      A[5*i + 10*j*M + 9*M*N] = i;
 ;;      *B++ = A[15*i + 20*j*M - 21*N*M + 4];
 
 define void @gcd4(i32* %A, i32* %B, i64 %M, i64 %N) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd4
-; DELIN: da analyze - none!
+; DELIN: da analyze - output [* *]!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - none!
+; DELIN: da analyze - input [* *]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc17
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
   br label %for.body3
 

 ;;      A[5*i + 10*j*M + 9*M*N] = i;
 ;;      *B++ = A[15*i + 20*j*M - 21*N*M + 5];
 
 define void @gcd5(i32* %A, i32* %B, i64 %M, i64 %N) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd5
-; DELIN: da analyze - none!
-; DELIN: da analyze - flow [> *]!
+; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - flow [<> *]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - none!
+; DELIN: da analyze - input [* *]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc17
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
   br label %for.body3
 

 ;;      *B++ = A[8*i][6*j + 1];
 
 define void @gcd6(i64 %n, i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   %cmp4 = icmp sgt i64 %n, 0
   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end12
 
 ; DELIN-LABEL: gcd6
-; DELIN: da analyze - none!
+; DELIN: da analyze - output [* *]!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - none!
+; DELIN: da analyze - input [* *]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - output [* *]!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc10
   %i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ]

test/Analysis/DependenceAnalysis/Invariant.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
 ; Test for a bug, which caused an assert when an invalid
 ; SCEVAddRecExpr is created in addToCoefficient.
 
 ; CHECK-LABEL: foo
 ; CHECK: da analyze - consistent input [S 0]!
 ; CHECK: da analyze - input [* *|<]!
 ; CHECK: da analyze - none!

test/Analysis/DependenceAnalysis/LoopExitingIV.ll

for.end:
   store i32 2, i32* %arrayidx1, align 4
   ret void
 }
 
 ; CHECK-LABEL: extraouterloop
 define void @extraouterloop(i32* nocapture %A, i32 %M) {
 ; CHECK: da analyze - consistent output [S 0]!
 ; CHECK: da analyze - output [S|<]!
-; CHECK: da analyze - output [S]!
+; CHECK: da analyze - consistent output [S]!
 
 entry:
   br label %for.outer
 
 for.outer:
   %z = phi i32 [ 0, %entry ], [ %zinc, %for.end ]
   br label %for.body
 

test/Analysis/DependenceAnalysis/NonAffineExpr.ll

-; RUN: opt < %s -analyze -basicaa -da-delinearize -da
+; RUN: opt < %s -analyze -basicaa -da
 ;
 ; CHECK: da analyze - consistent input [S S]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* *]!
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"
 target triple = "thumbv7--linux-gnueabi"
 

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s -check-prefix=DELIN
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s -check-prefix=DELIN
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 ; for (int i = 0; i < 100; ++i) {
 ;   int t0 = a[i][i];
 ;   int t1 = t0 + 1;
 ;   a[i][5] = t1;

test/Analysis/DependenceAnalysis/Preliminary.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'Preliminary.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;int p0(int n, int *A, int *B) {
 ;;  A[0] = n;
 ;;  return B[1];
 

test/Analysis/DependenceAnalysis/Propagating.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'Propagating.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 0; i < 100; i++)
 ;;    for (long int j = 0; j < 100; j++) {
 ;;      A[i + 1][i + j] = i;
 ;;      *B++ = A[i][i + j];

test/Analysis/DependenceAnalysis/Separability.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'Separability.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 0; i < 50; i++)
 ;;    for (long int j = 0; j < 50; j++)
 ;;      for (long int k = 0; k < 50; k++)
 ;;        for (long int l = 0; l < 50; l++) {

test/Analysis/DependenceAnalysis/StrongSIV.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'StrongSIV.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (int i = 0; i < n; i++) {
 ;;    A[i + 2] = i;
 ;;    *B++ = A[i];
 

test/Analysis/DependenceAnalysis/SymbolicSIV.ll

-; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
 
-; ModuleID = 'SymbolicSIV.bc'
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 0; i < n; i++) {
 ;;    A[2*i + n] = i;
 ;;    *B++ = A[3*i + 3*n];
 

 
 define void @symbolicsiv6(i32* %A, i32* %B, i64 %n, i64 %N, i64 %M) nounwind uwtable ssp {
 entry:
   %cmp1 = icmp eq i64 %n, 0
   br i1 %cmp1, label %for.end, label %for.body.preheader
 
 ; CHECK-LABEL: symbolicsiv6
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [0|<]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 

 ;;    *B++ = A[2*N*i - 3*M + 2];
 
 define void @symbolicsiv7(i32* %A, i32* %B, i64 %n, i64 %N, i64 %M) nounwind uwtable ssp {
 entry:
   %cmp1 = icmp eq i64 %n, 0
   br i1 %cmp1, label %for.end, label %for.body.preheader
 ; CHECK-LABEL: symbolicsiv7
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [0|<]!
+; CHECK: da analyze - flow [<>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 

test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll

-; RUN: opt < %s -basicaa -da-delinearize -loop-interchange -verify-dom-info -verify-loop-info \
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \
 ; RUN:     -S -pass-remarks=loop-interchange 2>&1 | FileCheck %s
 
 @A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16
 
 ;; Test to make sure we can handle zext instructions introduced by
 ;; IndVarSimplify.
 ;;
 ;;  for (int i = 0; i < 2; ++i)