[DependenceAnalysis] Allow subscripts of different types

[jingyue]

Summary

Several places in DependenceAnalysis assumes both SCEVs in a subscript pair
share the same integer type. For instance, isKnownPredicate calls
SE->getMinusSCEV(X, Y) which asserts X and Y share the same type. However,
DependenceAnalysis fails to ensure this assumption when producing a subscript
pair, causing tests such as NonCanonicalizedSubscript to crash. With this
patch, DependenceAnalysis runs unifySubscriptType before producing any
subscript pair, ensuring the assumption.

[jingyue]

fixed a minor typo

[sebpop]

Please add -da-delinearize to the testcase.
Otherwise the patch LGTM.

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

1

You also need to add -da-delinearize to exercise the code that you add in this patch: Delinearize is set to false by default.

[jingyue]

Thanks for the review, Sebastian! Updated the test.

[jingyue]

Got LGTM from sebpop.

include/llvm/Analysis/DependenceAnalysis.h

private:
     /// mapDstLoop - Given one of the loops containing the destination,
     /// return its level index in our numbering scheme.
     unsigned mapDstLoop(const Loop *DstLoop) const;
 
     /// isLoopInvariant - Returns true if Expression is loop invariant
     /// in LoopNest.
     bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const;
 
+    /// Makes sure both subscripts (i.e. Pair->Src and Pair->Dst) share the same
+    /// integer type by sign-extending one of them when necessary.
+    /// Sign-extending a subscript is safe because getelementptr assumes the
+    /// array subscripts are signed.
+    void unifySubscriptType(Subscript *Pair);
+
     /// removeMatchingExtensions - Examines a subscript pair.
     /// If the source and destination are identically sign (or zero)
     /// extended, it strips off the extension in an effort to
     /// simplify the actual analysis.
     void removeMatchingExtensions(Subscript *Pair);
 
     /// collectCommonLoops - Finds the set of loops from the LoopNest that
     /// have a level <= CommonLevels and are referred to by the SCEV Expression.
private:
 
     /// updateDirection - Update direction vector entry
     /// based on the current constraint.
     void updateDirection(Dependence::DVEntry &Level,
                          const Constraint &CurConstraint) const;
 
     bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
                         SmallVectorImpl<Subscript> &Pair,
-                        const SCEV *ElementSize) const;
+                        const SCEV *ElementSize);
 
   public:
     static char ID; // Class identification, replacement for typeinfo
     DependenceAnalysis() : FunctionPass(ID) {
       initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;

lib/Analysis/DependenceAnalysis.cpp

void DependenceAnalysis::collectCommonLoops(const SCEV *Expression,
   while (LoopNest) {
     unsigned Level = LoopNest->getLoopDepth();
     if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
       Loops.set(Level);
     LoopNest = LoopNest->getParentLoop();
   }
 }
 
+void DependenceAnalysis::unifySubscriptType(Subscript *Pair) {
+  const SCEV *Src = Pair->Src;
+  const SCEV *Dst = Pair->Dst;
+  IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
+  IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
+  if (SrcTy == nullptr || DstTy == nullptr) {
+    assert(SrcTy == DstTy && "This function only unify integer types and "
+                             "expect Src and Dst share the same type "
+                             "otherwise.");
+    return;
+  }
+  if (SrcTy->getBitWidth() > DstTy->getBitWidth()) {
+    // Sign-extend Dst to typeof(Src) if typeof(Src) is wider than typeof(Dst).
+    Pair->Dst = SE->getSignExtendExpr(Dst, SrcTy);
+  } else if (SrcTy->getBitWidth() < DstTy->getBitWidth()) {
+    // Sign-extend Src to typeof(Dst) if typeof(Dst) is wider than typeof(Src).
+    Pair->Src = SE->getSignExtendExpr(Src, DstTy);
+  }
+}
 
 // removeMatchingExtensions - Examines a subscript pair.
 // If the source and destination are identically sign (or zero)
 // extended, it strips off the extension in an effect to simplify
 // the actual analysis.
 void DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) {
   const SCEV *Src = Pair->Src;
   const SCEV *Dst = Pair->Dst;
   if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
       (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
     const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
     const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst);
-    if (SrcCast->getType() == DstCast->getType()) {
-      Pair->Src = SrcCast->getOperand();
-      Pair->Dst = DstCast->getOperand();
+    const SCEV *SrcCastOp = SrcCast->getOperand();
+    const SCEV *DstCastOp = DstCast->getOperand();
+    if (SrcCastOp->getType() == DstCastOp->getType()) {
+      Pair->Src = SrcCastOp;
+      Pair->Dst = DstCastOp;
     }
   }
 }
 
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src,

 
 /// Check if we can delinearize the subscripts. If the SCEVs representing the
 /// source and destination array references are recurrences on a nested loop,
 /// this function flattens the nested recurrences into separate recurrences
 /// for each loop level.
 bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
                                         const SCEV *DstSCEV,
                                         SmallVectorImpl<Subscript> &Pair,
-                                        const SCEV *ElementSize) const {
+                                        const SCEV *ElementSize) {
   const SCEVUnknown *SrcBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcSCEV));
   const SCEVUnknown *DstBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstSCEV));
 
   if (!SrcBase || !DstBase || SrcBase != DstBase)
     return false;
 
bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
   // 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.
   }
if (UsefulGEP) {
     unsigned P = 0;
     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
            SrcEnd = SrcGEP->idx_end(),
            DstIdx = DstGEP->idx_begin();
          SrcIdx != SrcEnd;
          ++SrcIdx, ++DstIdx, ++P) {
       Pair[P].Src = SE->getSCEV(*SrcIdx);
       Pair[P].Dst = SE->getSCEV(*DstIdx);
+      unifySubscriptType(&Pair[P]);
     }
   }
   else {
     DEBUG(dbgs() << "    ignoring GEPs\n");
     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
     DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
     DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

+; RUN: opt < %s -analyze -basicaa -da | FileCheck %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-apple-macosx10.6.0"
+
+; for (int i = 0; i < 100; ++i) {
+;   int t0 = a[i][i];
+;   int t1 = t0 + 1;
+;   a[i][5] = t1;
+; }
+; The subscript 5 in a[i][5] is deliberately an i32, mismatching the types of
+; other subscript. DependenceAnalysis before the fix crashed due to this
+; mismatch.
+define void @i32_subscript([100 x [100 x i32]]* %a, i32* %b) {
+; CHECK-LABEL: 'Dependence Analysis' for function 'i32_subscript'
+entry:
+  br label %for.body
+
+for.body:
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [=|<]!
+; CHECK: da analyze - none!
+  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.body ]
+  %a.addr = getelementptr [100 x [100 x i32]]* %a, i64 0, i64 %i, i64 %i
+  %a.addr.2 = getelementptr [100 x [100 x i32]]* %a, i64 0, i64 %i, i32 5
+  %0 = load i32* %a.addr, align 4
+  %1 = add i32 %0, 1
+  store i32 %1, i32* %a.addr.2, align 4
+  %i.inc = add i64 %i, 1
+  %exitcond = icmp ne i64 %i.inc, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:
+  ret void
+}